LeetCode题解877.stone-game

题目地址

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 次你也是赢的。

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

LeetCode题解55.jump-game

题目地址 https://leetcode.com/problems/jump-game/description/ 题目描述 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element i…

如何检查Point是否在对角线上？ - java

我有一个canvas和lines。在click上，我想检查单击是否在我的行上以突出显示它。我也有一些rectangles，只需使用正方形的start和end point即可轻松实现。但是对于diagonal line，我不能使用相同的技术，因为直线当然不能填充矩形。但是我还能怎么做到呢？此外，我还希望有一些“偏移”，这样，如果单击距线条足够近，它也会被标记，…

LeetCode题解3.longestSubstringWithoutRepeatingCharacters

题目地址 https://leetcode.com/problems/longest-substring-without-repeating-characters/description/ 题目描述 Given a string, find the length of the longest substring without repeating chara…

LeetCode题解计算机为什么是基于二进制的？

可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制

LeetCode题解统计城市的所有灯泡

这个是我刚毕业的时候，一个真实的面试题，这是一个开放题。题目描述：想办法，将一个城市的所有灯泡数量统计出来。题解：费米估算法1、如果某个城市常驻人口有1000万2、假设每5人居住在一套房里，每套房有灯泡5只，那么住宅灯泡共有1000万只3、假设公众场所每10人共享一只灯泡，那么共有100万只4、主要的这两者相加就得出了1100万只当然实际上这是估算的，具体应…