LeetCode 384. Shuffle an Array

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

继续阅读
LeetCode 381. Insert Delete GetRandom O1 Duplicates allowed

LeetCode 381. Insert Delete GetRandom O1 Duplicates allowed

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

继续阅读

LeetCode 380. Insert Delete GetRandom O1

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

继续阅读
LeetCode 376. Wiggle Subsequence

LeetCode 376. Wiggle Subsequence

Description
A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

继续阅读
LeetCode 375. Guess Number Higher or Lower II

LeetCode 375. Guess Number Higher or Lower II

Description
We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round: You guess 5, I tell you that it’s higher. You pay 5. Second round: You guess 7, I tell you that it’s higher. You pay5.Secondround:Youguess7,Itellyouthatit

shigher.Youpay7.
Third round: You guess 9, I tell you that it’s lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying 5 +5+7 + 9 =9=21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

继续阅读