0%

### leetcode Shuffle an Array

Shuffle a set of numbers without duplicates.

Example:

### leetcode Ransom Note

Given > an  > arbitrary > ransom > note > string  > and  > another  > string  > containing  > letters from > all  > the  > magazines, > write  > a  > function  > that  > will  > return  > true  > if  > the  > ransom  > note  > can  > be  > constructed  > from  > the  > magazines ;  > otherwise,  > it  > will  > return  > false.

Each  > letter > in > the > magazine  > string  > can > only  > be > used  > once > in > your  > ransom > note.

Note: You may assume that both strings contain only lowercase letters.

• 528. Random Pick with Weight
• 蓄水池抽样

### leetcode Insert Delete GetRandom O(1) - Duplicates allowed

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

Note: Duplicate elements are allowed.

1. insert(val): Inserts an item val to the collection.
2. remove(val): Removes an item val from the collection if present.
3. 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.

Example:

### leetcode Insert Delete GetRandom O(1)

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

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

Example:

### leetcode Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

Note: You may assume k is always valid, 1 ≤ k ≤ n2.

• 217 Contains Duplicate
• 219 Contains Duplicate II
• 220 Contains Duplicate III

### leetcode Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

1. Two Sum
1. 3Sum
1. 3Sum Closest
1. 4Sum
1. Two Sum II - Input array is sorted

### leetcode Wiggle Subsequence

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.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast,[1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples:

Follow up: Can you do it in O(n) time?