诶叵

Posted on | Edited on | In | | Views:
Symbols count in article: 34k | Reading time ≈ 35 mins.

请多多指教！

403. frog-jump

给一个数组表示石头所处的x坐标，青蛙每次只能跳上一次跳跃长度的-1,0,1三种可能，判断能否跳到最后一个石头。
相当于BFS，每个石头处维护一个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
// BFS，从开头出发，不断更新后续可达石头的新步数，若中途更新到了最后一个石头，就可达
public boolean canCross(int[] stones) {
    if (stones == null || stones.length == 0) {
        return true;
    }
    if (stones[0] != 0) {
        return false;
    }
    
    // 记录每个坐标的石头所能跳的长度
    Map<Integer, Set<Integer>> stone2step = new HashMap<>();
    for (int i = 0; i < stones.length; i++) {
        stone2step.put(stones[i], new HashSet<>());
    }
    stone2step.get(0).add(1);   // 第一步起码要能往后挪一步
    
    // 从第一个石头开始，往后更新每个石头的能跳步数
    for (int i = 0; i < stones.length; i++) {
        int currStone = stones[i];
        Set<Integer> steps = stone2step.get(currStone);
        for (int step: steps) {
            int newStone = currStone + step;
            if (newStone == stones[stones.length - 1]) {
                return true;
            }
            Set<Integer> newStep = stone2step.get(newStone);
            if (newStep != null) {   // 表示有这个新石头的坐标
                newStep.add(step + 1);
                newStep.add(step);
                if (step - 1 > 0) {
                    newStep.add(step - 1);
                }
            }
        }
    }
    return false;
}

249. group-shifted-strings

给一个String的数组，要求将其中能通过平移相同offset后相同的字符串group在一起.
先根据第一个字母算出与a的offset，然后将后续所有字母都根据这个offset来挪，拼接成key存入map。

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 {
    // group xxx的题，八成就是要找到同一组的共同点并定义好key
    // 这里的key就是长度相同的字符串每个字母挪动一定的offset可以相等
    // 根据首字母与'a'的offset来定义key，往key对应的List里add就好了
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> ans = new ArrayList<>();
        if (strings == null || strings.length == 0) {
            return ans;
        }
        
        Map<String, List<String>> map = new HashMap<>();
        for (String s: strings) {
            if (s.length() == 0) {
                if (!map.containsKey("")) {
                    map.put("", new ArrayList<>());
                }
                map.get("").add(s);
                continue;
            }
            char[] sChar = s.toCharArray();
            int offset = sChar[0] - 'a'; // 只有小写字母
            StringBuilder key = new StringBuilder();
            for (int i = 0; i < sChar.length; i++) {
                char c = (char)(sChar[i] - offset);
                if (c < 'a') {
                    c += 26;
                }
                key.append(c);
            }
            if (!map.containsKey(key.toString())) {
                map.put(key.toString(), new ArrayList<String>());
            }
            map.get(key.toString()).add(s);
        }
        
        // 每个List内部需要排序
        for (String key: map.keySet()) {
            List<String> list = map.get(key);
            Collections.sort(list);
            ans.add(list);
        }
        return ans;
    }
}

108. convert-sorted-array-to-binary-search-tree

取中间的为根节点，然后前后两半递归继续build。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return buildTree(nums, 0, nums.length - 1);
        
    }
    
    private TreeNode buildTree(int[] nums, int start, int end) {
        if (start > end) 
            return null;
        if (start == end) 
            return new TreeNode(nums[start]);
        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = buildTree(nums, start, mid - 1);
        node.right = buildTree(nums, mid + 1, end);
        return node;
    }
}

127. word-ladder

