LeetCode 第32场双周赛

题目

思路:
1. 一上来拿到这个题目并没有什么好办法, 到最后也没想到啥好办法, 所以无奈只能用暴力法.
2. 定义三个变量, 分别储存数组遍历索引(index), 该次循环是第几次(ans), 已经缺失的个数(count)
3. 循环条件是index < arr.size() && count < k, 这代表数组没有遍历完成并且缺失的个数还没到k
4. 当arr[index] != ans时, 此时只有一种情况, 那就是arr[index] > ans, 因为数组是由小到大并且没有重复元素, 此时只需要ans和count自增即可
5. 如果arr[index] == ans, 这个没啥好说的, index和ans都自增即可
6. 当循环结束时, 有两种可能
  1. count == k, 此时直接返回ans - 1即可
  2. index < arr.size() 此时缺失的数字要大于数组里最大的数, 所以返回ans + k - count - 1
7. 关于减1, 因为ans是从1开始, 而index, count是从0开始, 所以要减1
8. 此时因为情况1中k == count, 所以两种情况可以合并, 返回 ans + k - count - 1即可

代码:

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int ans = 1;
        int count = 0;
        int index = 0;
        while (count < k && index < arr.size()) {
            if (arr[index] == ans) {
                index++;
            } else {
                count++;
            }
            ans++;
        }
        ans = ans + k - count - 1;
        return ans;
    }
};

K次操作转变字符串

思路:
1. 这是一道语文题, 理解了题意就好做了
2. 关于k值, 指的是一个字母可以加(1~k), 然后变成另一个字母
3. 如果加的值i, 前面已经用过了, 就没法再用了
4. 因为k值可以超过26, 而每个字母加1 + 26*i(i >= 0), 效果是一样的
5. 所以首先创建一个26位的数组, 记录每种变化可以用几次
6. 剩下的就是遍历数组, 判断某个位置需要的是哪种变化, 就到对应数组位置减1即可
7. 如果这个位置已经是0了, 直接返回false
8. 否则遍历完成, 返回true

代码:

class Solution {
public:
    bool canConvertString(string s, string t, int k) {
        if (s.length() != t.length()) {
            return false;
        }
        vector<int> flags(26, k / 26);
        for (int i = 0; i < k % 26; ++i) {
            flags[i]++;
        }
        for (int i = 0; i < s.length(); ++i) {
            int num = t[i] - s[i];
            if (num == 0) {
                continue;
            }
            if (num < 0) {
                num += 26;
            }
            if (flags[num - 1] > 0) {
                flags[num - 1]--;
            } else {
                return false;
            }
        }
        return true;
    }
};

平衡括号字符串的最少插入次数

思路:
1. 这是一个考察栈应用的题, 但是并不需要真正的栈
2. 具体思想就是, 遇到左括号就压栈. 两个右括号就弹栈, 如果不符合这个条件就计算缺失括号的个数
3. 所以通过两个变量ans(最终需要返回的数), left(当前左括号的个数)来记录中间值
4. 遍历字符串, 如果是左括号, left自增
5. 如果是右括号, 那么判断下一个是否为右括号
6. 如果是, left自减, 并且索引下移
7. 如果否, ans自增, left自减(此时相当于添加了一个右括号)
8. 遍历结束, 返回 ans + left * 2即可, 因为要给剩余未匹配的左括号添加右括号, 而如果右括号多于左括号的情况时, 会在遍历的时候就累加到ans中了

代码:

class Solution {
public:
    int minInsertions(string s) {
        int ans = 0;
        int left = 0;
        auto it = s.begin();
        while (it != s.end()) {
            if (*it == '(') {
                left++;
                it++;
            } else {
                it++;
                if (*it == ')') {
                    if (left > 0) {
                        left--;
                    } else {
                        ans++;
                    }
                    it++;
                } else {
                    if (left > 0) {
                        left--;
                        ans++;
                    } else {
                        ans += 2;
                    }
                }
            }
        }
        ans += 2 * left;
        return ans;
    }
};

找出最长的超赞字符串

思路:
1. 因为字符串只有数字, 即字符只有0~9这10中情况
2. 所以使用一个整型数据储存本数出现的奇偶次, 通过后10位是否为0判断是否为偶数
3. 创建一个索引数组, 表示该状态上次出现的位置, 因为整型数据最大值为后十位都为1的状态, 所以数组容量开辟为1 << 11即可
4. 因为开始并没有访问任何数据, 所以数组初始化为-2, 表示每种数字都没有出现过
5. 将0位置初始化为-1(因为计算长度时, 是用索引减位置, 所以直接将开始初始化为-1, 免得后面还要加1)
6. 遍历字符串, 获得每个位置的值, 并修改状态数据对应位的奇偶性
7. 每遍历一次, 就查看上次这个状态时的索引位置是多少, 如果存在索引, 记录这是的最长的子字符串
8. 因为回文串是可以包含一个单独的字符的, 所以需要对含有一个字符的单独处理
9. 所以将每一位修改其奇偶性, 判断最长的超赞子字符串的长度, 并记录下来
10. 遍历最后, 如果这个状态下前面并没有出现过, 记录这个状态的索引值, 这是第一次出现的位置
11. 遍历结束, 返回最大值即可

代码:

class Solution {
public:
    int longestAwesome(string s) {
        // 如果数组长度小于2, 直接返回数组长度
        if (s.length() < 2) {
            return s.length();
        }
        // 初始化数组容量和内容
        vector<int> pos(1 << 11, -2);
        int status = 0, ans = 1;
        pos[status] = -1;
        for (int i = 0; i < s.length(); ++i) {
            int num = s[i] - '0';
            status ^= (1 << num);
            if (pos[status] != -2) {
                // 不含奇数的情况
                ans = max(ans, i - pos[status]);
            }
            int mask = 1;
            // 有一个奇数的情况
            for (int j = 1; j <= 10; ++j) {
                int key = status ^ mask;
                if (pos[key] != -2) {
                    ans = max(ans, i - pos[key]);
                }
                mask <<= 1;
            }
            // 记录第一次出现的位置
            if (pos[status] == -2) {
                pos[status] = i;
            }
        }
        return ans;
    }
};