Valid Palindrome LeetCode

题意非常简单，一个从头找一个从尾部找。如果碰到非数字和非字母的都跳过，然后比较首尾。

注意两个function: Character.isLetterOrDigit(char x);
Character.toLowerCase(char x);


public boolean isPalindrome(String s) {
        if(s==null || s.length()==0) return true;
       
        int i=0, j=s.length()-1;
        while(i<j){
            char a = s.charAt(i);
            char b = s.charAt(j);
            if(!Character.isLetterOrDigit(a)){
                i++;
                continue;
            }
            if(!Character.isLetterOrDigit(b)){
                j--;
                continue;
            }
            if(Character.toLowerCase(a)!=Character.toLowerCase(b)){
                return false;
            }
            i++; j--;
        }
        return true;
    }

Validate Binary Search Tree LeetCode

Recursion + 利用Binary Search Tree的特点。

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Java Code：

public boolean isValidBST(TreeNode root) {

        // IMPORTANT: Please reset any member data you declared, as

        // the same Solution instance will be reused for each test case.

        return (root==null)||(isValidBST(root.left) && isValidBST(root.right)

        && checkMax(root.left, root.val)&&checkMin(root.right,root.val));

    }

    

    private boolean checkMax(TreeNode root, int max){

        if(root==null) return true;

        while(root!=null && root.right != null){

            root=root.right;

        }

        return root.val < max;

    }

    

    private boolean checkMin(TreeNode root, int min){

        if(root==null) return true;

        while(root!=null && root.left != null){

            root=root.left;

        }

        return root.val > min;

    }

Updating two new solutions:
First, recursion with null check.
Second, use inorder traversal.

Merge Sorted Array LeetCode

这个题就是从后面向前面存数据，唯一需要注意的是，B没有都存入到A中，要再check一下，B是否都存入了A。


public void merge(int A[], int m, int B[], int n) {
        int len = m + n -1;
        int lenA = m - 1;
        int lenB = n - 1;
        while(lenA >= 0 && lenB >= 0 ){
            if(A[lenA] > B[lenB]){
                A[len] = A[lenA];
                len--;
                lenA--;
            }else{
                A[len] = B[lenB];
                len--;
                lenB--;
            }
        }
        while(lenB>=0){
            A[len] = B[lenB];
            len--;
            lenB--;
        }
    }

Climbing Stairs LeetCode

简单DP题很简单。


public int climbStairs(int n) {
        int[] result = new int[n+1];
        result[0] = 1;
        result[1] = 1;
        for(int i=2; i <n+1; i++){
            result[i]=result[i-1] + result[i-2];
        }
        return result[n];
    }

Valid Number LeetCode

分别讨论三种不同的cases, '-', 'e', '.'。 写出来的程序无比复杂，要把所有的条件都排除。这里要用两个flags, 一个记录负数，一记录e。

另外可以使用正则表达式。[-+]?(\\d+\\.?|\\.\\d+)\\d*(e[-+]?\\d+)?

这道题总写总错，原来是自己写的方法不是非常好，这里把存在e的数字前面搞成两部分。
ex：e2 false （firstPart==false）
2e （eFound==true && secondPart==false） false
其他的为true
代码写起来非常容易。
45.e3 is that correct?

public boolean isNumber(String s) {
     
        if (s==null) return false;
        char[] sArr=s.trim().toCharArray();
        if (sArr.length==0) return false;
     
        int index=0;
        if (sArr[index]=='+'||sArr[index]=='-') index++;
     
        boolean eFound=false;
        boolean dotFound=false;
        boolean firstPart=false;
        boolean secondPart=false;
        boolean spaceFound=false;
     
        while(index<sArr.length){
            if (sArr[index]=='.'){
                if(dotFound||eFound||spaceFound) return false;
                else dotFound=true;
            }
            else if (sArr[index]=='e'||sArr[index]=='E'){
                if (eFound||!firstPart||spaceFound) return false;
                else eFound=true;
            }
            else if (Character.isDigit(sArr[index])){
                if (spaceFound) return false;
                if (!eFound) firstPart=true;
                else secondPart=true;
            }
            else if (sArr[index]=='+'||sArr[index]=='-'){
                if (spaceFound) return false;
                if (!eFound||!(sArr[index-1]=='e'||sArr[index-1]=='E'))
                return false;
            }
            else if (sArr[index]==' ') spaceFound=true;
            else return false;
            index++;
        }
     
        if (!firstPart) return false;
        else if (eFound && !secondPart) return false;
        else return true;
    }

