算法题通读

发表于 | 分类于 ， |

前言

用非常意识流的语言简述每题的思路,可能只有我读得懂.

分治法

二叉树

宽度优先搜索

岛屿的个数

描述：给一个01矩阵，求不同的岛屿的个数。0代表海，1代表岛，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

这本质上是图的搜索，所以用BFS。BFS都要用到一个额外的空间来记录是否被访问过，但这里可以直接修改原来的数组，如果不要求保留原来数组的值。从第一个遍历到最后一个，如果是1，那么说明这是个岛屿，然后通过BFS把这个岛屿都标志为已经访问，以后就不会重复计算岛屿的个数了。
不用分层。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class Solution {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */
    public int numIslands(boolean[][] grid) {
        // Write your code here
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int islands = 0;
        int n = grid.length;
        int m = grid[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j]) {
                    markByBfs(grid, i, j);
                    islands++;
                }
            }
        }
        return islands;
    }
    private void markByBfs(boolean[][] grid, int i, int j) {
        int n = grid.length;
        int m = grid[0].length;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i * m + j);
        while(!queue.isEmpty()) {
            int temp = queue.poll();
            int x = temp / m;
            int y = temp - temp / m * m;
            if (inBound(x - 1, y, n, m) && grid[x - 1][y]) {
                queue.add((x - 1) * m + y);
                grid[x - 1][y] = false;
            }
            if (inBound(x + 1, y, n, m) && grid[x + 1][y]) {
                queue.add((x + 1) * m + y);
                grid[x + 1][y] = false;
            }
            if (inBound(x, y - 1, n, m) && grid[x][y - 1]) {
                queue.add(x * m + y - 1);
                grid[x][y - 1] = false;
            }
            if (inBound(x, y + 1, n, m) && grid[x][y + 1]) {
                queue.add(x * m + y + 1);
                grid[x][y + 1] = false;
            }
        }
    }
    private boolean inBound(int x, int y, int n, int m) {
        return x >= 0 && y >= 0 && x < n && y < m;
    }
}

二叉树的层次遍历

描述： 给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）

因为要分层，所以要有循环要有三层：
while
for (i … size)
for (left … right)

记住要在当前点把poll出去的点记录，即当机立断原理。

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
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode temp = queue.poll();
                level.add(temp.val);
                if (temp.left != null) {
                    queue.offer(temp.left);
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                }
            }
            res.add(level);
        }
        return res;
    }
}

安排课程

统计每个课程的入度,构建一个有向图.
然后从入度为0的点进行图的遍历,把入度为0的点加进队列,表示该课程已经上了,然后下一门的入度都减一,把0的点再加进队列里.最后如果上的课没有到达预定的值,表示有死环,返回空数组.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class Solution {
    /**
     * @param numCourses a total of n courses
     * @param prerequisites a list of prerequisite pairs
     * @return the course order
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // Write your code here
        int[] result = new int[numCourses];
        
        List[] edge = new ArrayList[numCourses];
        int[] degree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            edge[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < prerequisites.length; i++) {
            //统计每门课的入度数
            degree[prerequisites[i][0]]++;
            //构造有向图
            edge[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        
        Queue queue = new LinkedList();
        for (int i = 0; i < numCourses; i++) {
            if (degree[i] == 0) {
                queue.add(i);
            }
        }
        
        int index = 0;
        
        //bfs
        while(!queue.isEmpty()) {
            int course = (int)queue.poll();
            result[index++] = course;
            for (int i = 0; i < edge[course].size(); i++) {
                int next = (int)edge[course].get(i);
                degree[next]--;
                if (degree[next] <= 0) {
                    queue.add(next);
                }
            }
        }
        
        if(index == numCourses) {
            return result;
        }
        return new int[0];
    }
}

Knight Shortest Path

通过简单的bfs就行，技巧是设置一个方向数组。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * Definition for a point.
 * public class Point {
 *     public int x, y;
 *     public Point() { x = 0; y = 0; }
 *     public Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    /**
     * @param grid a chessboard included 0 (false) and 1 (true)
     * @param source, destination a point
     * @return the shortest path
     */
    public int shortestPath(boolean[][] grid, Point source, Point destination) {
        // Write your code here
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }
        if (source.x == destination.x && source.y == destination.y) {
            return 0;
        }
        Queue<Point> queue = new LinkedList<>();
        queue.offer(source);
        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point mainPoint = queue.poll();
                ArrayList<Point> list = getNextPoint(mainPoint, grid);
                for (Point next : list) {
                    if (next.x == destination.x && next.y == destination.y) {
                        return step;
                    }
                    queue.offer(next);
                }
            }
            step++;
        }
        return -1;
    }
    private boolean inBound(int x, int y, boolean[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        return x >= 0 && x < n && y >= 0 && y < m && !grid[x][y];
    }
    private ArrayList<Point> getNextPoint(Point point, boolean[][] grid) {
        int[] directionX = {1, 1, -1, -1, 2, 2, -2, -2};
        int[] directionY = {2, -2, 2, -2, 1, -1, 1, -1};
        ArrayList<Point> list = new ArrayList<>();
        for (int i = 0; i < 8; i++) {
            int x = point.x + directionX[i];
            int y = point.y + directionY[i];
            if (inBound(x, y, grid)) {
                grid[x][y] = true;
                list.add(new Point(x, y));
            }
        }
        return list;
    }
}

Zombie in Matrix

遍历一遍数组,把僵尸放进队列,统计人数;
while循环中,首先判断people是否为0(如果是0表示没有人了),分层遍历,僵尸出栈咬人,然后把新僵尸入栈. 

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public class Solution {
    /**
     * @param grid  a 2D integer grid
     * @return an integer
     */
    public int PEOPLE = 0;
    public int ZOMBIE = 1;
    public int WALL = 2;
    
    public int zombie(int[][] grid) {
        // Write your code here
        if (grid == null) {
            return -1;
        }
        int[] directionX = {0, 0, 1, -1};
        int[] directionY = {1, -1, 0 ,0};
        int n = grid.length;
        int m = grid[0].length;
        int people = 0;
        int day = 0;
        Queue<Coordinate> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == PEOPLE) {
                    people++;
                }
                if (grid[i][j] == ZOMBIE) {
                    queue.add(new Coordinate(i, j));
                }
            }
        }
        if (people == 0) {
            return 0;
        }
        while(!queue.isEmpty()) {
            int size = queue.size();
            day++;
            for (int i = 0; i < size; i++) {
                Coordinate temp = queue.poll();
                for (int j = 0; j < 4; j++) {
                    int x = temp.x + directionX[j];
                    int y = temp.y + directionY[j];
                    if (x < 0 || x >= n || y < 0 || y >= m) {
                        continue;
                    }
                    if (grid[x][y] == PEOPLE) {
                        grid[x][y] = ZOMBIE;
                        people--;
                        queue.offer(new Coordinate(x, y));
                    }
                    if (people == 0) {
                        return day;
                    }
                }
            }
        }
        return -1;
    }
}
class Coordinate {
    int x;
    int y;
    Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

图是否是树

一棵树一定满足边的数目比节点数多一.
如果不符合的先返回false;
构造一个无向图,然后进行遍历,统计遍历到的节点数,看看是否比边数少一;

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
32
33
34
35
36
37
38
39
40
41
42
public class Solution {
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it's a valid tree, or false
     */
    public boolean validTree(int n, int[][] edges) {
        // Write your code here
        if (n == 0 || edges.length != n - 1) {
            return false;
        }
        if (n == 1) {
            return true;
        }
        ArrayList[] node = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            node[i] = new ArrayList<Integer>();
        }
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        for (int i = 0; i < edges.length; i++) {
            node[edges[i][0]].add(edges[i][1]);
            node[edges[i][1]].add(edges[i][0]);
        }
        queue.offer(0);
        visited[0] = true;
        int visitNum = 0;
        while (!queue.isEmpty()) {
            int temp = queue.poll();
            visitNum++;
            for (int i = 0; i < node[temp].size(); i++) {
                int next = (int)node[temp].get(i);
                if (visited[next]) {
                    continue;
                }
                visited[next] = true;
                queue.offer(next);
            }
        }
        return visitNum == n;
    }
}

