[leetcode]Search a 2D Matrix II

不知是否最优 。。。 从右上角开始搜 大于 向右走 小于向下走

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

public class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0){ return false; } int row = 0; int col = matrix[0].length-1; while (row >= 0 && row < matrix.length && col >= 0 && col < matrix[0].length){ if (matrix[row][col] == target) return true; if (matrix[row][col] > target) col--; else row++; } return false; } }

[leetcode] Word Ladder

直接BFS..... 有一处搞了很久 发现原来return是转换过程有多少个word... 而不是换了多少个字母

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

public class Solution { public int ladderLength(String beginWord, String endWord, Set<String> wordList) { HashSet<String> notVisited = new HashSet<String>(wordList); boolean found = false; HashSet<String> nextLevel = new HashSet<String>(); HashSet<String> curLevel = new HashSet<String>(); curLevel.add(beginWord); notVisited.remove(beginWord); int level = 1; while (!found && !curLevel.isEmpty()){ if (curLevel.contains(endWord)){ found = true; }else{ level++; } for (String cur:curLevel){ getNextWords(nextLevel, notVisited, cur); } HashSet<String> inter = nextLevel; nextLevel = curLevel; curLevel = inter; nextLevel.clear(); } return found?level:0; } public void getNextWords(HashSet<String> nextWord, HashSet<String>notVisited, String current){ char []possible = current.toCharArray(); for (int i = 0; i < possible.length; i++){ char origin = possible[i]; for (char a = 'a'; a <= 'z'; a++){ if (a != origin){ possible[i] = a; String temp = String.valueOf(possible); if (notVisited.contains(temp)){ nextWord.add(temp); notVisited.remove(temp); } } } possible[i] = origin; } } }

[leetcode]Word Ladder II

这是条难题（base on time and memory limit) 大概思路就是记录每个字的parents.. 还有用hashset来装next level这样可以避免重复 当整个next level都生成完毕之后...就可以把notVisited里面的next level word 去掉 一举两得..既可以避免重复visit又可以满足同一个word有multiple parents的情况... **有个地方就是注意同样字母的时候 不应该算进possible

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

public class Solution { List<List<String>> result = new ArrayList<List<String>>(); public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) { HashMap<String, List<String>> parents = new HashMap<String, List<String>>(); HashSet<String> notVisited = new HashSet<String>(wordList); boolean found = false; HashSet<String> nextLevel = new HashSet<String>(); HashSet<String> curLevel = new HashSet<String>(); curLevel.add(beginWord); notVisited.remove(beginWord); while (!found && !curLevel.isEmpty()){ for (String cur:curLevel){ getNextWords(parents, nextLevel, notVisited, cur); } for (String next:nextLevel){ notVisited.remove(next); } if (nextLevel.contains(endWord)) found = true; HashSet<String> inter = nextLevel; nextLevel = curLevel; curLevel = inter; nextLevel.clear(); } if (!parents.containsKey(endWord)) return new ArrayList<List<String>>(); generateResult(parents, beginWord, endWord, new LinkedList<String>()); return result; } public void generateResult(HashMap<String, List<String>> parents, String start, String end, List<String> fromPrev){ if (start == end){ LinkedList<String> temp = new LinkedList<String>(fromPrev); temp.addFirst(start); result.add(temp); return; } List<String> parent = parents.get(end); ((LinkedList<String>) fromPrev).addFirst(end); for (String upper:parent){ generateResult(parents, start, upper, fromPrev); } ((LinkedList<String>) fromPrev).removeFirst(); } public void getNextWords(HashMap<String, List<String>> parents, HashSet<String> nextWord, HashSet<String>notVisited, String current){ char []possible = current.toCharArray(); for (int i = 0; i < possible.length; i++){ char origin = possible[i]; for (char a = 'a'; a <= 'z'; a++){ if (a != origin){ possible[i] = a; String temp = String.valueOf(possible); if (notVisited.contains(temp)) { nextWord.add(temp); List<String> parent = parents.containsKey(temp)?parents.get(temp):new ArrayList<String>(); parent.add(current); parents.put(temp, parent); } } } possible[i] = origin; } } }

next topic

divide and conquer

Backtracking

[leetcode]Surrounded Regions

这题leetcode设的memory好紧... 最后把recursion换成iterative做才过.. 还有BFS忘了track visited loop 搞了很久 

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