public boolean isNumber(String s) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(s==null)
        return false;
    char[] sArr = s.trim().toCharArray();

    if(sArr.length==0)
        return false;
    if(sArr.length==1&&!Character.isDigit(sArr[0]))
        return false;

    boolean decimalFound = false;
    boolean eFound = false;
    int end = sArr.length-1;
    for(int i=0;i<=end;i++){      
        char nextChar = i>=end?'x':sArr[i+1];
        char prevChar = i<=0?'x':sArr[i-1];
        switch(sArr[i]){
        case '+':
        case '-':
            if(prevChar!='e'&&i!=0)
                return false;
            if(prevChar=='e'&&i==end)
                return false;
            if (i==0&&nextChar=='e')
                return false;
            break;
        case '.':
            if(decimalFound || eFound)
                return false;
            if(i>=end && i<=0)
                return false;
            if(!Character.isDigit(prevChar) && !Character.isDigit(nextChar))
                return false;
            decimalFound = true;
            break;
        case 'e':
            if(eFound)
                return false;
            if(!Character.isDigit(prevChar) && !Character.isDigit(nextChar)
                &&nextChar!='-'|| end==i || i==0){
                        return false;                      
            }
            eFound = true;
            break;
        case ' ':
            return false;
        default:
            if(!Character.isDigit(sArr[i]))
                return false;
        }

    }
    return true;
     
    }

Better Solution from book of LEETCODE

public boolean isNumber(String s) {
        int i=0, n=s.length();
        while (i<n && Character.isWhitespace(s.charAt(i))) i++;
        if (i<n && (s.charAt(i) == '+' || s.charAt(i) == '-')) i++;
        boolean isNumeric = false;
        while (i<n && Character.isDigit(s.charAt(i))) {
            isNumeric = true;
            i++;
        }
        if (i<n && s.charAt(i) == '.') {
            i++;
            while (i<n && Character.isDigit(s.charAt(i))) {
            isNumeric = true;
            i++;
            }
        }
        if (isNumeric && i<n && (s.charAt(i) == 'e' || s.charAt(i) == 'E')) {
            i++;
            isNumeric = false;
             if (i<n && (s.charAt(i) == '+' || s.charAt(i) == '-')) i++;
            while (i<n && Character.isDigit(s.charAt(i))) {
                isNumeric = true;
                i++;
            }
        }
        while (i<n && Character.isWhitespace(s.charAt(i))) i++;
        return isNumeric && i == n;
    }

Merge Intervals LeetCode

这个题，先定义一个comparator，定义了comparator需要重写compare函数。 然后用两个interval比较第i-1个的end和第i个的start，如果第i-1个end大于等于第i个start，overlap第i个interval，否则没有overlap，直接存到result里面。

搞个小插曲： comparable 和comparator的区别，简单记两个都可以比较自定义的两个object。comparator是利用strategy design pattern来完成比较，并且可以实现sort功能。所以这个题我们用到了comparator，写了一个内部类。
另外Comparator 自己定义compare方法。
comparable定义的是compareTo方法

 public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        ArrayList<Interval> result = new ArrayList<Interval>();
        if(intervals == null || intervals.isEmpty()) return result;
     
        //define the comparator
        Comparator<Interval> comparator = new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2){
                if(i1.start < i2.start) return -1;
                else if(i1.start > i2.start) return 1;
                else{
                    if(i1.end < i2.end) return -1;
                    else if(i1.end > i2.end) return 1;
                    else return 0;
                }
            }
        };
     
        Collections.sort(intervals, comparator);
     
        //compare the intervals
        for(int i=0; i<intervals.size();i++){
            Interval curr = intervals.get(i);
            if(result.isEmpty()){
                result.add(curr);
            }else{
                Interval last = result.get(result.size()-1);
                if(last.end >= curr.start){
                    last.end = Math.max(last.end, curr.end);
                }else{
                    result.add(curr);
                }
            }
        }
        return result;
    }

Pow(x,n) LeetCode

