LeetCode Weekly Contest 200 Review.

第一题:Count Good Triplets

给你一个整数数组 arr ,以及 abc 三个整数。请你统计其中好三元组的数量。

如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件,则认为它是一个 好三元组 。

  • 0 <= i < j < k < arr.length
  • |arr[i] - arr[j]| <= a
  • |arr[j] - arr[k]| <= b
  • |arr[i] - arr[k]| <= c

其中 |x| 表示 x 的绝对值。

返回好三元组的数量

示例:

输入:arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
输出:4
解释:一共有 4 个好三元组:[(3,0,1), (3,0,1), (3,1,1), (0,1,1)] 。

分析

这一道题可以直接穷举,然后遍历出所有符合的条件即可。但是直接穷举的话还是比较慢,需要剪枝提高效率。剪枝的方法是先判断第一个条件,满足之后再进行下面的循环,这样可以在测试集中减少接近一半的时间

代码

Python

class Solution:
    def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
        length = len(arr)
        token = 0
        
        for i in range(length - 2):  # 第一个数
            for j in range(i + 1, length - 1): # 第二个数
                if abs(arr[i] - arr[j]) <= a:  # 在满足第一个条件之后再取第三个数
                    for k in range(j + 1, length):  # 第三个数
                        if (abs(arr[j] - arr[k]) <= b and abs(arr[i] - arr[k]) <= c):  # 继续判断后两个条件
                            token += 1  # 满足则 +1
        return token

C++

class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        int length = arr.size();
        int token = 0;

        for(int i = 0; i <= length - 3; ++i){
            for(int j = i + 1; j <= length - 2; ++j){
                if(abs(arr[i] - arr[j]) <= a){  // 判断完第一个条件再取第三个数
                    for(int k = j + 1; k < length; ++k){
                        if(abs(arr[j] - arr[k]) <= b  &&  abs(arr[i] - arr[k]) <= c)
                            token++;
                    }
                }
            }
        }
        return token;
    }
}

第二题:Find the Winner of an Array Game

给你一个由不同整数组成的整数数组 arr 和一个整数 k

每回合游戏都在数组的前两个元素(即 arr[0]arr[1] )之间进行。比较 arr[0]arr[1] 的大小,较大的整数将会取得这一回合的胜利并保留在位置 0 ,较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时,游戏结束,该整数就是比赛的赢家

返回赢得比赛的整数。

题目数据保证游戏存在赢家。

示例:

输入:arr = [2,1,3,5,4,6,7], k = 2
输出:5
解释:一起看一下本场游戏每回合的情况:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
因此将进行 4 回合比赛,其中 5 是赢家,因为它连胜 2 回合。

分析

这道题的话其实就相当于是多了个中断条件的比较算法,当连胜(也就是连续大于)一定次数,或者该数已成为数列最大值的时候就直接返回,因为当是最大值的时候,再接着比下去是没有意义的。

因为我求快心切,用了 Python 和最直观的算法,最开始的 Python 代码如下:

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        token = 0
        while token < k:
            if arr[0] > arr[1]:  # 赢了
                token += 1
                arr = [arr[0]] + arr[2:] + [arr[1]]  # 把第二个给移到后面
            else:
                token = 1  # 输了置一
                arr = arr[1:] + [arr[0]]  # 把第一个移到后面

        return arr[0]

结果发现超时了(笑),因为测试集有一个 100000000 次的,所以用这个最原始直观的方法会直接硬着头皮循环 100000000 次,但实际上后面的循环是没有意义的,十分耗时。所以后来就优化,改成了最终版本。

代码

Python

class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        token = 0
        index = 0
        while token < k and index < len(arr) - 1:  # k 次数达到了,或者 index 到了最后时停止
            if arr[index] > arr[index + 1]:
                arr[index + 1] = arr[index]  # 交换值
                token += 1  # 加一
            else:
                token = 1  # 小于就不加一
            index += 1  # 每轮比较 index 自增一

        return arr[index]  # 返回当前的值

C++

class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        int i = 0, t = 0;  // 算法与 Python 的基本一致
        while(t < k && i < arr.size() - 1){
            if(arr[i] > arr[i+1]){
                arr[i+1] = arr[i];  // 赢了就交换值,token 加一
                ++t;
            }else
                t = 1;
            ++i;  // 每轮 index 自增一
        }  
        return arr[i];  // 返回当前的值
    }
};

第三题:Minimum Swaps to Arrange a Binary Grid

给你一个 n x n 的二进制网格 grid,每一次操作中,你可以选择网格的相邻两行进行交换。

一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。

请你返回使网格满足要求的最少操作次数,如果无法使网格符合要求,请你返回 -1 。

主对角线指的是从 (1, 1) 到 (n, n) 的这些格子。

示例:

输入:grid = [[0,0,1],[1,1,0],[1,0,0]]
输出:3

分析

这道题虽然明面上是一道线性代数的三角矩阵化简问题,实际上却不是。如果将每一行从右到左的连续 0 的数量值生成出来形成一个新的数组,就会发现这其实是一道计算冒泡排序的步数的问题。

比如例子中的 grid 可以化简为一个 0 的数量的列表 [0, 1, 2],然后由这个列表变为 [2, 1, 0] 的步骤数就是最终的结果了。这么想的话这一道题的解法就会方便很多。我一开始写的一个算法虽然十分简洁快速,但是只能满足完全对角的矩阵判断。所以还是参考了大佬的算法自己再按着之前的算法改进了一下,提交了最后的 AC 版本。

