Posted Updated LeetCode / Hard / 复习3 minutes read (About 474 words)

25. Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

采用直接更改节点的方法可以使用O(1)的空间完成操作。

递归，DFS搜索，首先初始化一个哨兵节点。
将哨兵节点记录为first，下一个节点记录为second。

将first与second传入递归方法。
向下递归下一个节点，并将长度k-1。
当长度k等于1时，则递归到当前所需的栈底。将当前节点指向上一个节点，并将当前节点记录为last，下一个节点记录为next，返回true。
当curr为null时，返回false。

当递归返回为true时（即剩余的链表有k个节点以供翻转），上级的节点们都指向其前一个节点。当返回到的栈顶（即k等于最开始的值）时，将first指向last，将second指向next。

继续向下递归first与second。

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
/**
 * 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 {
    int K;
    ListNode next;
    ListNode prev;
    ListNode last;
    ListNode first;
    ListNode second;
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1) return head;
        
        K = k;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        prev = dummy;
        next = null;
        last = null;
        first = prev;
        second = prev.next;
        
        reverse(prev, dummy.next, k);
        
        return dummy.next;
    }
    
    private boolean reverse(ListNode prev, ListNode curr, int k){
        if(curr == null) return false;
        if(k == 1){
            last = curr;
            next = curr.next;
            curr.next = prev;
            return true;
        }
        
        if( reverse(curr, curr.next, k-1) ){
            curr.next = prev;
            if(k == K){
                first.next = last;
                second.next = next;
                first = curr;
                second = curr.next;
            
                reverse(first, second, k);
            }
            return true;
        }
        return false;
    }
    
    private void print(ListNode root){
        while(root != null){
            root = root.next;
        }
    }
}
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]);
    }
}
Follow

Recents

Archives

Links

×