ftalm: October 2015

Friday, October 30, 2015

[leetcode] Binary Tree Upside Down

做这题的一个提升就是先把recursive call当作能work的api.. 解决小问题先，再看小节然后大问题其实就解决了

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
     if (root == null || root.left == null){
      return root;
     }
        TreeNode one = upsideDownBinaryTree(root.right);
        TreeNode two = upsideDownBinaryTree(root.left);
        root.left.left = one;
        root.left.right = root;
        root.left = null;
        root.right = null;
        return two;
    }
}

[leetcode] Unique Binary Search Tree

Essentially a DP problem
number[i] = number[0] * number[i-1] + number[1]*number[i-1-1]......number[i-1]*number[0]
左边有n Node的时候右边最多只有 i-n-1 因为有一个在中间。。。而这些都是已经算过了的

public class Solution {
    public int numTrees(int n) {
        int check[] = new int[n+1];
        check[0] = 1;
        check[1] = 1;
        for (int i = 2; i <= n; i++){
            check[i] = 0;
            for (int j = 0; j <= i-1; j++){
                check[i] += (check[j]*check[i-j-1]);
            }
        }
        
        return check[n];
    }
}

[leetcode] Binary Tree Inorder Traversal

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null){
         return result;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.add(root);
        root = root.left;
        while(!stack.isEmpty()){
     if (root == null){
         TreeNode temp = stack.pop();
  result.add(temp.val);
  root = temp.right;
      }
      if (root != null){
          stack.push(root);
   root = root.left;
      }
 }

        return result;
    }
}

Wednesday, October 28, 2015

[leetcode] Dungeon Game

想了半天没想到和binary search有什么关系点了下tag发现是dp那就很简单了
bottom up, 算出沿路negative的最小值...
具体逻辑看code吧。。

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
     if (dungeon == null || dungeon.length < 1 || dungeon[0].length < 1){
      return 0;
     }
        int rowLen = dungeon.length;
        int columnLen = dungeon[0].length;
        int lastRow = rowLen-1;
        int lastColumn = columnLen-1;
        int dun[] = new int[columnLen];
        dun[lastColumn] = dungeon[lastRow][lastColumn] <= 0?
                             dungeon[lastRow][lastColumn]:0;
        for (int i = lastColumn-1; i >= 0; i--){
            dun[i] = dun[i+1]+dungeon[lastRow][i] <= 0?
                 dun[i+1]+dungeon[lastRow][i]:0;
        }
        for (int i = dungeon.length-2; i >= 0; i--){
         dun[lastColumn] = dungeon[i][lastColumn] + dun[lastColumn] <= 0?dungeon[i][lastColumn] + dun[lastColumn]:0;
         for (int j = lastColumn-1; j >= 0; j--){
          int goRight = dun[j+1]+dungeon[i][j];
          int goDown = dun[j]+dungeon[i][j];
          if (Math.max(goRight, goDown) > 0){
           dun[j] = 0;
          }else{
           dun[j] = Math.max(goRight, goDown);
          }
         }
        }
        return Math.abs(dun[0])+1;
    }
}

Tuesday, October 27, 2015

[leetcode] Pow(x,n)

二分法...
不断地使用n/2的结果来结合出新的数...
一个Case是INT_MIN转成正数会overflow.所以先加一再除回去。

public class Solution {
    public double myPow(double x, int n) {
        return n < 0?(1/recursivePow(x, Math.abs(n+1))/x): 
                     recursivePow(x, n);
    }
    
    private double recursivePow(double x, int n){
        if (n == 0){
            return 1;
        }
        double v = recursivePow(x, n/2);
        return n%2==0?v*v:v*v*x;
    }
}

Monday, October 26, 2015

[leetcode] course schedule

这条题就是把课的constraints 转化成有向图，然后dfs看所有生成的图有没有cycle
一开始会time limit exceed.后来做pruning了就过了..

public class Solution {
    boolean graph[][];
    boolean check[];
    int noCycleFromIndex[];
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        noCycleFromIndex = new int[numCourses];
        graph = new boolean[numCourses][numCourses];
        check = new boolean[numCourses];
        for (int i = 0; i < prerequisites.length; i++){
            graph[prerequisites[i][0]][prerequisites[i][1]] = true;
        }
        for(int i = 0; i < check.length; i++){
            if (noCycleFromIndex[i] == -1 || !checkGraph(i)){
                return false;
            }
        }
        return true;
    }
    
    private boolean checkGraph(int course){
        if (check[course] || noCycleFromIndex[course] == -1){
            return false;
        }
        
        if (noCycleFromIndex[course] == 1){
            return true;
        }
        
        check[course] = true;
        for (int i = 0; i < check.length; i++){
            if (graph[course][i]&&!checkGraph(i)){
                noCycleFromIndex[course] = -1;
                return false;
            }
        }
        check[course] = false;
        noCycleFromIndex[course] = 1;
        return true;
    }
    
}