克隆图

用hashmap记录每一点,然后bfs遍历图,克隆节点,然后从hashmap中拿出节点,然后克隆原图的的邻居。
要用一个set来记录遍历过的点.

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
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        // write your code here
        if (node == null) {
            return null;
        }
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        Queue<UndirectedGraphNode> queueCopy = new LinkedList<>();
        UndirectedGraphNode head = new UndirectedGraphNode(node.label);
        Map<Integer, UndirectedGraphNode> hash = new HashMap<>();
        queue.offer(node);
        queueCopy.offer(head);
        hash.put(head.label, head);
        while(!queue.isEmpty()) {
            UndirectedGraphNode temp = queue.poll();
            UndirectedGraphNode tempCopy = queueCopy.poll();
            for (UndirectedGraphNode next : temp.neighbors) {
                if (hash.containsKey(next.label)) {
                    tempCopy.neighbors.add(hash.get(next.label));
                    continue;
                }
                UndirectedGraphNode nei = new UndirectedGraphNode(next.label);
                tempCopy.neighbors.add(nei);
                hash.put(next.label, nei);
                queue.offer(next);
                queueCopy.offer(nei);
            }
        }
        return head;
    }
}

六度问题

做个简单的bfs就行,记住分层的时候不能用queue.size作为结束条件. edges case要注意一个源节点和目的节点相同.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Definition for Undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { 
 *         label = x;
 *         neighbors = new ArrayList<UndirectedGraphNode>(); 
 *     }
 * };
 */
public class Solution {
    /**
     * @param graph a list of Undirected graph node
     * @param s, t two Undirected graph nodes
     * @return an integer
     */
    public int sixDegrees(List<UndirectedGraphNode> graph,
                          UndirectedGraphNode s,
                          UndirectedGraphNode t) {
        // Write your code here
        if (graph == null) {
            return -1;
        }
        if (s == t) {
            return 0;
        }
        Set<UndirectedGraphNode> set = new HashSet<>();
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        set.add(s);
        queue.offer(s);
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            step++;
            for (int i = 0; i < size; i++) {
                UndirectedGraphNode node = queue.poll();
                for (UndirectedGraphNode next : node.neighbors) {
                    if (next == t) {
                        return step;
                    }
                    if (!set.contains(next)) {
                        queue.offer(next);
                        set.add(next);
                    }
                }
            }
        }
        return -1;
    }
}

非递归深搜

二叉树的前序遍历

刚开始我的思路是利用计算机递归的原理,在每个节点进栈的同时,把当前遍历到左节点还是右节点的状态也同时进栈.

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
32
33
34
35
36
37
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Preorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        if (root == null) {
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> res = new ArrayList<>();
        Stack stack = new Stack();
        stack.push(root);
        res.add(root.val);
        stack.push(0);
        while (!stack.isEmpty()) {
            Integer sign = (Integer)stack.pop();
            TreeNode curr = (TreeNode)stack.peek();
            if (curr.left != null && sign == 0) {
                stack.push(1);
                stack.push(curr.left);
                stack.push(0);
                res.add(curr.left.val);
                continue;
            }
            if (curr.right != null && sign != 2) {
                stack.push(2);
                stack.push(curr.right);
                stack.push(0);
                res.add(curr.right.val);
                continue;
            }
            stack.pop();
        }
        return res;
    }
}

当我苦苦思索怎么记录遍历的状态时,九章的答案让我有了醍醐灌顶的感觉,还有这种操作…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        List<Integer> preorder = new ArrayList<Integer>();
        
        if (root == null) {
            return preorder;
        }
        
        stack.push(root);
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            preorder.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        
        return preorder;
    }
}

二叉树的中序遍历

对于九章的答案我是很服气的..简洁巧妙…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Inorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        TreeNode curt = root;
        while (curt != null || !stack.empty()) {
            while (curt != null) {
                stack.add(curt);
                curt = curt.left;
            }
            curt = stack.pop();
            result.add(curt.val);
            curt = curt.right;
        }
        return result;
    }
}

二叉树的后序遍历

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
32
public ArrayList<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode prev = null; // previously traversed node
    TreeNode curr = root;
    if (root == null) {
        return result;
    }
    stack.push(root);
    while (!stack.empty()) {
        curr = stack.peek();
        if (prev == null || prev.left == curr || prev.right == curr) { // traverse down the tree
            if (curr.left != null) {
                stack.push(curr.left);
            } else if (curr.right != null) {
                stack.push(curr.right);
            }
        } else if (curr.left == prev) { // traverse up the tree from the left
            if (curr.right != null) {
                stack.push(curr.right);
            }
        } else { // traverse up the tree from the right
            result.add(curr.val);
            stack.pop();
        }
        prev = curr;
    }
    return result;
}

深度优先搜索

分割回文串

|a|b|c|d|e|f| ,这样分割,然后把分割的位置放到path中做dfs, 递归的参数中的index是index之前的元素都被判断过了,已经切成若干回文串,从index开始看能不能切成若干回文串. 递归结束条件是index == s.length(), 表示整个字符串都完成切割.
记住移除最后一个path元素的写法是: path.remove(path.size() - 1);

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
32
33
34
35
36
37
38
39
40
41
public class Solution {
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
    public List<List<String>> partition(String s) {
        // write your code here
        List<List<String>> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        List<Integer> path = new ArrayList<>();
        path.add(0);
        chooseOne(s, 0, res, path);
        return res;
    }
    private void chooseOne(String s, int index, List<List<String>> res, List<Integer> path) {
        if (index == s.length()) {
            List<String> subs = new ArrayList<>();
            for (int i = 1; i < path.size(); i++) {
                subs.add(s.substring(path.get(i - 1), path.get(i)));
            }
            res.add(subs);
        }
        for (int i = index + 1; i <= s.length(); i++) {
            if (isPalindrom(s, index, i)) {
                path.add(i);
                chooseOne(s, i, res, path);
                path.remove(path.size() - 1);
            }
        }
    }
    private boolean isPalindrom(String s, int start, int end) {
        for (int i = start, j = end - 1; i <= j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

数字组合 II

去重的时候,index之后的不能重复选,意思是在这一层中只能选一个,不能选重复的数字.i > index;

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
32
33
34
35
36
37
public class Solution {
    /**
     * @param num: Given the candidate numbers
     * @param target: Given the target number
     * @return: All the combinations that sum to target
     */
    public List<List<Integer>> combinationSum2(int[] num, int target) {
        // write your code here
        List<List<Integer>> res = new ArrayList<>();
        if (num == null || num.length == 0) {
            return res;
        }
        if (target <= 0) {
            return res;
        }
        Arrays.sort(num);
        List<Integer> path = new ArrayList<>();
        chooseOne(num, target, 0, res, path);
        return res;
    }
    private void chooseOne(int[] num, int target, int index, List<List<Integer>> res, List<Integer> path) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<Integer>(path));
        }
        for (int i = index; i < num.length; i++) {
            if (i > index && num[i - 1] == num[i]) {
                continue;
            }
            path.add(num[i]);
            chooseOne(num, target - num[i], i + 1, res, path);
            path.remove(path.size() - 1);
        }
    }
}

