1535 找出数组游戏的赢家 #模拟+优化
题意
给你一个由 不同 整数组成的整数数组 arr 和一个整数 k(1≤k≤1e9) 。每回合游戏都在数组的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≥数组长度，要连胜k次，至少比较完arr数组所有元素一轮，那要一轮都能够取胜且arr无重复数字，可推出只有arr的max才能满足连胜k局
总的来说，我并不需要模拟"较小的整数移至数组的末尾"的操作，O(n)即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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×n的二进制网格grid，每次操作可选择网格的相邻两行进行交换。
现要将给定网格转化为满足主对角线以上(从(1,1) 到(n,n))的格子全为 0的网格 ，要求使网格满足要求的最少操作次数。若无法使网格符合要求，返回 -1
样例
分析
那我们肯定要先将grid抽出关键信息，转化为一维数组a，a[i]代表第i行存0的个数(注意是从右到左，一旦碰到1便停止计入)。
在赛场上，观察到最终的grid，从第0行到第n−1行，0的个数几乎是““单调减少”。要将无序个数，转化为有序个数⟹ 排序消除逆序对？然而这并非是最优解，而且写着写着，会发现越来越多的数据得到的答案不符合最优解，比如{4,1,2,3,4}，显然我们是无需再将末尾的4交换到1号位置的。
我们不应该只比较行与行之间的相对大小，更要注意到第i行所需的0个数不小于(n−i−1)，我们从第0行开始遍历，一旦发现某一行满足条件，就无需再管当前行。检查下一行，如果不满足条件，我们要向下寻找能够满足条件且是第一个的(即该行0个数大于等于检查行所需0个数)，并把它交换上来。交换的同时统计操作次数，当遍历到最底行时便得到答案。
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
| 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++) {
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;
}
}
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能够承受这个数据范围，故只需在最后取模一次即可。
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
| 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;
}
};
|