Brute force的方法就是从头乘到位，这个题一下就是想到binary search。不停的分成两部分，这个时候就要考虑这个n是偶数还是奇数。程序实现比较容易。


 public double pow(double x, int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(n==0) return 1.0;
        if(n==1) return x;
        if(n==-1) return 1/x;
        if(n%2==0){
            double temp = pow(x,n/2);
            return temp*temp;
        }else{
            double temp = pow(x,(n-1)/2);
            return temp*temp*x;
        }
    }

这个题除了二分不知道难点在哪里，后来发现有一个corner case没有考虑到，就是负数转换为正数的时候会溢出。另外用位操作。

public double myPow(double x, int n) {
        if (n==0) return 1;
        boolean isOverflow = false;
        if (n<0) {
            x = 1/x;
            if (n==Integer.MIN_VALUE) {
                n = Integer.MAX_VALUE;
                isOverflow = true;
            } else {
                n=-n;
            }
        }
       
        double t = 1;
        if (isOverflow) t = t*x;
       
        while (n>0) {
            int last = n&1;
            if (last == 1) {
                t = t*x;
            }
            x= x*x;
            n=n>>1;
        }
        return t;
    }

Implement strStr() LeetCode

最简单的方法是brute force，直接逐个扫描。时间复杂度为O（mn）这里n是字符串长度，m是pattern的长度。Code如下：

public String strStr(String haystack, String needle) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(haystack == null || needle == null) return null;
        if(needle.length()==0) return haystack;
        int hLen = haystack.length();
        int nLen = needle.length();
        if(hLen < nLen) return null;
        for(int i=0; i<hLen; i++){
            int j=i;
            //适当的剪枝
            while(nLen+i <= hLen && j<hLen && haystack.charAt(j) == needle.charAt(j-i)){
                j++;
                if(j-i == nLen) return haystack.substring(i);
            }
        }
        return null;
    }

优化解法，肯定是要用到KMP(Knuth-Morris-Pratt)，中心思想是利用每次已经match的字符串信息来做优化。我找到一个ppt，做了适当的修改。
具体的讲解可以参考这个中文博客：http://blog.csdn.net/lin_bei/article/details/1252686
搞了个PPT也可以看下

Code如下

public String strStr(String haystack, String needle) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
      if(needle.length()==0) return haystack;
      int hLen = haystack.length();
      int nLen = needle.length();
   
      if(hLen < nLen) return null;
   
      int[] next = new int[nLen];
      getNext(needle, next);//O(m)space for storing the next position
      int i=0, j=0;
      while(i<hLen && j<nLen){
          if(haystack.charAt(i)==needle.charAt(j)){
              if(j==needle.length()-1) return haystack.substring(i-j);
              ++i;
              ++j;
          }else{
              if(j==0)i++;
              else j=next[j];
          }
      }
return null;
}

private void getNext(String str, int[] next){
   if(str.length()==0 || str.length()==1) return;
   int start = 0;
   int index = 2;
 
   while(index < str.length()){
       if(str.charAt(index-1)==str.charAt(start)){
           next[index++]=++start;
       }else if(start>0){
           start = next[start];
       }else{
           next[index++]=0;
       }
   }
 
}

Merge two sorted list LeetCode

这个题主要考实现，没太多难度，两个linkedlist里面比head的值得大小，逐个接到新的LinkedList里面。设置一个dummy node。


public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode prev = new ListNode(-1);
        ListNode curr = prev;
        while(l1!=null && l2!=null){
            if(l1.val < l2.val){
                curr.next = l1;
                l1 = l1.next;
            }else{
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        if(l1 != null){
            curr.next = l1;
        }
        if(l2 != null){
            curr.next = l2;
        }
        return prev.next;
    }

Valid parentheses LeetCode

这道题之所以愿意面试总出，俺个人认为可以有不同的写法，比如我就用了O（n）的空间写了一下，这样代码很简单。
思路： 用一个Stack去存放左括号，如果碰到右括号，就看stack中的顶部是否跟该右括号match，如果不match返回false；最后判断stack中是否为空。直接上code，我认为是非常容易在面试中写出来的code，我写了一遍，只出现了一个小的语法错误。

这个思路非常常用，类似的有那个simplify path 和 reverse polish notation都是类似的思想。



public boolean isValid(String s) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        Stack<Character> left = new Stack<Character>();
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            if(c=='(' || c=='[' || c=='{'){
                left.push(c);
            }else{
                if(left.size()==0)return false;
                char top = left.peek();
                if(c==')'){
                    if(top != '(') return false;
                }else if(c==']'){
                    if(top != '[') return false;
                }else{
                    if(top != '{') return false;
                }
                left.pop();
            }
        }
        return left.size()==0;
    }

