Leetcode 721. Accounts Merge

721. Accounts Merge

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
class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap();
        Map<String, ArrayList<String>> graph = new HashMap();
        for (List<String> account: accounts) {
            String name = account.get(0);
            for (int i =1; i<account.size(); i++) {
                String email = account.get(i);
                graph.computeIfAbsent(email, x-> new ArrayList<String>()).add(account.get(1)); 
                //return the ref tp a new Arraylist.add(..)
                //also the key value pair is put to map
                graph.computeIfAbsent(account.get(1), x-> new ArrayList<String>()).add(email);
                //反向链接
                emailToName.put(email, name);
            }
        }
        //graph是类似邻接链表的有向图结构,只包含email
        //emailToName 记录了邮件名到给定名字的映射
 
        Set<String> seen = new HashSet();
        List<List<String>> ans = new ArrayList();
        for (String email: graph.keySet()) {
            if (seen.add(email)) {
                Deque<String> stack = new LinkedList<>();
                stack.push(email);
                List<String> component = new ArrayList();
                //Use bfs to search neighbours
                while (!stack.empty()) {
                    String node = stack.pop();
                    component.add(node);
                    for (String nei: graph.get(node)) {
                        if (!seen.contains(nei)) {
                            seen.add(nei);
                            stack.push(nei);
                        }
                    }
                }
                Collections.sort(component);
                component.add(0, emailToName.get(email));
                ans.add(component);
            }
        }
        return ans;
    }
}

Union Find

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
class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        DSU dsu = new DSU();
        Map<String, String> emailToName = new HashMap();
        Map<String, Integer> emailToID = new HashMap();
        int id = 0;
        for (List<String> account: accounts) {
            String name = "";
            for (String email: account) {
                if (name == "") {
                    name = email;
                    continue;
                }
                emailToName.put(email, name);
                if (!emailToID.containsKey(email)) {
                    emailToID.put(email, id++);
                }
                dsu.union(emailToID.get(account.get(1)), emailToID.get(email));
            }
        }
 
        Map<Integer, List<String>> ans = new HashMap();
        for (String email: emailToName.keySet()) {
            int index = dsu.find(emailToID.get(email));
            ans.computeIfAbsent(index, x-> new ArrayList()).add(email);
        }
        for (List<String> component: ans.values()) {
            Collections.sort(component);
            component.add(0, emailToName.get(component.get(0)));
        }
        return new ArrayList(ans.values());
    }
}
class DSU {
    int[] parent;
    public DSU() {
        parent = new int[10001];
        for (int i = 0; i <= 10000; ++i)
            parent[i] = i;
    }
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}

Leetcode 44. Wildcard Matching

377. Combination Sum IV

DP

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 {
    public boolean isMatch(String s, String p) {
        boolean[][] match=new boolean[s.length()+1][p.length()+1];
        match[s.length()][p.length()]=true;
        for(int i=p.length()-1;i>=0;i--){
            if(p.charAt(i)!='*')
                break;
            else
                match[s.length()][i]=true; //倒着走
        }
        for(int i=s.length()-1;i>=0;i--){
            for(int j=p.length()-1;j>=0;j--){
                if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?')
                        match[i][j]=match[i+1][j+1];
                else if(p.charAt(j)=='*')
                        match[i][j]=match[i+1][j]||match[i][j+1];
                        //  match[i][j]=match[i+1][j] means * match form XXX to XXX[i]
                        //  match[i][j]=match[i][j+1] means * match *empty*
                else
                    match[i][j]=false;
            }
        }
        return match[0][0];
    }
}

Two pointer

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 boolean isMatch(String s, String p) {
        int i = 0;
        int j = 0;
        int lastStar = -1;
        int lastMatch = -1;
        while(i < s.length()){
            if(j<p.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?')){
                i++;
                j++;
            }else if(j<p.length() && p.charAt(j) == '*'){
                lastStar = j;
                lastMatch = i;
                j++; // consider the * would mean empty
            }else if(lastStar != -1){
                j = lastStar+1; //
                i = ++lastMatch;
            }else{
                return false;
            }
        }
        while(j < p.length() && p.charAt(j) == '*') j++;
        return j == p.length();
    }
}

