Skip to content

Latest commit

 

History

History
142 lines (110 loc) · 4.31 KB

877.stone-game.md

File metadata and controls

142 lines (110 loc) · 4.31 KB
Raw

题目地址

https://leetcode.com/problems/stone-game/description/

题目描述

Alex and Lee play a game with piles of stones.  There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].

The objective of the game is to end with the most stones.  The total number of stones is odd, so there are no ties.

Alex and Lee take turns, with Alex starting first.  Each turn, a player takes the entire pile of stones from either the beginning or the end of the row.  This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.



Example 1:

Input: [5,3,4,5]
Output: true
Explanation:
Alex starts first, and can only take the first 5 or the last 5.
Say he takes the first 5, so that the row becomes [3, 4, 5].
If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alex, so we return true.


Note:

2 <= piles.length <= 500
piles.length is even.
1 <= piles[i] <= 500
sum(piles) is odd.

思路

由于 piles 是偶数的，并且 piles 的总和是奇数的。

因此 Alex可以做到要不拿的全部是奇数，要么全部是偶数。

举个例子： 比如 Alex 第一次先拿第一个

这里有两种情况：

  1. Lee 如果拿了第二块（偶数），那么 Alex 继续拿第三块，以此类推。。。

  2. Lee 如果拿了最后一块（偶数），那么 Alex 继续拿倒数第二块，以此类推。。。

因此 Alex可以做到只拿奇数或者偶数，只是他可以控制的，因此他要做的就是数一下，奇数加起来多还是偶数加起来多就好了。 奇数多就全部选奇数，偶数就全部选偶数。 Lee 是没有这种自由权的。

关键点解析

  • 可以用 DP（动态规划）

  • 可以从数学的角度去分析

......(😅)

代码

/*
 * @lc app=leetcode id=877 lang=javascript
 *
 * [877] Stone Game
 *
 * https://leetcode.com/problems/stone-game/description/
 *
 * algorithms
 * Medium (60.46%)
 * Total Accepted:    21.4K
 * Total Submissions: 35.3K
 * Testcase Example:  '[5,3,4,5]'
 *
 * Alex and Lee play a game with piles of stones.  There are an even number of
 * piles arranged in a row, and each pile has a positive integer number of
 * stones piles[i].
 *
 * The objective of the game is to end with the most stones.  The total number
 * of stones is odd, so there are no ties.
 *
 * Alex and Lee take turns, with Alex starting first.  Each turn, a player
 * takes the entire pile of stones from either the beginning or the end of the
 * row.  This continues until there are no more piles left, at which point the
 * person with the most stones wins.
 *
 * Assuming Alex and Lee play optimally, return True if and only if Alex wins
 * the game.
 *
 *
 *
 * Example 1:
 *
 *
 * Input: [5,3,4,5]
 * Output: true
 * Explanation:
 * Alex starts first, and can only take the first 5 or the last 5.
 * Say he takes the first 5, so that the row becomes [3, 4, 5].
 * If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10
 * points.
 * If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win
 * with 9 points.
 * This demonstrated that taking the first 5 was a winning move for Alex, so we
 * return true.
 *
 *
 *
 *
 * Note:
 *
 *
 * 2 <= piles.length <= 500
 * piles.length is even.
 * 1 <= piles[i] <= 500
 * sum(piles) is odd.
 *
 *
 *
 */
/**
 * @param {number[]} piles
 * @return {boolean}
 */
var stoneGame = function(piles) {
  return true;
};

扩展

腾讯面试题：一共 100 只弓箭 你和你的对手共用。你们每次只能射出一支箭或者两支箭，射击交替进行，设计一个算法，保证自己获胜。

答案： 先手，剩下的是 3 的倍数就行（100-1=99），然后按照 3 的倍数射箭必赢。 比如你先拿了 1，剩下 99 个。 对手拿了 1，你就拿 2。这样持续 33 次就赢了。如果对手拿了 2 个，你就拿 1 个，这样持续 33 次你也是赢的。

这是一种典型的博弈问题， 你和对手交替进行，对手的行动影响你接下来的策略。 这算是一种最简单的博弈问题了