public class Solution { public void solve(char[][] board) { if (board == null || board.length == 0 || board[0].length == 0) return; for (int i = 0; i < board.length; i++){ if (board[i][0] == 'O') filpEdgeRegionToOne(board, i, 0); if (board[i][board[0].length-1] == 'O') filpEdgeRegionToOne(board, i, board[0].length-1); } for (int i = 0; i < board[0].length; i++){ if (board[0][i] == 'O') filpEdgeRegionToOne(board, 0, i); if (board[board.length-1][i] == 'O') filpEdgeRegionToOne(board, board.length-1, i); } for (int i = 0; i < board.length; i++){ for (int j = 0; j < board[0].length; j++){ if (board[i][j] == 'O') board[i][j] = 'X'; else if (board[i][j] == '1') board[i][j] = 'O'; } } } void filpEdgeRegionToOne(char[][]board, int i, int j){ int dirs[][] = {{1,0},{-1,0},{0,1},{0,-1}}; Queue<int[]> queue = new LinkedList<int[]>(); queue.add(new int[]{i,j}); while (!queue.isEmpty()){ int []location = queue.poll(); if (board[location[0]][location[1]] == 'O'){ board[location[0]][location[1]] = '1'; for (int k = 0; k < dirs.length; k++){ int x = location[0]+dirs[k][0]; int y = location[1]+dirs[k][1]; if (checkValid(board, x, y)) queue.add(new int[]{x,y}); } } } } boolean checkValid(char[][] board, int i, int j){ return !(i < 0 || i >= board.length || j < 0 || j >= board[i].length || board[i][j] == 'X' || board[i][j] == '1'); } }

[leetcode] Course Schedule II

貌似这是Topological sorting...上网看了下Topological的解释 思路就清晰了....

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 Solution { public int[] findOrder(int numCourses, int[][] prerequisites) { int[] inDegree = new int[numCourses]; List<HashSet<Integer>> out = new ArrayList<HashSet<Integer>>(); for (int i = 0; i < numCourses; i++){ out.add(new HashSet<Integer>()); } for (int i = 0; i < prerequisites.length; i++){ if (!out.get(prerequisites[i][1]).contains(prerequisites[i][0])){ inDegree[prerequisites[i][0]]++; out.get(prerequisites[i][1]).add(prerequisites[i][0]); } } Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 0; i < inDegree.length; i++){ if (inDegree[i] == 0) queue.add(i); } int result[] = new int[numCourses]; int curPtr = 0; while (!queue.isEmpty()){ int current = queue.poll(); result[curPtr++] = current; HashSet<Integer> outCourses = out.get(current); for (Integer temp:outCourses){ inDegree[temp]--; out.get(temp).remove(current); if (inDegree[temp] == 0) queue.add(temp); } } if (curPtr != numCourses) return new int[0]; return result; } }

[leetcode]Minimum Height Trees

这条题考的就是对graph和tree的熟悉程度... 记着tree maximum只可能有2个nodes能成为最短path的root... 围绕着这个做文章.. 不停地删leaf..剩下的（小于等于2）的结果就是所要的结果了..

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

public class Solution { public List<Integer> findMinHeightTrees(int n, int[][] edges) { int degree[] = new int[n]; HashMap<Integer, List<Integer>> nodes = new HashMap<Integer, List<Integer>>(); for (int i = 0; i < edges.length; i++){ int a = edges[i][0]; int b = edges[i][1]; List<Integer> listA = nodes.containsKey(a)?nodes.get(a):new ArrayList<Integer>(); List<Integer> listB = nodes.containsKey(b)?nodes.get(b):new ArrayList<Integer>(); listA.add(b); listB.add(a); nodes.put(a, listA); nodes.put(b, listB); degree[a]++; degree[b]++; } int remain = n; Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 0; i < n; i++){ if(degree[i] == 1) queue.add(i); } while (remain > 2){ int size = queue.size(); for (int i = 0; i < size; i++){ int leaf = queue.poll(); remain--; degree[leaf]--; for (Integer neighbor:nodes.get(leaf)){ degree[neighbor]--; if (degree[neighbor] == 1) queue.add(neighbor); } } } List<Integer> result = new ArrayList<Integer>(queue); if (n == 1) result.add(0); return result; } }