LeetCode 第 186 场周赛（1060/3107，前34.1%）

2. 题目

1. LeetCode 5392. 分割字符串的最大得分 easy

「分割字符串的得分」为 子字符串中 0 的数量加上 子字符串中 1 的数量。

```示例 1：

2 <= s.length <= 500

• 左右两边，前缀0，后缀1，一次遍历即可

```class Solution {
public:
int maxScore(string s) {
vector<int> left0(2*s.size()-1,0);
vector<int> right1(2*s.size()-1,0);
int i, n = s.size();
left0[0] = s[0]=='0' ? 1 : 0;
for(i = 1; i < n; ++i)
left0[2*i] = s[i]=='0'? left0[2*i-2]+1 : left0[2*i-2];

right1[2*n-2] = s[n-1]=='1' ? 1 : 0;
for(i = n-2; i >= 0; --i)
right1[2*i] = s[i]=='1'? right1[2*i+2]+1 : right1[2*i+2];
int maxsc = 0;
for(i = 1; i < 2*n-2; i+=2)
maxsc = max(maxsc, left0[i-1]+right1[i+1]);
return maxsc;
}
};```

4 ms 6.9 MB

```class Solution {
public:
int maxScore(string s) {
int i, one = 0, maxs = 0, zero = 0;
for(i = 0; i < s.size(); ++i)
{
if(s[i]=='1')
one++;
}
for(i = 0; i < s.size()-1; ++i)
{
if(s[i]=='0')
zero++;
else
one--;
maxs = max(maxs,zero+one);
}
return maxs;
}
};```

0 ms 6.4 MB

2. LeetCode 5393. 可获得的最大点数 medium

```示例 1：

1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length```

```class Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
vector<int> l(k+2,0);
vector<int> r(k+2,0);
int len = 1, i;
for(i = 0; i < k; ++i,++len)
l[len] = cardPoints[i]+l[len-1];
len = 1;
for(i = cardPoints.size()-1; len <= k; --i,++len)
r[len] = cardPoints[i]+r[len-1];
int maxScore = 0;
for(len = 0; len <= k; ++len)
maxScore = max(maxScore, l[len]+r[k-len]);
return maxScore;
}
};```

148 ms 44.2 MB

3. LeetCode 5394. 对角线遍历 II medium

```输入：nums = [[1,2,3],[4,5,6],[7,8,9]]

```输入：nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]

1 <= nums.length <= 10^5
1 <= nums[i].length <= 10^5
1 <= nums[i][j] <= 10^9
nums 中最多有 10^5 个数字。```

```class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
vector<int> ans;
int i = 0, j = 0, count = 0, c = 0, x, y, m = nums.size(),n=0, finishi = -1;
vector<int> precount(nums.size(),0);
for(i = 0; i < m; ++i)
{
count += nums[i].size();//总个数
n = max(n, int(nums[i].size()));//列最大个数
}
x = y = i = j = 0;
while(c < count)
{
i = x, j = y;//x,y起始位置
while(i>=0 && j<n && c<count)
{
if(j < nums[i].size())//在范围内
{
ans.push_back(nums[i][j]);
c++;//计数+1
precount[i]++;//该行写入答案数量+1
if(precount[i]==nums[i].size())//这行写完了
{
if(precount[finishi+1] == nums[finishi+1].size())
finishi++;//检查已完成的行，能不能往下挪
}
}
i--;
j++;
if(i <= finishi)
break;
}
x++;
if(x >= m)
{
x = m-1;
y++;
}
}
return ans;
}
};```

```class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
int i, j;
vector<vector<int>> v; //posx+posy, posx, val
for(i = 0; i < nums.size(); ++i)
{
for(j = 0; j < nums[i].size(); ++j)
{
v.push_back({i+j, i, nums[i][j]});
}
}
sort(v.begin(), v.end(),[&](auto a, auto b){
if(a[0]==b[0])
return a[1] > b[1];
return a[0] < b[0];
});
vector<int> ans(v.size());
i = 0;
for(auto& vi : v)
ans[i++] = vi[2];
return ans;
}
};```

• 按照两个坐标值的和分组，存入map，内层再嵌套map（x，val）
• 外层顺序遍历（坐标和小的先），内层逆序遍历（x大的先）
```class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
int i, j, size = 0;
map<int,map<int,int>> m;//posx+posy, posx, val
for(i = 0; i < nums.size(); ++i)
{
for(j = 0; j < nums[i].size(); ++j)
{
m[i+j][i] = nums[i][j];
size++;
}
}

vector<int> ans(size);
i = 0;
for(auto it = m.begin(); it != m.end(); ++it)
{
for(auto it1 = it->second.rbegin(); it1 != it->second.rend(); ++it1)
ans[i++] = it1->second;
}
return ans;
}
};```

4. LeetCode 5180. 带限制的子序列和 hard

```示例 1：

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4```

• 此题跟 LeetCode 239. 滑动窗口最大值（双端队列+单调栈） 非常类似，可以先看这题
• dp[i] 表示包含 i 位置的 最大子序和
• deque 里面保持递减状态（dp值递减，实际存储下标），距离超过 k 的，从队头出去
• 队头（最大的）>0，则 `dp[i] = dp[q.front()]+nums[i]`，否则，`dp[i] = nums[i]`
• 然后检查 dp[i] 要入队，队内是否单调递减，不满足，要`pop_back()`
```class Solution {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
int i, n = nums.size(), maxsum = INT_MIN;
vector<int> dp(n, 0);
dp[0] = nums[0];
maxsum = nums[0];
deque<int> q;
q.push_back(0);
for(i = 1; i < n; i++)
{
if(i-q.front() > k)//距离超过k了
q.pop_front();
if(dp[q.front()] > 0)//最大的大于0，可以变大
dp[i] = dp[q.front()]+nums[i];
else//不能变大，自己就是自己
dp[i] = nums[i];
maxsum = max(maxsum,dp[i]);//更新最大值
while(!q.empty() && dp[i] >= dp[q.back()])
q.pop_back();//不满足单点递减，pop_back
q.push_back(i);
}
return maxsum;
}
};```

112 ms 14.7 MB

0 条评论

• 程序员面试金典 - 面试题 17.04. 消失的数字（数学/位运算）

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/missing-number-lcci 著作权归领扣...

• 程序员面试金典 - 面试题 16.24. 数对和（双指针/哈希map）

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/pairs-with-sum-lcci 著作权归领扣...

• LintCode 1210. 升序子序列（DFS）

给定一个整数数组，找到所有不同的可能的升序子序列，一个升序子序列的长度至少应为2。

• [LeetCode]Array主题系列{1,11,15,16,18,26,27,31,33,34题}

1.内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程，具体内容层次按照{题目，分析，初解，初解结果，优化解，优化解结...

• Leetcode 566. Reshape the Matrix 矩阵变形(数组,模拟,矩阵操作)

在MATLAB中，reshape是一个非常有用的函数，它可以将矩阵变为另一种形状且保持数据不变。 已知一个由二维数组表示的矩阵，和两个正整数r(行),c(列)...

• 程序员面试金典 - 面试题 17.04. 消失的数字（数学/位运算）

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/missing-number-lcci 著作权归领扣...

• 程序员面试金典 - 面试题 16.24. 数对和（双指针/哈希map）

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/pairs-with-sum-lcci 著作权归领扣...

• 分割数组的最大值

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。 数组长度...

• 【LeetCode】494. 目标和

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一...