[leetcode]Number of Islands

每遇到没走过且是1的格立即increase total 再dfs把连着的1都记录下来...
然后move on 去下一个点...

public class Solution {
    HashSet<String> visited = new HashSet<String>();
    char[][] grid;
    public int numIslands(char[][] grid) {
        this.grid = grid;
        int total = 0;
        for (int i = 0; i < grid.length; i++){
            for (int j = 0; j < grid[0].length; j++){
                if (grid[i][j] == '1' && !visited.contains(""+i+","+j)){
                    total++;
                    dfs(i, j);
                }
            }
        }
        return total;
    }
    
    private void dfs(int x, int y){
        String location = ""+x+","+y;
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length 
                 || grid[x][y] == '0' || visited.contains(location)){
            return;
        }
        visited.add(location);
        dfs(x, y+1);
        dfs(x, y-1);
        dfs(x+1, y);
        dfs(x-1, y);
        return;
    }
}

[leetcode] clone graph

典型DFS题目。。用一个HashMap把已经clone过的node记住... 要是遇到了就不进行克隆过程直接拿来用

public class Solution {
    HashMap<UndirectedGraphNode, UndirectedGraphNode> visited = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null){
            return null;
        }
        UndirectedGraphNode root = dfsCopy(node);
        return root;
    }
    
    private UndirectedGraphNode dfsCopy(UndirectedGraphNode node){
        if (visited.containsKey(node)){
            return visited.get(node);
        }
       
        UndirectedGraphNode root = new UndirectedGraphNode(node.label);
        visited.put(node, root);
        for (int i = 0; i < node.neighbors.size(); i++){
            root.neighbors.add(dfsCopy(node.neighbors.get(i)));
        }
        
        return root;
    }
}

首先想到的solution是把array排列一下... 然后从小到大去sum candy总数。每当遇到一个新的数就把single round candy 增加1

..发现理解题意错了... 原来rating高的时候只要比neighbor 高就可以了
。。还有一个很独特的case 题目好像没说清楚..就是当两个neighbor rating一样高的时候后者只能拿一颗糖

思路：
candy[i] = candy[i-1]+1 when ratings[i] > ratings[i-1]
1 when ratings[i] == ratings[i-1]
candy[i-1]-1 when ratings[i] < ratings[i-1] (adjustment needs to be made)

首先向左扫描一次... 把递增的都算好。。递减的就直接assign 1
然后再向右扫描一次把错的值adjust 回来

public class Solution {
    public int candy(int[] ratings) {
   if (ratings == null || ratings.length == 0){
    return 0;
   }

   int localCache[] = new int[ratings.length];
   localCache[0] = 1;
   for (int i = 1; i < ratings.length; i++){
    if (ratings[i] > ratings[i-1]){
     localCache[i] = localCache[i-1]+1;
    }else{
     localCache[i] = 1;
    }
   }
   int sum = localCache[localCache.length-1];
   for (int i = ratings.length-2; i >= 0; i--){
    if (ratings[i] > ratings[i+1] && localCache[i] <= localCache[i+1]){
     localCache[i] = localCache[i+1]+1;
    }
    sum += localCache[i];
   }

   return sum;
    }
}

[leetcode] gas station

先走一圈算算总油量是否大于等于耗油量，若不是的话没有solution.

有的话以i作为起点... 到j, 如若 sum[i..j] < 0 就是 i 不能到j... 立即将j+1作为起点...如此类推。
直到找到一个点k 到结尾 n-1 能令sum[k..n-1] >= 0的

证明为什么这样可以成立的话.. 可以想象一个一个含有正数负数的数列。。这个数列的和既然>=0, 那么必然正数和>=负数和...

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
     if (gas==null || cost == null||gas.length != cost.length){
      return -1;
     }
        int sum = 0;
        for (int i = 0; i < gas.length; i++){
         sum += (gas[i]-cost[i]);
        }
        if (sum < 0){
         return -1;
        }
        int start = 0;
        sum = 0;
        for (int i = 0; i < gas.length; i++){
         sum += gas[i];
         sum -= cost[i];
         if (sum < 0){
          sum = 0;
          start = i+1;
         }
        }

        return start;
    }
}