很图论的题，每一个单词看作节点，路径有无根据「能否改一个字母变成它」判断，在BFS过程中可达就直接入queue。

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
public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (beginWord == null || endWord == null || beginWord.length() == 0 || endWord.length() == 0
          || beginWord.length() != endWord.length() || wordList == null || wordList.size() == 0) {
            return 0;
        }
        Set<String> wordSet = new HashSet<>(wordList);
        Queue<String> toVisit = new LinkedList<>();
        bfs(beginWord, wordSet, toVisit);
        int dist = 2;
        while (!toVisit.isEmpty()) {
            int size = toVisit.size();
            for (int i = 0; i < size; i++) {
                String curr = toVisit.poll();
                if (curr.equals(endWord)) {
                    return dist;
                } else {
                    bfs(curr, wordSet, toVisit);
                }
            }
            dist++;
        }
        return 0;
    }
    
    private void bfs(String beginWord, Set<String> wordSet, Queue<String> toVisit) {
        wordSet.remove(beginWord);
        StringBuilder sb = new StringBuilder(beginWord);
        for (int i = 0; i < sb.length(); i++) {
            char origin = sb.charAt(i);
            for (int k = 0; k < 26; k++) {
                char c = (char)('a' + k);
                sb.setCharAt(i, c);
                String curr = sb.toString();
                if (wordSet.contains(curr)) {
                    toVisit.add(curr);
                    wordSet.remove(curr);
                }
            }
            sb.setCharAt(i, origin);
        }
    }
}

126. word-ladder-ii

词典中每一个词都是一个node，要从起点到终点，如果要记录这些最短的路径具体是怎么走的，就需要在BFS判断可不可达并构建临街表的基础上再来一个DFS，从起点开始一直往后（不走回头路利用的是后出现的节点的距离一定是先经过的节点的距离+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
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
class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        wordSet.add(beginWord);
        Map<String, List<String>> neighborMap = new HashMap<>();
        Map<String, Integer> distanceMap = new HashMap<>();
        List<List<String>> ans = new ArrayList<>();
        bfs(beginWord, endWord, wordSet, neighborMap, distanceMap);
        dfs(beginWord, endWord, neighborMap, distanceMap, new Arraylist<String>(), ans);
        return ans;
    }
    // 用BFS构建邻接表并维护离起点的距离
    private void bfs(String beginWord, String endWord, Set<String> wordSet, 
    Map<String, List<String>> neighborMap, Map<String, Integer> distanceMap) {
        for (String word: wordSet) {
            neighborMap.put(word, new ArrayList<String>());
        }
        Queue<String> q = new LinkedList<>();
        q.add(beginWord);
        distanceMap.put(beginWord, 0);
        while (!q.isEmpty()) {
            int size = q.size();
            boolean reached = false;
            for (int i = 0; i < size; i++) {
                String currWord = q.poll();
                int currDistance = distanceMap.get(currWord);
                List<String> neighborList = getNeighborList(currWord, wordSet);
                for (String neighbor: neighborList) {
                    neighborMap.get(currWord).add(neighbor);
                    if (!distanceMap.containsKey(neighbor)) {
                        distanceMap.put(neighbor, currDistance + 1);
                        if (neighbor.equals(endWord)) {
                            reached = true;
                        } else {
                            q.add(neighbor);
                        }
                    }
                }
            }
            if (reached) {
                break;
            }
        }
    }
    // 通过替换字母并判断是否在dict中产生给定词的邻居
    private List<String> getNeighborList(String currWord, Set<String> wordSet) {
        char[] cstr = currWord.toCharArray();
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < cstr.length; i++) {
            char origin = cstr[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == origin) {
                    continue;
                }
                cstr[i] = c;
                String temp = new String(cstr);
                if (wordSet.contains(temp)) {
                    ret.add(temp);
                }
            }
            cstr[i] = origin;
        }
        return ret;
    }
    // 从起点开始往它的邻居DFS
    private void dfs(String currWord, String endWord, Map<String, List<String>> neighborMap,
    Map<String, Integer> distanceMap, List<String> path, List<List<String>> ans) {
        path.add(currWord);
        if (currWord.equals(endWord)) {
            ans.add(new ArrayList<String>(path));
        } else {
            int currDistance = distanceMap.get(currWord);
            List<String> neighborList = neighborMap.get(currWord);
            for (String neighbor: neighborList) {
                if (distanceMap.get(neighbor) == currDistance + 1) {
                    dfs(neighbor, endWord, neighborMap, distanceMap, path, ans);
                }
            }
        }
        path.remove(path.size() - 1);
    }
}

[Extra][path between 2 nodes in tree]

