Solution 3: 遍历一遍,填充。T(n): O(2n) 满足Note 2 。operations: n
题解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Solution{
//Solution 2
publicvoidmoveZeroes(int[] nums){
int j = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] != 0) {
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
j++;
}
}
}
//Solution 3
publicvoidmoveZeroes(int[] nums){
if (nums == null || nums.length == 0) return;
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0){
nums[j++] = nums[i];
}
}
for (;j<nums.length;j++){
nums[j] = 0;
}
}
}
2.Stack
LeetCode 20. Valid Parentheses (Easy)
Given a string containing just the characters ‘(’,’)’,’{’,’}’,’[’ and ’]’,determine if the input string is valid. An input string is valid if:
1.Open brackets must be closed by the same type of brackets. 2.Open brackets must be closed in correct order.
题意：类似于代码中括号合法检测。 Note that an empty string is also considered valid. Example 1: Input: “()” Output: true Example 2: Input: “()[]{}” Output: true Example 3: Input: “(]” Output: false Example 4: Input: “()[)]” Output: false Example 5: Input: “{[]}” Output: true
Solution 1： 四个if (error)
Solution 2: 计数 (error) ()()()[(])
Solution 3: Stack ()
题解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution{
publicbooleanisValid(String s){
HashMap<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put('}', '{');
map.put(']', '[');
Stack stack = new Stack();
for(int i = 0;i<s.length;i++) {
if(map.containtsKey(s.charAt(i))){ // end with
Character top = stack.empty() ? "*" : statck.pop(); //remove
if(top != map.get(s.charAt(i))){
returnfalse;
}
}else{
stack.push(s.charAt(i));
}
}
return stack.empty();
}
}
3.Linked List
LeetCode 61.Rotate List (Medium)
Given a linked list , rotate the list to the right by k places , where k is non-negative
public ListNode rotateRight(ListNode head, int k){
if (head==null||head.next==null) return head;
ListNode res = new ListNode(0);
res.next = head;
ListNode fast = res;
ListNode slower = res;
int i;
for ( i = 0; fast.next !=null; i++) {
fast = fast.next;
}
for (int j = i - k%i; j >0; j--) {
slower = slower.next;
}
// swap
fast.next = res.next;
res.next = slower.next;
slower.next = null;
return res.next;
}
}
4. Tree
589.N-ary Tree Preorder Traversal (Easy)
589 N-ary Tree Preorder Traversal
Given an n-ary tree, return the preorder traversal of its nodes’ values. Note: Return its preorder traversal as: [1,3,5,6,2,4]. Recursive solution is trivial, could you do it iteratively? 题意：前序遍历n叉数，不用递归，用遍历
Solution: 遍历
LcTree_1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution{
//solution: 用 stack 存储child 节点(因为前序遍历，所以遍历用倒序h)。
//用while 轮训child 节点值并存储..
public List<Integer> preorder(Node root){
List<Integer> ret = new ArrayList<>();
if (root == null) return ret;
Stack<Node> stack = new Stack<>();
stack.add(root);
while (!stack.empty()){
root = stack.pop();
ret.add(root.val);
for (int i = root.children.size()-1; i >=0; i--) {
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Note: m and n will be at most 100.
Example 1:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
1
2
3
4
5
6
7
> Input:
> 11110
> 11010
> 11000
> 00000
> Output: 1
>
>
Example 2:
1
2
3
4
5
6
7
> Input:
> 11000
> 11000
> 00100
> 00011
> Output: 3
>
题解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
// DFS
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int m = grid.length;
int n = grid[0].length;
int islandNums = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1'){
++islandNums;
dfs(grid, i, j, m, n);
}
}
}
return islandNums;
}
public void dfs(char[][] grid, int mStart, int nStart, int m, int n) {
if (mStart < 0 || nStart < 0 || mStart >= m || nStart >= n || grid[mStart][nStart] == '0') return;
public void backTracking(List<List<Integer>> list,List<Integer> tempList, int[] nums, int start) {
list.add(new ArrayList<>(tempList));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i-1]) continue; //skip
tempList.add(nums[i]);
backTracking(list,tempList,nums,i+1);
tempList.remove(tempList.size()-1);
}
}
}
8.Greed
背包—>局部最优
LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee
Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.
You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)
Return the maximum profit you can make.
Example 1:
1
2
3
4
5
> Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
> Output: 8
> Explanation: The maximum profit can be achieved by:
> Buying at prices[0] = 1Selling at prices[3] = 8Buying at prices[4] = 4Selling at prices[5] = 9The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
>
>
Note:
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int maxProfit(int[] prices, int fee) {
if (prices == null || prices.length <=1) return 0;