[leetcode] Jump Game I & II

每走到新的一格更新还可以走多少步然后一直走下去直到不可以再走或者到达最后

public class Solution {
    public boolean canJump(int[] nums) {
     int furthese = 0;
     int stepLeft = nums[0];
     int currentIndex = 0;
     while (stepLeft != 0 && currentIndex < nums.length){
      stepLeft--;
      currentIndex++;
      if (currentIndex != nums.length)
          stepLeft = Math.max(stepLeft, nums[currentIndex]);
     }

     return currentIndex == nums.length || currentIndex == nums.length-1;
    }
}

Jump Game II
今天重新看了次不会做...
再来
把整个跳跃过程分成几块..
从起点到第一块能cover的最远处，每经过一个element算一下下一块能够cover到多远.. 当第一块用完之后改用第二块... 这里增加一个跳... 如此类推。

public class Solution {
    public int jump(int[] nums) {
        if (nums==null||nums.length==0||nums.length==1){
            return 0;
        }
        int result = 0;
        int coverage = 0;
        int currentBlock = 0;
        for (int i = 0; i < nums.length; i++){
            if (i > currentBlock){
                currentBlock = coverage;
                result++;
            }
            
            coverage = Math.max(coverage,nums[i]+i);
        }
        
        return result;
    }
}

[leetcode]Largest Number

这题没想到怎么对比前续相同的string的前后....
后来发现可以直接对比究竟是s1+s2大还是s2+s1大....就可以了
还有一个case是当 array里面全是0，长度大于等于2的时候

public class Solution {
    public String largestNumber(int[] nums) {
        String[] result = new String[nums.length];
        for (int i = 0; i < nums.length; i++){
            result[i] = ""+nums[i];
        }
        Arrays.sort(result, new Comparator<String>(){
            public int compare(String s1, String s2){
                String o1 = s1+s2;
                String o2 = s2+s1;
                return o2.compareTo(o1);
            }
        });
        String output = "";
        for (int i = 0; i <result.length; i++){
            output += result[i];
        }
        if (output.charAt(0)=='0'){
            return "0";
        }
        return output;
    }
}

Sunday, October 25, 2015

[leetcode] Insertion Sort List

开一个新list, 然后逐个逐个把input的node 插到新list里面

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        while (head != null){
            ListNode pre = dummy;
            ListNode next = dummy.next;
            ListNode current = head;
            head = head.next;
            while (next != null && next.val < current.val){
                pre = next;
                next = next.next;
            }
            pre.next = current;
            current.next = next;
        }
        return dummy.next;
    }
}

Thursday, October 22, 2015

[leetcode] Maximal Square

好吧。我是看了提示
就是每一格都是代表它所在的正方形的右下角...
可以表示为
size[i][j] = min(size[i-1][j-1], size[i][j-1], size[i-1][j])+1
implementation 可以直接用一个滚动数组instead of 2d Array

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix == null||matrix.length==0||matrix[0].length==0){
            return 0;
        }
        int maxSquare = 0;
        int []row = new int[matrix[0].length];
        for (int i = 0; i < matrix[0].length; i++){
            row[i] = matrix[0][i] - '0';
            maxSquare = Math.max(maxSquare, row[i]);
        }
        for (int i = 1; i < matrix.length; i++){
            int temp = row[0];
            row[0] = matrix[i][0] - '0';
            for (int j = 1; j < matrix[0].length; j++){
                int hold = row[j];
                if (matrix[i][j] != '0'){
                    row[j] = Math.min(row[j], Math.min(row[j-1], temp))+1;
                    maxSquare = Math.max(maxSquare, row[j]*row[j]);
                }else{
                    row[j] = 0;
                }
                temp = hold;
            }
        }
        return maxSquare;
    }
}

[leetcode]Maximal Rectangle

这题也是做一次想一次

其实就是base on largest rectangle in histogram的idea

从上到下把每行当作histogram的地基再生成对应高度然后交给largest rectangle去算面积

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        int []rolling = new int[matrix[0].length+1];
        int maxArea = 0;
        for (int i = 0; i < matrix.length; i++){
            for (int j = 0; j < matrix[i].length; j++){
                rolling[j] = matrix[i][j] == '0'?0:rolling[j]+1;
            }
            maxArea = Math.max(maxArea, findLargest(rolling));
        }
        return maxArea;
    }

    private int findLargest(int []height){
        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        for (int i = 0; i < height.length; i++){
            while (!stack.isEmpty() && height[i] < height[stack.peek()]){
                int index = stack.pop();
                int width = i-(stack.isEmpty()?0:(stack.peek()+1));
                max = Math.max(max, height[index]*width);
            }
            stack.push(i);
        }
        return max;
    }
}

