如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习上岸经历校招总结阿里、字节、腾讯、美团等一二线大厂真实面经也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# 877. 石子游戏

力扣原题链接(点我直达) (opens new window)

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i]

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数,所以没有平局。

亚历克斯和李轮流进行,亚历克斯先开始。 每回合,玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平,当亚历克斯赢得比赛时返回 true ,当李赢得比赛时返回 false

示例:

输入:[5,3,4,5]
输出:true
解释:
亚历克斯先开始,只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗,这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗,那么剩下的是 [4,5],亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗,那么剩下的是 [3,4],亚历克斯拿走后 4 颗赢得 9 分。
这表明,取前 5 颗石子对亚历克斯来说是一个胜利的举动,所以我们返回 true 。
1
2
3
4
5
6
7
8

提示:

  1. 2 <= piles.length <= 500
  2. piles.length 是偶数。
  3. 1 <= piles[i] <= 500
  4. sum(piles) 是奇数。

# 第一版,看的解析,很厉害

https://leetcode-cn.com/problems/stone-game/solution/dong-tai-gui-hua-by-cliant/

动态规划+二维数组

判断的结果为先拿者是否可以拿到较多的石子。可以将问题转换为先拿者的石子数相对于后拿者的石子数的差值是否为正数,即表示先拿者的石子数是否多于后拿者的石子数。所以在依次拿石子的过程中,依次判断先拿者相对于后拿者的石子数即可。

不妨以 f(i,j)f(i,j) 表示对于下标 ii 到下标 jj 的 (j-i+1)(j−i+1) 堆石子,当前选手相对于对手能够多出的石子数。若 i==ji==j,则明显当前选手相对于对手多出的石子数为 f(i,j)=piles[i]f(i,j)=piles[i],因为只有一堆石子。

若有两堆或多堆石子,则 f(i,j)=max(piles[i]-f(i+1,j), piles[j]-f(i,j-1))f(i,j)=max(piles[i]−f(i+1,j),piles[j]−f(i,j−1)),其中 f(i+1,j)f(i+1,j) 表示对手相对于当前选手多出的石子,当前选手选择 piles[i]piles[i],所以当前选手相对于对手多出的石子为 piles[i]-f(i+1,j)piles[i]−f(i+1,j)。同理对于 piles[j]-f(i,j-1))piles[j]−f(i,j−1)) 。所以当前选手取两种情况中的最大值。

以 dp[i][j]dp[i][j] 二维数组存储 f(i,j)f(i,j) 的值,递推过程如下图所示:

因为初始情况只知道 i==ji==j ,即对角线上的 dpdp 值,所以推导 dpdp 数组按照红色序号顺序进行。

执行用时 :12 ms, 在所有 cpp 提交中击败了49.16%的用户

内存消耗 :17.1 MB, 在所有 cpp 提交中击败了20.00%的用户

    bool stoneGame(vector<int>& piles) {
        //dp[i][j]为i开始到j结束alex能赢li多少分 alex先拿的话
	   //dp[i][j] = max(piles[i]-dp[i+1][j],piles[j]-dp[i][j-1])(先拿左边的-对手比我多的,先拿右边的-对手比我多的)
	int len = piles.size();
	vector<vector<int>> dp (len,vector<int>(len,0));
	for (int i = 0; i < len; i++) {
		dp[i][i] = piles[i];
	}
	for (int i = 1; i < len; i++) {
		for (int j = 0; j < len - i; j++) {
			dp[j][j + i] = max(piles[j] - dp[j + 1][j + i], piles[j + i] - dp[j][j + i - 1]);
		}
	}
	return dp[0][len - 1] > 0;
        
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 降维处理

执行用时 :12 ms, 在所有 cpp 提交中击败了49.16%的用户

内存消耗 :8.2 MB, 在所有 cpp 提交中击败了96.80%的用户

    bool stoneGame(vector<int>& piles) {
	int len = piles.size();
	vector<int> dp (piles);

	for (int i = 1; i < len; ++i)
		for (int j = 0; j < len - i; ++j)
			dp[j] = max(piles[j] - dp[j + 1], piles[j + i] - dp[j]);

	return dp[0] > 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11