old

Documentation

Index

• Constants
• func PredictTheWinner(nums []int) bool
• func PredictTheWinnerMax(i, j int) int
• type Node133
• type RandomizedCollection
  • func Constructor() RandomizedCollection
  • func (this *RandomizedCollection) GetRandom() int
  • func (this *RandomizedCollection) Insert(val int) bool
  • func (this *RandomizedCollection) Remove(val int) bool

Constants

const TargetMax = 24 + 1e-3

const TargetMin = 24 - 1e-3

Functions

func PredictTheWinner

func PredictTheWinner(nums []int) bool

486. 预测赢家 给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1：

输入：[1, 5, 2] 输出：False 解释：一开始，玩家1可以从1和2中进行选择。 如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。 所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。 因此，玩家 1 永远不会成为赢家，返回 False 。 示例 2：

输入：[1, 5, 233, 7] 输出：True 解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。

最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。

提示：

1 <= 给定的数组长度 <= 20. 数组里所有分数都为非负数且不会大于 10000000 。 如果最终两个玩家的分数相等，那么玩家 1 仍为赢家。

func PredictTheWinnerMax

func PredictTheWinnerMax(i, j int) int

Types

type Node133

type Node133 struct {
	Val       int
	Neighbors []*Node133
}

type RandomizedCollection

type RandomizedCollection struct {
	// contains filtered or unexported fields
}

381. O(1) 时间插入、删除和获取随机元素 - 允许重复 设计一个支持在平均 时间复杂度 O(1) 下， 执行以下操作的数据结构。

注意: 允许出现重复元素。

insert(val)：向集合中插入元素 val。 remove(val)：当 val 存在时，从集合中移除一个 val。 getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。 示例:

// 初始化一个空的集合。 RandomizedCollection collection = new RandomizedCollection();

// 向集合中插入 1 。返回 true 表示集合不包含 1 。 collection.insert(1);

// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。 collection.insert(1);

// 向集合中插入 2 ，返回 true 。集合现在包含 [1,1,2] 。 collection.insert(2);

// getRandom 应当有 2/3 的概率返回 1 ，1/3 的概率返回 2 。 collection.getRandom();

// 从集合中删除 1 ，返回 true 。集合现在包含 [1,2] 。 collection.remove(1);

// getRandom 应有相同概率返回 1 和 2 。 collection.getRandom();

func Constructor

func Constructor() RandomizedCollection

* Initialize your data structure here.

func (*RandomizedCollection) GetRandom

func (this *RandomizedCollection) GetRandom() int

* Get a random element from the collection.

func (*RandomizedCollection) Insert

func (this *RandomizedCollection) Insert(val int) bool

* Inserts a value to the collection. Returns true if the collection did not already contain the specified element.

func (*RandomizedCollection) Remove

func (this *RandomizedCollection) Remove(val int) bool

* Removes a value from the collection. Returns true if the collection contained the specified element.