public class Solution {
    public int maximalRectangle(char[][] matrix) {
     if (matrix == null || matrix.length == 0){
      return 0;
     }
        int rolling[] = new int[matrix[0].length];
        int maxArea = 0;
        for (int i = 0; i < matrix.length; i++){
         for (int j = 0; j < matrix[i].length; j++){
          rolling[j] = (matrix[i][j] == '0'?0:rolling[j]+1);
         }
         maxArea = Math.max(maxArea, maxAreaHistogram(rolling));
        }
        return maxArea;
    }

    public int maxAreaHistogram(int histogram[]){
     if (histogram == null){
      return 0;
     }
     Stack<Integer> stack = new Stack<Integer>();
     int dummyHis[] = Arrays.copyOf(histogram, histogram.length+1);
     int i = 0;
     int maxArea = 0;
     while (i < dummyHis.length){
      if (stack.isEmpty() || dummyHis[i] >= dummyHis[stack.peek().intValue()]){
       stack.push(i++);
      }else{
       int temp = stack.pop().intValue();
       maxArea = Math.max(maxArea, dummyHis[temp]*(stack.isEmpty()?i:i-stack.peek().intValue()-1));
      }
     }
     return maxArea;
    }
}

[leetcode] Largest Rectangle in Histogram

这题做了好几遍都是每次做要想很久甚至要搜索..
这里纪录下来印象深刻点

重点是用一个base on nums[index]递增的stack.. 来记录index...
一旦遇到比stack top小的 pop out.. 接着用当前i减去stack top之前的数再减1来计算宽度 (因为stack top之前的index代表着第一个比stack top小的高，这样求宽度就对了）

edge case 在最后加一个0来trigger 最后的结果计算
参考这个网址里的图：http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html
文章写得太繁琐了不过。

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) return 0;
        Stack<Integer> stack = new Stack<Integer>();
        int h2[] = Arrays.copyOf(height, height.length+1);
        int maxArea = 0;
        for (int i = 0; i < h2.length; i++){
            while (!stack.isEmpty() && h2[stack.peek()] > h2[i]){
                int index = stack.pop();
                int width = i - (stack.isEmpty()?0:(stack.peek())+1);
                maxArea = Math.max(maxArea, h2[index]*width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0){
            return 0;
        }
        int i = 0;
        int maxArea = 0;
        Stack<Integer> stack = new Stack<Integer>();
        int[] copyHeight = Arrays.copyOf(height, height.length+1);
        while(i < copyHeight.length){
            if (stack.isEmpty() || copyHeight[i] >= copyHeight[stack.peek()]){
                stack.push(i++);
            }else{
                maxArea = Math.max(maxArea, copyHeight[stack.pop()]*(stack.isEmpty()?i:i-stack.peek()-1));
                if (stack.isEmpty()&&i!=height.length){
                    stack.push(i);
                }
            }
        }
        return maxArea;
    }
}

[leetcode] Perfect Squares

这题我先从recursion入手... 把recursive case写出来(top to bottom) 然后再尝试 (Bottom to top)转成DP problem去解决
发现
f(n) = Math.min(f(k*k)+f(n-k*k)) if n is not a perfect square, k is the largest number < square root of n)
1 if n is a perfect square

**有人用Lagrange's Four-Square Theorem 更快可以解决。

public class Solution {
    public int numSquares(int n) {
        int p[] = new int[n+1];
        p[0] = 0;
        p[1] = 1;
        for (int i = 2; i <= n; i++){
         int largestSquare = (int)Math.sqrt((double)i);
         if (largestSquare*largestSquare == i){
             p[i] = 1;
         }else{
             p[i] = Integer.MAX_VALUE;
             for (int j = largestSquare; j>=1; j--){
              p[i] = Math.min(p[i], p[j*j]+p[i-j*j]);
             }
         }
        }
        return p[n];
    }
}

Wednesday, October 21, 2015

[leetcode] Climbing Stairs

每一步都是靠前一步和前两步决定的
currentstep = previousstep+previousTwoSteps
这样直接bottom up 上去就好了