数字组合

去重 主要不是出现第一次的数字就跳过,因为之前已经有了,而且是不限的,所以要跳过.

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
32
33
34
35
36
37
public class Solution {
    /**
     * @param candidates: A list of integers
     * @param target:An integer
     * @return: A list of lists of integers
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // write your code here
        List<List<Integer>> res = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return res;
        }
        if (target <= 0) {
            return res;
        }
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        chooseOne(candidates, target, 0, res, path);
        return res;
    }
    private void chooseOne(int[] candidates, int target, int index, List<List<Integer>> res, List<Integer> path) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<Integer>(path));
        }
        for (int i = index; i < candidates.length; i++) {
            if (i > 0 && candidates[i] == candidates[i - 1]) {
                continue;
            }
            path.add(candidates[i]);
            chooseOne(candidates, target - candidates[i], i, res, path);
            path.remove(path.size() - 1);
        }
    }
}

带重复元素的子集

空集是任何集合的子集,所以当集合为空时也要加入.
去重也是i>index,每层选一个不同的加入.

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 {
    /**
     * @param nums: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] nums) {
        // write your code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (nums == null) {
            return res;
        }
        Arrays.sort(nums);
        ArrayList<Integer> path = new ArrayList<>();
        chooseOne(nums, 0, res, path);
        return res;
    }
    private void chooseOne(int[] nums,
                           int index,
                           ArrayList<ArrayList<Integer>> res,
                           ArrayList<Integer> path) {
        res.add(new ArrayList<Integer>(path));
        for (int i = index; i < nums.length; i++) {
            if (i > index && nums[i] == nums[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            chooseOne(nums, i + 1, res, path);
            path.remove(path.size() - 1);
        }
    }
}

带重复元素的排列

如果是不带重复元素的排列,那只要在每一层中选一个之前没选过的放进去(path.contians(nums[i])).
如果是带重复元素的排列,用老方法的话,会造成无法把重复元素加进path中.所以要用isNA(不用重复初始化)数组表示哪个位置的元素已经加入了,但是还有一个问题就是用位置不能区分元素是否一样,(在同一层中不能选重复的元素),那就只能sort.那么判断这一层中有没有把和当前数值相同的元素加进path放进递归了,就需要和前面一个元素比较,如果相同,而且可用(或者不可用,这样写是倒过来加,比如[2’, 2’’, 2’’’],结果是[2’’’,2’’,2’]),说明同一种元素已经放过进path里面了,跳过.
所以需要 排序和前置检查, 记录数组.

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
32
33
34
35
36
class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        // Write your code here
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null) {
            return res;
        }
        Arrays.sort(nums);
        List<Integer> path = new ArrayList<>();
        boolean[] isNA = new boolean[nums.length];
        chooseOne(nums, 0, res, path, isNA);
        return res;
    }
    private void chooseOne(int[] nums, int index, List<List<Integer>> res, List<Integer> path, boolean[] isNA) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<Integer>(path));
        }
        for (int i = 0; i < nums.length; i++) {
            if (isNA[i]) {
                continue;
            }
            if (i > 0 && nums[i] == nums[i - 1] && isNA[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            isNA[i] = true;
            chooseOne(nums, i + 1, res, path, isNA);
            isNA[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

全排列

每层从0开始选一个之前没选的即可.

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
class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    public List<List<Integer>> permute(int[] nums) {
        // write your code here
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null) {
            return res;
        }
        List<Integer> path = new ArrayList<>();
        chooseOne(nums, res, path);
        return res;
    }
    private void chooseOne(int[] nums, List<List<Integer>> res, List<Integer> path) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<Integer>(path));
        }
        for (int i = 0; i < nums.length; i++) {
            if (path.contains(nums[i])) {
                continue;
            }
            path.add(nums[i]);
            chooseOne(nums, res, path);
            path.remove(path.size() - 1);
        }
    }
}

Word Break II

待续,为什么九章用hashmap做就能过

1
2
3
4
5
6
7
8
9
public class Solution {
    /**
     * @param s a string
     * @param wordDict a set of words
     */
    public List<String> wordBreak(String s, Set<String> wordDict) {
        
    }
}

单词接龙 II

用bfs构建一个图，从start开始，到end结束，同时要记录每个点到start的距离。
找路径用dfs，从end开始，到start结束。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class Solution {
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return a list of lists of string
      */
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        // write your code here
        HashMap<String, List<String>> node = new HashMap<>();
        HashMap<String, Integer> distance = new HashMap<>();
        List<List<String>> result = new ArrayList<>();
        List<String> path = new ArrayList<String>();
        initByBfs(start, end, dict, node, distance);
        countDistance(start, end, distance, node, path, result);
        return result;
    }
    private void initByBfs(String start,
                      String end,
                      Set<String> dict,
                      HashMap<String, List<String>> node,
                      HashMap<String, Integer> distance) {
        Queue<String> queue = new LinkedList<String>();
        queue.offer(start);
        distance.put(start, 0);
        dict.add(start);
        dict.add(end);
        int dis = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            dis++;
            for (int num = 0; num < size; num++) {
                String s = queue.poll();
                node.put(s, new ArrayList<String>());
                for (int i = 0; i < s.length(); i++) {
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        String next = s.substring(0, i) + ch + s.substring(i + 1);
                        if (dict.contains(next)) {
                            node.get(s).add(next);
                            if (!distance.containsKey(next)) {
                                queue.offer(next);
                                distance.put(next, dis);
                            }
                        }
                    }
                }
            }
        }
    }
    private void countDistance(String start,
                               String end,
                               HashMap<String, Integer> distance,
                               HashMap<String, List<String>> node,
                               List<String> path,
                               List<List<String>> result) {
        path.add(end);
        if (end.equals(start)) {
            Collections.reverse(path);
            result.add(new ArrayList<String>(path));
            Collections.reverse(path);
        } else {
            for (String next : node.get(end)) {
                if (distance.containsKey(next)
                    && distance.get(next) == distance.get(end) - 1) {
                    countDistance(start, next, distance, node, path, result);
                }
            }
        }
        path.remove(path.size() - 1);
    }
}