给一个二叉树，和两个节点A，B，找出从A到B的路径，返回结果要求顺序存到一个链表中。
找到A和B的共同祖先，然后倒序输出到A的路径，再输出到B的路径。

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
86
87
88
89
90
91
public class Apple {
    // 共同祖先：递归左边，递归右边，两边都有则root为LCA，否则就是左右二者其中之一
    private static TreeNode getLCA(TreeNode root, TreeNode n1, TreeNode n2) {
		if (root == null) {
			return null;
		}
		if (root == n1 || root == n2) {
			return root;
		}
		TreeNode left = getLCA(root.left, n1, n2);
		TreeNode right = getLCA(root.right, n1, n2);
		if (left != null && right != null) {
			return root;
		}
		if (left == null && right == null) {
			return null;
		}
		return left == null? right: left;
	}
    private static String findPathBetween(TreeNode root, TreeNode start, TreeNode end) {
		if (root == null) {
			return "";
		}
		TreeNode lca = getLCA(root, start, end);
		List<TreeNode> pathToStart = new ArrayList<TreeNode>();
		findPathTo(lca, start, pathToStart);
		List<TreeNode> pathToEnd = new ArrayList<TreeNode>();
		findPathTo(lca, end, pathToEnd);
		
		StringBuilder sb = new StringBuilder();
		for (int i = pathToStart.size() - 1; i > 0; i--) {
			if (sb.length() == 0) {
				sb.append(pathToStart.get(i).val);
			} else {
				sb.append("->");
				sb.append(pathToStart.get(i).val);
			}
		}
		for (TreeNode node : pathToEnd) {
			sb.append("->");
			sb.append(node.val);
		}
		return sb.toString();
		
	}
	private static boolean findPathTo(TreeNode start, TreeNode end, List<TreeNode> curr) {
		curr.add(start);
		if (start == end) {
			return true;
		} else {
			if (start.left != null) {
				if (findPathTo(start.left, end, curr)) {
					return true;
				}
			}
			if (start.right != null) {
				if (findPathTo(start.right, end, curr)) {
					return true;
				}
			}
		}
		curr.remove(curr.size() - 1);
		return false;
	}
    public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		public TreeNode(int val) {
			this.val = val;
		}
	}
	public static void main(String[] args) {
		TreeNode root = new TreeNode(0);
		TreeNode n1 = new TreeNode(1);
		TreeNode n2 = new TreeNode(2);
		TreeNode n3 = new TreeNode(3);
		TreeNode n4 = new TreeNode(4);
		TreeNode n5 = new TreeNode(5);
		TreeNode n6 = new TreeNode(6);
		TreeNode n7 = new TreeNode(7);
		root.left = n1;
		root.right = n2;
		n1.left = n5;
		n1.right = n6;
		n2.left = n3;
		n2.right = n4;
		n3.left = n7;
		System.out.println(findPathBetween(root, n2, n5));
	}
}

[extra][overlap interval]

给两个interval的数组，求二者overlap的部分.
定义一个endCurr表示当前的结尾，然后取两个数组中start较小的与它比较，如果重合就将start为起点、endCurr为结尾new一个新的interval存入结果，然后更新endCurr（如果比该start处对应的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
public List<Interval> findOverlapping(Interval[] i1, Interval[] i2) {
    List<Interval> res = new ArrayList<Interval>();
    int i = 0;
    int j = 0;
    int endCurr = i1[0].start > i2[0].start ? i2[0].start : i1[0].start;
    while (i < i1.length && j < i2.length) {
        if (i1[i].start > i2[j].start) {
            if (i2[j].start < endCurr) {
                Interval temp = new Interval(i2[j].start, endCurr);
                res.add(temp);
            }
            endCurr = Math.max(i2[j].end, endCurr);
            j++;
        } else {
            if (i1[i].start < endCurr) {
                Interval temp = new Interval(i1[i].start, endCurr);
                res.add(temp);
            }
            endCurr = Math.max(i1[i].end, endCurr);
            i++;
        }
    }
    return res;
}

[extra][inplace convert binary tree to BST]

