Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitcaf33c6

Browse files
Update
1 parentea689c7 commitcaf33c6

10 files changed

+398
-9
lines changed

‎README.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,8 @@
4444
*[数组：就移除个元素很难么？](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
4545
*[数组：滑动窗口拯救了你](https://mp.weixin.qq.com/s/UrZynlqi4QpyLlLhBPglyg)
4646
*[数组：这个循环可以转懵很多人！](https://mp.weixin.qq.com/s/KTPhaeqxbMK9CxHUUgFDmg)
47+
*[数组：总结篇](https://mp.weixin.qq.com/s/LIfQFRJBH5ENTZpvixHEmg)
48+
*[字符串：这道题目，使用库函数一行代码搞定](https://mp.weixin.qq.com/s/X02S61WCYiCEhaik6VUpFA)
4749
* 精选链表相关的面试题
4850
* 精选字符串相关的面试题
4951
* 精选栈与队列相关的面试题
@@ -428,6 +430,7 @@ int countNodes(TreeNode* root) {
428430
|[0450.删除二叉搜索树中的节点](https://github.com/youngyangyang04/leetcode/blob/master/problems/0450.删除二叉搜索树中的节点.md)|树|中等|**递归**|
429431
|[0454.四数相加II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0454.四数相加II.md)|哈希表|中等|**哈希**|
430432
|[0459.重复的子字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0459.重复的子字符串.md)|字符创|简单|**KMP**|
433+
|[0486.预测赢家](https://github.com/youngyangyang04/leetcode/blob/master/problems/0486.预测赢家.md)|动态规划|中等|**递归****记忆递归****动态规划**|
431434
|[0491.递增子序列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0491.递增子序列.md)|深度优先搜索|中等|**深度优先搜索/回溯算法**|
432435
|[0541.反转字符串II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0541.反转字符串II.md)|字符串|简单|**模拟**|
433436
|[0575.分糖果](https://github.com/youngyangyang04/leetcode/blob/master/problems/0575.分糖果.md)|哈希表|简单|**哈希**|
@@ -437,6 +440,7 @@ int countNodes(TreeNode* root) {
437440
|[0701.二叉搜索树中的插入操作](https://github.com/youngyangyang04/leetcode/blob/master/problems/0701.二叉搜索树中的插入操作.md)|树|简单|**递归****迭代**|
438441
|[0705.设计哈希集合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0705.设计哈希集合.md)|哈希表|简单|**模拟**|
439442
|[0707.设计链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0707.设计链表.md)|链表|中等|**模拟**|
443+
|[0841.钥匙和房间](https://github.com/youngyangyang04/leetcode/blob/master/problems/0841.钥匙和房间.md)|孤岛问题|中等|**bfs****dfs**|
440444
|[1047.删除字符串中的所有相邻重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/1047.删除字符串中的所有相邻重复项.md)|栈|简单|**栈**|
441445
|[剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)|字符串|简单|**双指针**|
442446
|[面试题02.07.链表相交](https://github.com/youngyangyang04/leetcode/blob/master/problems/面试题02.07.链表相交.md)|链表|简单|**模拟**|

‎pics/486.预测赢家.png

42.9 KB
Loading

‎pics/486.预测赢家1.png

80 KB
Loading

‎pics/486.预测赢家2.png

73 KB
Loading

‎pics/486.预测赢家3.png

42.6 KB
Loading

‎pics/486.预测赢家4.png

41.6 KB
Loading

‎pics/841.钥匙和房间.png

55.7 KB
Loading

‎problems/0486.预测赢家.md

Lines changed: 279 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,279 @@
1+
##题目地址
2+
3+
##思路
4+
5+
在做这道题目的时候，最直接的想法，就是计算出player1可能得到的最大分数，然后用数组总和减去player1的得分就是player2的得分，然后两者比较一下就可以了。
6+
7+
那么问题是如何计算player1可能得到的最大分数呢。
8+
9+
##单独计算玩家得分
10+
11+
以player1选数字的过程，画图如下：
12+
13+
<imgsrc='../pics/486.预测赢家2.png'width=600> </img></div>
14+
15+
可以发现是一个递归的过程。
16+
17+
按照递归三部曲来：
18+
19+
1. 确定递归函数的含义，参数以及返回值。
20+
21+
定义函数getScore，就是用来获取玩家1的最大得分。 参数为start 和 end 代表获取[start, end]这个区间的最大值，当然还需要传入nums。
22+
23+
返回值就是玩家1的最大得分。
24+
25+
代码如下：
26+
27+
```
28+
int getScore(vector<int>& nums, int start, int end) {
29+
```
30+
31+
32+
2. 确定终止条件
33+
34+
当start == end的时候，玩家A的得分就是nums[start]，代码如下：
35+
```
36+
if (start == end) {
37+
return nums[start];
38+
}
39+
```
40+
41+
3. 确定单层递归逻辑
42+
43+
玩家1的得分，等于集合左元素的数值+ 玩家2选择后集合的最小值（因为玩家2也是最聪明的）
44+
45+
46+
而且剩余集合中的元素数量为2，或者大于2，的处理逻辑是不一样的！
47+
48+
如图：当集合中的元素数量大于2，那么玩家1先选，玩家2依然有选择的权利。
49+
<imgsrc='../pics/486.预测赢家3.png'width=600> </img></div>
50+
所以代码如下：
51+
```
52+
if ((end - start) >= 2) {
53+
selectLeft = nums[start] + min(getScore(nums, start + 2, end), getScore(nums, start + 1, end - 1));
54+
selectRight = nums[end] + min(getScore(nums, start + 1, end - 1), getScore(nums, start, end - 2));
55+
}
56+
```
57+
58+
59+
如图：当集合中的元素数量等于2，那么玩家1先选，玩家2没得选。
60+
<imgsrc='../pics/486.预测赢家4.png'width=600> </img></div>
61+
62+
所以代码如下：
63+
```
64+
if ((end - start) == 1) {
65+
selectLeft = nums[start];
66+
selectRight = nums[end];
67+
}
68+
```
69+
70+
单层递归逻辑代码如下：
71+
72+
```
73+
int selectLeft, selectRight;
74+
if ((end - start) >= 2) {
75+
selectLeft = nums[start] + min(getScore(nums, start + 2, end), getScore(nums, start + 1, end - 1));
76+
selectRight = nums[end] + min(getScore(nums, start + 1, end - 1), getScore(nums, start, end - 2));
77+
}
78+
if ((end - start) == 1) {
79+
selectLeft = nums[start];
80+
selectRight = nums[end];
81+
}
82+
83+
return max(selectLeft, selectRight);
84+
```
85+
86+
这些可以写出这道题目整体代码如下：
87+
88+
```
89+
class Solution {
90+
private:
91+
int getScore(vector<int>& nums, int start, int end) {
92+
if (start == end) {
93+
return nums[start];
94+
}
95+
int selectLeft, selectRight;
96+
if ((end - start) >= 2) {
97+
selectLeft = nums[start] + min(getScore(nums, start + 2, end), getScore(nums, start + 1, end - 1));
98+
selectRight = nums[end] + min(getScore(nums, start + 1, end - 1), getScore(nums, start, end - 2));
99+
}
100+
if ((end - start) == 1) {
101+
selectLeft = nums[start];
102+
selectRight = nums[end];
103+
}
104+
105+
return max(selectLeft, selectRight);
106+
}
107+
public:
108+
bool PredictTheWinner(vector<int>& nums) {
109+
int sum = 0;
110+
for (int i : nums) {
111+
sum += i;
112+
}
113+
int player1 = getScore(nums, 0, nums.size() - 1);
114+
int player2 = sum - player1;
115+
return player1 >= player2;
116+
}
117+
};
118+
```
119+
120+
可以有一个优化，就是把重复计算的数值提取出来，如下：
121+
```
122+
class Solution {
123+
private:
124+
int getScore(vector<int>& nums, int start, int end) {
125+
int selectLeft, selectRight;
126+
int gap = end - start;
127+
if (gap == 0) {
128+
return nums[start];
129+
} else if (gap == 1) { // 此时直接取左右的值就可以
130+
selectLeft = nums[start];
131+
selectRight = nums[end];
132+
} else if (gap >= 2) { // 如果gap大于2，递归计算selectLeft和selectRight
133+
// 计算的过程为什么用min，因为要按照对手也是最聪明的来计算。
134+
int num = getScore(nums, start + 1, end - 1);
135+
selectLeft = nums[start] +
136+
min(getScore(nums, start + 2, end), num);
137+
selectRight = nums[end] +
138+
min(num, getScore(nums, start, end - 2));
139+
}
140+
return max(selectLeft, selectRight);
141+
}
142+
public:
143+
bool PredictTheWinner(vector<int>& nums) {
144+
int sum = 0;
145+
for (int i : nums) {
146+
sum += i;
147+
}
148+
int player1 = getScore(nums, 0, nums.size() - 1);
149+
int player2 = sum - player1;
150+
// 如果最终两个玩家的分数相等，那么玩家 1 仍为赢家，所以是大于等于。
151+
return player1 >= player2;
152+
}
153+
};
154+
```
155+
156+
##计算两个玩家的差值
157+
158+
以上是单独计算出两个选手的得分，逻辑上直观，但是代码确实比较冗余。
159+
160+
因为就我们要求的结果其实就是两个选手的胜负，那么不用两个选手的得分，而是把问题转换为两个选手所拿元素的差值。
161+
162+
代码如下：
163+
164+
```
165+
class Solution {
166+
private:
167+
int getScore(vector<int>& nums, int start, int end) {
168+
if (end == start) {
169+
return nums[start];
170+
}
171+
int selectLeft = nums[start] - getScore(nums, start + 1, end);
172+
int selectRight = nums[end] - getScore(nums, start, end - 1);
173+
return max(selectLeft, selectRight);
174+
}
175+
public:
176+
bool PredictTheWinner(vector<int>& nums) {
177+
return getScore(nums, 0, nums.size() - 1) >=0 ;
178+
}
179+
};
180+
```
181+
182+
计算的过程有一些是冗余的，在递归的过程中，可以使用一个memory数组记录一下中间结果，代码如下：
183+
184+
```
185+
class Solution {
186+
private:
187+
int getScore(vector<int>& nums, int start, int end, int memory[21][21]) {
188+
if (end == start) {
189+
return nums[start];
190+
}
191+
if (memory[start][end]) return memory[start][end];
192+
int selectLeft = nums[start] - getScore(nums, start + 1, end, memory);
193+
int selectRight = nums[end] - getScore(nums, start, end - 1, memory);
194+
memory[start][end] = max(selectLeft, selectRight);
195+
return memory[start][end];
196+
}
197+
public:
198+
bool PredictTheWinner(vector<int>& nums) {
199+
int memory[21][21] = {0}; // 记录递归中中间结果
200+
return getScore(nums, 0, nums.size() - 1, memory) >= 0 ;
201+
}
202+
};
203+
```
204+
205+
此时效率已经比较高了
206+
<imgsrc='../pics/486.预测赢家.png'width=600> </img></div>
207+
208+
那么在看一下动态规划的思路。
209+
210+
211+
##动态规划
212+
213+
214+
定义一个二维数组，先明确是用来干什么的，dp[i][j] 表示两个玩家在数组 i 到 j 区间内游戏能赢对方的差值（i <= j）。
215+
216+
假如玩家1先取左端 nums[i]，那么玩家2能赢对方的差值是dp[i+1][j] ，如果玩家1先取取右端 nums[j]，玩家2能赢对方的差值就是dp[i][j-1]，
217+
218+
那么 不难理解如下公式：
219+
220+
`dp[i][j] = max((nums[i] - dp[i + 1][j]), (nums[j] - dp[i][j - 1]));`
221+
222+
223+
确定了状态转移公式之后，就要想想如何遍历。
224+
225+
一些同学确定的方程，却不知道该如何遍历这个遍历推算出方程的结果，我们来看一下。
226+
227+
首先要给dp[i][j]进行初始化，首先当i == j的时候，nums[i]就是dp[i][j]的值。
228+
229+
代码如下：
230+
231+
```
232+
// 当i == j的时候，nums[i]就是dp[i][j]
233+
for (int i = 0; i < nums.size(); i++) {
234+
dp[i][i] = nums[i];
235+
}
236+
```
237+
238+
接下来就要推导公式了，首先要知道最终求是dp[0][nums.size() - 1]是否大于等于0，也就是求dp[0][nums.size() - 1] 至关重要。
239+
240+
从下图中，可以看出在推导方程的时候一定要从右上角向下推导，而且矩阵左半部分根本不用管！
241+
242+
<imgsrc='../pics/486.预测赢家1.png'width=600> </img></div>
243+
244+
按照上图中的规则，不难列出推导公式的循环方式如下：
245+
246+
```
247+
for(int i = nums.size() - 2; i >= 0; i--) {
248+
for (int j = i + 1; j < nums.size(); j++) {
249+
dp[i][j] = max((nums[i] - dp[i + 1][j]), (nums[j] - dp[i][j - 1]));
250+
}
251+
}
252+
253+
```
254+
255+
最后整体动态规划的代码：
256+
257+
##
258+
259+
```
260+
class Solution {
261+
public:
262+
bool PredictTheWinner(vector<int>& nums) {
263+
// dp[i][j] 表示两个玩家在数组 i 到 j 区间内游戏能赢对方的差值（i <= j）
264+
int dp[22][22] = {0};
265+
// 当i == j的时候，nums[i]就是dp[i][j]
266+
for (int i = 0; i < nums.size(); i++) {
267+
dp[i][i] = nums[i];
268+
}
269+
for(int i = nums.size() - 2; i >= 0; i--) {
270+
for (int j = i + 1; j < nums.size(); j++) {
271+
dp[i][j] = max((nums[i] - dp[i + 1][j]), (nums[j] - dp[i][j - 1]));
272+
}
273+
}
274+
return dp[0][nums.size() - 1] >= 0;
275+
}
276+
};
277+
```
278+
279+

‎problems/0541.反转字符串II.md

Lines changed: 33 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,43 @@
11

2-
##题目地址
2+
#题目地址
33

44
https://leetcode-cn.com/problems/reverse-string-ii/
55

6-
##思路
6+
>简单的反转还不够，我要花式反转
77
8-
先做0344.反转字符串，在做这道题目更好一些
8+
#题目：541. 反转字符串II
99

10-
for循环中i 每次移动 2 * k，然后判断是否需要有反转的区间
10+
给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。
11+
12+
如果剩余字符少于 k 个，则将剩余字符全部反转。
13+
14+
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
15+
16+
示例:
17+
18+
输入: s = "abcdefg", k = 2
19+
输出: "bacdfeg"
20+
21+
#思路
22+
23+
这道题目其实也是模拟，实现题目中规定的反转规则就可以了。
24+
25+
一些同学可能为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。
26+
27+
其实在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。
28+
29+
因为要找的也就是每2 * k 区间的起点，这样写，程序会高效很多。
30+
31+
**所以当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。**
1132

1233
性能如下：
1334
<imgsrc='../pics/541_反转字符串II.png'width=600> </img></div>
1435

15-
##C++代码
36+
那么这里具体反转的逻辑我们要不要使用库函数呢，其实用不用都可以，使用reverse来实现反转也没毛病，毕竟不是解题关键部分。
37+
38+
#C++代码
1639

17-
使用C++库里的反转函数reverse
40+
使用C++库函数reverse的版本如下：
1841

1942
```
2043
class Solution {
@@ -35,13 +58,14 @@ public:
3558
};
3659
```
3760

38-
自己实现反转函数
61+
那么我们也可以实现自己的reverse函数，其实和题目[344. 反转字符串](https://mp.weixin.qq.com/s/X02S61WCYiCEhaik6VUpFA)道理是一样的。
62+
63+
下面我实现的reverse函数区间是左闭右闭区间，代码如下：
3964
```
4065
class Solution {
4166
public:
4267
void reverse(string& s, int start, int end) {
43-
int offset = (end - start + 1) / 2;
44-
for (int i = start, j = end; i < start + offset; i++, j--) {
68+
for (int i = start, j = end; i < j; i++, j--) {
4569
swap(s[i], s[j]);
4670
}
4771
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp