Posted Updated LeetCode / Medium2 minutes read (About 259 words)

1249. Minimum Remove to Make Valid Parentheses

Given a string s of ‘(‘ , ‘)’ and lowercase English characters.

Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

  • It is the empty string, contains only lowercase characters, or
  • It can be written as AB (A concatenated with B), where A and B are valid strings, or
  • It can be written as (A), where A is a valid string.

用栈储存括号，按顺序将括号压入栈。
如果和上一个括号配对，则挤出上一个括号。

当栈不为空时，如果栈顶的符号为“)”，则优先去掉字符串左侧的括号。
如果栈顶的符号为“(”，则优先去掉字符串右侧的括号。
最后返回字符串。

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
class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuffer sb = new StringBuffer(s);
        
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(') stack.push('(');
            else if(s.charAt(i) == ')'){
                if(!stack.isEmpty() && stack.peek() == '(') stack.pop();
                else stack.push(')');
            }
        }
        
        while(!stack.isEmpty()){
            if(stack.pop() == ')'){
                int index = sb.indexOf(")");
                sb.delete(index, index+1);
            }
            else{
                int index = sb.lastIndexOf("(");
                sb.delete(index, index+1);
            }
        }        
        return sb.toString();
    }
}
Posted Updated LeetCode / Mediuma minute read (About 189 words)

413. Arithmetic Slices

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

  • For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.
    Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

动态规划，遍历一次记录所有数字的差。
然后遍历并计算连续相同的数字数量temp。
当不相同时，则计算temp长度可以选择的组合数，将其添加到count。

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
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {

        if(nums.length == 1) return 0;
        int[] difference = new int[nums.length-1];
        for(int i = 0; i < nums.length-1; i++){
            difference[i] = nums[i+1] - nums[i];
        }
        
        int count = 0;
        int temp = 1;
        int prev = difference[0];
        for(int j = 1; j < nums.length-1; j++){
            if(difference[j] == prev){
                temp++;
            }
            else{
                count += combinations(temp);
                temp = 1;
            }
            prev = difference[j];
        }
        count += combinations(temp);
        return count;
    }
    
    private int combinations(int n){
        return (n * (n-1)) / 2;
    }
}
Posted Updated LeetCode / Mediuma minute read (About 208 words)

62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

动态规划，每一个位置的线路都等于其左侧和上侧的两条线路的加和。
将初始的两个边值设置为1，然后计算直至终点位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int count;
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for(int j = 0; j < n; j++){
            dp[0][j] = 1;
        }
        
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
Posted Updated LeetCode / Medium3 minutes read (About 385 words)

785. Is Graph Bipartite?

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

  • There are no self-edges (graph[u] does not contain u).
  • There are no parallel edges (graph[u] does not contain duplicate values).
  • If v is in graph[u], then u is in graph[v] (the graph is undirected).
  • The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.
    A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

原题等于问：每个节点与其相连接的节点是否可以颜色不同？
通过BFS搜索，将每一层通过开关flag分组。
创建一个visited数组，记录分组和遍历情况。
当节点被放入错误的分组时，返回false。

注意因为图里的各个节点可能不连接，因此需要遍历对所有节点进行BFS搜索，通过visited的情况进行剪枝。

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 {
    public boolean isBipartite(int[][] graph) {
        Queue<int[]> q = new LinkedList<>();
        int[] visited = new int[graph.length];
        
        for(int i = 0; i < graph.length; i++){
            boolean flag = false;
            if(graph[i].length == 0 || visited[i] != 0) continue;
            q.add(graph[i]);
            visited[i] = 1;
            int size = 1;
        
            while(!q.isEmpty()){
                for(int j = 0; j < size; j++){
                    int[] node = q.poll();
                    for(int next : node){
                        if(visited[next] == 0){
                            q.add(graph[next]);
                        }
                        if(flag){
                            if(visited[next] == 2) return false;
                            visited[next] = 1;
                        }
                        else{
                            if(visited[next] == 1) return false;
                            visited[next] = 2;
                        }
                    }
                }
                flag = !flag;
                size = q.size();
            }
        }
        return true;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 409 words)

1631. Path With Minimum Effort

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

A*算法，启发式搜索。BFS搜索结合Priority Queue。
采用一个数组储存当前访问点的位置，以及其effort。
采用优先队列，优先搜索effort最小的方向。
每次循环倾倒出队列中所有的元素。
计算上一个节点和当前节点的差值作为nextEffort，并和上一个节点的effort作比较，较大的作为当前节点的effort，
将effort作为权重，优先搜索一个层级内effort较小的路径。
将所有操作加入队列，并排除越界的位置。
当当前节点为最后一个节点时，返回其effort。

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
class Solution {
    int min;
    public int minimumEffortPath(int[][] heights) {
        int[][] operations = {{1,0},{-1,0},{0,1},{0,-1}};
        int m = heights.length, n = heights[0].length;
        
        Queue<int[]> q = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        int[] point = {0, 0, 0};
        int size = 1;
        int[][] visited = new int[m][n];
        
        q.add(point);
        while(!q.isEmpty()){
            
            for(int k = 0; k < size; k++){
                int[] curr = q.poll();
                int i = curr[0], j = curr[1], currEffort = curr[2];
                if(visited[i][j] == 1) continue;
                visited[i][j] = 1;
                if(i == m-1 && j == n-1) return currEffort;
                for(int[] operation : operations){
                    int nextX = i + operation[0];
                    int nextY = j + operation[1];
                    if(nextX < 0 || nextY < 0 || nextX >= m || nextY >= n) continue;
                    int nextEffort = Math.max(currEffort, Math.abs(heights[i][j] - heights[nextX][nextY]));
                    int[] next = {nextX, nextY, nextEffort};
                    
                    q.add(next);
                }
            }
            size = q.size();
        }
        return -1;
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 209 words)

45. Jump Game II

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

设置一个当前可以访问的最大范围limit，在遍历中对其进行更新。
和当前可访问位置中的最远距离end，每次访问到达end时，计算步数。

遍历数组，比较limit和当前i能访问的最远距离i+nums[i]，保留较大值。
当i达到end时，更新end为之前记录的可访问最远距离limit。步数+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int jump(int[] nums) {
        int count = 0;
        int limit = 0;
        int end = 0;
        
        for(int i = 0; i < nums.length-1; i++){
            limit = Math.max(limit, i + nums[i]);
            if(i == end){
                end = limit;
                count++;
            }
        }
        
        return count;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 484 words)

707. Design Linked List

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

  • MyLinkedList() Initializes the MyLinkedList object.
  • int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
  • void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
  • void addAtTail(int val) Append a node of value val as the last element of the linked list.
  • void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
  • void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

单链表，设置一个哨兵节点在头部。
设置辅助方法，取得index的前一个节点。
addAtHead和addAtTail都可以采用addAtIndex实现。

采用双链表速度可以更快。

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
class MyLinkedList {
    ListNode head;
    int size;
    public MyLinkedList() {
        ListNode dummy = new ListNode(0);
        head = dummy;
        size = 0;
    }
    
    public ListNode getPrev(int index){
        ListNode prev = head;
        for(int i = 0; i < index; i++){
            prev = prev.next;
        }
        return prev;
    }
    
    public int get(int index) {
        if(index >= size) return -1;
        return getPrev(index).next.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index > size) return;
        ListNode prev = getPrev(index);
        ListNode temp = prev.next;
        prev.next = new ListNode(val);
        prev.next.next = temp;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index >= size) return;
        if(index == size-1){
            ListNode prev = getPrev(index);
            prev.next = null;
            size--;
            return;
        }
        ListNode prev = getPrev(index);
        prev.next = prev.next.next;
        size--;
    }
    
    private void print(){
        ListNode root = head.next;
        while(root != null){
            System.out.print(root.val+" ->   ");
            root = root.next;
        }
        System.out.println("Size:   "+size);
    }
    
    class ListNode{     
        int val;
        ListNode next;
        public ListNode(int v){
            val = v;
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
Posted Updated LeetCode / Medium / 复习2 minutes read (About 353 words)

1202. Smallest String With Swaps

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

并查集，注意要使用路径压缩否则会超时。
先将所有配对联通。然后创建一个数组group记录每个字符串位置的分组情况。
根据分组，借助优先队列保存字符串。
通过哈希表创建group和PriorityQueue的映射。
按当前位置的分组情况和优先队列的顺序来添加字符串。
最后返回字符串。

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
class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        StringBuffer sb = new StringBuffer();
        UnionFind uf = new UnionFind(s.length());
        
        for(List<Integer> pair : pairs){
            uf.union(pair.get(0), pair.get(1));    
        }
        
        int[] group = new int[s.length()];
        for(int i = 0; i < s.length(); i++){
            group[i] = uf.find(i);
        }
        
        HashMap<Integer, PriorityQueue<Character>> map = new HashMap<>();
        
        for(int i = 0; i < s.length(); i++){
            PriorityQueue<Character> bin = map.getOrDefault(group[i], new PriorityQueue<Character>());
            bin.add(s.charAt(i));
            map.put(group[i], bin);
        }
        for(int i = 0; i < s.length(); i++){
            sb.append(map.get(group[i]).poll());
        }
        return sb.toString();
    }
    
    class UnionFind {
        int[] parent;
        int[] count;
        public UnionFind(int n){
            parent = new int[n];
            count = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
                count[i] = 1;
            }
        } 
        
        private int find(int id){
            if(parent[id] == id) return id;
            parent[id] = find(parent[id]);
            return parent[id];
        }
        
        private boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            if(count[p1] > count[p2]) parent[p2] = p1;
            else parent[p1] = p2;
            return true;
        }
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 440 words)

55. Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

反向查找，动态规划。
到达目标点前必须到达上一个节点，且上一个节点能前进的步数必须大于目标点。
设置目标点goal，反向遍历goal以外的点。
如果该点能前进的步数加上自身的位置i大于目标点，则可以从上一个点到达goal。
更新goal的位置到上一个点。
如果遍历结束后，能返回到起始点0，则可以到达终点。

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean canJump(int[] nums) {
        int goal = nums.length-1;
        for(int i = nums.length-2; i >=0; i--){
            if(nums[i] >= goal - i) goal = i;
        }
        return goal == 0;
    }
}

贪心算法，储存一个到i时可以到达的最远值maxJump。
遍历数组，如果i大于maxJump，则无法到达下一个点，返回false。
在当前点可以到达的最大范围为nums[i]+i，如果大于maxJump则更新该值。
遍历完毕返回true。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean canJump(int[] nums) {
        int maxJump = 0;
        for(int i = 0; i < nums.length; i++){
            if(i > maxJump) return false;
            maxJump = Math.max(maxJump, nums[i] + i);
        }
        return maxJump >= nums.length-1;
    }
}

设置一个数组记录可访问的范围。
当遍历时，如果可以访问，则将当前位置可以进一步访问的位置变为1。
如果访问范围大于等于数组末尾，则返回真。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean canJump(int[] nums) {
        int[] reach = new int[nums.length];
        reach[0] = 1;
        
        for(int i = 0; i < nums.length; i++){
            if(reach[i] == 1){
                if(i == nums.length-1) return true;
                for(int j = 0; j < nums[i]; j++){
                    if(i+j+1 >= nums.length) return true;
                    reach[i+j+1] = 1;
                }
            }
        }
        return false;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 291 words)

213. House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

动态规划，和普通的动态规划不同的是这道题是首尾相连的。
因此分两种情况讨论——如果选择了头，就不选择尾。反之亦然。
建立两个动态规划表，分别选择第一个和第二个数字作为第一次抢劫的目标。
前一个最多抢劫到倒数第一个房子，后一个最多抢劫到最后一个房子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        
        int max = 0;
        int[] dp = new int[nums.length+1];
        int[] dp2 = new int[nums.length+1];
        dp[1] = nums[0];

        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(dp[i-2] + nums[i-1], dp[i-1]);
        }

        dp2[2] = nums[1];
        
        for(int i = 3; i <= nums.length; i++){
            dp2[i] = Math.max(dp2[i-2] + nums[i-1], dp2[i-1]);
        }
        
        return Math.max(dp[dp.length-2], dp2[dp2.length-1]);
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 267 words)

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

先建立一个哨兵节点，next指向head。
交换时同时传入前一个节点pre和当前节点root。
当当前节点非null且下一个节点非null，则可以交换两个节点。
首先保存当前节点的下一个节点next和下一个节点的下一个节点last。

  • 1.将pre指向next。
  • 2.将next指向root。
  • 3.将root指向last。
  • 4.处理下一组节点，root作为pre，root.next作为root递归。
    最后返回哨兵节点的next。
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        swap(dummy, head);
        return dummy.next;
    }
    
    private void swap(ListNode pre, ListNode root){
        if(root == null || root.next == null){
            return;
        }
        else if(root != null && root.next != null){
            
            ListNode last = root.next.next;
            ListNode next = root.next;
            pre.next = next;
            next.next = root;
            root.next = last;
        }
        swap(root, root.next);
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 301 words)

79. Word Search

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

回溯，遍历所有初始元素。
当寻找的字符与当前matrix里的字符相同时，将当前位置记录在visited里，并向下递归搜索四个方向，回溯visited。
当越界或者字符已经visited时返回false。
当寻找到单词的最后一位时，如果当前matrix里的字符与搜索的字符相等，则返回true。反之返回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
class Solution {
    char[][] bd;
    String wd;
    int[][] visited;
    public boolean exist(char[][] board, String word) {
        boolean ans = false;
        visited = new int[board.length][board[0].length];
        bd = board;
        wd = word;
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                ans = ans || backtracking(i, j, 0);
            }
        }
        return ans;
    }
    
    private boolean backtracking(int i, int j, int n){
        
        if(i < 0 || j < 0 || i >= bd.length || j >= bd[0].length || n >= wd.length()) return false;
        if(visited[i][j] == 1) return false;
        if(n == wd.length()-1) return bd[i][j] == wd.charAt(n); 
        if( bd[i][j] == wd.charAt(n) ){
            n++;
            visited[i][j] = 1;
            boolean a = backtracking(i+1, j, n);
            boolean b = backtracking(i-1, j, n);
            boolean c = backtracking(i, j+1, n);
            boolean d = backtracking(i, j-1, n);
            visited[i][j] = 0;
            return a || b || c || d;
        }
        return false;
    }
}
Posted Updated LeetCode / Mediuma minute read (About 166 words)

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

