leetcode Insert Delete GetRandom O(1)
Design a data structure that supports all following operations in 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.Example:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
RandomizedSet randomSet = new RandomizedSet();
// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);
// Returns false as 2 does not exist in the set.
randomSet.remove(2);
// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);
// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();
// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);
// 2 was already in the set, so return false.
randomSet.insert(2);
// Since 1 is the only number in the set, getRandom always return 1.
randomSet.getRandom();
leetcode Kth Smallest Element in a Sorted Matrix
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:
2
3
4
5
6
7
8
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.Note: You may assume k is always valid, 1 ≤ k ≤ n2.
leetcode Contains Duplicate 整理
leetcode Combination Sum IV
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:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.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?
leetcode K sum 整理
leetcode Wiggle Subsequence
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:
2
3
4
5
6
7
8
9
10
Output: 6
The entire sequence is a wiggle sequence.
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Input: [1,2,3,4,5,6,7,8,9]
Output: 2Follow up: Can you do it in O(n) time?
LNMP站点配置指南
最近把服务器的架构从LAMP换成了LNMP（linux + nginx + mysql + php），顺便换了个服务器。下面把过程记录一下。
2017/7/17 更新 : centos 6.9 + nginx 1.12.1 + mysql 5.7 + php 7.1
leetcode Guess Number Higher or Lower II
leetcode Guess Number Higher or Lower II
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:
2
3
4
5
6
7
8
9
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 pay $7.
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 + $7 + $9 = $21.Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
Hint:
- The best strategy to play the game is to minimize the maximum loss you could possibly face. Another strategy is to minimize the expected loss. Here, we are interested in the first scenario.
- Take a small example (n = 3). What do you end up paying in the worst case?
- Check out this article if you're still stuck.
- The purely recursive implementation of minimax would be worthless for even a small n. You MUST use dynamic programming.
- As a follow-up, how would you modify your code to solve the problem of minimizing the expected loss, instead of the worst-case loss?
leetcode Guess Number Higher or Lower
leetcode Guess Number Higher or Lower
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 is higher or lower.
You call a pre-defined API
guess(int num)which returns 3 possible results (-1,1, or0):
2
3
1 : My number is higher
0 : Congrats! You got it!Example:
2
3
Return 6.
leetcode Find K Pairs with Smallest Sums
leetcode Find K Pairs with Smallest Sums
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u,v) which consists of one element from the first array and one element from the second array.
Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.
Example 1:
2
3
4
5
6
Return: [1,2],[1,4],[1,6]
The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]Example 2:
2
3
4
5
6
Return: [1,1],[1,1]
The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]Example 3:
2
3
4
5
6
Return: [1,3],[2,3]
All possible pairs are returned from the sequence:
[1,3],[2,3]