数组与链表

滑动窗口内数的和

要注意k == nums.length == 0 的情况.
res[]的大小是nums.length - k + 1
res[0] 存初始的值
res[i - k + 1] = res[i - k] - nums[i - k] + nums[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    /**
     * @param nums a list of integers.
     * @return the sum of the element inside the window at each moving.
     */
    public int[] winSum(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k < 0 || nums.length < k) {
            return new int[0];
        }
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < k; i++) {
            res[0] += nums[i];
        }
        for (int i = k; i < nums.length; i++) {
            res[i - k + 1] = res[i - k] - nums[i - k] + nums[i];
        }
        return res;
    }
}

Insert into a Cyclic Sorted List

有四种情况:

  1. pre <= x <= curr
  2. x比所有元素都大,那么应该放在最大最小交界处(pre > curr)
  3. 同上, x比所有元素都小
  4. 如果把链表都遍历完了还没有完成插入,那么就应该放到最后.(当链表只有一个元素或者链表中的数值大小都一样)
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
32
33
34
35
36
37
38
39
40
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param node a list node in the list
     * @param x an integer
     * @return the inserted new list node
     */
    public ListNode insert(ListNode node, int x) {
        // Write your code here
        if (node == null) {
            ListNode newNode =  new ListNode(x);
            newNode.next = newNode;
            return newNode;
        }
        ListNode pre = node;
        ListNode head = pre;
        while (true) {
            node = node.next;
            if (x <= node.val && x >= pre.val
                || pre.val > node.val && (x >= pre.val || x <= node.val)
                || head == node) {
                ListNode newNode = new ListNode(x);
                newNode.next = node;
                pre.next = newNode;
                return pre;
            }
            pre = pre.next;
        }
    }
}

合并两个排序链表

while 中的条件是 l1 != null && l2 != null (是&& )

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param ListNode l1 is the head of the linked list
     * @param ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // write your code here
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head = new ListNode(0);
        ListNode pre = head;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                pre.next = l2;
                pre = pre.next;
                l2 = l2.next;
            } else {
                pre.next = l1;
                pre = pre.next;
                l1 = l1.next;
            }
        }
        if (l1 != null) {
            pre.next = l1;
        }
        if (l2 != null) {
            pre.next = l2;
        }
        return head.next;
    }
}

子数组之和

把每个prefixSum都记录下来,map先添加(0, -1).
之后看map有没有相同的prefixSum,如果有就可以返回了.

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
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number 
     *          and the index of the last number
     */
    public ArrayList<Integer> subarraySum(int[] nums) {
        // write your code here
        ArrayList<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        Map<Integer, Integer> map = new HashMap<>();
        int prefixSum = 0;
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            if (map.containsKey(prefixSum)) {
                res.add(map.get(prefixSum) + 1);
                res.add(i);
                return res;
            }
            map.put(prefixSum, i);
        }
        return res;
    }
}

最大子数组

minPre = 0;
这样最小前缀不会出现正数.

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
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int prefixSum = 0;
        int minPre = 0;
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            if (prefixSum - minPre > max) {
                max = prefixSum - minPre;
            }
            if (prefixSum < minPre) {
                minPre = prefixSum;
            }
        }
        return max;
    }
}

最接近零的子数组和

把所有的前缀排序,找出最接近的.开始的下标要加一.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number 
     *          and the index of the last number
     */
    public int[] subarraySumClosest(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int prefixSum = 0;
        PreAndIndex[] p = new PreAndIndex[nums.length + 1];
        p[0] = new PreAndIndex(0, -1);
        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];
            p[i + 1] = new PreAndIndex(prefixSum, i);
        }
        Arrays.sort(p, new Comparator<PreAndIndex>() {
            public int compare(PreAndIndex o1, PreAndIndex o2) {
                return o1.prefixSum - o2.prefixSum;
            }
        });
        int[] res = new int[2];
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < p.length; i++) {
            int diff = Math.abs(p[i].prefixSum - p[i-1].prefixSum);
            if (diff < min) {
                min = diff;
                res[0] = p[i].index > p[i - 1].index ? p[i - 1].index + 1 : p[i].index + 1;
                res[1] = p[i].index > p[i - 1].index ? p[i].index : p[i - 1].index;
            }
        }
        return res;
    }
}
class PreAndIndex {
    int prefixSum;
    int index;
    public PreAndIndex(int prefixSum, int index) {
        this.prefixSum = prefixSum;
        this.index = index;
    }
}

复制带随机指针的链表