public class Solution {
    public int climbStairs(int n) {
        if (n <= 1){
            return 1;
        }
        int i_1 = 1;
        int i_2 = 1;
        int result = 0;
        for (int i = 2; i <= n; i++){
            result = i_1 + i_2;
            i_2 = i_1;
            i_1 = result;
        }
        
        return result;
    }
}

[leetcode] Unique Binary Search Trees

这题之前写过但现在一看一点思路也没有.
搜索到的答案很巧妙，希望下次看到类似的可以举一反三

每个含有n个node的binary tree.. 里面每个数字k都可以作为root, 然后左边会有k-1个node, 右边则有n-k-1个node ... 而左边右边的可能性则会在bottom up的过程中早已计算好,可以直接用
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(0)

public class Solution {
    public int numTrees(int n) {
        if (n == 0){
            return 1;
        }
        int p[] = new int[n+1];
        p[0] = 1;
        p[1] = 1;
        for (int i = 2; i <= n; i++){
            for (int j = 0; j < i; j++){
                p[i] += (p[j]*p[i-j-1]);
            }
        }
        return p[n];
    }
}

Tuesday, October 20, 2015

[leetcode] Word Break II

这题DFS的话会有很多重复计算分支
所以参照Word Break 里面的lookup, 先建一个table 来知道那段是有solution的才DFS进去
这里是从string尾部开始做DFS的

*其实我觉得还可以更加快。。就是建一个hashtable 然后bottom up 上去可以进一步减少DFS的次数，下一pass的时候试下吧

public class Solution {
    boolean[] lookup;
    List<String> result = new ArrayList<String>();
    public List<String> wordBreak(String s, Set<String> wordDict) {
        if (s.length() == 0){
            return result;
        }
        constructLookup(s, wordDict);
        dfs(s, wordDict, s.length()-1, "");
        return result;
    }
    
    private void dfs(String s, Set<String> wordDict, int currentIndex, String strFromUpper){
        if (wordDict.contains((s.substring(0, currentIndex+1)))){
            result.add(s.substring(0, currentIndex+1)+strFromUpper);
        }
        
        for(int i = currentIndex; i >= 1; i--){
            if (lookup[i-1] && wordDict.contains(s.substring(i, currentIndex+1))){
                String tempStr = " "+s.substring(i, currentIndex+1)+strFromUpper;
                dfs(s, wordDict, i-1, tempStr);
            }
        }
    }
    
    private void constructLookup(String s, Set<String> wordDict){
        lookup = new boolean[s.length()];
        if (wordDict.contains(s.substring(0,1))){
            lookup[0] = true;
        }
        for (int i = 1; i < s.length(); i++){
            lookup[i] = wordDict.contains(s.substring(0, i+1));
            for (int j = i-1; j >= 0 && !lookup[i]; j--){
                lookup[i] = lookup[j] && wordDict.contains(s.substring(j+1, i+1));
            }
        }
        return;
    }
}

[leetcode] Word Break

这题可以用Dynamic programming 解答.
subproblem[i] 表示 0到i的substring 能不能被间开..
subproblem[i] = subproblem[j] && substring[j+1,i+1) is in dictionary

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if (s.length() == 0){
            return true;
        }
        boolean []lookup = new boolean[s.length()];
        lookup[0] = wordDict.contains(s.substring(0,1));
        for (int i = 1; i < s.length(); i++){
            lookup[i] = wordDict.contains(s.substring(0, i+1));
            for (int j = i-1; j >= 0 && !lookup[i]; j--){
                lookup[i] = lookup[j] && wordDict.contains(s.substring(j+1,i+1));
            }
        }
        return lookup[s.length()-1];
    }
}

[leetcode]Add and Search Word - Data structure design

这题就是在Implement Trie (Prefix Tree) 基础上加个DFS

public class WordDictionary {
    TrieNode root = new TrieNode();
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++){
            char temp = word.charAt(i);
            if (!node.hasChild(temp)){
                node.addChild(temp);
            }
            node = node.getChild(temp);
        }
        node.setNodeAWordEnd();
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    public boolean search(String word) {
        return dfs(word, root, 0);
    }

    private boolean dfs(String word, TrieNode root, int currentIndex){
        if (currentIndex == word.length()){
            return root.isNodeWordEnd();
        }
        char currentChar = word.charAt(currentIndex);
        if (root.hasChild(currentChar)){
            return dfs(word, root.getChild(currentChar), currentIndex+1);
        }

        if (currentChar == '.'){
            Iterator<TrieNode> listOfChildren = root.getChildren().values().iterator();
            while (listOfChildren.hasNext()){
                if (dfs(word, listOfChildren.next(), currentIndex+1)){
                    return true;
                }
            }
        }

        return false;
    }
}


