1 Star 2 Fork 1

mirrors/azl397985856-leetcode

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
.github
.vscode
91
assets
backlog
collections
daily
problems
1.two-sum.en.md
1.two-sum.md
100.same-tree.md
1004.max-consecutive-ones-iii.md
101.symmetric-tree.md
101.symmetrical-tree.en.md
1011.capacity-to-ship-packages-within-d-days-en.md
1011.capacity-to-ship-packages-within-d-days.md
1014.best-sightseeing-pair.md
1015.smallest-integer-divisible-by-k.md
1019.next-greater-node-in-linked-list.md
102.binary-tree-level-order-traversal.md
1020.number-of-enclaves.md
1023.camelcase-matching.md
103.binary-tree-zigzag-level-order-traversal.md
1031.maximum-sum-of-two-non-overlapping-subarrays.md
1032.stream-of-characters.md
104.maximum-depth-of-binary-tree.en.md
104.maximum-depth-of-binary-tree.md
1043.partition-array-for-maximum-sum.md
1053.previous-permutation-with-one-swap.md
108.convert-sorted-array-to-binary-search-tree.en.md
108.convert-sorted-array-to-binary-search-tree.md
109.Convert-Sorted-List-to-Binary-Search-Tree.md
11.container-with-most-water.md
1104.path-in-zigzag-labelled-binary-tree.md
1128.number-of-equivalent-domino-pairs.md
1129.shortest-path-with-alternating-colors.md
113.path-sum-ii.md
1131.maximum-of-absolute-value-expression.md
1138.alphabet-board-path.md
1168.optimize-water-distribution-in-a-village-en.md
1168.optimize-water-distribution-in-a-village.md
1178.number-of-valid-words-for-each-puzzle.md
1186.maximum-subarray-sum-with-one-deletion.md
1203.sort-items-by-groups-respecting-dependencies.md
121.best-time-to-buy-and-sell-stock.en.md
121.best-time-to-buy-and-sell-stock.md
1218.longest-arithmetic-subsequence-of-given-difference.md
122.best-time-to-buy-and-sell-stock-ii.en.md
122.best-time-to-buy-and-sell-stock-ii.md
1227.airplane-seat-assignment-probability.md
124.binary-tree-maximum-path-sum.md
125.valid-palindrome.en.md
125.valid-palindrome.md
1255.maximum-score-words-formed-by-letters.md
1260.shift-2d-grid.en.md
1260.shift-2d-grid.md
1261.find-elements-in-a-contaminated-binary-tree.md
1262.greatest-sum-divisible-by-three.md
128.longest-consecutive-sequence.md
129.sum-root-to-leaf-numbers.md
1297.maximum-number-of-occurrences-of-a-substring.md
130.surrounded-regions.md
131.palindrome-partitioning.md
1310.xor-queries-of-a-subarray.md
132.palindrome-partitioning-ii.md
1332.remove-palindromic-sequences.en.md
1332.remove-palindromic-subsequences.md
1334.find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance.md
136.single-number.en.md
136.single-number.md
1371.find-the-longest-substring-containing-vowels-in-even-counts.en.md
1371.find-the-longest-substring-containing-vowels-in-even-counts.md
1381.design-a-stack-with-increment-operation.md
139.word-break.md
140.word-break-ii.md
142.Linked-List-Cycle-II.md
1423.maximum-points-you-can-obtain-from-cards.md
1435.jump-game-iv.md
1438.longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit.md
144.binary-tree-preorder-traversal.md
1449.form-largest-integer-with-digits-that-add-up-to-target.md
145.binary-tree-postorder-traversal.md
146.lru-cache.md
147.insertion-sort-list.md
1494.parallel-courses-ii.md
15.3sum.md
150.evaluate-reverse-polish-notation.md
152.maximum-product-subarray.md
1521.find-a-value-of-a-mysterious-function-closest-to-target.md
1526.minimum-number-of-increments-on-subarrays-to-form-a-target-array.md
153.find-minimum-in-rotated-sorted-array.md
154.find-minimum-in-rotated-sorted-array-ii.md
155.min-stack.en.md
155.min-stack.md
1558.minimum-numbers-of-function-calls-to-make-target-array.md
1574.shortest-subarray-to-be-removed-to-make-array-sorted.md
1589.maximum-sum-obtained-of-any-permutation.md
160.Intersection-of-Two-Linked-Lists.en.md
160.Intersection-of-Two-Linked-Lists.md
1631.path-with-minimum-effort.md
1638.count-substrings-that-differ-by-one-character.md
1639.number-of-ways-to-form-a-target-string-given-a-dictionary.md
1649.create-sorted-array-through-instructions.md
1658.minimum-operations-to-reduce-x-to-zero.md
167.two-sum-ii-input-array-is-sorted.en.md
167.two-sum-ii-input-array-is-sorted.md
1671.minimum-number-of-removals-to-make-mountain-array.md
169.majority-element.en.md
169.majority-element.md
1697.checking-existence-of-edge-length-limited-paths.md
17.Letter-Combinations-of-a-Phone-Number.md
1713.minimum-operations-to-make-a-subsequence.md
172.factorial-trailing-zeroes.en.md
172.factorial-trailing-zeroes.md
1723.find-minimum-time-to-finish-all-jobs.md
1737.change-minimum-characters-to-satisfy-one-of-three-conditions.md
1770.maximum-score-from-performing-multiplication-operations.md
1787.make-the-xor-of-all-segments-equal-to-zero.md
1793.maximum-score-of-a-good-subarray.md
1834.single-threaded-cpu.md
1835.find-xor-sum-of-all-pairs-bitwise-and.md
1871.jump-game-vii.md
1872.stone-game-viii.md
1899.merge-triplets-to-form-target-triplet.md
19.removeNthNodeFromEndofList.md
190.reverse-bits.en.md
190.reverse-bits.md
1904.the-number-of-full-rounds-you-have-played.md
1906.minimum-absolute-difference-queries.md
191.number-of-1-bits.en.md
191.number-of-1-bits.md
1970.last-day-where-you-can-still-cross.md
198.house-robber.en.md
198.house-robber.md
199.binary-tree-right-side-view.md
2.add-two-numbers.en.md
2.add-two-numbers.md
20.valid-parentheses.md
20.valid-parents.en.md
200.number-of-islands.md
2007.find-original-array-from-doubled-array.md
2008.maximum-earnings-from-taxi.md
2009.minimum-number-of-operations-to-make-array-continuous.md
201.bitwise-and-of-numbers-range.md
2025.maximum-number-of-ways-to-partition-an-array.md
203.remove-linked-list-elements.en.md
203.remove-linked-list-elements.md
2030.smallest-k-length-subsequence-with-occurrences-of-a-letter.md
206.reverse-linked-list.en.md
206.reverse-linked-list.md
208.implement-trie-prefix-tree.md
209.minimum-size-subarray-sum.md
21.merge-two-sorted-lists.en.md
21.merge-two-sorted-lists.md
2102.sequentially-ordinal-rank-tracker.md
211.add-and-search-word-data-structure-design.md
212.word-search-ii.md
2141.maximum-running-time-of-n-computers.md
215.kth-largest-element-in-an-array.md
2172.count-good-triplets-in-an-array.md
219.contains-duplicate-ii.en.md
219.contains-duplicate-ii.md
22.generate-parentheses.md
220.contains-duplicate-iii.md
2209.minimum-white-tiles-after-covering-with-carpets.md
221.maximal-square.md
226.invert-binary-tree.en.md
226.invert-binary-tree.md
227.basic-calculator-ii.md
2281.sum-of-total-strength-of-wizards.md
229.majority-element-ii.md
23.merge-k-sorted-lists.md
230.kth-smallest-element-in-a-bst.md
2306.naming-a-company.md
2312.selling-pieces-of-wood.md
232.implement-queue-using-stacks.en.md
232.implement-queue-using-stacks.md
236.lowest-common-ancestor-of-a-binary-tree.md
238.product-of-array-except-self.md
239.sliding-window-maximum.md
24.swapNodesInPairs.md
240.search-a-2-d-matrix-ii.md
25.reverse-nodes-in-k-groups-en.md
25.reverse-nodes-in-k-groups.md
2591.distribute-money-to-maximum-children.md
2592.maximize-greatness-of-an-array.md
2593.find-score-of-an-array-after-marking-all-elements.md
26.remove-duplicates-from-sorted-array.en.md
26.remove-duplicates-from-sorted-array.md
263.ugly-number.en.md
263.ugly-number.md
279.perfect-squares.md
2817.minimum-absolute-difference-between-elements-with-constraint.md
283.move-zeroes.en.md
283.move-zeroes.md
2842.count-k-subsequences-of-a-string-with-maximum-beauty.md
2865.beautiful-towers-i.md
2866.beautiful-towers-ii.md
29.divide-two-integers.md
2939.maximum-xor-product.md
295.find-median-from-data-stream.md
297.serialize-and-deserialize-binary-tree.md
2972.count-the-number-of-incremovable-subarrays-ii.md
3.longest-substring-without-repeating-characters.md
30.substring-with-concatenation-of-all-words.md
301.remove-invalid-parentheses.md
3027.find-the-number-of-ways-to-place-people-ii.md
3041.maximize-consecutive-elements-in-an-array-after-modification.md
3082.find-the-sum-of-the-power-of-all-subsequences.md
309.best-time-to-buy-and-sell-stock-with-cooldown.md
31.next-permutation.md
3108.minimum-cost-walk-in-weighted-graph.md
312.burst-balloons.md
32.longest-valid-parentheses.md
322.coin-change.md
3229.minimum-operations-to-make-array-equal-to-target.md
324.wiggle-sort-ii.md
328.odd-even-linked-list.md
33.search-in-rotated-sorted-array.md
330.patching-array.md
331.verify-preorder-serialization-of-a-binary-tree.md
3336.find-the-number-of-subsequences-with-equal-gcd.md
334.increasing-triplet-subsequence.md
3347.maximum-frequency-of-an-element-after-performing-operations-ii.md
335.self-crossing.md
337.house-robber-iii.md
3377.digit-operations-to-make-two-integers-equal.md
342.power-of-four.en.md
342.power-of-four.md
343.integer-break.md
349.intersection-of-two-arrays.en.md
349.intersection-of-two-arrays.md
365.water-and-jug-problem.md
371.sum-of-two-integers.en.md
371.sum-of-two-integers.md
378.kth-smallest-element-in-a-sorted-matrix.md
380.insert-delete-getrandom-o1.md
385.mini-parser.md
39.combination-sum.md
394.decode-string.md
4.median-of-two-sorted-arrays.md
40.combination-sum-ii.md
401.binary-watch.en.md
401.binary-watch.md
416.partition-equal-subset-sum.md
42.trapping-rain-water.en.md
42.trapping-rain-water.md
424.longest-repeating-character-replacement.md
437.path-sum-iii.en.md
437.path-sum-iii.md
438.find-all-anagrams-in-a-string.md
445.add-two-numbers-ii.md
454.4-Sum-ii.en.md
454.4-sum-ii.md
455.AssignCookies.en.md
455.AssignCookies.md
456.132-pattern.md
457.circular-array-loop.md
46.permutations.md
460.lfu-cache.md
464.can-i-win.md
47.permutations-ii.md
470.implement-rand10-using-rand7.md
472.concatenated-words.md
473.matchsticks-to-square.md
474.ones-and-zeros-en.md
48.rotate-image.md
480.sliding-window-median.md
483.smallest-good-base.md
488.zuma-game.md
49.group-anagrams.md
493.reverse-pairs.md
494.target-sum.md
5.longest-palindromic-substring.md
50.pow-x-n.md
501.Find-Mode-in-Binary-Search-Tree-en.md
504.base-7.md
513.find-bottom-left-tree-value.md
516.longest-palindromic-subsequence.md
518.coin-change-2.md
52.N-Queens-II.md
525.contiguous-array.md
53.maximum-sum-subarray-cn.en.md
53.maximum-sum-subarray-cn.md
53.maximum-sum-subarray-en.md
547.friend-circles-en.md
547.number-of-provinces.md
55.jump-game.md
56.merge-intervals.md
560.subarray-sum-equals-k.en.md
560.subarray-sum-equals-k.md
5640.maximum-xor-with-an-element-from-array.md
57.insert-interval.md
575.distribute-candies.en.md
575.distribute-candies.md
5775.minimum-skips-to-arrive-at-meeting-on-time.md
5935.find-good-days-to-rob-the-bank.md
5936.detonate-the-maximum-bombs.md
5965.intervals-between-identical-elements.md
60.permutation-sequence.md
606.construct-string-from-binary-tree.md
609.find-duplicate-file-in-system.md
61.Rotate-List.md
611.valid-triangle-number.md
62.unique-paths.md
6201.maximize-number-of-subsequences-in-a-string.md
63.unique-paths-ii.md
65.valid-number.md
66.plus-one.en.md
66.plus-one.md
661.image-smoother.md
664.strange-printer.md
665.non-decreasing-array.md
673.number-of-longest-increasing-subsequence.md
679.24-game.md
686.repeated-string-match.md
710.random-pick-with-blacklist.md
714.best-time-to-buy-and-sell-stock-with-transaction-fee.md
715.range-module.md
718.maximum-length-of-repeated-subarray.md
721.accounts-merge.md
726.number-of-atoms.md
73.set-matrix-zeroes.md
735.asteroid-collision.md
75.sort-colors.md
754.reach-a-number.md
768.max-chunks-to-make-sorted-ii.md
78.subsets-en.md
78.subsets.md
785.is-graph-bipartite.md
79.word-search-en.md
79.word-search.md
790.domino-and-tromino-tiling.md
799.champagne-tower.md
80.remove-duplicates-from-sorted-array-ii.md
801.minimum-swaps-to-make-sequences-increasing.md
805.split-array-with-same-average.md
816.ambiguous-coordinates.md
820.short-encoding-of-words.md
821.shortest-distance-to-a-character.en.md
821.shortest-distance-to-a-character.md
838.push-dominoes.md
839.similar-string-groups.md
84.largest-rectangle-in-histogram.md
85.maximal-rectangle.md
86.partition-list.md
87.scramble-string.md
873.length-of-longest-fibonacci-subsequence.md
874.walking-robot-simulation.en.md
874.walking-robot-simulation.md
875.koko-eating-bananas.md
877.stone-game.md
88.merge-sorted-array.en.md
88.merge-sorted-array.md
886.possible-bipartition.md
887.super-egg-drop.md
895.maximum-frequency-stack.md
898.bitwise-ors-of-subarrays.md
90.subsets-ii-en.md
90.subsets-ii.md
900.rle-iterator.md
909.snakes-and-ladders.md
91.decode-ways.md
911.online-election.md
912.sort-an-array.md
918.maximum-sum-circular-subarray.md
92.reverse-linked-list-ii.md
932.beautiful-array.md
935.knight-dialer.md
94.binary-tree-inorder-traversal.md
947.most-stones-removed-with-same-row-or-column.md
95.unique-binary-search-trees-ii.md
959.regions-cut-by-slashes.md
96.unique-binary-search-trees.md
975.odd-even-jump.md
978.longest-turbulent-subarray.md
98.validate-binary-search-tree.md
987.vertical-order-traversal-of-a-binary-tree.md
995.minimum-number-of-k-consecutive-bit-flips.md
997.find-the-town-judge.md
Bus-Fare.md
Connected-Road-to-Destination.md
Every-Sublist-Min-Sum.md
Increasing-Digits.md
Kth-Pair-Distance.md
Largest-Equivalent-Set-of-Pairs.md
Longest-Contiguously-Strictly-Increasing-Sublist-After-Deletion.md
Longest-Matrix-Path-Length.md
Maximize-the-Number-of-Equivalent-Pairs-After-Swaps.md
Minimum-Dropping-Path-Sum.md
Minimum-Light-Radius.md
Number-Stream-to-Intervals.md
Number-of-Substrings-with-Single-Character-Difference.md
Sort-String-by-Flipping.md
Ticket-Order.md
Triple-Inversion.md
binode-lcci.en.md
binode-lcci.md
consecutive-wins.md
get-kth-magic-number-lcci.md
lcp20.meChtZ.md
lcp21.Za25hA.md
max-black-square-lcci.md
sub-sort-lcci.md
selected
templates
thinkings
.gitignore
.mdl_style.rb
.mdlrc
.nojekyll
CONTRIBUTING.en.md
CONTRIBUTING.md
Kapture 2020-08-19 at 11.37.36.gif
LICENSE.txt
README.en.md
README.md
SUMMARY.md
_config.yml
book.json
cover.jpg
donation.md
epilogue.md
introduction.md
package.json
thanksGiving.md
thanksGiving2.md
thanksGiving3.md
yarn.lock
克隆/下载
877.stone-game.md 2.86 KB
一键复制 编辑 原始数据 按行查看 历史
lucifer 提交于 5年前 . feat: 电子书

题目地址(877. 石子游戏)

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

题目描述

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 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 。
 

提示:

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

前置知识

  • 动态规划

公司

  • 阿里
  • 字节

思路

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

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

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

这里有两种情况:

  1. Lee 如果拿了第二块(偶数),那么 Alex 继续拿第三块,以此类推。。。

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

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

关键点解析

  • 可以用 DP(动态规划)

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

代码

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

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

Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/minhanghuang/azl397985856-leetcode.git
git@gitee.com:minhanghuang/azl397985856-leetcode.git
minhanghuang
azl397985856-leetcode
azl397985856-leetcode
master

搜索帮助