回溯，记录左右括号的出现次数。
每次递归都添加左侧括号。
左侧括号的数量大于右侧括号时递归下一级才可以添加右侧括号。
当左侧括号和右侧括号达到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
30
31
class Solution {
    int N;
    List<String> ret;
    StringBuffer sb;
    
    public List<String> generateParenthesis(int n) {
        ret = new ArrayList<>();
        sb = new StringBuffer();
        N = n;
        backtracking(0, 0);
        return ret;
    }
    
    private void backtracking(int left, int right){
        if(left > N || right > N){
            return;
        }
        if(left == N && right == N){
            ret.add(sb.toString());
            return;
        }
        if(left > right){
            sb.append(')');
            backtracking(left, right+1);
            sb.delete(sb.length()-1, sb.length());        
        }
        sb.append('(');
        backtracking(left+1, right);
        sb.delete(sb.length()-1, sb.length());        
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 380 words)

1584. Min Cost to Connect All Points

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

并查集，最小生成树(Minimum spanning tree)，Kruskal算法。
Edge辅助类，保存并计算两点的id和其曼哈顿距离。
将edges根据其距离排序。

遍历所有的edge，如果edge的两点没有合并，则合并两点，并取这条边作为结果。
加和所有的结果，答案就是最小值。

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
class Solution {
    public int minCostConnectPoints(int[][] points) {
        List<Edge> edges = new ArrayList<Edge>();
        int min = 0;
        for(int i = 0; i < points.length; i++){
            for(int j = i+1; j < points.length; j++){
                 edges.add(new Edge(points, i, j));
            }
        }
        
        Collections.sort(edges, (a, b) -> a.length - b.length);
        UnionFind uf = new UnionFind(points.length);
        
        for(Edge e : edges){
            if(uf.union(e.id1, e.id2)){
                min += e.length;
            }
        }
        return min;
    }

    class UnionFind{
        private int[] parents;
        private int[] size;
    
        public UnionFind(int n){
            size = new int[n];
            parents = new int[n];
            for(int i = 0; i < n; i++){
                parents[i] = i;
                size[i] = 1;
            }
        }
    
        public int find(int id){
            if(parents[id] == id) return id;
            return find(parents[id]);
        }
    
        public boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            
            if(p1 == p2) return false;
        
            if(size[p1] < size[p2]){
                parents[p1] = p2;
                size[p2] += size[p1];
            }
            else{
                parents[p2] = p1;
                size[p1] += size[p2];
            }
            return true;
        }
    }

    class Edge{
        int id1;
        int id2;
        int length;
        public Edge(int[][] points, int _id1, int _id2){
            id1 = _id1;
            id2 = _id2;
            length = Math.abs(points[id1][0] - points[id2][0]) + Math.abs(points[id1][1] - points[id2][1]);
        }
    }
}
Posted Updated LeetCode / Mediuma minute read (About 189 words)

17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

回溯，每个回溯层级添加数字对应的字符。

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
class Solution {
    public List<String> letterCombinations(String digits) {

        
        List<String> ret = new ArrayList<>();
        if(digits.equals("")) return ret;
        
        char[][] bin = new char[8][0];
        bin[0] = new char[]{'a', 'b', 'c'}; 
        bin[1] = new char[]{'d', 'e', 'f'};
        bin[2] = new char[]{'g', 'h', 'i'};
        bin[3] = new char[]{'j', 'k', 'l'};
        bin[4] = new char[]{'m', 'n', 'o'};
        bin[5] = new char[]{'p', 'q', 'r', 's'};
        bin[6] = new char[]{'t', 'u', 'v'};
        bin[7] = new char[]{'w', 'x', 'y', 'z'};
        
        backtracking(ret, new StringBuffer(), bin, digits, 0);
        return ret;
    }
    
    private void backtracking(List<String> ret, StringBuffer sb, char[][] bin, String digits, int i){
        if(sb.length() == digits.length() ){
            ret.add(sb.toString());
            return;
        }
        
        for(char c : bin[digits.charAt(i)-'2']){
            sb.append(c);
            backtracking(ret, sb, bin, digits, i+1);
            sb.delete(sb.length()-1, sb.length());
        }
    }
}
Follow

Recents

Archives

Links

×