刷题打卡 －pxu

314. Binary Tree Vertical Order Traversal
make sure the min and max data assign is opposite
    private int min = Integer.MAX_VALUE;
    private int max = Integer.MIN_VALUE;

#200. Number of Islands
didn't notice the grid are chars
char[][] grid
if(grid[row][col] == 1) is not going to work.
should be using:
if(grid[row][col] == '1')

pxu 发表于 2018-5-22 10:32
#200. Number of Islands
didn't notice the grid are chars
char[][] grid

also implemented with union find: the union function should be
parent[pu] = parent[pv];
the grid pos: should be cols*row+ col

#261. Graph Valid Tree
with dfs, 1st, create all the list within the map in advance
2nd: check the status in the end of dfs to make sure all the nodes are touched
with unionfind solution: union method, should be parents[pv] = pu instead of parents[v] = u;
need to check n -1 == edges.length

#210. Course Schedule II
should handle dependency is empty case
  if( prerequisites ==null || prerequisites.length == 0){
      for(int i= 0; i< numCourses;i++){
          res[i] = i;
      }
      return res;
  }

return empty array should be:
if(!dfs(list, i, status, resList)){
                return new int[0];
}

207. Course Schedule
use 3 status
int status[] = new int[numCourses];
used list<list<Integer>> to store the edge information

#269. Alien Dictionary
use topological and dfs
similar with course schedule

17. Letter Combinations of a Phone Number
mistake: should use char as the key of map
map.put('2', Arrays.asList('a','b','c'));

backtrack template:
step 1: in main method: invoked
backtrack(res, new StringBuilder(), digits, 0);

step2: in implementation method, go through  the elements and add, backtrack , remove last elements

loop the possible candidate
int index = digits.charAt(pos) - '0';
        
for(char c: keys[index].toCharArray()){
    sb.append(c);
    backtrack(res,sb,digits, pos+1);
    sb.deleteCharAt(sb.length()-1);
}

#215. Kth Largest Element in an Array
need quickselect to invoke the partition
in the partition, should always check left<=right on each steps!

while(left <= right){
    while(left <=right && nums[left]<= nums[pivot]) left++;
    while(left<=right && nums[right] > nums[pivot]) right--;
    if(left <= right){
        swap(nums,left, right);
    }
}

#127. Word Ladder
use Set<String> wordSet = new HashSet<>(wordList);
use bfs + 26 letters

make a wish: get the offer before the floor reach 300

#126 Word Ladder II
tricky:the used word can not directly removed from the dictionary. The used word is only removed when steps change.
Used to visisted and unvisited set to check and make sure the same word could be added mulitple times in the same level

used bfs to get the graph(reversed way) and dfs to get the list. check word==startword. added word first after the operation, remove it from the list;

used 26 letters to find the right candidates