1. 数组能形成多少数对

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

一开始用无序map，结果才超过5%，然后看数据范围，长度和数字都在100以下，那用map确实大材小用且浪费了。直接用一个101容量的数组即可。这次几乎双百了。

代码

class Solution {
public:
    vector<int> numberOfPairs(vector<int>& nums) {
        vector<int> ans(2, 0);
        // unordered_map<int, int> ump;
        // for (auto& num : nums) {
        //     ump[num]++;
        //     if (ump[num] == 2) {
        //         ump.erase(num);
        //         ++ans[0];
        //     }
        // }
        // ans[1] = ump.size();
        vector<int> cnt(101, 0);
        for (auto& num : nums) {
            ++cnt[num];
            if ((cnt[num] & 1) == 0) ++ans[0];
        }
        ans[1] = nums.size() - (ans[0] << 1);
        return ans;
    }
};

2. 数位和相等数对的最大和

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

原本的思路也没什么问题，主要是在找最大和的时候效率有些低。如果一个个去对比，要n的平方，而如果直接把相同数位和的数字排下序再计算和，就只要n的对数复杂度，以后应该注意这点。

代码

class Solution {
public:
    int maximumSum(vector<int>& nums) {
        auto bitSum = [&](int num) -> int {
            int x = num;
            int sum = 0;
            while (x) {
                sum += x % 10;
                x /= 10;
            }
            return sum;
        };

        int n = nums.size();
        unordered_map<int, vector<int>> ump;
        vector<int> bitSums(n);
        for (int i = 0; i < n; ++i) {
            bitSums[i] = bitSum(nums[i]);
        }
        int ans = -1;
        for (int i = 0; i < n; ++i) {
            ump[bitSums[i]].push_back(nums[i]);
        }
        for (auto& elem : ump) {
            int m = elem.second.size();
            if (m == 1) continue;
            sort(elem.second.begin(),elem.second.end());
            ans = max(ans, elem.second[m - 1] + elem.second[m - 2]);
        }
        return ans;
    }
};

3. 裁剪数字后查询第 K 小的数字

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

参考这篇

直接根据题目描述进行模拟。

实现时并不用真的去截取字符串，或者将字符串转换为数字进行比较。遍历查询数组，定义一个sort的cmp，传入两个整数下标，根据下标指示的字符串和当前查询需要截取的位数，返回bool，用这种方式，将下标进行了排序，最后将排序后的下标返回即可。

按照同样的思路和逻辑写了一遍，结果有用例超时。仔细对比，发现是第二个字符串忘了写引用。一个符号引发的惨案。

代码

class Solution {
public:
    vector<int> smallestTrimmedNumbers(vector<string> &nums, vector<vector<int>> &queries) {
        vector<int> ans(queries.size());
        int n = nums.size(), m = nums[0].length();
        int index[n];
        for (int i = 0; i < queries.size(); ++i) {
            iota(index, index + n, 0);
            auto& qur = queries[i];
            stable_sort(index, index + n, [&] (int a, int b) -> bool {
                auto& s = nums[a], &t = nums[b]; // 一定要用引用
                for (int j = m - qur[1]; j < m; ++j) {
                    if (s[j] != t[j]) return s[j] < t[j];
                }
                return false;
            });
            ans[i] = index[qur[0] - 1];
        }
        return ans;
    }
};

4. 使数组可以被整除的最少删除次数

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

还是比较简单的，先求出第二个数组的最大公因数，再将第一个数组排序，遍历看当前元素是否能被最大公因数整除，不能就++ans。最后如果ans等于数组长度，则返回-1。

代码

class Solution {
private:
    int gcd (int a, int b) {
        if (a < b) {
            a ^= b;
            b ^= a;
            a ^= b;
        }
        if (b == 0) return a;
        else return gcd(b, a % b);
    }
public:
    int minOperations(vector<int>& nums, vector<int>& numsDivide) {
        int maxFac = numsDivide[0];
        for (int i = 1; i < numsDivide.size(); ++i) maxFac = gcd(maxFac, numsDivide[i]);
        sort(nums.begin(), nums.end());
        int j = 0;
        int ans = 0;
        for (; j < nums.size(); ++j) {
            if (maxFac % nums[j] == 0) break;
            else ++ans;
        }
        return ans == nums.size() ? -1 : ans;
    }
};

5. 装满杯子需要的最短总时长

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

每次取数组中最大的两个减一。

代码

class Solution {
public:
    int fillCups(vector<int>& amount) {
        int ans = 0;
        sort(amount.begin(), amount.end());
        while (amount[2] != 0) {
            amount[2]--;
            amount[1]--;
            sort(amount.begin(), amount.end());
            ++ans;
        }
        return ans;
    }
};

6. 无限集中的最小数字

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

用set做存储。末尾是连续区间的最小值，前面是离散值。初始时只有一个1。删除时，先记录下set首元素，如果set大小为1，说明全部值都连续，那么在末尾插入一个加1值，然后抹去首元素。如果大于1，直接抹去即可。插入时，先看值是否在连续区间内（即是否大于set末尾元素），如果在，那么不用插入，如果不在，说明是离散值，直接插入即可（set自动去重）。

代码

class SmallestInfiniteSet {
private:
    set<int> before;
public:
    SmallestInfiniteSet() {
        before.clear();
        before.emplace(1);
    }

    int popSmallest() {
        int x = *before.begin();
        if (before.size() == 1) before.emplace(x + 1);
        before.erase(before.begin());
        return x;
    }

    void addBack(int num) {
        if (num < *before.rbegin()) before.emplace(num);
    }
};

7. 移动片段得到字符串

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

首先认识到，如果两个字符串都删掉下划线后不相等，则前者一定无法变为后者（其实就意味着LR不能互相越过）。

其次，如果变化后的L在变化前L的右边，或者变化后R在变化前R的左边，也返回false。

代码

class Solution {
public:
    bool canChange(string start, string target) {
        auto s = start, t = target;
        s.erase(remove(s.begin(), s.end(), '_'), s.end());
        t.erase(remove(t.begin(), t.end(), '_'), t.end());
        if (s != t) return false;
        for (int i = 0, j = 0; i < start.size(); ++i) {
            if (start[i] == '_') continue;
            while (target[j] == '_') ++j;
            if (i != j && (start[i] == 'L') == (i < j)) return false;
            ++j;
        }
        return true;
    }
};

8. 统计理想数组的数目

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

纯数学题……

代码