[LeetCode] Longest palindromic substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Another Linear time solution, please see This link

Java Code:
   
    

public String longestPalindrome(String s) {
         String palindrom = "";
        int maxLen = 0;
        
        int index1 = 0, index2 = 0;
        int i = 0;
        while(i < 2*s.length()){
            index1 = i/2;
            index2 = i/2 + i%2;
            
            while(index1 >= 0 && index2 < s.length() && s.charAt(index2) == s.charAt(index1)){     
                index1--;
                index2++;
            }
            
            if(index2 > index1 && maxLen < (index2 - index1 - 1)) {
                palindrom = s.substring(index1+1, index2);
                maxLen = index2 - index1 - 1; 
            }
            
            i++;
        }
        
        return palindrom;
    }

[Leetcode] Longest common prefix

Write a function to find the longest common prefix string amongst an array of strings. 

解题思路：
1. 遍历数组，找出当前commonprefix下一个str的commonprefix。
2. 查看数组里所有的变量的第i位置上的字符相等否

   public String longestCommonPrefix(String[] strs) {
        String prefix = "";
        
        if(strs.length == 0) return prefix;
        
        prefix = strs[0];
        
        for(int i = 1; i < strs.length && prefix.length() > 0; i++){
            
            int j = 0;
            
            while(j < prefix.length() && j < strs[i].length() && prefix.charAt(j) == strs[i].charAt(j)) j++;
            
            prefix = prefix.substring(0, j);
        }
        
        return prefix;
    }

public String longestCommonPrefix(String[] strs) {
         String res = "";
        if(strs.length == 0) return res;
        res = strs[0];
        
        for(int i = 0; i < res.length(); i++){         
            for(int j = 1; j < strs.length; j++){
                if(i >= strs[j].length() || strs[j].charAt(i) != res.charAt(i)){
                    return res.substring(0, i);
                }
            }
        }
        
        return res;
    }

[LeetCode]Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10]. 

解题思路： insertion sort 的演变

Java Code:

public List insert(List intervals, Interval newInterval) {
           List res = new ArrayList(intervals);
        
        int s = 0;
        
        // at index s, the start is correct. we need to merge the end.
        while(s < intervals.size() && newInterval.start >= intervals.get(s).start){
            s++;
        }
        
        if(s > 0 && newInterval.start <= intervals.get(s-1).end){
            s--;
        }else{
            res.add(s, newInterval);
        }
        
        res.get(s).end = Math.max(newInterval.end, res.get(s).end);
        s++;
              
       while( s < res.size() && newInterval.end >= res.get(s).start){
           newInterval.end = Math.max(newInterval.end, res.get(s).end);
           res.remove(s);
       }
        
        return res;
    }

[LeetCode] Convert sorted array to binary search tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Java Code:
  

public TreeNode sortedArrayToBST(int[] num) {
        return sortedSubArrayToBST(num, 0, num.length-1);
    }
      
      public TreeNode sortedSubArrayToBST(int[] num, int begin, int end){
          if( begin > end) return null;
          int middle = (begin+end)/2;
          
          TreeNode root = new TreeNode(num[middle]);
          
          root.left = sortedSubArrayToBST(num, begin, middle-1);
          root.right = sortedSubArrayToBST(num, middle+1, end);
          
          return root;
    }

[LeetCode] Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. 

解题思路：recursion

Java Code:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List> res = new ArrayList>();
        List solution = new ArrayList();
        
        combination(candidates, 0, target, res, solution);
        
        return res;
    }
    
    public void combination(int[] candidates, int startIndex, int target, List> res, List solution){
        if(target == 0){
            List tmp = new ArrayList(solution);
            res.add(tmp);
            return;
        }
        
        for(int i = startIndex; i < candidates.length; i++){
            if(candidates[i] <= target){
                solution.add(candidates[i]);
                combination(candidates, i, target - candidates[i], res, solution);
                solution.remove(solution.size() - 1);
            }else break;
        }
    }

[LeetCode] Construct binary tree from Inorder and Preorder

Given preorder and inorder traversal of a tree, construct the binary tree.

Java Code:

 

public TreeNode buildTree(int[] preorder, int[] inorder) {
         if(inorder.length != preorder.length || preorder.length == 0) return null; 
           
          return buildSubTree(inorder, 0, inorder.length-1, preorder, 0, inorder.length-1);
        
    }
    
     public TreeNode buildSubTree(int[] inorder, int begin, int end, int[] preorder, int s, int t) {
        
           TreeNode root = new TreeNode(preorder[s]);
           int pos = begin;
           
           for(int i = begin; i <= end; i++){
               if(inorder[i] == preorder[s]){
                   pos = i;
                   break;
               }
           }
              
           if(begin <= pos - 1) root.left = buildSubTree(inorder, begin, pos-1, preorder, s+1, s+pos-begin);
           
           if(pos+1 <= end) root.right = buildSubTree(inorder, pos+1, end, preorder, s + pos-begin+1, t);
           
           return root;
    }

[LeetCode]Construct binary tree from inorder and postorder traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

解题思路：
1. 从postorder里找到root node, 然后在inorder里找到此root node, 分别recursion

Java Code:

 public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length != postorder.length || postorder.length == 0) return null; 
           
          return buildSubTree(inorder, 0, inorder.length-1, postorder, 0, inorder.length-1);
        
    }
     
      public TreeNode buildSubTree(int[] inorder, int begin, int end, int[] postorder, int s, int t) {
        
           TreeNode root = new TreeNode(postorder[t]);
           int pos = begin;
           
           for(int i = begin; i <= end; i++){
               if(inorder[i] == postorder[t]){
                   pos = i;
                   break;
               }
           }
              
           if(begin <= pos - 1) root.left = buildSubTree1(inorder, begin, pos-1, postorder, s, s+pos-begin-1);
           
           if(pos+1 <= end) root.right = buildSubTree1(inorder, pos+1, end, postorder, s + pos-begin, t-1);
           
           return root;
    }