class TrieNode {
    HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
    boolean isWord = false;
    char currentChar;

    public TrieNode() {
        
    }

    public TrieNode(char in){
        currentChar = in;
    }

    public void addChild(char kid){
        if (children.containsKey(kid)){
            return;
        }
        children.put(kid, new TrieNode(kid));
    }


    public boolean hasChild(char kid){
        return children.containsKey(kid);
    }

    public TrieNode getChild(char kid){
        if (!hasChild(kid)){
            return null;
        }
        return children.get(kid);
    }

    public boolean isNodeWordEnd(){
        return isWord;
    }
    
    public void setNodeAWordEnd(){
        isWord = true;
    }
    
    public HashMap<Character, TrieNode> getChildren(){
        return children;
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

[leetcode] Implement Trie (Prefix Tree)

没什么好说的。code非常直观

class TrieNode {
    // Initialize your data structure here.
    HashMap children = new HashMap();
    boolean isWord = false;
    char currentChar;

    public TrieNode() {
        
    }

    public TrieNode(char in){
        currentChar = in;
    }

    public void addChild(char kid){
        if (children.containsKey(kid)){
            return;
        }
        children.put(kid, new TrieNode(kid));
    }


    public boolean hasChild(char kid){
        return children.containsKey(kid);
    }

    public TrieNode getChild(char kid){
        if (!hasChild(kid)){
            return null;
        }
        return children.get(kid);
    }

    public boolean isNodeWordEnd(){
        return isWord;
    }
    
    public void setNodeAWordEnd(){
        isWord = true;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++){
            char temp = word.charAt(i);
            if (!node.hasChild(temp)){
                node.addChild(temp);
            }
            node = node.getChild(temp);
        }
        node.setNodeAWordEnd();
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++){
            char temp = word.charAt(i);
            if (!node.hasChild(temp)){
                return false;
            }
            node = node.getChild(temp);
        }
        return node.isNodeWordEnd();
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++){
            char temp = prefix.charAt(i);
            if (!node.hasChild(temp)){
                return false;
            }
            node = node.getChild(temp);
        }
        return true;
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");

[leetcode] Regular Expression Matching

input: string, pattern
当pattern下一个字母不是'*'的时候.. 对比string当前字母和pattern当前字母，然后两个string recursion到下一个字母
当下一个字母是'*'的时候..用while loop 去试能match的各种状况

Monday, October 19, 2015

[leetcode] Word Search

这条题意思是寻找2d arry里面有没有字母通过连接上下左右邻居且不重复的情况下存在一个单词
每格作为一个起点用DFS搜索，就是用DFS 上下左右走个遍... 看看每格的字母是不是跟string.charAt(index)一样凡是出界，已经走过，不相等直接return false
代码很直观

public class Solution {
    String word;
    char[][] board;
    boolean checked[][];
    public boolean exist(char[][] board, String word) {
        checked = new boolean[board.length][board[0].length];
        this.word = word;
        this.board = board;
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                if (recursiveSol(i,j,0)){
                    return true;
                }
            }
        }
        
        return false;
    }
    
    boolean recursiveSol(int row, int column, int index){
        if (row >= board.length || 
            column >= board[0].length ||
            row < 0 ||
            column < 0 ||
            word.charAt(index) != board[row][column] ||
            checked[row][column]){
            return false;
        }
        
        if (word.charAt(index) == board[row][column] && index == word.length()-1){
            return true;
        }
        
        checked[row][column] = true;
        boolean result = false;
        if (recursiveSol(row+1, column, index+1) || recursiveSol(row-1, column, index+1) 
         || recursiveSol(row, column+1, index+1) || recursiveSol(row, column-1, index+1)){
            return true;
        }

        checked[row][column] = false;
        return false;
    }
}

[leetcode] Restore IP Addresses