Leetcode 377. Combination Sum IV

377. Combination Sum IV

Top-down DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] comb = new int[target + 1];
        comb[0] = 1;
        for (int i = 1; i < comb.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i - nums[j] >= 0) {
                    comb[i] += comb[i - nums[j]];
                }
            }
        }
        return comb[target];
    }
}

Bottom up Memoication

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    private int[] dp;
 
    public int combinationSum4(int[] nums, int target) {
        dp = new int[target + 1];
        Arrays.fill(dp, -1);
        dp[0] = 1;
        return helper(nums, target);
    }
 
    private int helper(int[] nums, int target) {
        if (dp[target] != -1) {
            return dp[target];
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (target >= nums[i]) {
                res += helper(nums, target - nums[i]);
            }
        }
        dp[target] = res;
        return res;
    }
}

Leetcode 670. Maximum Swap

670. Maximum Swap

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maximumSwap(int num) {
        String str = num + "";
        int[] table = new int[str.length()];
        int maxIndex = str.length()-1;
        for(int i = str.length() -1; i>=0; i--){
            if(str.charAt(i) >= str.charAt(maxIndex) || i == str.length()-1){
                table[i] = i;
                if(str.charAt(i) > str.charAt(maxIndex))
                    maxIndex = i;
            }else{
                table[i] = maxIndex;
            }  
        }
        System.out.println(Arrays.toString(table));
        for(int i =0; i<str.length(); i++){
            if(table[i] != i){
                return Integer.parseInt(str.substring(0,i) +str.charAt(table[i]) + str.substring(i+1,table[i]) + str.charAt(i) +  str.substring(table[i]+1));
            }
        }
        return num;
    }
}

Bucket

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maximumSwap(int num) {
        char[] digits = Integer.toString(num).toCharArray();
 
        int[] buckets = new int[10];
        for (int i = 0; i < digits.length; i++) {
            buckets[digits[i] - '0'] = i;
        }
 
        for (int i = 0; i < digits.length; i++) {
            for (int k = 9; k > digits[i] - '0'; k--) {
                if (buckets[k] > i) {
                    char tmp = digits[i];
                    digits[i] = digits[buckets[k]];
                    digits[buckets[k]] = tmp;
                    return Integer.valueOf(new String(digits));
                }
            }
        }
 
        return num;
    }
}

Leetcode 43. Multiply Strings

43. Multiply Strings

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] pos = new int[m + n];
 
        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); 
                int p1 = i + j, p2 = i + j + 1;
                int sum = mul + pos[p2];
 
                pos[p1] += sum / 10; //进位 index从大到小,保证了所有位数都会调整
                pos[p2] = (sum) % 10; //调整
                //index越大,位数越小 是反向的
            }
        }  
 
        StringBuilder sb = new StringBuilder();
        for(int p : pos) 
            if(sb.length() != 0 || p != 0)  //排除开头为0的数组
                sb.append(p);
        return sb.length() == 0 ? "0" : sb.toString();
    }   
}

Leetcode 161. One Edit Distance

161. One Edit Distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if(s.length() > t.length()) 
            return isOneEditDistance(t, s);
        int m = s.length(), n = t.length();
        if(n - m > 1) return false;
        for(int i = 0; i < m; i++) {
            if(s.charAt(i) != t.charAt(i)) 
                return s.substring(i + 1).equals(t.substring(i + 1)) || s.substring(i).equals(t.substring(i + 1));
                // replace or delete(add)
        }
        return n > m; //n is one more than m
        // here is to determine there must be one edit distance 
        // equal condition doesn't count for true
    }
}

Leetcode 689. Maximum Sum of 3 Non-Overlapping Subarrays

