左右元素和的差值

题目链接

解题思路

直接按照题目要求模拟即可，两次遍历求出 leftSum 和 rightSum，再计算得出 answer.

解题代码

class Solution {
public:
    vector<int> leftRigthDifference(vector<int>& nums) {
        int n = nums.size();
        vector<int> leftSum(n, 0);
        for (int i = 0; i < n - 1; ++i) {
            leftSum[i + 1] = leftSum[i] + nums[i];
        }
        vector<int> rightSum(n, 0);
        for (int i = n - 1; i > 0; --i) {
            rightSum[i - 1] = rightSum[i] + nums[i];
        }
        vector<int> res;
        for (int i = 0; i < n; ++i) {
            res.emplace_back(abs(leftSum[i] - rightSum[i]));
        }
        return res;
    }
};

找出字符串的可整除数组

题目链接

找出字符串的可整除数组

解题思路

n 的取值范围为 1 <= n <= 1e5，因此直接暴力求解显然是行不通的。

对于处理大整数除以某个数的余数的问题，有一些常见的公式可以用于简化运算：

(a+b) mod n = ((a mod n)+ (b mod n)) mod n
(a-b) mod n = ((a mod n) - (b mod n)+n) mod n
ab mod n = (a mod n) (b mod n) mod n

具体到本题而言，由于 word[0,…,i] 表示的数等于 word[0,…,i - 1] * 10 + word[i]，因此可以上述公式，将 (a * b + c) mod n 转换为 ((a mod n) * b + c) mod n，即 word[0,...,i] mod n = ((word[0,...,i - 1] mod n) * 10 + word[i]) mod n ，而 word[0,...,i - 1] mod n 正好就是上一个大整数作模运算的余数。

因此可以维护一个余数 rem，初始值为 0，每次遍历将 rem 的值根据上述递推公式更新：rem = (rem * 10 + word[i] - '0') % m ，再判断该余数 rem 是否为 0，加入结果数组中。

解题代码

class Solution {
public:
    vector<int> divisibilityArray(string word, int m) {
        vector<int> res;
        long long rem = 0;
        for (int i = 0; i < word.size(); ++i) {
            rem = (rem * 10 + word[i] - '0') % m;
            if (rem == 0) res.emplace_back(1);
            else res.emplace_back(0);
        }
        return res;
    }
};

求出最多标记下标

题目链接

求出最多标记下标

解题思路

对于本题这种选择满足条件的最大值的问题，可以考虑使用二分答案法。即确定可能答案的最小和最大值，然后进行二分查找，利用 check 函数进行判断，直到找到满足条件的最大值。

显然，可能的最大答案为 n / 2 对（n 个下标），最小答案为 0. 而要判断 k 对下标是否可能，则可以利用贪心的思想，让第 i 个最小的数和第 k - i + 1 个最大的数进行配对，且 i 从 0 到 k（共有 k 组配对），只要该最优匹配下有一组不满足条件（即 2 * nums[i] > nums[j]），则一定无法形成 k 组配对，即最大答案必定小于 k；若这 k 组配对都满足条件，则最大答案必定大于等于 k.

解题代码

class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        auto check = [&](int k) -> bool {
            int p1 = 0, p2 = n - k + p1;
            while (p2 < n) {
                if (nums[p1] * 2 > nums[p2]) {
                    return false;
                }
                ++p1;
                ++p2;
            }
            return true;
        };
        int res = -1;
        int left = 0, right = n / 2;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (check(mid)) {
                res = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return 2 * res;
    }
};