部分题思路

10 Regular Expression Match

• Back Tracking
  • boundary condition: sLen == 0 || pLen == 0
  • then deal with p.charAt(1) == '*' and other

if(pLen == 0) return sLen == 0; // pLen = a*? ;
if(sLen == 0) return pLen == 0 || pLen > 1 && p.charAt(1) == '*' && isMatch(s, p.substring(2));
if(pLen > 1 && p.charAt(1) == '*') {
	return (isMatch(s, p.substring(2)) || ((sLen > 0 && (s.charAt(0) == p.charAt(0)) || p.charAt(0) == '.') && isMatch(s.substring(1), p))); // when try to get s.charAt(0) make sure s is not empty
}
else {
	return (sLen > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1), p.substring(1)));
}

• Dynamic Programming

23 Merge k Sorted Lists

• Heap​

ListNode res = new ListNode(0);
return res.next;

25 Reverse Nodes in k Group

• count and revers

for(int i = 0; i < k; i++) {
    next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
}

33 Search in Rotated Array

• Binary Search
  • find the realMin
  • to get the related position of nodes in Rotated Array by realMid = (mid + realMin) % nums.length
  • use mid else end = mid - 1; // use mid

while(start < end) { // get the real mid
    mid = start + (end - start) / 2;
    if(mid >= 1 && nums[mid] < nums[mid-1]) {
        start = mid;
        break;
    }
    if(nums[mid] < nums[end]) end = mid - 1;
        else start = mid + 1;
    }

43 Multiply String

• String
  • use int[] prod = new int[len1 + len2]; to store each production of every two digits
  • two for loops to compute prod
  • convert prod to string, from end to begin // when go through from end, must use i = len-1 and i--
  • remove ‘0’ at the beginning of result, but don’t remove the last ‘0’

49 Group Anagrams

• Question: output format

for(int j = 0; j < strs[i].length(); j++) {
	key *= PRIMES[strs[i].charAt(j) - 'a'];
}
if(map.containsKey(key)) {
	lol.get(map.get(key)).add(strs[i]);
}
else {
	List t = new LinkedList<String>();
	t.add(strs[i]);
	lol.add(t);
	map.put(key, index++);
}

56 Merge Intervals

if(intervals.get(i).start <= end) { // <=

##76 Minimum Window Substring

• Hash Table, use int[128] to store remaining char

int start = 0, end = 0, min = Integer.MAX_VALUE, minStart = 0;
while(end <= s.length() && start < s.length()) { // end <= s.length()
	if(require > 0) { // end move forward, require > 0
	if(end == s.length()) break; // in case that t is longer than s
     ...
    }
return min == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart+min); //take care that t might be longer than s

117 Populating Next Right Pointers in Each Node II

-Dummy point at left of leftmost node

while(root != null) { //
    if(root.left != null) {
        curNode.next = root.left;
        curNode = curNode.next;
    }
    if(root.right != null) {
        curNode.next = root.right;
        curNode = curNode.next;
    }
    root = root.next;
}

133 Clone Graph

• DFS + map
• use map to denote whether a node has been visited

return map.get(node.label); // must return what we added early, if we return node, would be a reference of original graph
map.put(newNode.label, newNode); //not map.put(node.label, node);
for(UndirectedGraphNode neighbor : node.neighbors) {
	newNode.neighbors.add(cloneGraph(neighbor));
}

158 Read N Characters Given Read4 II - Call multiple times

• Two pointer

int bufCnt = 0;
int bufPtr = 0;
char[] innerBuf = new char[4];
int ptr = 0;

161 One Edit Distance

return s.substring(i).equals(t.substring(j+1)) || s.substring(i+1).equals(t.substring(j+1));
return j == t.length()-1;

200 Number of Islands

// 第一次'0'的单引号漏掉了，找了很久才发现！！！
if(i < 0 || i == grid.length || j <0 || j == grid[i].length || grid[i][j] != '1') {
	return;
}

215 Kth Largest Element in an Array

• D ivide and Conquer
• 每次更新begin 和 end之后要拿begin和end来做边界条件，而不是0和 nums.length - 1 来做边界，这一点在其他时候也要注意，边界条件尽量不要用硬编码
• don’t miss the boundary condition，if(left == right) return nums[left];
• Heap
• PriorityQueue pq = new PriorityQueue(k+1); // add(), poll();

221 Maximal Square

• DP
• 有两个矩阵，一个表示路，一个用来计数，当需要判断有没有路并在计数上叠加时很容易比错矩阵
• 优化：开一个大一层的计数矩阵来计数就可以不用初始化计数矩阵的上左两边了

253 Meeting Rooms II

• Heap

Arrays.sort(intervals, new Comparator<Interval>() {
	public int compare(Interval a, Interval b) { return a.start - b.start; }
});
PriorityQueue<Interval> pq = new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>() {
	public int compare(Interval a, Interval b) { return a.end - b.end;}
});

261 Graph Valid Tree

• Union Find

return n == edges.length + 1; // not always rigth
while(sets[target] != -1) { // use while not if

• DFS & BFS

265 Paint House II

introduce two min: min1 min2
//current color is the same as last use min2
else use min1
costs[i][j] += last2 < 0 ? 0 : costs[i-1][last2];  // use former result"i-1"
update min1 min2
if(min1 < 0 || costs[i][j] < costs[i][min1]) {
	min2 = min1;
	min1 = j;
}
else if(min2 < 0 || costs[i][j] < costs[i][min2]) { //use else 	here to get the second min
	min2 = j;
}

269 Alien Dictionary

• Topological Sort

List<int[]> edges = new LinkedList<int[]>();
String str1 = "", str2 = "";
Queue<Integer> queue = new LinkedList<Integer>();
String res = "";
int[] inDegree = new int[26];
int num = 0;
// get edges(char pair)
// initial inDegree
// caculate inDegree
// find nodes whose inDegree == 0
return res.length() == num ? res : ""; // have to judge whether

149 Max Points on a Line

• Map<x, Map<y, n>>
• <dx, dy> to identify whether on the same line, in order to deal with vertical situation
• overlap variable deal with overlap situation

if(x == 0 && y == 0) { //
overlap++;
continue;
}

• res = Math.max(res, max + overlap + 1); // +1 count the node itself