1535 找出数组游戏的赢家 #模拟+优化

题意

给你一个由不同整数组成的整数数组 arr 和一个整数 k(\(1\leq k\leq1e9\)) 。每回合游戏都在数组的arr[0] 和 arr[1]之间进行，比较两者大小，较大的元素将会取得这一回合的胜利并保留在位置 0 ，较小者移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的赢家，现求该整数

样例

因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合

分析

观察\(k\)的数据范围，直接模拟肯定过不了。我们猜想当遍历到数组末端时，赢家已经确定下来。

我们先假定\(k<\)数组长度，设存在\(cur<pos\)，\(a[cur]>a[0, pos-1]\)且\(a[cur]<a[pos]\)。现有两种情况：

如果\(cur<\)数组长度\(-1\)且获胜整数的连胜达到\(k\)时，毫无疑问直接返回\(arr[cur]\)
如果\(cur=\)数组长度但是连胜次数还没到达\(k\)，此时，我们可以知道\(arr[cur]\)一定比\(arr[0, cur-1]\)大，又因为\(cur\)到达数组长度，可以推出\(arr[cur]\)为数组中的最大值，继续比较搬过来的元素，将没有意义。故也是\(arr[cur]\)

当\(k\ge\)数组长度，要连胜\(k\)次，至少比较完\(arr\)数组所有元素一轮，那要一轮都能够取胜且\(arr\)无重复数字，可推出只有\(arr\)的\(max\)才能满足连胜\(k\)局

总的来说，我并不需要模拟"较小的整数移至数组的末尾"的操作，\(O(n)\)即可

class Solution {

public:

    int getWinner(vector<int>& arr, int k) {

        int len = arr.size();

        int cur = 0;

        int cnt = 0;

        for (int pos = 1; pos < len; pos++) {

            if (arr[cur] > arr[pos]) {

                cnt++;

            }

            else {

                cur = pos;

                cnt = 1;

            }

            if (cnt == k)

                return arr[cur];

        }

        return arr[cur];

    }

};

1536 排布二进制网格的最少交换次数 #贪心

题意

给定\(n\times n\)的二进制网格\(grid\)，每次操作可选择网格的相邻两行进行交换。

现要将给定网格转化为满足主对角线以上(从 \((1, 1)\) 到 \((n, n)\))的格子全为 0的网格，要求使网格满足要求的最少操作次数。若无法使网格符合要求，返回 -1

样例

分析

那我们肯定要先将\(grid\)抽出关键信息，转化为一维数组\(a\)，\(a[i]\)代表第\(i\)行存0的个数(注意是从右到左，一旦碰到1便停止计入)。

在赛场上，观察到最终的\(grid\)，从第\(0\)行到第\(n-1\)行，0的个数几乎是““单调减少”。要将无序个数，转化为有序个数\(\Longrightarrow\) 排序消除逆序对？然而这并非是最优解，而且写着写着，会发现越来越多的数据得到的答案不符合最优解，比如{\(4, 1, 2, 3, 4\)}，显然我们是无需再将末尾的4交换到1号位置的。

我们不应该只比较行与行之间的相对大小，更要注意到第\(i\)行所需的0个数不小于\((n-i-1)\)，我们从第0行开始遍历，一旦发现某一行满足条件，就无需再管当前行。检查下一行，如果不满足条件，我们要向下寻找能够满足条件且是第一个的(即该行0个数大于等于检查行所需0个数)，并把它交换上来。交换的同时统计操作次数，当遍历到最底行时便得到答案。

class Solution {

public:

    int minSwaps(vector<vector<int>>& grid) {

        int zero[205] = { 0 }, len = grid.size();

        for (int i = 0; i < len; i++) {

            int cnt = 0;

            for (int j = grid[i].size() - 1; j >= 0; j--) {

                if (grid[i][j] == 0) cnt++;

                else break;

            }

            zero[i] = cnt;

        }

        int ans = 0;

        for (int i = 0; i < len; i++) { //枚举第i行

            if (zero[i] >= len - i - 1) continue;

            int now = len - i - 1; //条件所需个数

            int pos = i;

            for (int j = i + 1; j < len; j++) {

                if (zero[j] >= now) {

                    pos = j; break;

                }

            }//pos存第一个满足条件的那一行

            if (pos == i) return -1;

            for (int j = pos; j >= i+1; j--) {

                swap(zero[j], zero[j - 1]);

                ans++;

            }

        }

        return ans;

    }

};

1537 最大得分 #分段统计极值 #双指针

题意

给定两个有序且数组内元素互不相同的数组``nums1 和nums2`。一条合法路径定义如下：

选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。

从左到右遍历当前数组。
若遇到了 nums1 和 nums2 中都存在的值，那么可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。
得分定义为合法路径中不同数字的和。

现要求所有可能合法路径中的最大得分，并将它对 10^9 + 7 取余后返回。

样例

结果为\(30\)

分析

自己写的时候想得复杂了，利用双指针，比较两指针指向元素大小，先指向小元素的指针前进。直到两指针指向元素相等，再比较两个数组的前一条段的和，获得局部极大值，累加进答案。当有一指针到达数组末端时，将有剩余元素的数组继续一路迭代累加，最后再比较一次极大值，计入答案取模。注意，由于要比较局部的极大值，如果一边做加法一边取模会影响比较结果，且long long能够承受这个数据范围，故只需在最后取模一次即可。

typedef long long ll;

class Solution {

private: const int MOD = 1e9 + 7;

public:

    ll mymax(ll& a, ll& b) {

        return a > b ? a : b;

    }

    int maxSum(vector<int>& nums1, vector<int>& nums2) {

        int len1 = nums1.size(), len2 = nums2.size();

        int p1 = 0, p2 = 0;

        ll sum1 = 0, sum2 = 0;

        ll ans = 0;

        while (p1 < len1 && p2 < len2) {

            if (nums1[p1] > nums2[p2]) {

                sum2 = (sum2 + nums2[p2]);

                p2++;

            }

            else if (nums1[p1] < nums2[p2]) {

                sum1 = (sum1 + nums1[p1]);

                p1++;

            }

            else {

                ans = (ans + mymax(sum1, sum2));

                ans = (ans + nums1[p1]);

                sum1 = sum2 = 0;

                p1++; p2++;

            }

        }

        while (p1 < len1) sum1 = (sum1 + nums1[p1++]);

        while (p2 < len2) sum2 = (sum2 + nums2[p2++]);

        ans = (ans + mymax(sum1, sum2)) % MOD;

        return ans;

    }

};

巴特西

Leetcode 周赛#200 题解

1535 找出数组游戏的赢家 #模拟+优化

题目链接

题意

样例

分析

1536 排布二进制网格的最少交换次数 #贪心

题目链接

题意

样例

分析

1537 最大得分 #分段统计极值 #双指针

题目链接

题意

样例

分析

最新文章

热门文章