数据结构和算法

た入场券 2021-12-16 11:27 388阅读 0赞

## 找出那个特殊的字母 ##

给定两个字符串s和t，它们只包含小写字母。字符串t由字符串s随机重排，然后在随机位置添加一个字母。请找出在t中被添加的字母。

> **示例**  
> 如果字符串`s = "abcd";`，`t = "abdec";`，则输出为`e`。

*  方法一：使用异或运算求和

char FindTheDiffAlp(const std::string s, const std::string t) { const std::string st = s + t; char c = 0; for (std::size_t i = 0; i < st.size(); ++i) { c ^= st.at(i); } return c; }

*  方法二：分别求和再相减

char FindTheDiffAlp(const std::string s, const std::string t) { int sum_s = 0; int sum_t = 0; // 分别对s和t求和，使用int防止求和结果溢出 for (std::size_t i = 0; i < s.size(); ++i) { sum_s += s.at(i); } for (std::size_t i = 0; i < t.size(); ++i) { sum_t += t.at(i); } return (char)(sum_t - sum_s); }

*  方法三：边加边减

char FindTheDiffAlp(const std::string s, const std::string t) { int c = t.at(s.size()); for (std::size_t i = 0; i < s.size(); ++i) { c += t.at(i); c -= s.at(i); } return (char)(c); }

*  方法四：使用数组计数

char FindTheDiffAlp(const std::string s, const std::string t) { char c = '0'; int alps[26] = {0}; for (std::size_t i = 0; i < s.size(); ++i) { alps[s.at(i) - 'a']++; } for (std::size_t i = 0; i < t.size(); ++i) { if (--alps[t.at(i) - 'a'] < 0) { c = t.at(i); break; } } return c; }

--------------------

## 找出字符串中的第一个唯一字符 ##

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引值。如果不存在，则返回-1。

> **示例**  
> 如果字符串`s = "leetcode";`，则返回`0`。  
> 如果字符串`s = "loveleetcode";`，则返回`2`。

*  方法一：使用字符数组记录字符出现的次数

int FindTheUniqAlp(const std::string s) { int alps[26] = {0}; for (std::size_t i = 0; i < s.size(); ++i) { ++alps[s.at(i) - 'a']; } int i = 0; while ((i < s.size()) && (alps[s.at(i) - 'a'] > 1)) { ++i; } return (i == s.size() ? -1 : i); }

*  方法二：判断第一次出现和最后一次出现的序号是否相同

int FindTheUniqAlp(const std::string s) { for (std::size_t i = 0; i < s.size(); ++i) { if (s.find_first_of(s.at(i)) == s.find_last_of(s.at(i))) { return i; } } return -1; }

--------------------

## 找出缺失数字 ##

给定一个包含0，1，2，...，n中的n个数的序列，找出其中没有出现在序列中的那个数。

> **示例**  
> 输入：\[3, 0, 1\]  
> 输出：2
> 
> 输入：\[9, 6, 4, 2, 3, 5, 7, 0, 1\]  
> 输出：8

*  方法一：数组求和再逐一减去

int FindMissingNum(const int nums[], int size) { // int nums[] = {9, 6, 4, 2, 3, 5, 7, 0, 1}; // int size = sizeof(nums) / sizeof(nums[0]); int sum = (0 + size) * (size + 1) / 2; // 假设最小值是0，那最大值就是size+1-1；假设最小值是1，那最大值就是size+1 for (int i = 0; i < size + 1; ++i) { sum -= *(nums + i); } return sum; }

*  方法二：把数组的值作为新数组的下标

int FindMissingNum(const int nums[], int size) { int arr[size + 1] = {0}; for (int i = 0; i < size + 1; ++i) { arr[*(nums + i)] = 1; } for (int i = 0; i < size + 1; ++i) { if (0 == arr[i]) { return i; } } return -1; }

--------------------

转载于:https://www.cnblogs.com/dongshanzhishi/p/10759894.html