先复制节点
1->1’->2->2’->null
在从头开始复制random
最后把原始链和复制链拆开.
要注意null的问题,当random==null时,cp的random不再是random.next;
同理,拆链的时候,拆到最后,cp节点不用再操作.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// version 2
public class Solution {
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        // write your code here
        if (head == null) {
            return head;
        }
        RandomListNode p = head;
        while (p != null) {
            RandomListNode insert = new RandomListNode(p.label);
            insert.next = p.next;
            p.next = insert;
            p = p.next.next;
        }
        p = head;
        while (p != null) {
            if (p.random == null) {
                p.next.random = null;
            } else {
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        p = head;
        RandomListNode cp = p.next;
        RandomListNode cpHead = cp;
        while (p != null) {
            p.next = p.next.next;
            p = p.next;
            if (p != null) {
                cp.next = p.next;
                cp = cp.next;
            }
        }
        return cpHead;
    }
}
/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
// public class Solution {
//     /**
//      * @param head: The head of linked list with a random pointer.
//      * @return: A new head of a deep copy of the list.
//      */
//     public RandomListNode copyRandomList(RandomListNode head) {
//         // write your code here
//         if (head == null) {
//             return null;
//         }
//         Map<Integer, RandomListNode> hash = new HashMap<>();
//         RandomListNode ans = head;
//         while (head != null) {
//             if (!hash.containsKey(head.label)) {
//                 RandomListNode node = new RandomListNode(head.label);
//                 hash.put(node.label, node);
//             }
//             if (head.random !=null && !hash.containsKey(head.random.label)) {
//                 RandomListNode randomCopy = new RandomListNode(head.random.label);
//                 hash.put(randomCopy.label, randomCopy);
//             }
//             if (head.next != null && !hash.containsKey(head.next.label)) {
//                 RandomListNode nextCopy = new RandomListNode(head.next.label);
//                 hash.put(nextCopy.label, nextCopy);
//             }
//             if (head.random != null) {
//                 hash.get(head.label).random = hash.get(head.random.label);
//             }
//             if (head.next != null) {
//                 hash.get(head.label).next = hash.get(head.next.label);
//             }
//             head = head.next;
//         }
//         return hash.get(ans.label);
//     }
// }

带环链表

设置一个fast指针,一个slow指针,fast每次走两步,slow每次一步.
初始的时候,slow = head, fast = head.next;
while(fast != null && fast.next != null)
while里先判断fast == slow

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
32
33
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    public boolean hasCycle(ListNode head) {  
        // write your code here
        if (head == null) {
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            if (fast == slow) {
                return true;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return false;
    }
}

链表排序

首先要找到一个链的中点.
1->null,中点是null,findMid返回1;
1->2->null,中点是2,findMid返回1;
sortList(null || 1->null) 返回head(如果1->null不直接返回的话会无穷递归),这函数的作用是二分拆开,最后合并返回.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: You should return the head of the sorted linked list,
                    using constant space complexity.
     */
    public ListNode sortList(ListNode head) {  
        // write your code here
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tmp = findMid(head);
        ListNode mid = tmp.next;
        tmp.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(mid);
        return merge(left, right);
    }
    private ListNode findMid(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    private ListNode merge(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head = new ListNode(0);
        ListNode p = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if (l1 != null) {
            p.next = l1;
        }
        if (l2 != null) {
            p.next = l2;
        }
        return head.next;
    }
}

两个排序数组的中位数

  1. i 或者 j 超出范围, 直接选另外一个数组的
  2. k <= 1, 直接比较A[i] 和 B[j],返回小的
  3. i + len - 1 或者 j + len - 1 超出范围,扔掉比较长的数组的len个
  4. 两者比较,扔掉小的
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
32
33
34
35
36
37
38
39
class Solution {
    /**
     * @param A: An integer array.
     * @param B: An integer array.
     * @return: a double whose format is *.5 or *.0
     */
    public double findMedianSortedArrays(int[] A, int[] B) {
        // write your code here
        int len = A.length + B.length;
        int mid = findKth(A, B, 0, 0, len / 2 + 1);
        if (len % 2 == 0) {
            mid += findKth(A, B, 0, 0, len / 2);
            return mid / 2.0;
        }
        return (double)mid;
    }
    private int findKth(int[] A, int[] B, int i, int j, int k) {
        if (i >= A.length) {
            return B[j + k - 1];
        }
        if (j >= B.length) {
            return A[i + k - 1];
        }
        if (k <= 1) {
            return A[i] > B[j] ? B[j] : A[i];
        }
        int len = k / 2 - 1;
        if (i + len >= A.length) {
            j += len + 1;
        } else if (j + len >= B.length) {
            i += len + 1;
        } else if (A[i + len] > B[j + len]) {
            j += len + 1;
        } else {
            i += len + 1;
        }
        return findKth(A, B, i, j, k - k / 2);
    }
}

K组翻转链表

如果head为空或者head.next为空就可以直接返回了.
先统计链表的长度,如果不够k个就返回head.
翻转k个节点要用到4个指针,分别是pre, p, next, 还有head
head最后链接下一个翻转返回的节点.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param head a ListNode
     * @param k an integer
     * @return a ListNode
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // Write your code here
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = head;
        int num = 0;
        while (p != null && num < k) {
            num++;
            p = p.next;
        }
        if (num < k) {
            return head;
        }
        
        p = head.next;
        
        ListNode pre = head;
        ListNode next = head.next;
        
        while (next != null && num > 1) {
            next = next.next;
            p.next = pre;
            pre = p;
            p = next;
            num--;
        }
        head.next = reverseKGroup(next, k);
        return pre;
    }
}

双指针

Two Sum - Data structure design

要注意value - i == i的情况.

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
32
33
34
35
public class TwoSum {
    Map<Integer, Integer> nums;
    // Add the number to an internal data structure.
    public TwoSum() {
        nums = new HashMap<>();
    }
    public void add(int number) {
        // Write your code here
        if (!nums.containsKey(number)) {
            nums.put(number, 1);
        } else {
            nums.put(number, nums.get(number) + 1);
        }
    }
    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        // Write your code here
        for (Integer i : nums.keySet()) {
            if (i == value - i && nums.get(i) > 1) {
                return true;
            }
            if (i != value - i && nums.containsKey(value - i)){
                return true;
            }
        }
        return false;
    }
}
// Your TwoSum object will be instantiated and called as such:
// TwoSum twoSum = new TwoSum();
// twoSum.add(number);
// twoSum.find(value);

去除重复元素

  1. 可以用Set来记录
  2. 先排序, 然后insert初始为1,因为第一点肯定不用插入,然后比较后一点和前一点,如果不同(意味着第一次出现)就插入insert处.last之前都是不重复的
  3. 先排序, 然后insert初始为1,insert记录着上一个不重复数字的值.
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// public class Solution {
//     /**
//      * @param nums an array of integers
//      * @return the number of unique integers
//      */
//     public int deduplication(int[] nums) {
//         // Write your code here
//         if (nums == null || nums.length == 0) {
//             return 0;
//         }
//         int insertPoint = 0;
//         Set<Integer> hash = new HashSet<>();
//         for (int i = 0; i < nums.length; i++) {
//             if (!hash.contains(nums[i])) {
//                 hash.add(nums[i]);
//                 nums[insertPoint++] = nums[i];
//             }
//         }
//         return insertPoint;
//     }
// }
public class Solution {
    /**
     * @param nums an array of integers
     * @return the number of unique integers
     */
    public int deduplication(int[] nums) {
        // Write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int insertPoint = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != nums[insertPoint - 1]) {
                nums[insertPoint++] = nums[i];
            }
        }
        return insertPoint;
    }
}
public class Solution {
    /**
     * @param nums an array of integers
     * @return the number of unique integers
     */
    public int deduplication(int[] nums) {
        // Write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int last = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[last++] = nums[i];
            }
        }
        return last;
    }
}

Two Sum - Less than or equal to target

如果nums[start]+nums[end]<=target,那么res += end - start, start这一点统计完了,start++;
如果nums[start]+nums[end]>target,那么end要往回走,直到满足条件.

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
public class Solution {
    /**
     * @param nums an array of integer
     * @param target an integer
     * @return an integer
     */
    public int twoSum5(int[] nums, int target) {
        // Write your code here
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        int start = 0; 
        int end = nums.length - 1;
        Arrays.sort(nums);
        int res = 0;
        while (start < end) {
            if (nums[start] + nums[end] <= target) {
                res += end - start;
                start++;
            } else {
                end--;
            }
        }
        return res;
    }
}

Two Sum - Input array is sorted

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
public class Solution {
    /*
     * @param nums an array of Integer
     * @param target = nums[index1] + nums[index2]
     * @return [index1 + 1, index2 + 1] (index1 < index2)
     */
    public int[] twoSum(int[] nums, int target) {
        // write your code here
        if (nums == null || nums.length <= 1) {
            return new int[0];
        }
        int[] res = new int[2];
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] < target) {
                left++;
            } else if (nums[left] + nums[right] > target) {
                right--;
            } else {
                res[0] = left + 1;
                res[1] = right + 1;
                return res;
            }
        }
        return res;
    }
}

Two Sum - Unique pairs

