数据结构和算法

找出那个特殊的字母

给定两个字符串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