这条题就是一般的DFS，但要注意corner cases
1. 连续0的时候要只用第一个剩下的留给下一代
2. 数字大于255
3. 剪枝，当余下的长度比剩下需要用到的数字的max (每段3位最多，乘与剩下多少段）多的时候直接return
4. 段数要满足了再加进去result

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        rec(s, "", 0, 0);
        return result;
    }
    
    List<String> result = new ArrayList<String>();
    public void rec(String s,String fromPrev, int starting, int component){
        if (component == 4 || starting >= s.length()) return;
        if (component == 3){
            String leftOver = s.substring(starting);
            if (leftOver.length() > 3 || Integer.valueOf(leftOver) > 255) return;
            if (leftOver.charAt(0) == '0' && leftOver.length() > 1) return;
            result.add(fromPrev+leftOver);
            return;
        }
        for (int i = starting+1; i <= starting+3 && i <= s.length(); i++){
            int number = Integer.valueOf(s.substring(starting, i));
            if (number < 256){
                rec(s, fromPrev+number+".", i, component+1);
            }
            if (number == 0) break;
        }
        return;
    }
}

public class Solution {
    List result = new ArrayList();
    String s;
    public List restoreIpAddresses(String s) {
        this.s = s;
        findSol("", 0, 0);
        return result;
    }
    
    private void findSol(String currentResult, int currentSection, int currentIndex){
        if ((s.length()-currentIndex) > (4-currentSection)*3){
            return;
        }
        if (currentResult.length() == s.length()+4 && currentIndex == s.length() && currentSection == 4){
            result.add(currentResult.substring(0, currentResult.length()-1));
            return;
        }
        int previousNum=-1;
        for(int i = currentIndex; i < currentIndex+3 && i < s.length();i++){
            Integer a = new Integer(s.substring(currentIndex, i+1));
            if (a.intValue() < 256 && previousNum != 0){
                previousNum = a.intValue();
                findSol(currentResult+a.intValue()+'.', currentSection+1, i+1);
            }
        }
        return;
    }
}

[leetcode]Sudoku Solver

这题的思路是
用recursion, 遇到非'.'跳过，遇到'.' 就从 ‘1’ 到'9' 每个数字做一次DFS
需要一个helper function来检验当前sukdoku是否有效

public class Solution {
    public void solveSudoku(char[][] board) {
        solveSudokuHelper(board, 0, 0);
    }

    public boolean solveSudokuHelper(char[][] board, int startI, int startJ){
        if (startI == board.length){
            return true;
        }
        if (startJ == board[0].length){
            return solveSudokuHelper(board, startI+1, 0);
        }
        if (board[startI][startJ] != '.'){
            return solveSudokuHelper(board, startI, startJ+1);
        }  
        for (char temp = '1'; temp <= '9'; temp++){
            board[startI][startJ] = temp;
            if (isValidSudoku(board, startI, startJ) && solveSudokuHelper(board, startI, startJ+1)){
                return true;
            }
        }
        board[startI][startJ] = '.';
        return false;
    }

    public boolean isValidSudoku(char[][] board, int i, int j) {
        for (int checkRow = 0; checkRow < board[0].length; checkRow++){
            if (checkRow != j && board[i][checkRow] == board[i][j]){
                return false;
            }
        }

        for (int checkColumn = 0; checkColumn < board.length; checkColumn++){
            if (checkColumn != i && board[checkColumn][j] == board[i][j]){
                return false;
            }
        }

        int boxRow = (i/3)*3;
        int boxColumn = (j/3)*3;
        for (int k = boxRow; k < boxRow+3; k++){
            for (int q = boxColumn; q < boxColumn+3; q++){
                if (k != i && q != j && board[k][q] == board[i][j]){
                    return false;
                }
            }
        }

        return true;
    }
}

[leetcode] Permutation Sequence

这条题是个数学题
[1,2,....,n]
去掉第一位... 剩下就有 (n-1)!种可能...
所以第一位可以用 k/(n-1)!来求..
然后第二位就剩下 K2 = k%(n-1)!， K2/(n-2)! 来求... 如此类推

public class Solution {
    public String getPermutation(int n, int k) {
        int factor[] = new int[n];
        List nums = new ArrayList();
        factor[0] = 1;
        nums.add(1+"");
        for (int i = 1; i < n; i++){
            factor[i] = factor[i-1]*i;
            nums.add((i+1)+"");
        }
        
        k-=1;
        StringBuilder result = new StringBuilder();
        for (int i = n; i >= 1; i--){
            int j = k / factor[i-1];
            k %= factor[i-1];
            result.append(nums.remove(j));
        }
        
        return result.toString();
    }
}

Sunday, October 18, 2015

[Leetcode]Permutations II

这题大集合不知道为什么一直没过。。
然后上网找了个和我一模一样但用cpp写的一下就过了。。。

