leetcode解题思路分析（一百一十六）973 - 979 题_leecode的point数组

973. 最接近原点的 K 个点
     给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。这里，平面上两点之间的距离是 欧几里德距离（ √(x1 - x2)2 + (y1 - y2)2 ）。你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。

可以排序、用堆，但是最好的方法是类似于快排的思想分治查找

class Solution {
private:
    mt19937 gen{random_device{}()};

public:
    void random_select(vector<vector<int>>& points, int left, int right, int k) {
        int pivot_id = uniform_int_distribution<int>{left, right}(gen);
        int pivot = points[pivot_id][0] * points[pivot_id][0] + points[pivot_id][1] * points[pivot_id][1];
        swap(points[right], points[pivot_id]);
        int i = left - 1;
        for (int j = left; j < right; ++j) {
            int dist = points[j][0] * points[j][0] + points[j][1] * points[j][1];
            if (dist <= pivot) {
                ++i;
                swap(points[i], points[j]);
            }
        }
        ++i;
        swap(points[i], points[right]);
        // [left, i-1] 都小于等于 pivot, [i+1, right] 都大于 pivot
        if (k < i - left + 1) {
            random_select(points, left, i - 1, k);
        }
        else if (k > i - left + 1) {
            random_select(points, i + 1, right, k - (i - left + 1));
        }
    }

    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        int n = points.size();
        random_select(points, 0, n - 1, k);
        return {points.begin(), points.begin() + k};
    }
};

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

974. 和可被 K 整除的子数组
     给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。子数组 是数组的 连续 部分。

首先使用前缀和，然后我们要判断的是(sum[j]−sum[i])%K是否等于 0。
根据 mod 运算的性质，我们知道 (sum[j] - sum[i])%K = sum[j]%K - sum[i]%K
故若想 (sum[j] - sum[i])%K = 0，则必有 sum[j]%K = sum[i]%K。
所有满足 nums[i:j]中元素之和可以被 K 整除的开始下标 i，必有 sum[j]%K = sum[i]%K。我们以 sum[i]%K作为键值统计其出现的频率，从而对于每个下标 j 我们可以立即获得能和它组成满足要求的子数组的开始下标 i 的数量。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> record = {{0, 1}};
        int sum = 0;
        for (int elem: nums) {
            sum += elem;
            // 注意 C++ 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
            int modulus = (sum % k + k) % k;
            ++record[modulus];
        }

        int ans = 0;
        for (auto [x, cx]: record) {
            ans += cx * (cx - 1) / 2;
        }
        return ans;
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

975. 奇偶跳

class Solution {
private:
    vector<int> calculateNext(vector<int>& indexes)
    {
        int n = indexes.size();
        // 初始化的无效值
        vector<int> res(n, -1);
        // 保持单调递减的栈，一旦大于，则弹出后直到更小
        stack<int> s;

        for (int i = 0; i < n; ++i)
        {
            // 找到更小的，那么就更新对应的序号
            while (!s.empty() && s.top() < indexes[i])
            {
                res[s.top()] = indexes[i];
                s.pop();
            }
            s.push(indexes[i]);
        }

        return res;
    }
public:
    int oddEvenJumps(vector<int>& arr) {
        int n = arr.size();
        vector<int> indexes(n, 0);
        for (int i = 0; i < n; ++i)
        {
            indexes[i] = i;
        }

        // oddNext是需要更大，升序排列
        sort(indexes.begin(), indexes.end(), [&arr](int a, int b) {
            return arr[a] < arr[b] || (arr[a] == arr[b] && a < b);
        });
        vector<int> oddNext = calculateNext(indexes);
        // 相反计算eventNext,降序排列
        sort(indexes.begin(), indexes.end(), [&arr](int a, int b) {
            return arr[a] > arr[b] || (arr[a] == arr[b] && a < b);
        });
        vector<int> evenNext = calculateNext(indexes);

        // 动态规划初始化
        bool odd[n];
        memset(odd, 0, sizeof(odd));
        bool even[n];
        memset(even, 0, sizeof(even));
        odd[n-1] = true;
        even[n-1] = true;
        
        for (int i = n -2; i >= 0; --i)
        {
            if (oddNext[i] != -1)
            {
                odd[i] = even[oddNext[i]];
            }
            if (evenNext[i] != -1)
            {
                even[i] = odd[evenNext[i]];
            }
        }

        int res = 0;
        for (int i = 0; i < n; ++i)
        {
            res += odd[i] == true;
        }

        return res;
    }
};

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

976. 三角形的最大周长
     给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形，返回 0。

贪心算法：既然取最大的，就排序后从最大开始取。三角形a < b < c的情况下，a + b > c即可，那么如果第二第三大的都不满足，后面更小的肯定也不行，因此不需要多重循环。

class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        sort(A.begin(), A.end());
        for (int i = (int)A.size() - 1; i >= 2; --i) {
            if (A[i - 2] + A[i - 1] > A[i]) {
                return A[i - 2] + A[i - 1] + A[i];
            }
        }
        return 0;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

977. 有序数组的平方
     给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

双指针滑动：从两端开始，比较其平方，将较大的数放在返回结果的尾端。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                ans[pos] = nums[i] * nums[i];
                ++i;
            }
            else {
                ans[pos] = nums[j] * nums[j];
                --j;
            }
            --pos;
        }
        return ans;
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

978. 最长湍流子数组
     给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度

本题动态规划的难点在于需要考虑两种dp情况，一种是i比i-1大，一种是i比i-1小，两种情况需要分别对两个dp均做处理。理清了这个思路之后就会很容易做。

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int ret = 1;
        int n = arr.size();
        int dp0 = 1, dp1 = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                dp0 = dp1 + 1;
                dp1 = 1;
            } else if (arr[i - 1] < arr[i]) {
                dp1 = dp0 + 1;
                dp0 = 1;
            } else {
                dp0 = 1;
                dp1 = 1;
            }
            ret = max(ret, dp0);
            ret = max(ret, dp1);
        }
        return ret;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

979. 在二叉树中分配硬币
     给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。返回使每个结点上只有一枚硬币所需的移动次数。

后序遍历，节点值小于1，从父节点减去对应的差值，使当前节点值为1；节点值大于1，父节点加上对应的差值，使当前节点值为1；节点值为1则不用处理。每次根节点加减的值也是需要移动的步数。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int ret = 0;
    void traversal(TreeNode* cur, TreeNode* pre) {
        if (!cur) return ;

        traversal(cur->left, cur);
        traversal(cur->right, cur);
        if (cur->val < 0) {
            ret += 1 - cur->val;
            pre->val -= 1 - cur->val;
        }
        if (cur->val == 0) {
            ret++;
            pre->val--;
        }
        if (cur->val > 1) {
            ret += cur->val - 1;
            pre->val += cur->val - 1;
        }
    }

public:
    int distributeCoins(TreeNode* root) {
        TreeNode* pre = new TreeNode(1);
        traversal(root, pre);
        
        return ret;
    }
};
// 

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