给一个普通的二叉树，转换成二分查找树BST。
方法一：直接中序遍历并将结果存起来，排序后直接赋值回去，可以维持原有的树的形状。
方法二；如果要求in-place，就先将二叉树建成一个双向链表，然后排序（归并O(NlgN)），然后再将双向链表恢复成二分查找树（经过了平衡，没法维持原本的了）。将链表恢复成BST除了取中间值为根然后递归两边，还有一个tricky的方法是从叶开始往根build，复杂度O(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
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
86
87
88
public class Apple {
    public TreeNode binaryTree2BST(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return root;
        }
        binaryTree2DLL(root);       // 转换成双链表  O(N)
        head = mergeSortDLL(head);  // 归并排序     O(N*logN)
        return DLL2BST();           // 双链表转BST  O(N)
    }
    TreeNode prev = null, head = null;
    private void binaryTree2DLL(TreeNode root) {
        if (root == null) {
            return;
        }
        binaryTree2DLL(root.left);
        
        if (prev == null) {
            head = root;    // 最左边的那个为头节点，一次性赋值
        } else {
            root.left = prev;
            prev.right = root;
        }
        prev = root;
        binaryTree2DLL(root.right);
    }
    private TreeNode mergeSortDLL(TreeNode head) {
        if (head == null || head.right == null) {
            return head;
        }
        TreeNode halfHead = partition(head);
        head = mergeSortDLL(head);
        halfHead = mergeSortDLL(halfHead);
        return merge(head, halfHead);
    }
    private TreeNode partition(TreeNode head) {
        TreeNode fast = head, slow = head;
        while (fast.right != null && fast.right.right != null) {
            fast = fast.right.right;
            slow = slow.right;
        }
        TreeNode mid = slow.right;
        slow.right = null;
        return mid;
    }
    private TreeNode merge(TreeNode first, TreeNode second) {
        if (first == null) {
            return second;
        }
        if (second == null) {
            return first;
        }
        if (first.val < second.val) {
            first.right = merge(first.right, second);
            first.right.left = first;
            first.left = null;
            return first;
        } else {
            second.right = merge(first, second.right);
            second.right.left = second;
            second.left = null;
            return second;
        }
    }
    private TreeNode DLL2BST() {
        int n = countNodes(head);
        return DLL2BST(n);
    }
    private TreeNode DLL2BST(int n) {
        if (n <= 0) {
            return null;
        }
        TreeNode left = DLL2BST(n / 2);    // 左子树的根节点
        TreeNode root = head;              // 
        root.left = left;
        head = head.right;      // 挪到下一个节点为起点
        root.right = DLL2BST(n - n / 2 - 1);    // 减去左边和root节点的剩余数
        return root;
    }
    private int countNodes(TreeNode head) {
        int count = 0;
        while (head != null) {
            count++;
            head = head.right;
        }
        return count;
    }
}

[extra][product between indices]

  • 给一个正数数组，给两个索引x和y，求数组从x到y（inclusive）的积。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public class Apple {
        public int getProduct(int[] nums, int x, int y) {
            if (nums == null || nums.length == 0
            || y < x || y >= nums.length || x < 0) {
                return 0;
            }
            // 缓存cache[i]表示从0到i - 1的积
            int[] cache = new int [nums.length + 1];
            cache[0] = 1;
            for (int i = 1; i <= nums.length; i++) {
                cache[i] = nums[i] * cache[i - 1];
            }
            // 从x到y的积就是"到y的积"除以"到x - 1的积"
            return cache[y + 1] / cache[x];
        }
    }

  • 数组中含有0呢？ 前面的方法不能直接用，难道要用一个n*n的数组穷举出所有情况？其实前面的方法加多个标记0的即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public class Apple {
        public int getProduct2(int[] nums, int x, int y) {
            if (nums == null || nums.length == 0
            || y < x || y >= nums.length || x < 0) {
                return 0;
            }
            int[] cache = new int [nums.length + 1];
            int[] zeroCount = new int [nums.length + 1];
            cache[0] = 1;
            for (int i = 1; i <= nums.length; i++) {
                if (nums[i] = 0) {
                    cache[i] = 1;
                    zeroCount[i] = zeroCount[i - 1] + 1;
                } else {
                    cache[i] = nums[i] * cache[i - 1];
                    zeroCount[i] = zeroCount[i - 1];
                }
            }
            return zeroCount[y + 1] != zeroCount[x]? 0: cache[y + 1] / cache[x];
        }
    }

362. design-hit-counter