思路就是Permutations I 把array sort了下和有duplicate 的时候只有前一个duplicate 用了当前的才可以用。

[Leetcode] Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/

做完longest palindromic substring之后
http://ftalm.blogspot.com/2015/10/leetcode-longest-palindromic-substring.html
这题明朗了很多就是和longest palindromic substring（建所有substring 是否palindrom的table+DFS)

public class Solution {
    List> result = new ArrayList>();
    boolean check[][];
    List temp = new ArrayList();
    public List> partition(String s) {
        check = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++){
            check[i][i] = true;
            for (int j = 0; j < i; j++){
                check[j][i] = s.charAt(j) == s.charAt(i) && (i-j==1 || check[j+1][i-1]);
            }
        }
        findSol(0, temp, s);
        return result;
    }
    
    private void findSol(int start, List list, String str){
        if (start == str.length()){
            result.add(new ArrayList(list));
            return;
        }
        for (int i = start; i < str.length(); i++){
            if (check[start][i]){
                list.add(str.substring(start, i+1));
                findSol(i+1, list, str);
                list.remove(list.size()-1);
            }
        }
    }
}

Saturday, October 17, 2015

[leetcode] Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

找出最长的palindrom substring

做法就是每个index 都作为中心点，以0,和length-1为边界把偶数和奇数长的substring找出来
然后记录下最长的

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() == 0){
            return "";
        }
        
        String longestEver = s.substring(0,1);
        for (int i = 0; i <= s.length()-2; i++){
            String temp = findPadlindrome(i,i,s);
            String temp2 = findPadlindrome(i,i+1,s);
            String longer = temp.length()>temp2.length()?temp:temp2;
            longestEver = longer.length()>longestEver.length()?longer:longestEver;
        }
        return longestEver;
    }
    
    private String findPadlindrome(int centerLeft, int centerRight, String s){
        if (s.charAt(centerLeft) != s.charAt(centerRight)){
            return "";
        }
        int begin = centerLeft;
        int end = centerRight;
        while (begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)){
            begin -= 1;
            end += 1;
        }
        
        return s.substring(begin+1, end);
    }
}

Google了一下， DP的算法
就是用 check[a][b] 代表 substring a到b 是不是palindrom
可以分解成
check[a][b] = check[a+1][b-1] str[a] == str[b]
当a == b时 check[a][b] = true

public class Solution {
    public String longestPalindrome(String s) {
        boolean check[][] = new boolean[s.length()][s.length()];
        int longest = 0;
        int start=0, end=0;
        for (int i = 0; i < s.length(); i++){
            check[i][i] = true;
            for (int j = 0; j < i; j++){
                check[j][i] = s.charAt(i) == s.charAt(j) && ((i-j < 2) ||check[j+1][i-1]);
                if (check[j][i] && longest < (i-j+1)){
                    longest = i-j+1;
                    start = j;
                    end = i;
                }
            }
        }
        return s.substring(start, end+1);
    }
}

KMP 算法总结

之前看过关于kmp的文章好多次了然后都忘了
这里简洁总结一下方便下次快速想起

好开始，

A，B 两条string，要稳B 到底有无match A其中一条substring.
关键就系整一个next 数组
系next 数组之前，先讲下
1. 最长公共元素长度，具体自己体下图。

就是从该位置i结束的postfix (AjAj+1...Ai) 最多能与从0开始多长的prefix(A0A1..Ak) match到

当然 length(postfix) == length(prefix)

2.next 数组，其实就是把上表数字往右移一格，index 0 值为-1

用法：

字符不配对时 next数组告诉你从哪里重新开始而不是总是跳回开头。

（参考资料里面噶3.3.2 可以参考下）

next 数组生成方法：

void GetNext(char* p,int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前缀，p[j]表示后缀  
        if (k == -1 || p[j] == p[k])   
        {  
            ++k;  
            ++j;  
            next[j] = k;  
        }  
        else   
        {  
            k = next[k];  
        }  
    }  
}

就是跳回去再跳回去直到回到原点或者匹配

int KmpSearch(char* s, char* p)  
{  
    int i = 0;  
    int j = 0;  
    int sLen = strlen(s);  
    int pLen = strlen(p);  
    while (i < sLen && j < pLen)  
    {  
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++      
        if (j == -1 || s[i] == p[j])  
        {  
            i++;  
            j++;  
        }  
        else  
        {  
            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]      
            //next[j]即为j所对应的next值        
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}

参考嘎资料
http://blog.csdn.net/v_july_v/article/details/7041827