Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) – Push element x onto stack.
• pop() – Removes the element on top of the stack.
• top() – Get the top element.
• getMin() – Retrieve the minimum element in the stack.

Example:

1
2
3
4
5
6
7
8

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

0-1背包问题

描述：有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。

特点是：每种物品仅有一件，可以选择放或不放。

思路：对于前i件物品放入容量为j的背包中这个问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为j的背包中”，价值为f[i-1][j]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为j-v[i]的背包中”，此时能获得的最大价值就是f[i-1][j-v[i]]再加上通过放入第i件物品获得的价值w[i]。

1

dp[i][j] = max(f[i - 1][j],f[i - 1][j - w[i]] + v[i])

例子：5个物品，（重量，价值）分别为：（5，12），（4，3），（7，10），（2，3），（6，6）:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class Main {
    public static void main(String[] args) {
        int[] v = new int[]{12, 3, 10, 3, 6};
        int[] w = new int[]{5, 4, 7, 2, 6};
        int[][] dp = new int[5][16];
      	//初始化第一行
        for (int j = 0; j <= 15; j++) {
            dp[0][j] = w[0] <= j ? v[0] : 0;
        }
        for (int i = 1; i < 5; i++) {
            for (int j = 1; j <= 15; j++) {
                if (j - w[i] >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[4][15]);
    }
}

拓展：对于空间的优化？

采用滚动数组的思想进行降维处理：

将i视作数组的更新轮数

dp[i][v]是由dp[i-1][v]和dp[i-1][j-v[i]]两个子问题递推而来，能否保证在推dp[i][j]时（也即在第i次主循环中推dp[j]时）能够得到dp[i-1][j]和dp[i-1][j-v[i]]的值呢？事实上，这要求在每次主循环中我们以j=V..0的顺序推dp[j]，这样才能保证推dp[j]时dp[j-v[i]]保存的是状态dp[i-1][j-v[i]]的值。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了dp[i][j]由dp[i][j-v[i]]推知，与本题意不符。

伪代码：

1
2
3
4
5

for i=1..N:

	for j=V..0:

		dp[j]=max{dp[j],f[j-v[i]]+w[i]};

再拓展：如果要求放满怎么办？

那么在初始化时除了dp[0]为0,其它dp、[1..V]均设为负无穷，这样就可以保证最终得到的dp[N]是一种恰好装满背包的最优解。

可以这样理解：初始化的dp数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是负无穷了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

Description

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Example 1:

1
2
3

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

1
2
3
4

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

Description

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

• If there exists a solution, it is guaranteed to be unique.
• Both input arrays are non-empty and have the same length.
• Each element in the input arrays is a non-negative integer.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Input: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13

Input: 
gas  = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Description

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

Example:

1
2
3
4
5
6
7
8

Input:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

Explanation:
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.

Note:

1. The number of nodes will be between 1 and 100.
2. The undirected graph is a simple graph#Simple_graph), which means no repeated edges and no self-loops in the graph.
3. Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
4. You must return the copy of the given node as a reference to the cloned graph.

Description

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

1
2
3
4
5
6

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

Description

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example:

1
2
3
4

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

1
2
3
4

X X X X
X X X X
X X X X
X O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Description

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

1
2
3
4
5
6
7
8
9

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Description

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

1
2
3

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Description

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

1
2
3
4
5
6
7
8
9

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

1
2
3
4
5
6
7
8

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.