AI刷题-异或编码、拼凑单词 chi

一、异或编码

问题描述

测试样例

解题思路：

问题理解

解题思路

数据结构选择

算法步骤

最终代码：

运行结果：

二、拼凑单词 chi

问题描述

测试样例

解题思路：

问题理解

数据结构选择

算法步骤

最终代码：

运行结果：

一、异或编码

问题描述

在一个神秘的实验室里，科学家小艾正在研究一种特殊的编码技术。她有一个经过编码的浮动数字序列 a，这个序列是通过对原始数字序列 data 进行相邻元素的按位异或操作得到的。具体而言，对于序列 data 中的每两个相邻元素，都会生成一个新元素：a[i] = data[i] XOR data[i + 1]。

现在，小艾获得了编码后的序列 a 以及原始序列 data 的第一个元素 d0。她的目标是利用这些信息解码，恢复出原始的数字序列 data。

请帮助小艾找出原始的数字序列 data。

测试样例

样例1：

输入：a = [2, 5, 1], d0 = 3
输出：[3, 1, 4, 5]

样例2：

输入：a = [7, 4, 3], d0 = 6
输出：[6, 1, 5, 6]

样例3：

输入：a = [8, 1], d0 = 9
输出：[9, 1, 0]

样例4：

输入：a = [9, 2, 3], d0 = 4
输出：[4, 13, 15, 12]

样例5：

输入：a = [3, 6, 5], d0 = 7
输出：[7, 4, 2, 7]

解题思路：

问题理解

编码过程：
- 给定一个原始序列 data，通过相邻元素的按位异或操作生成一个新的序列 a。
- 具体来说，a[i] = data[i] XOR data[i + 1]。
解码过程：
- 现在我们有了编码后的序列 a 和原始序列的第一个元素 d0。
- 目标是恢复出原始的数字序列 data。

解题思路

逆向操作：
- 由于 a[i] = data[i] XOR data[i + 1]，我们可以通过逆向操作来恢复 data。
- 具体来说，data[i + 1] = data[i] XOR a[i]。
逐步恢复：
- 从已知的 d0 开始，逐步计算出 data 中的每一个元素。
- 初始时，data[0] = d0。
- 然后，对于每一个 i，计算 data[i + 1] = data[i] XOR a[i]。

数据结构选择

使用一个 vector 来存储恢复后的 data 序列。

算法步骤

初始化 data 的第一个元素为 d0。
从 a 的第一个元素开始，依次计算 data 中的每一个元素。
将计算出的 data 元素存储到 vector 中。
返回恢复后的 data 序列。

最终代码：

#include <iostream>
#include <vector>
using namespace std;std::vector<int> solution(std::vector<int> a, int d0) {// 初始化 data 序列，第一个元素为 d0std::vector<int> data = {d0};// 逐步恢复 data 序列for (int i = 0; i < a.size(); ++i) {// 计算 data[i + 1] = data[i] XOR a[i]int next_data = data.back() ^ a[i];// 将计算出的 data 元素添加到 vector 中data.push_back(next_data);}// 返回恢复后的 data 序列return data;
}int main() {cout << (solution({2, 5, 1}, 3) == std::vector<int>{3, 1, 4, 5}) << endl;cout << (solution({7, 4, 3}, 6) == std::vector<int>{6, 1, 5, 6}) << endl;cout << (solution({8, 1}, 9) == std::vector<int>{9, 1, 0}) << endl;cout << (solution({9, 2, 3}, 4) == std::vector<int>{4, 13, 15, 12}) << endl;cout << (solution({3, 6, 5}, 7) == std::vector<int>{7, 4, 2, 7}) << endl;return 0;
}

运行结果：

二、拼凑单词 chi

问题描述

小C在处理一个字符串问题。给定一个字符串 text，你需要使用 text 中的字母尽可能多地拼凑出单词 "chi"。字符串中的每个字母最多只能被使用一次。你需要返回最多可以拼凑出多少个单词 "chi"。

测试样例

样例1：

输入：text = "chiichcc"
输出：2

样例2：

输入：text = "chicchcic"
输出：2

样例3：

输入：text = "cccchhii"
输出：2

解题思路：

问题理解

你需要从给定的字符串 text 中尽可能多地拼凑出单词 "chi"。每个字母最多只能被使用一次。

数据结构选择

为了有效地统计每个字母的出现次数，我们可以使用一个哈希表（在C++中可以使用 std::unordered_map）来记录每个字母的频率。

算法步骤

统计字母频率：遍历字符串 text，统计每个字母的出现次数。
计算最多能拼凑的单词数：
- 单词 "chi" 由字母 'c'、'h' 和 'i' 组成。
- 计算每个字母 'c'、'h' 和 'i' 的出现次数。
- 由于每个单词 "chi" 需要一个 'c'、一个 'h' 和一个 'i'，所以最多能拼凑的单词数是这三个字母出现次数的最小值。

最终代码：

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;int solution(std::string text) {// PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE// write code here// Step 1: 统计字母频率std::unordered_map<char, int> frequency;for (char c : text) {frequency[c]++;}// Step 2: 计算最多能拼凑的单词数int count_c = frequency['c'];int count_h = frequency['h'];int count_i = frequency['i'];// 计算最多能拼凑的单词数int max_words = min(count_c, min(count_h, count_i));return max_words;
}int main() {cout << (solution("chiichcc") == 2) << endl;cout << (solution("chicchcic") == 2) << endl;cout << (solution("cccchhii") == 2) << endl;return 0;
}