代码

Python

class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        n = len(grid)
        nums = []  # 该列表存放每行从右到左的 0 个数
        for i in range(n):
            j = n - 1
            while j >= 0 and grid[i][j] == 0:
                j -= 1
            nums.append(n - 1 - j)

        steps = 0
        for i in range(n - 1):
            need_zeros = n - 1 - i

            j = i
            while j < len(nums) and nums[j] < need_zeros:
                j += 1  # 不满足要求则 j + 1,继续判断下一行,满足或者到边界则跳出

            if j == len(nums):  # 等于数组长度则证明没有满足的行,返回 -1
                return -1

            steps += j - i  # 满足则加上步数
            nums.insert(i, nums.pop(j))  # 换序,把该位置的值插到前面对应的 i 位置处
        return steps

太晚了,就没有写 C++ 的版本,网上随便找了一份,简单看了一下,算法是一模一样的,都是判断然后计数:

C++

class Solution {
public:
    int minSwaps(vector<vector<int>>& grid) {
        int n = grid.size(); //网格规模
        vector<int> a; //记录每一行后缀0个数的数组
        for(int i = 0; i < n; i++)
        {
            int count = 0;
            for(int j = n - 1; j >= 0; j--)
            {
                if(grid[i][j] == 0) count++; //数每一行的后缀0
                else break;
            }
            a.push_back(count); 
        }
        int count = 0; //交换次数
        for(int i = 0; i < n - 1; i++)
        {
            if(a[i] >= n - i - 1) continue;//满足条件,该行直接跳过
            else{//不满足条件
                int j = i; //用新参数遍历找满足条件的后缀0
                for(; j < n; j++)
                {
                    if(a[j] >= n - i - 1) break;
                }
                if(j == n) return -1; //找不到,直接返回-1
                for(; j > i; j--) //找到了最先满足条件的后缀0个数 
                {
                    swap(a[j], a[j - 1]); //每一行交换上去
                    count++; //记录交换次数
                }
            }
        }
        return count;
    }
};

第四题:Get the Maximum Score

你有两个有序且数组内元素互不相同的数组 nums1 和 nums2 。

一条合法路径定义如下:

选择数组 nums1 或者 nums2 开始遍历(从下标 0 处开始)。从左到右遍历当前数组。如果你遇到了 nums1 和 nums2 中都存在的值,那么你可以切换路径到另一个数组对应数字处继续遍历(但在合法路径中重复数字只会被统计一次)。得分定义为合法路径中不同数字的和。请你返回所有可能合法路径中的最大得分。

由于答案可能很大,请你将它对 10^9 + 7 取余后返回。

示例:

输入:nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
输出:30
解释:合法路径包括:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],(从 nums1 开始遍历)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]  (从 nums2 开始遍历)
最大得分为上图中的绿色路径 [2,4,6,8,10] 。

分析

这道题有点出乎我的意料,比第三题要简单一些。说白了就是找到两条路中路径最大的一条,其中两条路的值相同的节点之间可以相互切换,所以这就有两个算法:

  • 第一种是双指针法,因为两个都是有序数列,所以每轮哪个小就推哪个,然后分别记录值,到相同的节点时把两者中较大的一个路径值加入总路径值中。

  • 第二种是哈希 + sum 算法,先把 nums1 序列生成字典,然后第二个数组 nums2 每一个值比配时,都会都检索一遍 nums1 的哈希,然后取出对应值的指针。这里快的原因是字典在索引的时候是用的哈希算法,比普通的便利要快上很多。

第二种算法本质上和第一个差不多,但是由于哈希 + sum 比遍历快,所以整体速度也快一些。第一个算法比较简单,所以我就直接用了第二种方法提交了 AC 版本。

代码

Python

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        d = {t: i for i, t in enumerate(nums1)}  # 转成字典
        ans = 0
        p, q = 0, 0
        for j, t in enumerate(nums2):
            if t in d:
                i = d[t]  # 哈希算法,取出指针
                ans += max(sum(nums1[p: i]), sum(nums2[q: j]))  # 当前相同值的指针到上一对相同指针之间的值求和的最大值
                p, q = i, j  # 更新指针
        ans += max(sum(nums1[p: ]), sum(nums2[q: ]))
        return ans % 1000000007  # 按要求,最后返回余数

C++ 的代码就是算法一的双指针版本。

C++

int maxSum(vector<int>& nums1, vector<int>& nums2) {
        long sum1 = 0, sum2 = 0;
        long res = 0;
        int i = 0, j = 0;
        while(i < nums1.size() && j < nums2.size()){
            if(nums1[i] == nums2[j]){
                res += (max(sum1, sum2) + nums1[i]);
                sum1 = 0;
                sum2 = 0;
                i++;
                j++;
            }
            else if(nums1[i] < nums2[j]){
                sum1 += nums1[i];
                i++;                
            }
            else{
                sum2 += nums2[j];
                j++;
            }            
        }
        while(i < nums1.size()){
            sum1 += nums1[i];
            i++;
        }
        while(j < nums2.size()){
            sum2 += nums2[j];
            j++;
        }
        res += max(sum1, sum2);
        return res % ((int)pow(10, 9) + 7 );