实现一个计数器，返回给定时间点之前300秒内的hit数。

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 HitCounter {
    private int[] hits;
    private int[] time;
    final private int TIMEWINDOW = 300;
    /** Initialize your data structure here. */
    public HitCounter() {
        hits = new int [TIMEWINDOW];
        time = new int [TIMEWINDOW];
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        int index = timestamp % TIMEWINDOW;
        if (time[index] != timestamp) {
            time[index] = timestamp;
            hits[index] = 1;
        } else {
            hits[index]++;
        }
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        int count = 0;
        for (int i = 0; i < TIMEWINDOW; i++) {
            if (timestamp - time[i] < TIMEWINDOW) {
                count += hits[i];
            }
        }
        return count;
    }
}

[extra][subarray sum]

求所有等于target的subarray,有点类似209. minimum-size-subarray-sum.
双指针，一前一后，一旦前面挪动后所得的sum太大，就开始挪后面的。

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<int[]> minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int slow = 0, fast = 0, currSum = 0;
        while (fast < nums.length) {
            if (nums[fast] >= s) {
                return 1;
            }
            if (currSum >= s || fast - slow > minLen) {
                minLen = Math.min(minLen, fast - slow);
                currSum -= nums[slow++];
            } else {
                currSum += nums[fast++];
            }
        }
        while (currSum >= s) {
            minLen = Math.min(minLen, fast - slow);
            currSum -= nums[slow++];
        }
        return slow == 0? 0: minLen;
    }
}

anagrams

group问题，定义key：这里就是string按照字母顺序排好序之后的新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
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        if (strs == null || strs.length == 0) {
            return ans;
        }
        Map<String, Integer> map = new HashMap<>();
        for (String str: strs) {
            char[] sChar = str.toCharArray();   // sort str
            Arrays.sort(sChar);             
            String newStr = new String(sChar);  // the key to get the index in ans
            if (map.containsKey(newStr)) {
                int index = map.get(newStr);
                ans.get(index).add(str);
            } else {
                map.put(newStr, ans.size());
                List<String> temp = new ArrayList<>();
                temp.add(str);
                ans.add(temp);
            }
        }      
        return ans;
    }
}

70. climbing-stairs

爬楼梯，每次只能爬1或2步，求共有多少种到达顶楼的方式。
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
26
27
public class Solution {
    public int climbStairs(int n) {
        int[] dp = new int [n + 1];
        dp[0] = 1;
        if (n > 0) {
            dp[1] = 1;
        }
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}
class Solution {
    public int climbStairs(int n) {
        if (n < 2) {
            return 1;
        }
        int prev2 = 1, prev1 = 1, ans = prev2 + prev1;
        for (int i = 2; i <= n; i++) {
            ans = prev2 + prev1;
            prev2 = prev1;
            prev1 = ans;
        }
        return ans;
    }
}

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
25
26
27
28
29
30
31
32
33
class Solution {
    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null
           || num1.length() == 0 || num2.length() == 0) {
            return "";
        }
        int m = num1.length(), n = num2.length();
        int[] result = new int [m + n];
        char[] cnum1 = num1.toCharArray(), cnum2 = num2.toCharArray();
        
        // from least significant bit
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mult = (cnum1[i] - '0') * (cnum2[j] - '0');
                int first = i + j, second = i + j + 1;
                int sum = mult + result[second];    // add carry from prev steps
                result[first] += sum / 10;  // accumulate
                result[second] = sum % 10;  // overwrite
            }
        }
        
        StringBuilder sb = new StringBuilder();
        int i = 0;
        // find the first non-zero item
        while (i < result.length && sb.length() == 0 && result[i] == 0) {
            i++;
        }
        while (i < result.length) {
            sb.append(result[i++]);
        }
        return sb.length() == 0? "0": sb.toString();
    }
}

[extra][even space]

给一个句子，再给一个宽度，要求均匀分配空格。

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
public class Apple {
    private String evenSpace(String input, int width) {
        if (input.length() > width) {
            return input;
        }
        String[] words = input.split(" ");
        int wordLenSum = 0;
        for (int i = 0; i < words.length; i++) {
            wordLenSum += words[i].length();
        }
        
        return putLine(words, width, wordLenSum);
    }
    private String putLine(String[] words, int maxWidth, int wordSum) {
        StringBuilder sb = new StringBuilder(words[start]);
        int spaceSum = maxWidth - wordSum;
        int spaceCount = words.length;
        int mod = spaceSum % spaceCount, quo = spaceSum / spaceCount;
        for (int i = 0; i < words.length; i++) {
            if (mod != 0) {
                int useCount = quo + 1;
                appendSpace(sb, useCount);
                spaceSum -= useCount;
                spaceCount--;
                mod =  spaceSum % spaceCount;
                quo = spaceSum / spaceCount;
            } else {
                appendSpace(sb, quo);
            }
            sb.append(words[i]);
        }
        return sb.toString();
    }
}