String to Integer LeetCode

这个题水题，没什么可说的。需要注意以下的几个注意事项：
1.首先是边界条件，如果是遇到null或者长度为零的字符串返回值，leetcode期望的答案为0.
2.处理数字前面的空格
3.处理第一个字符，第一个字符可以是数字或者是+，-号。设置一个boolean neg来记录该数的正负。
4.接下来就是要处理overflow了，用了一个boolean的overflow，这里有两种overflow，一种是正数或者负数的溢出。另一种是位数大于MAX_VALUE
<处理overflow的时候要小心，一种是214748364再加一位出现overflow，还有一种是数字大于1000000000，关系要搞对，是或的关系。>
5.返回值时，要考虑到正负，用记录正负的neg。

废话不多说，直接上代码


public int atoi(String str) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(str == null || str.length() == 0) return 0;
       int ans=0;
       int index=0;
       boolean neg = false;
       boolean overflow = false;
       int len = str.length();
     
       //first step skip all the whitespace
       while(index<len && str.charAt(index)==' ')index++;
       if(str.charAt(index)=='+'){
           neg = false;
           index++;
       }
       if(str.charAt(index)=='-'){
           neg = true;
           index++;
       }
       while(index<len && str.charAt(index)>='0' && str.charAt(index)<='9'){
           int digit = str.charAt(index)-'0';
           if((ans >=214748364)&& ((!neg && digit>=7)||(neg&&digit>=8)||ans>=1000000000)){
               overflow = true;
               break;
           }
           ans=ans*10+digit;
           index++;
       }
       if(overflow){
           if(neg) return Integer.MIN_VALUE;
           else return Integer.MAX_VALUE;
       }
       if(neg) return (-1)*ans;
       else return ans;
    }

4SUM LeetCode

思路： 跟3SUM相同，这个时候我为了让代码尽可能简洁，没有搞剪枝，直接就是2重for循环+2SUM。这个时间复杂度为O(n^2)
另外的思路：可以把所有的pair都存到hashmap里，然后做2SUM


public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        HashSet<ArrayList<Integer>> avoidDups = new HashSet<ArrayList<Integer>>();
        if(num.length < 4) return res;
        Arrays.sort(num);
     
        for(int i=0; i<num.length-3; i++){
            for(int j=i+1; j<num.length-2; j++){
                int start = j+1;
                int end = num.length-1;
                while(start<end){
                    if(num[start]+num[end] == target-num[i]-num[j]){ //find one
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    temp.add(num[i]);
                    temp.add(num[j]);
                    temp.add(num[start]);
                    temp.add(num[end]);
                    avoidDups.add(temp);
                    //update index
                    start++;
                    end--;
                    }else if(num[start]+num[end] > target-num[i]-num[j]) end--;
                    else start++;
                 
                }
            }
        }
        res.addAll(avoidDups);
        return res;
    }

public List<List<Integer>> fourSum(int[] num, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Arrays.sort(num);
       
        for (int i=0; i<num.length-3; i++) {
            if (i!=0 && num[i]==num[i-1]) continue;
            for (int j=i+1; j<num.length-2; j++) {
                if (j!=i+1 && num[j]==num[j-1]) continue;
                int start = j+1;
                int end = num.length-1;
                while (start < end) {
                    int runningSum = num[i] + num[j] + num[start] + num[end];
                    if (target < runningSum) {
                        end--;
                    } else if (target > runningSum) {
                        start++;
                    } else {
                        List<Integer> tempList = new ArrayList<Integer>();
                        tempList.add(num[i]);
                        tempList.add(num[j]);
                        tempList.add(num[start]);
                        tempList.add(num[end]);
                        result.add(tempList);
                        start++;
                        end--;
                        while (start < end && num[start] == num[start-1]) start++;
                        while (start < end && num[end] == num[end+1]) end--;
                    }
                }
            }
        }
        return result;
    }

Three Sum Closest LeetCode

废话不多说，这个题跟3SUM没有任何变化，直接上code。


