合并两个二维数组 - 求和法

题目链接

解题思路

本题较为基础，可以直接分别遍历两数组，再用哈希表记录两数组中各编号的累加和，但该方法比较消耗空间，时间上的性能也不理想。

考虑到数组 nums1 和 nums2 都包含互不相同的 id，并按 id 以递增顺序排列，因此想到利用归并排序的思想，设立双指针 p1 和 p2，若两指针所指数组元素的 id 相同，则将 { nums1[p1][0], nums1[p1][1] + nums2[p2][1] } 进行归并，否则将较小 id 的元素（假设 p1 所指元素 id 更小） { nums1[p1][0], nums1[p1][1] } 进行归并。

解题代码

class Solution {
public:
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        vector<vector<int>> res;
        int p1 = 0, p2 = 0;
        while (p1 < nums1.size() && p2 < nums2.size()) {
            if (nums1[p1][0] == nums2[p2][0]) {
                res.push_back({ nums1[p1][0], nums1[p1][1] + nums2[p2][1] });
                ++p1;
                ++p2;
            }
            else if (nums1[p1][0] < nums2[p2][0]) {
                res.push_back({ nums1[p1][0], nums1[p1][1] });
                ++p1;
            }
            else {
                res.push_back({ nums2[p2][0], nums2[p2][1] });
                ++p2;
            }
        }
        while (p1 < nums1.size()) {
            res.push_back({ nums1[p1][0], nums1[p1][1] });
            ++p1;
        }
        while (p2 < nums2.size()) {
            res.push_back({ nums2[p2][0], nums2[p2][1] });
            ++p2;
        }
        return res;
    }
};

将整数减少到零需要的最少操作数

题目链接

将整数减少到零需要的最少操作数

解题思路

本题我最开始想往位运算的思路上出发，但无法得到一个有效的解法。

最后在题目示例中发现一个规律：要想使得操作次数最小，每次需要减去或加上离当前正整数 n 最近的 2 的幂数，而该幂数可能是第一个大于 n 的幂数，或是第一个小于 n 的幂数，若 n 本身就是 2 的幂数，则操作次数为 1。

由此可想到利用递归分治的思想，若第一个大于 n 的幂数为 n1，第一个小于 n 的幂数为 n2，使 n 等于 0 需要执行的最少操作数为：使得 n1 - n 等于 0 和使得 n - n2 等于 0 需要执行得最少操作次数中得较小值加上 1，即 minOperations(n) = min(minOperations(n1 - n), minOperations(n - n2)) + 1.

解题代码

class Solution {
public:
    int minOperations(int n) {
        int n1 = 1;
        while (n1 < n) {
            n1 *= 2;
        }
        if (n1 == n) return 1;
        int n2 = n1 / 2;
        return min(minOperations(n1 - n), minOperations(n - n2)) + 1;
    }
};