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());
        }
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 411 words)

142. Linked List Cycle II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

快慢指针。快指针的移动速度是慢指针的两倍。
设环外长度为a，b是快指针和慢指针相遇的位置，c是环中剩余位置。
可以由此得到公式a + (n + 1)b + nc = 2(a + b)，也就是a = c + (n - 1)(b + c)
由于（b + c）是环的长度。因此，当两个指针相遇时，在头部设置一个新节点。慢指针和新指针将在循环入口处相遇，此时返回节点。

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if( head == null || head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow.equals(fast)) break;
        }
        
        if(fast == null || fast.next == null){
            return null;
        }
        
        ListNode root = head;
        while(!root.equals(slow)){
            slow = slow.next;
            root = root.next;
        }
        return root;
    }
}

哈希表，递归并将节点加入哈希集合，如果重复则返回节点，反之返回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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    HashSet<ListNode> set;
    public ListNode detectCycle(ListNode head) {
        set = new HashSet<>();
        return findCycle(head, 0);
    }
    
    private ListNode findCycle(ListNode root, int count){
        if(root == null){
            return null;
        }
        if(set.contains(root)){
            return root;
        }
        set.add(root);
        count++;
        return findCycle(root.next, count);
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 348 words)

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

递归，每次递归时建立root的next节点，然后将root移动到root.next。
计算两个节点的和并填入root节点。每次计算时需要计算是否进位。
递归两个节点的next节点，并将carry传入。
当一个节点为null时，只递归和计算另一个节点。
当两个节点为null时，如果有carry需要将其放入新节点，如果没有则返回。

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 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 addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode();
        addTwo(l1,l2,root,0);
        return root.next;
    }
    
    private void addTwo(ListNode l1, ListNode l2, ListNode root, int carry){
        if(l1 == null && l2 == null && carry == 0){
            return;
        }
        else if(l1 == null && l2 == null){
            root.next = new ListNode();
            root = root.next;
            root.val = carry;
            return;
        }
        else if(l1 == null){
            root.next = new ListNode();
            root = root.next;
            root.val = (l2.val + carry) % 10;
            carry = (l2.val + carry) / 10;
            addTwo(null, l2.next, root, carry);
            return;
        }
        else if(l2 == null){
            root.next = new ListNode();
            root = root.next;
            root.val = (l1.val + carry) % 10;
            carry = (l1.val + carry) / 10;
            addTwo(null, l1.next, root, carry);
            return;
        }
        root.next = new ListNode();
        root = root.next;
        root.val = (l1.val + l2.val + carry) % 10;
        carry = (l1.val + l2.val + carry) / 10;

        addTwo(l1.next, l2.next, root, carry);
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 229 words)

40. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

由于有重复性元素，因此先将数组排序。
储存一个数组，记录元素是否被选择。
回溯，遍历选择元素，并计算加和，并记录选择的元素。当选择的元素与上一个元素重复时，则跳过。

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 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(candidates, ret, new ArrayList<>(), new int[candidates.length], target, 0, 0);
        return ret;
    }
    
    private void backtracking(int[] candidates, List<List<Integer>> ret, List<Integer> arr, int[] visited, int target, int sum, int level){
        if(sum > target ){
            return;
        }
        else if (sum == target){
            ret.add(new ArrayList<>(arr));
            return;
        }

        for(int i = level; i < candidates.length; i++){
            if(i > 0 && candidates[i] == candidates[i-1] && visited[i-1] == 0) continue;
            visited[i] = 1;
            arr.add(candidates[i]);
            sum+= candidates[i];
            backtracking(candidates, ret, arr, visited, target, sum, i+1);
            visited[i] = 0;
            sum-= candidates[i];
            arr.remove(arr.size()-1);
        }
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 240 words)

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

回溯，记录当前加和。
遍历所有数组元素，当sum大于target时返回，等于target时加入数组并返回。
每次遍历并回溯元素时只递归当前元素和其之后的元素。（防止重复。）

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 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        backtracking(candidates, ret, new ArrayList<>(), target, 0, 0);
        return ret;
    }
    
    private void backtracking(int[] candidates, List<List<Integer>> ret, List<Integer> arr, int target, int sum, int level){
        if(sum > target ){
            return;
        }
        else if (sum == target){
            ret.add(new ArrayList<>(arr));
            return;
        }

        for(int i = level; i < candidates.length; i++){
            arr.add(candidates[i]);
            sum+= candidates[i];
            backtracking(candidates, ret, arr, target, sum, i);
            sum-= candidates[i];
            arr.remove(arr.size()-1);
        }
    }
}
Follow

Recents

Archives

Links

×