32. longest-valid-parentheses

  • 给一个只包含了(和)的字符串，求其中合法匹配的最大子字符串长度。
  • 动态规划，dp[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
    class Solution {
        public int longestValidParentheses(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            int[] dp = new int [s.length()];    // maxLen till curr char (only for valid ')')
            char[] sChar = s.toCharArray();
            int ans = 0;
            for (int i = 0; i < sChar.length; i++) {
                // only ) is count as valid bit
                if (sChar[i] == ')') {      // "xxx)"
                    if (i > 0) {        
                        if (sChar[i - 1] == '(') {  // prev is (, simply add 2 to prevprev
                            dp[i] = 2 + (i > 1? dp[i - 2]: 0);
                        } else {                    // prev is (
                            int prev = i - dp[i - 1] - 1;   // move to the very front of prev slot
                            if (prev >= 0 && sChar[prev] == '(') {  // only ( can match curr )
                                dp[i] = (prev > 0? dp[prev - 1]: 0) + 2 + dp[i - 1];    // check ('s prev
                            }
                        }
                        ans = Math.max(ans, dp[i]);
                    }
                }
                
            }
            return ans;
        }
    }

543. diameter-of-binary-tree

可以普通O(N^2)的DFS或者优化后的O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    private int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        getMaxDepth(root);
        return max;
    }
    private int getMaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getMaxDepth(root.left);  // 左深度
        int right = getMaxDepth(root.right);// 右深度
        
        max = Math.max(max, left + right);  // 形成^的diameter
        return Math.max(left, right) + 1;   // 返回新的深度
    }
}

472. concatenated-words

