由于考研等因素的影响，已经时隔一年没有参加力扣周赛了，长时间没有好好琢磨算法题，思维敏捷度确实有所下降，好在这次周赛前两题都没有什么难度，但第三题却把简单问题想复杂了，第四题就基本上都没怎么读题了。。。

正整数和负整数的最大计数

题目链接

正整数和负整数的最大计数

解题思路

直接依照题意统计该数组中正整数和负整数的个数，然后返回较大个数即可，送分题。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maximumCount(vector<int>& nums) {
        int cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0) {
                ++cnt1;
            }
            else if (nums[i] < 0) {
                ++cnt2;
            }
        }
        return max(cnt1, cnt2);
    }
};

执行 K 次操作后的最大分数

题目链接

执行 K 次操作后的最大分数

解题思路

同样也是直接模拟，既然要求的是所能获得的最大分数，那么只需保证每次从数组中选取的是当前数组的最大值即可。对于此类贪心选择问题，容易想到利用优先队列（基于堆实现），相较于顺序查找最大值，优先队列可将每次选取最大值的时间复杂度降至 O(log(n))。

具体步骤是先将数组所有元素存入优先队列中，然后选出队头元素（即最大值）并出队，分数累加该值后，按照题意将该值替换为 ceil(nums[i]) / 3，再存入优先队列中，重复操作 k 次即可得到结果。

对于向上取整的处理很简单，只需判断该数 val 能否被 3 整除，若能，则直接令 val = val / 3 即可，若不能，由于整数相除会舍弃小数位，即相当于向下取整，因此令 val = val / 3 + 1.

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    long long maxKelements(vector<int>& nums, int k) {
        priority_queue<int> maxQueue;
        for (int i = 0; i < nums.size(); ++i) {
            maxQueue.emplace(nums[i]);
        }
        long long res = 0;
        for (int i = 0; i < k; ++i) {
            int maxVal = maxQueue.top();
            maxQueue.pop();
            res += maxVal;
            if (maxVal % 3 == 0) {
                maxVal /= 3;
            }
            else {
                maxVal = maxVal / 3 + 1;
            }
            maxQueue.emplace(maxVal);
        }
        return res;
    }
};

使字符串总不同字符的数目相等

题目链接

使字符串总不同字符的数目相等

解题思路

本题最开始写的时候思路很不清晰，写了一大堆判断条件最终也没能成功求解。

事实上本题如果注意到一个关键点就能很快建立思路，即两字符串之间各个字符的交换其实完全可以等价为两字符串之间各种字符的交换，因为题目要求两字符串不同字符个数相同，因此其实与各字符所处的下标无关，即当 word1 = "abcc", word2 = "aab" 时，word1[2] 和 word2[0] 交换与 word1[3] 和 word[1] 交换其实是完全一样的。明白这一点之后，发现交换的可能性最大不过 26 * 26 种，完全可以直接枚举求解。

基本求解步骤如下：对于 word1 和 word2 分别设置长度为 26 的数组 chCnt1 和 chCnt2 统计各字母在字符串的个数，cnt1 和 cnt2 分别统计两字符串不同字符的个数。然后执行一个 26 * 26 的二重循环，表示 word1 的 i 字符与 word2 的 j 字符交换，修改 chCnt1, chCnt2 的值，以判断交换后是否满足不同字符个数相同，若不满足，将修改过的 chCnt 数组复原。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    bool isItPossible(string word1, string word2) {
        int cnt1 = 0, cnt2 = 0;
        vector<int> chCnt1(26, 0), chCnt2(26, 0);
        for (int i = 0; i < word1.size(); ++i) {
            int idx = word1[i] - 'a';
            if (chCnt1[idx] == 0) {
                ++cnt1;
            }
            ++chCnt1[idx];
        }
        for (int i = 0; i < word2.size(); ++i) {
            int idx = word2[i] - 'a';
            if (chCnt2[idx] == 0) {
                ++cnt2;
            }
            ++chCnt2[idx];
        }
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < 26; ++j) {
                if (chCnt1[i] == 0 || chCnt2[j] == 0) {
                    continue;
                }
                int c1 = cnt1, c2 = cnt2;
                --chCnt1[i];
                if (chCnt1[i] == 0) --c1;
                ++chCnt1[j];
                if (chCnt1[j] == 1) ++c1;
                --chCnt2[j];
                if (chCnt2[j] == 0) --c2;
                ++chCnt2[i];
                if (chCnt2[i] == 1) ++c2;
                if (c1 == c2) {
                    return true;
                }
                ++chCnt1[i];
                --chCnt1[j];
                ++chCnt2[j];
                --chCnt2[i];
            }
        }
        return false;
    }
};