记得要去重,要把end移到和之前数值不一样的点.

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
32
33
34
35
public class Solution {
    /**
     * @param nums an array of integer
     * @param target an integer
     * @return an integer
     */
    public int twoSum6(int[] nums, int target) {
        // Write your code here
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        Arrays.sort(nums);
        int res = 0;
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] < target) {
                left++;
            } else if (nums[left] + nums[right] > target) {
                right--;
            } else {
                res++;
                int tmp = nums[right];
                while (left < right) {
                    if (nums[right] != tmp) {
                        break;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

两数和的最接近值

在指针移动的过程中更新diff就行,把diff初始化成最大整型即可.

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
public class Solution {
    /**
     * @param nums an integer array
     * @param target an integer
     * @return the difference between the sum and the target
     */
    public int twoSumClosest(int[] nums, int target) {
        // Write your code here
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        Arrays.sort(nums);
        int start = 0;
        int end = nums.length - 1;
        int diff = Integer.MAX_VALUE;
        while (start < end) {
            int sum = nums[start] + nums[end];
            if (sum < target) {
                diff = Math.min(diff, Math.abs(target - sum));
                start++;
            } else if (sum > target) {
                diff = Math.min(diff, Math.abs(target - sum));
                end--;
            } else {
                return 0;
            }
        }
        return diff;
    }
}

颜色分类

判断条件是i <= pr,因为不知pr是什么内容,所以要判断一下.
nums[i]==0,left++,i++;

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
32
class Solution {
    /**
     * @param nums: A list of integer which is 0, 1 or 2 
     * @return: nothing
     */
    public void sortColors(int[] nums) {
        // write your code here
        if (nums == null || nums.length < 1) {
            return;
        }
        int pl = 0;
        int pr = nums.length - 1;
        int i = 0;
        while (i <= pr) {
            if (nums[i] == 2) {
                swap(nums, i, pr);
                pr--;
            } else if (nums[i] == 0) {
                swap(nums, i, pl);
                pl++;
                i++; // nums[pl] must be 1 when pl != i;
            } else {
                i++;
            }
        }
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

排颜色 II

相当于做一次快排,当快排中的while结束的时候,end和start相差1。end最后停留在<=mid的地方,或者越界; start最后停留在>mid的地方,或者越界

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
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */
    public void sortColors2(int[] colors, int k) {
        // write your code here
        if (colors == null || colors.length <= 0) {
            return;
        }
        partition(colors, k, 1, 0, colors.length - 1);
    }
    private void partition(int[] colors, int top, int down, int start, int end) {
        if (start >= end) {
            return;
        }
        if (top == down) {
            return;
        }
        int left = start;
        int right = end;
        int mid = down + (top - down) / 2;
        while (start <= end) {
            while (start <= end && colors[start] <= mid) {
                start++;
            }
            while (start <= end && colors[end] > mid) {
                end--;
            }
            if (start < end) {
                swap(colors, start, end);
            }
        }
        partition(colors, top, mid + 1, start, right);
        partition(colors, mid, down, left, end);
    }
    private void swap(int[] colors, int i, int j) {
        int temp = colors[i];
        colors[i] = colors[j];
        colors[j] = temp;
    }
}

三数之和

最左边的指针位置是i + 2 < numbers.length
记得排序和去重

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
32
33
34
35
36
37
38
39
40
public class Solution {
    /**
     * @param numbers : Give an array numbers of n integer
     * @return : Find all unique triplets in the array which gives the sum of zero.
     */
    public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {
        // write your code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (numbers == null || numbers.length < 3) {
            return res;
        }
        Arrays.sort(numbers);
        for (int i = 0; i + 2 < numbers.length; i++) {
            if (i > 0 && numbers[i] == numbers[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = numbers.length - 1;
            while (left < right) {
                int sum = numbers[i] + numbers[left] + numbers[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    ArrayList<Integer> set = new ArrayList<Integer>();
                    set.add(numbers[i]);
                    set.add(numbers[left]);
                    set.add(numbers[right]);
                    res.add(set);
                    int tmp = numbers[right];
                    while (left < right && numbers[right] == tmp) {
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

数组划分

当left==right时,若nums[left]=k,若nums[left]>=k,right–,nums[right]<k,所以返回left;

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
public class Solution {
	/** 
     *@param nums: The integer array you should partition
     *@param k: As description
     *return: The index after partition
     */
    public int partitionArray(int[] nums, int k) {
	    //write your code here
	    if (nums == null || nums.length <= 1) {
	        return 0;
	    }
	    int left = 0;
	    int right = nums.length - 1;
	    while (left <= right) {
	        while (left <= right && nums[left] < k) {
	            left++;
	        }
	        while (left <= right && nums[right] >= k) {
	            right--;
	        }
	        if (left < right) {
	            int tmp = nums[left];
    	        nums[left] = nums[right];
    	        nums[right] = tmp;
	        }
	    }
	    return left;
    }
}

哈希函数与堆

哈希函数

设字符串为abc，那么hash值的计算过程如下：
hash = (hash 31 + ‘a’) % mod
hash = 031 + ‘a’
hash = ‘a’31 + ‘b’
hash = ‘a’31^2 + ‘b’*31 + ‘c’

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    /**
     * @param key: A String you should hash
     * @param HASH_SIZE: An integer
     * @return an integer
     */
    public int hashCode(char[] key,int HASH_SIZE) {
        // write your code here
        if (key == null || key.length == 0) {
            return 0;
        }
        long hashcode = 0;
        for (int i = 0; i < key.length; i++) {
            hashcode = (hashcode * 33 + key[i]) % HASH_SIZE;
        }
        return (int)hashcode;
    }
}

优秀成绩

用Arrays排序来解决,按照学号优先再按成绩又高到低排.

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
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for a Record
 * class Record {
 *     public int id, score;
 *     public Record(int id, int score){
 *         this.id = id;
 *         this.score = score;
 *     }
 * }
 */
public class Solution {
    /**
     * @param results a list of <student_id, score>
     * @return find the average of 5 highest scores for each person
     * Map<Integer, Double> (student_id, average_score)
     */
    public Map<Integer, Double> highFive(Record[] results) {
        // Write your code here
        Map<Integer, Double> map = new HashMap<>();
        Arrays.sort(results, new Comparator<Record>() {
           public int compare(Record o1, Record o2) {
               if (o1.id == o2.id) {
                   return o2.score - o1.score;
               }
               return o1.id - o2.id;
           }
        });
        for (int i = 0; i < results.length; i++) {
            if (map.containsKey(results[i].id)) {
                continue;
            }
            int sc = 0;
            for (int j = i; j < i + 5 && j < results.length; j++) {
                sc += results[j].score;
            }
            map.put(results[i].id, sc / 5.0);
            i += 4;
        }
        return map;
    }
}

K个最近的点

用优先队列(大根堆)做,把所有的point加进优先队列中,队列大小超过k之后移除队列的头.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    /**
     * @param points a list of points
     * @param origin a point
     * @param k an integer
     * @return the k closest points
     */
    private Point globalOrigin = null;
    public Point[] kClosest(Point[] points, Point origin, int k) {
        // Write your code here
        if (points == null || points.length == 0 || points.length < k) {
            return new Point[0];
        }
        globalOrigin = origin;
        PriorityQueue<Point> pq = new PriorityQueue<>(k, new Comparator<Point>() {
            public int compare(Point p2, Point p1) {
                int diff1 = getDiff(p1, globalOrigin);
                int diff2 = getDiff(p2, globalOrigin);
                if (diff1 == diff2) {
                    return p1.x == p2.x ? p1.y - p2.y : p1.x - p2.x;
                }
                return diff1 - diff2;
            }
        });
        for (Point p : points) {
            pq.offer(p);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        Point[] res = new Point[k];
        while (!pq.isEmpty()) {
            res[pq.size() - 1] = pq.poll();
        }
        return res;
    }
    private int getDiff(Point p1, Point p2) {
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }
}

Kth Largest Element II

优先队列(小根堆)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    /**
     * @param nums an integer unsorted array
     * @param k an integer from 1 to n
     * @return the kth largest element
     */
    public int kthLargestElement2(int[] nums, int k) {
        // Write your code here
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);
        for (int i = 0; i < nums.length; i++) {
            pq.offer(nums[i]);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        return pq.peek();
    }
};

前K大数

优先队列小根堆

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
class Solution {
    /*
     * @param nums an integer array
     * @param k an integer
     * @return the top k largest numbers in array
     */
    public int[] topk(int[] nums, int k) {
        // Write your code here
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);
        for (int i = 0; i < nums.length; i++) {
            pq.offer(nums[i]);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        int[] res = new int[pq.size()];
        while (!pq.isEmpty()) {
            res[pq.size() - 1] = pq.poll();
        }
        return res;
    }
}

重哈希

把原来的数组中的链表按新的键值加入到新的hash表中.
先把链表的头结点移到新的hash表中,如果该位置是null的话,可以直接加入,否则找到该位置的链表的尾节点,尾节点链接到链表,这时候头结点顺利移动到新的hash表中,再把头结点的下一个节点移到新Hash表,直到把所有节点移完.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param hashTable: A list of The first node of linked list
     * @return: A list of The first node of linked list which have twice size
     */    
    public ListNode[] rehashing(ListNode[] hashTable) {
        // write your code here
        if (hashTable == null) {
            return hashTable;
        }
        int capacity = hashTable.length * 2;
        ListNode[] newHash = new ListNode[capacity];
        for (int i = 0; i < capacity / 2; i++) {
            if (hashTable[i] == null) {
                continue;
            }
            ListNode p = hashTable[i];
            hashTable[i] = null;
            while (p != null) {
                int key = (p.val % capacity + capacity) % capacity;
                if (newHash[key] != null) {
                    ListNode head = newHash[key];
                    while (head.next != null) {
                        head = head.next;
                    }
                    head.next = p;
                    p = p.next;
                    head.next.next = null;
                } else {
                    newHash[key] = p;
                    p = p.next;
                    newHash[key].next = null;
                }
            }
        }
        return newHash;
    }
};

合并k个排序链表

这有很多方法.
假如有n个节点,m条链表

  1. 优先队列: 把每个链表中的头结点放到pq中,然后在队列中选一个最小的头结点,把这个头结点所在的链表poll出来,然后移除头节点后(如果不是null)再放进队列中.
    时间复杂度是o(nlogm)(每个节点进队需要logm时间),空间复杂度是o(m);

  2. merge two by two
    时间复杂度是(nlogm)

  3. Divide & Conquer

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
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    public ListNode mergeKLists(List<ListNode> list) {  
        // write your code here
        if (list == null || list.size() == 0) {
            return null;
        }
        ListNode head = new ListNode(0);
        ListNode p = head;
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(list.size(), new Comparator<ListNode>() {
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) != null) {
                pq.offer(list.get(i));    
            }
        }
        while (!pq.isEmpty()) {
            p.next = pq.poll();
            p = p.next;
            if (p.next != null) {
                pq.offer(p.next);
            }
        }
        p.next = null;
        return head.next;
    }
}

丑数 II

每个数都要分别乘以2,3,5.
只有前面的都已经乘以2了,后面的数才可以乘;同理,3,5;
用p2,p3,p5来标识最近哪一个数最后乘了2,3或者5.
如果p2的位置乘以2等于列表中最大的数,说明p2这个位置中的数不必乘以2了,p2++;同理p3,p5;
知道得到k个丑数,那么可以返回了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    /**
     * @param n an integer
     * @return the nth prime number as description.
     */
    public int nthUglyNumber(int n) {
        if (n <= 1) {
            return 1;
        }
        List<Integer> uglys = new ArrayList<>();
        uglys.add(1);
        int p2 = 0, p3 = 0, p5 = 0;
        while (uglys.size() < n) {
            int lastNum = uglys.get(uglys.size() - 1);
            if (uglys.get(p2) * 2 == lastNum) p2++;
            if (uglys.get(p3) * 3 == lastNum) p3++;
            if (uglys.get(p5) * 5 == lastNum) p5++;
            uglys.add(Math.min(Math.min(uglys.get(p2) * 2, uglys.get(p3) * 3), uglys.get(p5) * 5));
        }
        return uglys.get(uglys.size() - 1);
    }
};

strStr II

用hashcode计算
几个公式:
power=power31^m%mod
targetCode=(targetCode31+target.charAt(i))%mod;做m次
hash=(hash31+source.charAt(i))%mod; 先做m次.
判断两个code是否相等。
当i>=m的时候,hash要减去i-m+1的值乘以power%mod。为了不得到负数,hash = (hash - (source.charAt(i - m) power) % mod + mod) % mod;

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
32
33
34
35
36
37
38
public class Solution {
    /**
     * @param source a source string
     * @param target a target string
     * @return an integer as index
     */
    public int strStr2(String source, String target) {
        // Write your code here
        if (source == null || target == null || target.length() > source.length()) {
            return -1;
        }
        if (target.length() == 0) {
            return 0;
        }
        long power = 1;
        long hashcode = 0;
        long hash = 0;
        long mod = Integer.MAX_VALUE / 31;
        int m = target.length();
        for (int i = 0; i < m; i++) {
            power = (power * 31) % mod;
            hashcode = (hashcode * 31 + target.charAt(i)) % mod;
        }
        for (int i = 0; i < source.length(); i++) {
            hash = (hash * 31 + source.charAt(i)) % mod;
            if (i < m - 1) {
                continue;
            }
            if (i >= m) {
                hash = (hash - (source.charAt(i - m) * power) % mod + mod) % mod;
            }
            if (hash == hashcode && source.substring(i - m + 1, i + 1).equals(target)) {
                return i - m + 1;
            }
        }
        return -1;
    }
}

LRU缓存策略

链表用双向链表实现,为了在O(1)时间内删除节点.
用hashMap记录每个节点,可以在set数据的时候用O(1)的时间找到节点.
设置一个head节点,一个tail节点.head的作用是达到容量时把队头移除;tail的作用是把最新的数据放到对尾;

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class Solution {
    private int capacity;
    private HashMap<Integer, Node> hash = new HashMap<>();
    private Node head = new Node(-1, -1), tail = new Node(-1, -1);
    private class Node {
        int key;
        int value;
        Node next;
        Node prev;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
            next = null;
            prev = null;
        }
    }
    // @param capacity, an integer
    public Solution(int capacity) {
        // write your code here
        this.capacity = capacity;
        tail.prev = head;
        head.next = tail;
    }
    // @return an integer
    public int get(int key) {
        // write your code here
        if (!hash.containsKey(key)) {
            return -1;
        }
        
        Node lastNode = hash.get(key);
        lastNode.prev.next = lastNode.next;
        lastNode.next.prev = lastNode.prev;
        
        moveToTail(lastNode);
        
        return hash.get(key).value;
    }
    // @param key, an integer
    // @param value, an integer
    // @return nothing
    public void set(int key, int value) {
        // write your code here
        if (get(key) != -1) {
            hash.get(key).value = value;
            return;
        }
        if (hash.size() == capacity) {
            hash.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }
        Node lastNode = new Node(key, value);
        moveToTail(lastNode);
        hash.put(key, lastNode);
    }
    private void moveToTail(Node curr) {
        curr.next = tail;
        curr.prev = tail.prev;
        tail.prev.next = curr;
        tail.prev = curr;
    }
}

动态规划

不同的路径

只需要o(m) 或者o(n)的空间
if (i == 0 || j == 0) path[j] = 1; //不要写成0了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    public int uniquePaths(int m, int n) {
        // write your code here 
        if (m == 0 || n == 0) {
            return 1;
        }
        int[] path = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    path[j] = 1;
                } else {
                    path[j] = path[j - 1] + path[j];
                }
            }
        }
        return path[n - 1];
    }
}