public int threeSumClosest(int[] num, int target) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        Arrays.sort(num);
        int smallest = Integer.MAX_VALUE;
        int closest = Integer.MAX_VALUE;
        for(int i=0; i<num.length-2; i++){
            if(i>0 && num[i]==num[i-1]) continue;
            int start = i+1;
            int end = num.length-1;
           
            while(start<end){
                int runningSum = num[i]+num[start]+num[end];
                int diff = Math.abs(runningSum - target);
                //update the smallest and colsest
                if(smallest > diff) {
                    smallest = diff;
                    closest = runningSum;
                }
                //compare with the target
                if(runningSum == target) return target;
                else if(runningSum > target) end--;
                else start++;
               
            }
        }
        return closest;
    }

Three SUM LeetCode

3SUM
思路： 运用2SUM中的第二个方法，唯一需要注意的地方就是防止重复的结果出现。
比如 数组 {1, 1, 1, 2, 3, 4} target 6
这样我们实际上只有一组答案，就是{1, 1, 2} 另外一组跟这个组是一模一样的所以跳过。

具体看代码。
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {

        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(num.length < 3) return res;
        Arrays.sort(num);
        for(int i=0; i<num.length - 2 && num[i]<=0; i++){
        //num[i]<= 0适当的减少了一定量的计算，如果想不到应该也没关系
            if(i>0 && num[i]==num[i-1]) continue; //防止duplicate
            int start = i + 1;
            int end = num.length - 1;
            while(start < end){
                int runningSum = num[i] + num[start] + num[end];
                if (runningSum > 0) end--;
                else if(runningSum < 0) start++;
                else{//find one solution and save it to the arraylist
                ArrayList<Integer> temp = new ArrayList<Integer>();
                temp.add(num[i]);
                temp.add(num[start]);
                temp.add(num[end]);
                res.add(temp);
             
                //update start and end
                start++;
                end--;
                //skip the duplicates
                while(start<end && num[start]==num[start - 1]) start++;
                while(start<end && num[end] == num[end + 1]) end--;
                }
            }
        }
        return res;
    }

Updating version:
public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
if (num == null || num.length < 3) return result;
Arrays.sort(num);

for (int i=0; i<num.length-2 &&num[i] <= 0; i++) {
//avoid duplicate for the first elements
if (i>0 && num[i]==num[i-1]) continue;
int start = i + 1;
int end = num.length - 1;
while (start < end) {
int runningSum = num[i] + num[start] + num[end];
//DO 2SUM searching
if (runningSum >0) {
end--;
} else if (runningSum < 0) {
start++;
} else {
List<Integer> temp = new ArrayList<Integer>();
temp.add(num[i]);
temp.add(num[start]);
temp.add(num[end]);
result.add(temp);

//updating the index to avoid the duplicate for 2nd and 3rd elements
start++;
end--;
while (start < end && num[start] == num[start-1]) start++;
while (start < end && num[end] == num[end + 1]) end--;
}
}

}
return result;  
    }

Two Sum LeetCode

思路1： 利用Hash将数组从左到右扫一遍，把target - numbers[i]存到HashMap里面，这样做可以不需要将所有数都扫一遍，Time O(n） Space O(n)
思路2：（Two pointers）将头尾两个数加起来和target比，比target大，就移动将尾部的pointer向左移动，如果比target小就将头部的pointer向右移动。


public class TowSum {
public static void main(String[] args) {
int[] test ={20,21,25,30,75};
System.out.println(Arrays.toString(twoSum2(test,100)));
}

public static int[] twoSum(int[] numbers, int target) {
       
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
        int[] res = new int[2];
        for(int i=0; i<numbers.length; i++){
            if(map.containsKey(numbers[i])){
                res[0] = map.get(numbers[i]);
                res[1] = i + 1;
                break;
            }else{
                map.put(target - numbers[i],i+1);
            }
        }
        return res;
    }

//如果是已经排好序的数据，时间O（n）space O（1）
//为3Sum做准备
public static int[] twoSum2(int[] numbers, int target){
int start = 0;
int end = numbers.length - 1;
while(start < end){
int runningSum = numbers[start] + numbers[end];
if(runningSum == target) return new int[]{start + 1, end + 1};//start + 1这个不是index，而是第几个数
else if (runningSum > target) end--;
else start++;
}
return null;
}
}