给一个String的数组，求其中能由其他String拼接而成的字符串。和wordbreak很像。
先根据长度排序，然后从字符串前面（维护一个Set）取字符串，然后就变成了wordbreak了。

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
public class Solution {
    public static List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> result = new ArrayList<>();
        Set<String> preWords = new HashSet<>();
        Arrays.sort(words, new Comparator<String>() {
            public int compare (String s1, String s2) {
                return s1.length() - s2.length();
            }
        });
        for (int i = 0; i < words.length; i++) {
            if (canForm(words[i], preWords)) {
                result.add(words[i]);
            }
            preWords.add(words[i]);
        }
        return result;
    }
	
    private static boolean canForm(String word, Set<String> dict) {
        if (dict.isEmpty()) return false;
	    boolean[] dp = new boolean[word.length() + 1];
	    dp[0] = true;
	    for (int i = 1; i <= word.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(word.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
	    return dp[word.length()];
    }
}

138. copy-list-with-random-pointer

  • 一个链表，每个节点除了含有label和next以外还含有一个指向任意节点的random引用。深复制这个链表。

  • 方法一：用HashMap存放各个链表节点和它对应的复制品。

    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
     /**
     * 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 {
        HashMap<RandomListNode, RandomListNode> map;
        public RandomListNode copyRandomList(RandomListNode head) {
            map = new HashMap<RandomListNode, RandomListNode>();
            if (head == null) {
                return null;
            }
            
            RandomListNode prev = null, curr = head, newHead = null;
            while (curr != null) {
                RandomListNode newNode = null;
                if (map.containsKey(curr)) {
                    newNode = map.get(curr);
                } else {
                    newNode = new RandomListNode(curr.label);
                    map.put(curr, newNode);
                }
                
                if (prev != null) {
                    prev.next = newNode;
                } else {
                    newHead = newNode;
                }
                if (curr.random != null) {
                    if (map.containsKey(curr.random)) {
                        newNode.random = map.get(curr.random);
                    } else {
                        RandomListNode temp = new RandomListNode(curr.random.label);
                        newNode.random = temp;
                        map.put(curr.random, temp);
                    }
                }
                prev = newNode;
                curr = curr.next;
            }
            return newHead;
        }
    }

  • 把每一个拷贝的节点拼接到原节点的后面，这样一轮循环过后所有节点都有了一份拷贝；第二轮循环就是为random赋值了，既然知道原节点之后就是对应的拷贝节点，那random的引用也就可以直接获得了。最后一轮循环则是把拷贝的节点正确地拼接起来，最后返回。

    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 {
        public RandomListNode copyRandomList(RandomListNode head) {
            if (head == null) {
                return null;
            }
            RandomListNode curr = head, currNext = null, currCopy = null;
            while (curr != null) {
                currNext = curr.next;   // 先暂存原节点的next
                
                currCopy = new RandomListNode(curr.label);
                curr.next = currCopy;   // 原节点next指向复制品
                currCopy.next = currNext;   // 复制品next指向原节点的next
                
                curr = currNext;
            }
            curr = head;        // 从原链表头开始遍历
            while (curr != null) {
                if (curr.random != null) {
                    // 节点的next就是它的复制品
                    curr.next.random = curr.random.next;
                }
                curr = curr.next.next;
            }
            
            RandomListNode fakeHead = new RandomListNode(0);
            curr = head;
            currCopy = fakeHead;
            
            // 恢复原链表同时产生复制品链表
            while (curr != null) {
                currNext = curr.next.next;
                
                currCopy.next = curr.next;
                currCopy = curr.next;
                
                curr.next = currNext;
                curr = currNext;
            }
            return fakeHead.next;
        }
    }

139. word-break

给一个字符串，判断能否由给定dict中的单词组成。
当前是否可以取决于”以当前字符结尾、前面某处开头的单词来自于dict”且”该起点往前也是可以的”。

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 Apple {
	public boolean workBreak(String s, List<String> wordDict) {
		if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
			return false;
		}
		Set<String> wordSet = new HashSet<>();
		int maxLen = 0;
		for (String word: wordDict) {
			wordSet.add(word);
			maxLen = Math.max(maxLen, word.length());
		}
		boolean[] dp = new boolean [s.length() + 1];
		for (int i = 1; i <= s.length(); i++) {
			for (int j = i - 1; j >= 0 && i - j <= maxLen; j--) {
				if (dp[j] && wordSet.contains(s.substring(j, i))) {
					dp[i] = true;
					break;
				}
			}
		}
		return dp[s.length()];
	}
}

98. validate-binary-search-tree

验证二叉树是否是BST。

  • 递归检查左节点，然后当前节点与prev比较大小保证从小到达，然后更新prev再潜入右边。
  • 或者用Stack迭代，中序遍历。
  • 或者分而治之，给定节点的范围，判断当前节点是否符合，然后更新两侧的范围再潜入下去。
    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
    public class Apple {
        // 一直往左边潜下去，找到第一个元素，然后设置prev
        private TreeNode prev1 = null;
    	private boolean validateBST1(TreeNode root) {
    		if (root == null) {
    			return true;
    		}
    		if (!validateBST1(root.left)) {
    			return false;
    		}
    		if (prev1 != null && prev1.val >= root.val) {
    			return false;
    		}
    		prev1 = root;
    		return validateBST1(root.right);
    	}
    	private boolean validateBST2(TreeNode root) {
    		if (root == null) {
    			return true;
    		}
    		Stack<TreeNode> stack = new Stack<>();
    		TreeNode prev = null;
    		while (root != null || !stack.isEmpty()) {
    			while (root != null) {
    				stack.push(root);
    				root = root.left;
    			}
    			root = stack.pop();
    			if (prev != null && prev.val >= root.val) {
    				return false;
    			}
    			prev = root;
    			root = root.right;
    		}
    		return true;
    	}
    	private boolean validateBST3(TreeNode root) {
    		return dvcq(root, Long.MIN_VALUE, Long.MAX_VALUE);
    	}
    	private boolean dvcq(TreeNode root, long min, long max) {
    		if (root == null) {
    			return true;
    		}
    		if (root.val <= min || root.val >= max) {
    			return false;
    		}
    		return dvcq(root.left, min, Math.min(root.val, max))
    				&& dvcq(root.right, Math.max(root.val, min), max);
    	}
    }