689. Maximum Sum of 3 Non-Overlapping Subarrays

  • DP for sum
  • DP for left max and right max
  • Iteration with damper
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
class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] table = new int[nums.length - k +1];
        int count  = 0;
        int index = 0;
        for(int i = 0; i<nums.length; i++){
            if( i < k-1){
                count += nums[i];
            }else{
                count += nums[i];
                table[index++] = count;
                count -= nums[i-k+1];
            }
        }
        //System.out.println(Arrays.toString(table));
 
        int[] left = new int[table.length];
        for(int i =0; i<table.length; i++){
            if(i != 0){
                if(table[i] > table[left[i-1]]){ // here is greater to keep lexicographically smallest 
                    left[i] = i;
                }else{
                    left[i] = left[i-1];
                }
            }
        }
        // System.out.println(Arrays.toString(left));
        int[] right = new int[table.length];
        for(int i = table.length-1; i>= 0; i--){
            if(i != table.length -1){
                if(table[i] >= table[right[i+1]]){ //here is greater and equal to keep  lexicographically smallest 
                    right[i] = i;
                }else{
                    right[i] = right[i+1];
                }
            }else{
                right[i] = i;
            }
        }  
        //System.out.println(Arrays.toString(right));
        int[] ans = new int[]{-1, -1, -1};
        for(int i = k; i<table.length - k; i++){
            int p = left[i-k];
            int q = right[i+k];
            if(ans[0] == -1 || table[i] + table[p] + table[q] > table[ans[0]] + table[ans[1]] + table[ans[2]]){
                ans[0] = p;ans[1] = i;ans[2] = q;
            }
        }
        return ans;
 
    }
}

Leetcode 479. Largest Palindrome Product

479. Largest Palindrome Product

This is a boring problem which can be only inplemented with brute force! The fastest solution is hard-code!
Naive implementation:

  • Find all pali in the porper range
  • Check if the pali can be factorial
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
class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) 
            return 9;
        long max = (long) Math.pow(10, n) - 1;
        long min = max / 10 + 1;
        long t = 0;
        for (long num = max - 1; num >= min; num--) {
            t = makePalindrome(num);
            if (isFactorable(t, max, min)) {
                return (int)(t % 1337);
            }
        }
        return -1;
    }
 
    private long makePalindrome(long num) {
        long res = num;
        while (num > 0) {
            res = res * 10 + num % 10;
            num /= 10;
        }
        return res;
    }
 
    public boolean isFactorable(long num, long max, long min) {
        long mid = (long)Math.sqrt(num);
        if (mid > max || mid < min) 
            return false;
        long low = mid, high = mid, t = low * high;
        while (t != num) {
            if (t < num) {
                if (++high > max) 
                    return false;
            } else {
                if (--low < min) 
                    return false;
            }
            t = low * high;
        }
        return true;
    }
 
}

Leetcode 29. Divide Two Integers

29. Divide Two Integers

Entend two times as much base!
Use bit manipulation to escape the multiplication!
Notice: Integer.MIN_VALUE / -1 will cause overflow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int divide(int dividend, int divisor) {
        if(divisor == 0) return Integer.MAX_VALUE;
        if(dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        int sign = ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) ? -1 : 1;
        long n1 = Math.abs((long)dividend);
        long n2 = Math.abs((long)divisor);
        int res = 0;
        while(n2 <= n1) {
            long base = n2;
            for(int i = 0; base <= n1; i++) {
                n1 -= base;
                base <<= 1;
                res = res + (1 << i);
            }
        }
        return sign * res;
    }
}

Leetcode 114. Flatten Binary Tree to Linked List

114. Flatten Binary Tree to Linked List

DFS

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 void flatten(TreeNode root) {
        helper(root);
    }
 
    public TreeNode helper(TreeNode root){
        if(root == null) return null;
        TreeNode left = helper(root.left);
        TreeNode right = helper(root.right);
        if(left != null){
            left.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        if(right == null){
            if(left == null){
                return root;
            }else{
                return left;
            }
        }else{
            return right;
        }  
    }
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void flatten(TreeNode root) {
        Stack<TreeNode> s = new Stack<TreeNode>();
        if (root == null) return;
        s.push(root);
        TreeNode cur, pre = null;
        while (!s.isEmpty())
        {
            cur = s.pop();
            if (pre != null) 
            {
                pre.left = null;
                pre.right = cur;
            }
            pre = cur;
            if (cur.right != null) s.push(cur.right);
            if (cur.left != null) s.push(cur.left);
        }
    }
}