不同的路径 II

先初始化第一行第一列,遇到等于一的情况,就设置一个标志,不再设为1.
path[j] += path[j - 1]

要注意blocki/blockj不要弄反了.

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
32
33
34
35
36
37
public class Solution {
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // write your code here
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
            return 0;
        }
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        boolean blocki = false;
        boolean blockj = false;
        int[] path = new int[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (obstacleGrid[0][j] == 1) {
                    blocki = true;
                }
                if (obstacleGrid[i][0] == 1) {
                    blockj = true;
                }
                if (i == 0 && !blocki || j == 0 && !blockj) {
                    path[j] = 1;
                } else if (i == 0 && blocki || j == 0 && blockj) {
                    path[j] = 0;
                } else if (obstacleGrid[i][j] == 1) {
                    path[j] = 0;
                } else {
                    path[j] += path[j - 1];
                }
            }
        }
        return path[m - 1];
    }
}

爬楼梯

因为某个状态只与前两个状态有关,所以只需要两个变量来记录.
dp[i % 2] = dp[0] + dp[1];

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        // write your code here
        int[] dp = new int[2];
        dp[0] = 1;
        for (int i = 0; i <= n; i++) {
            dp[i % 2] = dp[0] + dp[1];
        }
        return dp[n % 2];
    }
}
### [数字三角形](https://www.lintcode.com/zh-cn/problem/triangle/#)
```java
public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(int[][] triangle) {
        // write your code here
        if (triangle == null || triangle.length == 0 || triangle[0].length == 0) {
            return 0;
        }
        if (triangle.length == 1) {
            return triangle[0][0];
        }
        int m = triangle.length;
        int[] sum = new int[m];
        for (int i = m - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                if (i == m - 2) {
                    sum[j] = triangle[i][j] + Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
                } else {
                    sum[j] = triangle[i][j] + Math.min(sum[j], sum[j + 1]);
                }
            }
        }
        return sum[0];
    }
}

完美平方

定义一个数组dp[]
先把1,4,9,16,25…填上1
然后把从一到n填上
比如12可以分解成dp[11]+1,dp[8]+1,dp[3]+1,选最小的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    /**
     * @param n a positive integer
     * @return an integer
     */
    public int numSquares(int n) {
        // Write your code here
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 1; i * i <= n; i++) {
            dp[i * i] = 1;
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j * j < i; j++) {
                dp[i] = Math.min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }
}

最小路径和

四种情况

  1. i==0&&j==0 sum[j] = grid[0][0];
  2. i==0&&j!=0 sum[j] = sum[j - 1] + grid[0][j];
  3. j==0&&i!=0 sum[j] += grid[i][0];
  4. i!=0&&j!=0 sum[j] = grid[i][j] + Math.min(sum[j], sum[j - 1]);
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
public class Solution {
    /**
     * @param grid: a list of lists of integers.
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    public int minPathSum(int[][] grid) {
        // write your code here
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[] sum = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    sum[j] = grid[i][j];
                } else if (i == 0) {
                    sum[j] = sum[j - 1] + grid[i][j];
                } else if (j == 0) {
                    sum[j] += grid[i][j];
                } else {
                    sum[j] = grid[i][j] + Math.min(sum[j], sum[j - 1]);
                }
            }
        }
        return sum[n - 1];
    }
}

Largest Divisible Subset

一个数组用来记录路径
一个数组用来记录整除数的个数.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public class Solution {
    /**
     * @param nums a set of distinct positive integers
     * @return the largest subset 
     */
    public List<Integer> largestDivisibleSubset(int[] nums) {
        // Write your code here
        List<Integer> list = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return list;
        }
        Arrays.sort(nums);
        int n = nums.length;
        int[] count = new int[n];
        int[] path = new int[n];
        count[0] = 1;
        path[0] = 0;
        for (int i = 1; i < nums.length; i++) {
            int index = findMost(nums, count, i);
            if (index == -1) {
                count[i] = 1;
                path[i] = i;
            } else {
                count[i] = count[index] + 1;
                path[i] = index;
                
            }
        }
        int lastIndex = find(nums, count, n);
        while (lastIndex != path[lastIndex]) {
            list.add(nums[lastIndex]);
            lastIndex = path[lastIndex];
        }
        list.add(nums[lastIndex]);
        return list;
    }
    private int findMost(int[] nums, int[] count, int end) {
        int index = -1;
        int num = nums[end];
        int co = Integer.MIN_VALUE;
        for (int i = 0; i < end; i++) {
            if (num % nums[i] == 0) {
                if (count[i] > co) {
                    co = count[i];
                    index = i;
                }
            }
        }
        return index;
    }
    private int find(int[] nums, int[] count, int end) {
        int index = -1;
        int co = Integer.MIN_VALUE;
        for (int i = 0; i < end; i++) {
            if (count[i] > co) {
                co = count[i];
                index = i;
            }
        }
        return index;
    }
}

跳跃游戏

贪心算法最简单
设置一个farest变量,记录能到达的最远地方

贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     /
    public boolean canJump(int[] A) {
        // wirte your code here
        if (A == null || A.length == 0) {
            return false;
        }
        int farest = 0;
        for (int i = 0; i < A.length; i++) {
            if (i > farest) {
                return false;
            }
            farest = Math.max(i + A[i], farest);
        }
        return true;
    }
}

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
    public boolean canJump(int[] A) {
        // wirte your code here
        boolean[] can = new boolean[A.length];
        can[0] = true;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (can[j] && j + A[j] >= i) {
                    can[i] = true;
                }
            }
        }
        return can[A.length - 1];
    }
}

最长上升子序列

记录每个点之前有多少个比自己小的,最后遍历一遍数组找到最长序列

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
public class Solution {
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    public int longestIncreasingSubsequence(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] count = new int[nums.length];
        count[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            count[i] = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    count[i] = Math.max(count[i], count[j]);
                }
            }
            count[i]++;
        }
        for (int i = 0; i < nums.length; i++) {
            if (count[i] > count[0]) {
                count[0] = count[i];
            }
        }
        return count[0];
    }
}