九章算法

1  BST迭代器

注意点：1. 实际就是中序遍历的非递归写法，迭代器就是要用Stack存储数据，不过把不同的模块功能进行了分割，而不是一次完成中序遍历；

　　　　2. 可以把添加到Stack单独抽取成一个函数，面向对象，更容易理解。

http://www.lintcode.com/en/problem/binary-search-tree-iterator/#

 public class BSTIterator {
    //@param root: The root of binary tree.
    TreeNode next = null;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    public BSTIterator(TreeNode root) {
        // write your code here
        next = root;
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        // write your code here
        while(next != null) {
            stack.push(next);
            next = next.left;
        }
        if(stack.isEmpty()) return false;
        return true;
    }
    
    //@return: return next node
    public TreeNode next() {
        // write your code here
        if(!hasNext()) return null;
        TreeNode cur = stack.pop();
        if(cur.right == null) next = null;
        else next = cur.right;
        return cur;
    }
}

2 二叉查找树中搜索

注意点：见代码

　　　　不一定要完全遍历二叉树，可以在遍历前判断下来减少遍历的量。

　　　　if(root.val > k1) 　helper(root.left, result, k1, k2);

http://www.lintcode.com/zh-cn/problem/search-range-in-binary-search-tree/

//可以定义一个 ArrayList<Integer> result的成员变量，这样helper中就不需要resul作为参数一直传递添加了。
  public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
     ArrayList<Integer> result = new ArrayList<Integer> ();
     helper(root, result, k1, k2);
     return result;
 }
 private void helper(TreeNode root, ArrayList<Integer>  result, int k1, int k2) {
     if(root == null) return;
     helper(root.left, result, k1, k2);
     if(root.val >= k1 && root.val <= k2) result.add(root.val);
     helper(root.right, result, k1, k2);
     return;
 }

3 二叉树中插入结点

http://www.lintcode.com/en/problem/insert-node-in-a-binary-search-tree/

注意点：非递归的插入方式

 public TreeNode insertNode(TreeNode root, TreeNode node) {
        // write your code here
        if(root == null) {
            root = node;
            return root;
        }
        if(root.val <= node.val) {
            root.right = insertNode(root.right, node);
            
        } else {
            root.left = insertNode(root.left, node);
        }
        return root;
    }
//非递归
 public TreeNode insertNode(TreeNode root, TreeNode node) {
        // write your code here
        if(root == null) {
            root = node;
            return root;
        }
        TreeNode last = null, temp = root;
        while(temp != null) {
            last = temp;
            if(temp.val <= node.val) temp = temp.right;
            else temp = temp.left;
        }
        if(last != null) { //可以不判断，last不可能为null
            if(last.val <= node.val) last.right = node;
            else last.left = node;
        }
        return root;
    }
    

4  二叉树删除结点

http://www.lintcode.com/en/problem/remove-node-in-binary-search-tree/

注意点：见代码

　　　　结点的传递是地址传递，所以将待改变结点的引用传入函数，函数操作后，整个树是会发生变化的。

　　　　待删结点有两个子树的删除方式：

　　

public TreeNode removeNode(TreeNode root, int value) {
        TreeNode dummy = new TreeNode(0); //dummy的值随便取，反正不输出，为了仅仅是给root设个头
        dummy.left = root; 
        
        TreeNode parent = findNode(dummy, root, value);
        TreeNode node; //待删结点
        if (parent.left != null && parent.left.val == value) {
            node = parent.left;
        } else if (parent.right != null && parent.right.val == value) {
            node = parent.right;
        } else {
            return dummy.left ;  //待删结点不存在
        }
        
        deleteNode(parent, node);
        
        return dummy.left ;
    }
    
    private TreeNode findNode(TreeNode parent, TreeNode node, int value) {  //返回待删结点的父节点，待删的不存在也返回父节点
        if (node == null) {
            return parent;
        }
        
        if (node.val == value) {
            return parent;
        }
        if (value < node.val) {
            return findNode(node, node.left, value);
        } else {
            return findNode(node, node.right, value);
        }
    }
    
    private void deleteNode(TreeNode parent, TreeNode node) {
        if (node.right == null) {
            if (parent.left == node) {
                parent.left = node.left;
            } else {
                parent.right = node.left;
            }
        } else {
            TreeNode temp = node.right;
            TreeNode father = node;
            
            while (temp.left != null) {
                father = temp;
                temp = temp.left;
            }
            
            if (father.left == temp) {
                father.left = temp.right;
            } else {
                father.right = temp.right;
            }
            
            if (parent.left == node) {
                parent.left = temp;
            } else {
                parent.right = temp;
            }
            
            temp.left = node.left;
            temp.right = node.right;
        }
    }

 DP--------------------------------------------------------------------------------------------------------------------------------------------------------------------

满足下面三个条件之一：
● 求最大值最小值
● 判断是否可行
● 统计方案个数
则 极有可能 是使用动态规划求解

序列型dp 递推表达式f[] 里代表着含有0个~length个字符，所以数组的长度定义为length+1；
区间型dp 递推表达式f[] 里代表着坐标，所以数组的长度定义为length；

1  数字三角形

http://www.lintcode.com/zh-cn/problem/triangle/

疑问： 用HashMap怎么存？编译不通过？？？？？

注意点：top- down 、down - top、 记忆化搜索

　　　　初始化三角形的顶点和两个侧边

错误点：

//搜索记忆，查找过的结点不需要再查一次，所以复杂度为O(n * n)
int[][] triangle = null;
int[][] sumMin = null;
int n;
public int minimumTotal(int[][] triangle) {
    if(triangle == null || triangle.length == 0 || triangle[0].length == 0) return 0;
    this.n = triangle.length;
    this.triangle = triangle;
    this.sumMin = new int[n][n];
    for(int i = 0; i< n; i++) {
        for(int j = 0; j < n ; j++) sumMin[i][j] = Math.MAX_VALUE;
    }
    
    return helper(0, 0);
}
private  int helper(int x, int y) {
    if(x >= n) return 0;
    if(sumMin[x][y] != Math.MAX_VALUE) return sumMin[x][y];
    sumMin[x][y] = Math.min(helper(x+1, y),helper(x+1,y+1)) + triangle[x][y];
    return  sumMin[x][y];
}
// 同上，用哈希表存查过的结点
int[][] triangle = null;
HashMap<int[], Integer> sumMin = new HashMap<int[], Integer>();
int n;
public int minimumTotal(int[][] triangle) {
    if(triangle == null || triangle.length == 0 || triangle[0].length == 0) return 0;
    this.n = triangle.length;
    this.triangle = triangle;
    for(int i = 0; i< n; i++) {
        for(int j = 0; j < n ; j++) sumMin[i][j] = Math.MAX_VALUE;
    }
    
    return helper(0, 0);
}
private  int helper(int x, int y) {
    if(x >= n) return 0;
    if(sumMin.containsKey({x,y})) return sumMin.get({x,y});
    int value = Math.min(helper(x+1, y),helper(x+1,y+1)) + triangle[x][y];
    sumMin.put({x,y}, value);
    return  value;
}
//top - down
public int minimumTotal(int[][] triangle) {
    if(triangle == null || triangle.length == 0 || triangle[0].length == 0) return 0;
    int row = triangle.length;
    for(int i =1; i < row; i++) {
        triangle[i][0] +=  triangle[i-1][0];
        triangle[i][i] += triangle[i-1][i-1];
    }
    for(int i = 2; i < row; i++) {
        for(int j =1; j < i; j++) {
            triangle[i][j] += Math.min(triangle[i-1][j],triangle[i-1][j-1]);
        }
    }
    for(int i = 1; i < row; i++) {
        triangle[row-1][0] = Math.min(triangle[row-1][i],triangle[row-1][0]);
    }
    return triangle[row-1][0];
}
//down - top
public int minimumTotal(int[][] triangle) {
    if(triangle == null || triangle.length == 0 || triangle[0].length == 0) return 0;
    int row = triangle.length;
    for(int i= row -2; i >=0; i--) {
        for(int j=0; j<= i; j++)
        triangle[i][j] += Math.min(triangle[i+1][j], triangle[i+1][j+1]);
    }
    return triangle[0][0];
}

2 爬梯子

http://www.lintcode.com/zh-cn/problem/climbing-stairs/

注意点：类似斐波那契别超时~

public int climbStairs(int n) { 
     if(n == 0) return 1;
    a = 1;
    b = 1;
    for(int i = 2; i <= n; i++) {
        int c = a+ b;
        c= b;
        a = b;
    }
    return c;
 }
//---------------------
 public int climbStairs(int n) { 
    int[] f = new int[n+1];
    if(n == 0) return 1;
    f[0] = 1;
    f[1] = 1;
    for(int i = 2; i <= n; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f[n];
 }

// 递归调用会超时,因为有重复计算的过程
   public int climbStairs(int n) {
       if(n == 0) return 1;
       if(n == 1) return 1;
       return climbStairs(n-2)+climbStairs(n-1);
   }
 //  加入记忆化搜索,还超时
 int[] result = null;
   public int climbStairs(int n) {
       result = new int[n];
       Arrays.fill(result, -1);
       if(n == 0) return 1;
       if(n == 1) return 1;
       result[0] = 1,   result[1] = 1;
       return helper(n);
   }
   private int helper(n) {
       if(result[n] != -1) return result[n];
       return helper(n-1) + helper(n-2);
   }
   //
    public int climbStairs(int n) {
         if(n <=1) return 1;
         int last = 1, last_last = 1;
         int now = 0;
         for(int i=1 ; i< n;i++) {
             now = last + last_last;
             last_last = last;
             last = now;
         }
         return now;
     }

3 跳跃游戏

http://www.lintcode.com/zh-cn/problem/jump-game/

注意点：O(N * N)的时间复杂度

错误点：

 //  me
   public boolean canJump(int[] A) {
        // wirte your code here
        if(A == null || A.length == 0) return false;
        int n = A.length;
        int pos =0;
        while(pos <= n -1) {
            if(A[pos] >= n - 1 - pos) return true;
            else {
                int temp = pos + A[pos];
                while(A[temp] == 0) {
                    temp--;
                    if(temp <= pos) return false;
                }
                pos = temp;
            } 
        }
        return false;        
    }
// greedy
public boolean canJump(int[] A) {
    if(A == null || A.length == 0) return false;    
    int farthest = A[0];
    for(int i = 1; i< A.length; i++) {
        if(farthest >= i && farthest < i+ A[i]) {
            farthest = i + A[i];
        }
    }
    return farthest>= A.length - 1;
}
//dp
    public boolean canJump(int[] A) {
    if(A == null || A.length == 0) return false;
    boolean[] can = new boolean[A.length];
    can[0] = true;
    for(int i = 1; i < A.length; i++) {
        for(int j = 0; j < i; j++) {
            if(can[j] && A[j] + j >= i) {
                can[i] = true;
                break;
            }
        }
    }
    return can[A.length - 1];
}

4  跳跃游戏二

http://www.lintcode.com/zh-cn/problem/jump-game-ii/

注意点：

错误点：结果数组没有初始化，数组间的关系没搞清楚

public int jump(int[] A) {
        // state
        int[] steps = new int[A.length];

        // initialize
        steps[0] = 0;
        for (int i = 1; i < A.length; i++) {
            steps[i] = Integer.MAX_VALUE;
        }

        // function
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (steps[j] != Integer.MAX_VALUE && j + A[j] >= i) {
                    //steps[i] = Math.min(steps[i], steps[j] + 1);
                    steps[i] = steps[j] + 1;
                    break; //贪心
                }
            }
        }
        
        // answer
        return steps[A.length - 1];
    }

5  two Sum

http://www.lintcode.com/en/problem/two-sum/

注意点： map里存需要的值和它的角标；

//dp
  public int[] twoSum(int[] numbers, int target) {
    // write your code here
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int i = 0 ; i< numbers.length; i++) {
        if(map.get(numbers[i]) != null) {
            int[] result = {map.get(numbers[i]) + 1, i+1};
            return result;
        }
        // if在前，put在后，一定要这样，先看有没有再放。
        map.put(target - numbers[i], i);
    }
    int[] result = {};
    return result;
 }
//---------------------------
public int[] twoSum(int[] numbers, int target) {
    // write your code here
    if(numbers == null || numbers.length <= 1) return null;
    for(int i = 0; i< numbers.length - 1; i++) {
        for(int j = i+1; j< numbers.length; j++) {
            if(numbers[i] == target - numbers[j]) return new int[]{i + 1, j + 1};
        }
    }
    return null;
 }

 6 k sum   不会

http://www.lintcode.com/zh-cn/problem/k-sum/

 7 最长上升连续子序列

http://www.lintcode.com/zh-cn/problem/longest-increasing-continuous-subsequence/

注意点：

public int longestIncreasingContinuousSubsequence(int[] A) {
    if(A == null || A.length == 0) return 0;
    int[] result = new int[A.length];
    Arrays.fill(result, 1);
    int max = 1;
    for(int i = 1; i< A.length; i++) {
        if(result[i -1] == 1) {
            result[i] =2;
            if(max < result[i]) max = result[i];
            continue;
        }
        if(A[i-2] < A[i -1] && A[i-1] < A[i] ||
        A[i-2] > A[i-1] && A[i-1] > A[i])
        result[i] =  result[i- 1]+1;
        else result[i] = 2;
        if(max < result[i]) max = result[i];
    }
    return max;
}
//------------------------------------------------------------
public int longestIncreasingContinuousSubsequence(int[] A) {
    if(A == null || A.length == 0) return 0;
    int max = 1;
    int length =1;
    for(int i = 1; i < A.length; i++) {
        if(A[i] > A[i-1]) length++;
        else length=1;
        max= Math.max(length, max);
    }
    for(int i = A.length -2; i >=0; i--) {
        if(A[i+1] < A[i]) length++;
        else length=1;
        max= Math.max(length, max);
    }
    return max;
}

 8 最长连续序列

http://www.lintcode.com/zh-cn/problem/longest-consecutive-sequence/

注意点： 求数组中连续序列个数的两种方式：　

　　　　　　　先排序，在求最长的递增序列长度；

　　　　　　　把元素放到set里，之后遍历数组，查找是否包含连续序列，见代码。

public int longestConsecutive(int[] num) {
     if(num == null || num.length == 0) return 0;
     int[] sortArray = bucketSort(num);
     int[] f= new int[sortArray.length];
     f[0] = 1;
     int maxLen = 1;
     for(int i = 1; i < sortArray.length; i++) {
         f[i] = 1;
         if(sortArray[i] == sortArray[i -1] + 1) {
             f[i] = f[i - 1] + 1;
         } else if(sortArray[i] == sortArray[i -1]) f[i] = f[i - 1];
         if(maxLen < f[i]) maxLen = f[i];
     }
     return maxLen;
 }
 private int[] bucketSort(int[] num) {
     if(num == null || num.length == 0) return null;
     int max = 0, min = 0;
     for(int i : num) {
         if(max <= i) max = i;
         if(min >= i) min = i;
     }
     long[] bucket = new long[max - min + 1];
     for(int i : num) {
         //如果min= 3， 4应该放在1的位置
         bucket[i - min]++;
     }
     int[] result = new int[num.length];
     int i = 0;
     for(int j = 0; j < bucket.length; j++) {
        if(bucket[j] == 0) continue;
        while(bucket[j] != 0) {
            result[i] = j + min;
            bucket[j] -= 1;
            i++;
        }        
     }
     return result;
 }

 public int longestConsecutive(int[] num) {
     if(num == null || num.length == 0) return 0;
     Set<Integer> set = new HashSet<Integer>();
     for(int i : num) set.add(i);
     int max = 0;
     for(int i = 0; i< num.length; i++) {
         int down = num[i];
         while(set.contains(down)) {
             set.remove(down);
             down--;
         }
         int up = num[i] + 1;
         while(set.contains(up)) {
             set.remove(up);
             up++;
         }
         max = Math.max(max, up-down - 1);
     }
     return max;
 }

public int longestConsecutive(int[] num) {
    if(num == null || num.length == 0) return 0;
    int max = 1;
    Arrays.sort(num);
    HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
    for(int i = 0; i < num.length; i++) {
        if(map.get(num[i]) != null) {
            map.put(num[i] + 1, map.get(num[i]) + 1);
        } else     map.put(num[i] + 1, 1);
        max = Math.max(max, map.get(num[i] + 1));
    }
    return max;
}
//用set存放，while循环找顺序序列，而不需要提前排序
 public int longestConsecutive(int[] num) {
    if(num == null || num.length == 0) return 0;
    HashSet<Integer> set = new HashSet<Integer>();
    for(int i = 0; i < num.length; i++) {
        set.add(num[i]);
    }
    int max = 1;
    for(int i=0;i< num.length; i++) {
        int down = num[i] - 1;
        while(set.contains(down)) {
            set.remove(down);
            down--;
        }
        int up = num[i] + 1;
        while(set.contains(up)) {
            set.remove(up);
            up++;
        }
        max = Math.max(max, up - down -1);
    }
    return max;
}

 9 最大子数组  部分答案看不懂，还是不懂~~~

http://www.lintcode.com/zh-cn/problem/maximum-subarray/

注意点：

public int maxSubArray(int[] nums) {
    //错误点： 没有考虑到 4，-1，2,1 这种情况，应该是6，目前结果时4.
    if(nums == null || nums.length == 0) return 0;
    int[] f = new int[nums.length];
    int max = f[0] =  nums[0];
    for(int i = 1; i < nums.length; i++) {
        if(nums[i] >= 0) {
            if(f[i - 1] >=0) f[i] = f[i-1] + nums[i];
            else f[i] = nums[i];
        } else {
            if(f[i - 1] < nums[i]) f[i] = nums[i];
            else f[i] = nums[i];
            
        }
        max = Math.max(max, f[i]);
    }
    return max;
}
public int maxSubArray(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int max = nums[0], sum = 0;
    for(int i = 0; i < nums.length; i++) {
        sum +=nums[i];
        max = Math.max(sum, max);
        sum = Math.max(sum, 0);
    }
    return max;
}

 public int maxSubArray(int[] nums) {
    int max = Integer.MIN_VALUE, sum = 0;
    if(nums == null || nums.length  ==0) return 0;
    for(int i =0; i < nums.length; i++) {
        sum += nums[i];
        max = Math.max(sum, max); //用max记录每次sum后现阶段遇到的最大sum和。
        sum = Math.max(0, sum);  //每次sum的和一定要大于0，否则之前sum的数字就不要了。
    }
    return max;
 }
 //---------------------------------------------------------------
  public int maxSubArray(int[] nums) {
    int max = Integer.MIN_VALUE, sum = 0;
    if(nums == null || nums.length  ==0) return 0;
    int[] partMax = new int[nums.length];
    int[] globalMax = new int[nums.length];
    partMax[0] = globalMax[0] = nums[0];
    
    for(int i = 1; i < nums.length; i++) {
        partMax[i] = Math.max(partMax[i - 1] + nums[i], nums[i]);
        globalMax = Math.max(partMax[i], globalMax[i-1]);
    }
    return globalMax[nums.length - 1];
}

 10 分割回文串2

http://www.lintcode.com/zh-cn/problem/palindrome-partitioning-ii/#

注意点：

private boolean[][] getInstance(String s) {
    boolean[][] str = new boolean[s.length()][s.length()];
    for(int i = 0; i < s.length(); i++) {
        str[i][i] = true;
    }
    for(int i = 0; i < s.length() - 1; i++) {
        str[i][i+1] = s.charAt(i) == s.charAt(i+1);
    }
    for(int len = 2;len <s.length(); len++) {
        for(int i = 0; i + len < s.length(); i++) {
            str[i][i+len] = str[i + 1][i+len -1] && s.charAt(i) == s.charAt(i+len);
        }
    }
    return str;
}
public int minCut(String s) {
    if(s==null || s.length() ==0) return 0;
    boolean[][] str = getInstance(s);
    int[] f = new int[s.length() + 1];
    for(int i = 0; i < f.length; i++) {
        f[i] = i - 1;
    }
    for(int i= 1; i <= s.length(); i++) {
        for(int j = 0; j < i; j++) {
            if(str[j][i-1]) {
                f[i]= Math.min(f[i], f[j] + 1);
            }
        }
    }
    return f[f.length -1];
}

for(int i = 0; i<f.length; i++) {  
        f[i] = i - 1;  //i长度的字符串,最多分割i-1刀可以构成回文串，设为Integer.MAX_VALUE也行,关键是f[0]=-1,f[1]=0
    }
    for(int i = 1; i <= s.length(); i++) { //长度为i的字符串
        for(int j = 0; j< i; j++) {              //两个子串： 0~j-1, j~i-1，判断是否是回文串。
            if(str[j][i-1]) {
                f[i] = Math.min(f[i], f[j] + 1);  //f[j]已经在之前求出来了,表示0~j-1这j个字符至少分几刀可以形成回文串
            }
        }
    }

  private boolean isPalindrome(String s, int start, int end) {
    for(int i = start, j = end; i < j; i++,j--) {
        if(s.charAt(i) != s.charAt(j)) return false;        
    }
    return true;
}
private boolean[][] getPalindromeInstance(String s) {
    boolean[][] str = new boolean[s.length()][s.length()];
    for(int i = 0; i<s.length(); i++) {
        str[i][i] = true;
    }
    for(int i = 0; i<s.length() - 1; i++) {
        str[i][i+1] = isPalindrome(s, i, i+1);
    }
    for(int len = 2; len < s.length(); len++) {  //长度是len+1的子串
        for(int i = 0; i + len < s.length(); i++) {    //len+i代表尾角标位置
            str[i][i+len] = isPalindrome(s, i + 1, i+len - 1) && s.charAt(i) == s.charAt(i+len);
        }
    }
    return str;
}
public int minCut(String s) {
     if(s==null || s.length() == 0) return 0;
     boolean[][] str = getPalindromeInstance(s);
     
     int[] f = new int[s.length() + 1];
     for(int i = 0; i < f.length; i++) {  //长度为i的字符串最多分割i-1次就可以都是回文串，也可以将f[i]设为Integer.MAX_VALUE；
         f[i] = i - 1;
     }
     for(int i = 1; i<= s.length(); i++) {//i个字符构成回文串
        for(int j = 0; j < i; j++) {
            if(str[j][i -1]) {
                f[i] = Math.min(f[i],f[j] + 1);
            }
        }
     }
     return f[f.length - 1];
}

 11  单词分割

http://www.lintcode.com/problem/word-break

public boolean wordBreak(String s, Set<String> dict) {
    if(s == null || s.length() == 0) return true;
    if(dict == null ||dict.size() == 0) return false;
    int wordLen = 0;
    for(String s1 : dict) {
        wordLen = Math.max(wordLen, s1.length());
    }
    boolean f[] = new boolean[s.length() + 1];
    f[0] = true;
    for(int i = 1; i <= s.length(); i++) {   //i表示包含i个单词，j表示最后一个单词的长度
        f[i] = false;
        //0~i-1   0~i-j-1,i-j~i-1
        for(int j=1;j<=wordLen && j<=i; j++) {
            if(f[i-j]) {
                if(dick.contains(s.subString(i-j, i-1))) {
                    f[i] = true;
                    break;
                }
            }
        }
    }
    return f[f.length - 1];
}

public boolean wordBreak(String s, Set<String> dict) {
    if(s == null || dict == null) return false;
    if(dict.size() == 0) {
        if(s.length() == 0 ) return true;
        return false;
    }
    int maxLen = 0;
    for(String s1 : dict) {
        maxLen = Math.max(s1.length(), maxLen);
    }
    boolean[] canBreak = new boolean[s.length() + 1];
    canBreak[0] = true;
    for(int i = 1; i <= s.length(); i++) {
        canBreak[i] = false;
        for(int lastWordLen = 1; lastWordLen <=i && lastWordLen <= maxLen; lastWordLen++) {
            if(canBreak[i - lastWordLen]) {    //最后一个单词的下标是 [i - lastWordLen, i) 左开右闭，包含的字符个数为lastWordLen
                String word = s.substring(i - lastWordLen, i); 
                if(dict.contains(word)) {
                    canBreak[i] = true;
                    break;
                }
            }
        }
    }
    return canBreak[s.length()];
}

 12 最长公共子序列  LCS

http://www.lintcode.com/zh-cn/problem/longest-common-subsequence/#

public int longestCommonSubsequence(String A, String B) {
    if(A == null || B == null || A.length() == 0 || B.length() == 0) {
        return 0;
    }
    int m = A.length(), n = B.length();
    int[][] f = new int[m+1][n+1];
    for(int i = 1; i <=m; i++) {
        f[i][0] = 0;
    }
    for(int i = 0; i <=n; i++) {
        f[0][i] = 0;
    }
    for(int i = 1; i<=m; i++) {
        for(int j =1; j<=n; j++) {
            if(A.charAt(i-1) == B.charAt(j-1)) {
                f[i][j] = f[i-1][j-1]+1;
            } else {
                f[i][j] = Math.max(f[i][j-1],f[i-1][j]);
            }
        }
    }
    return f[m][n];
}

    public int longestCommonSubsequence(String A, String B) {
    if(A == null || B == null || A.length() == 0 || B.length() == 0) return 0;
    int[][] lcs = new int[A.length() + 1][B.length() + 1];
    for(int i = 0; i <= A.length(); i++) {
        lcs[i][0] = 0;
    }
    for(int j = 0; j <= B.length(); j++) {
        lcs[0][j] = 0;
    }
    for(int i = 1; i <= A.length(); i++) {
        for(int j = 1; j <= B.length(); j++) {
            if(A.charAt(i-1) == B.charAt(j-1)) {
                lcs[i][j] =  Math.max(lcs[i - 1][j - 1]+1, Math.max(lcs[i - 1][j], lcs[i][j - 1]));  //只写lcs[]][]+1即可，不用判断的
            } else {
                lcs[i][j] =  Math.max(lcs[i - 1][j - 1]+0, Math.max(lcs[i - 1][j], lcs[i][j - 1]));
            }
        }
    }
    return lcs[A.length()][B.length()];
}

 13  最长公共子串

http://www.lintcode.com/zh-cn/problem/longest-common-substring/#

问题： contains复杂度O(n)？？？

注意点：

错误点： f[i][j]的含义搞不太懂，想一想递归关系之间的具体实现过程。在循环过程中，公共子串中的每一个字符都会作为最后一个字符去进行比较。

public int longestCommonSubstring(String A, String B) {
    if(A == null || B == null || A.length() == 0 || B.length() == 0) return 0;
    int max = 0;
    for(int i = 0; i < A.length(); i++) {
        for(int j= i + 1; j <= A.length(); j++) {
            if(B.contains(A.substring(i,j))) max = Math.max(max, j- i);
        }
    }
    return max;                //O(n * n * n)
 }
//----------------------------------------------------
public int longestCommonSubstring(String A, String B) {
    if(A == null || B == null || A.length() == 0 || B.length() == 0) return 0;
    
    int[][] lcs = new int[A.length() + 1][B.length() + 1];
    for(int i = 1; i <= A.length(); i++) {
        for(int j = 1; j <= B.length(); j++) {
            if(A.charAt(i-1) == B.charAt(j-1)) {
                lcs[i][j] = lcs[i - 1][j - 1]+1;
            } else {
                lcs[i][j] =  0;
            }
        }
    }
    
    int max = 0;    
    for(int i = 1; i <= A.length(); i++) {
        for(int j = 1; j <= B.length(); j++) {
            max = Math.max(max, lcs[i][j]);
        }
    }
    return max;
}

 14 编辑距离

http://www.lintcode.com/zh-cn/problem/edit-distance/#

 // 为什么要死记公式啊，先求lcs再去匹配一致，考虑并不周全     abc     cab  
 public int minDistance(String word1, String word2) {
    if(word1 == null || word2 == null) {
        if(word1 != null) return word1.length();
        if(word2 != null) return word2.length();
        return 0;
    }
    int[][] lcs = new int[word1.length() + 1][word2.length() + 1];
    for(int i = 1; i <= word1.length(); i++) {
        for(int j = 1; j <= word2.length(); j++) {
            if(word1.charAt(i-1) == word2.charAt(j-1)) {
                lcs[i][j] = lcs[i - 1][j - 1]+1;
            } else {
                lcs[i][j] =  0;
            }
        }
    }
    int max = 0;    
    for(int i = 1; i <= word1.length(); i++) {
        for(int j = 1; j <= word2.length(); j++) {
            max = Math.max(max, lcs[i][j]);
        }
    }
    return Math.max(word1.length()-max, word2.length() - max);
}
//----------------------
 public int minDistance(String word1, String word2) {
    if(word1 == null || word2 == null) {
        if(word1 != null) return word1.length();
        if(word2 != null) return word2.length();
        return 0;
    }
    int[][] f =  new int[word1.length() + 1][word2.length() + 1];
    for(int i = 0; i <= word1.length(); i++) f[i][0] = i;
    for(int j = 0; j <= word2.length(); j++) f[0][j] = j;
    
    for(int i = 1; i <=word1.length(); i++) {
        for(int j = 1; j <= word2.length(); j++) {
            if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
                f[i][j] = Math.min(Math.min(f[i-1][j] + 1, f[i][j-1]+1),f[i- 1][j - 1]);
            } else {
                f[i][j] = Math.min(Math.min(f[i-1][j] + 1, f[i][j-1]+1),f[i- 1][j - 1] + 1);
            }
        }
    }
    return f[word1.length()][word2.length()];
 }

链表----------------------------------------------------------------------------------------

注意事项： 调用node.next时，一定要确保node非null，否则空指针异常。

　　　　　链表的head 和head.next是否为空先判断下，类似二叉树root要单独拿出来考虑一样。

链表的基本操作
1. Insert a Node in Sorted List
2. Remove a Node from Linked List
3. Reverse a Linked List
4. Merge Two Linked Lists
5. Middle of a Linked List

1.  // 最简单的方法
    private ListNode reverse(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode prev = null;
        while(head!= null ) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
    //另一种写法
 private ListNode reverse(ListNode head) {
     if(head == null || head.next == null) return head;
     ListNode tail = head;
     ListNode next =tail.next;
     while(next != null) {
         ListNode temp = next.next;
         next.next =tail;
        tail = next;
        next =temp;
     }        
     head =tail;
     tail.next = null;
     return head;
 }
4. private ListNode merge(ListNode left, ListNode right) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while(left != null && right != null) {
        tail.next = left;
        left = left.next;
        tail = tail.next;
        tail.next = right;
        right.next = right;
        tail = tail.next;
    }
    if(left != null) tail.next = left;
    else tail.next = right;
    return dummy.next;
}
5.   快慢指针
    private ListNode getMid(ListNode head) {}
     //12345  要找到3
     if(head == null || head.next == null) return head;
     ListNode slow = head, fast = head;
     while(fast.next != null && fast.next.next != null) {
         slow = slow.next;
         fast = fast.next.next;
     }
     return slow;
    //查找倒数第n个结点
    private ListNode find(ListNode head) {
          ListNode slow = head, fast = head;
    // 1 2 3 4 5  找4，倒数第2个，需要在fast走第二步的时候，slow开始走第一步
    int i = 0;
    while(fast.next != null) {
        i++;
        fast = fast.next;
        if(i < 2) coutinue;
        slow = slow.next;
    }
    return slow;
    }

1　　删除排序链表2

http://www.lintcode.com/zh-cn/problem/remove-duplicates-from-sorted-list-ii/

//----------------运行超时
  public static ListNode deleteDuplicates(ListNode head) {
        // write your code here
        if(head == null || head.next == null) return head;
        ListNode prev = null;
        ListNode curr = head;
        Map<ListNode,Integer> map = new HashMap<ListNode,Integer>();
        int value = 0;
        while(curr != null) {
            if(map.get(curr) != null) {
                map.put(curr,map.get(curr) + 1);
            } else {
                map.put(curr,1);
            }
        }
        prev.next = head;
        curr = head;
        ListNode currNext = curr.next;
        while(currNext != null) {
            if(map.get(currNext) != 1) {
                curr = currNext;
                currNext.next = currNext.next;
            }
        }
        return prev.next;
    }
//--------------------------------------------------
 public static ListNode deleteDuplicates(ListNode head) {
     if(head == null || head.next == null) return head;
     ListNode dummy = new ListNode(0);
     dummy.next = head;
     //只要不用next操作，引用再怎么换也不会影响链表。
     head = dummy;
     while(head.next != null && head.next.next != null) {
         if(head.next.val == head.next.next.val) {
             int val = head.next.val;
             while(head.next != null && head.next.val == val) {
                 head.next = head.next.next;
             }
         } else {
             head = head.next;
         }
     }
     return dummy.next;
 }

2　　 删除排序链表

http://www.lintcode.com/zh-cn/problem/remove-duplicates-from-sorted-list/#

注意点：引入dummy的目的是为了不用将头结点删除与否分情况讨论。这里头结点肯定不用删除，所以可以不引入dummy。

            也可以沿用删除链表2的解法，稍微改改。

 public static ListNode deleteDuplicates(ListNode head) { 
        // write your code here
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while(head.next != null && head.next.next != null) {
            if(head.next.val == head.next.next.val) {
                head.next = head.next.next;
            } else head = head.next;
        }
        return dummy.next;
    }  

3　　反转链表

http://www.lintcode.com/zh-cn/problem/reverse-linked-list/

注意点： 死记解法，四步骤

 public ListNode reverse(ListNode head) {
        // write your code here
       ListNode prev = null;
       while(head != null) {
           ListNode temp = head.next;
           head.next = prev;
           prev = head;
           head = temp;
       }
       return prev;
    }

4 　　反转链表2

http://www.lintcode.com/zh-cn/problem/reverse-linked-list-ii/

错误点： 第二个for循环里写成了if(nPost.next== null) return null;

注意点： 第二个for循环里，n~m ,共n-m+1个数字，需要nNode走n-m次，i=m+1时，n移动了一次,所以i最后出了循环需要等于m+n-m = n

public ListNode reverseBetween(ListNode head, int m , int n) {
      if(head == null || m >= n) return head;
      ListNode dummy = new ListNode(0);
      dummy.next = head;
      head = dummy;
      for (int i = 1; i < m; i++) {
          if(head != null) head = head.next;
          else return null;
      }
      ListNode mprev = head;
      ListNode mNode = mprev.next;
      ListNode nNode = mNode;
      ListNode nPost = nNode.next;
      for(int i = m; i < n;i++) {
          if(nPost == null) return null;
          ListNode temp = nPost.next;
          nPost.next = nNode;
          nNode = nPost;
          nPost = temp;
      }
      mprev.next = nNode;
      mNode.next = nPost;
      return dummy.next;
      
  }

5　　链表划分

http://www.lintcode.com/zh-cn/problem/partition-list/

注意点： 将链表分成两个子链，左链放比指定数小的，右链连比指定数大的，最后再将他们合并。

　　　　　leftDummy和rightDummy保持不动，作为头指针，然后从它们的位置发出left和right指针，作为尾指针，依次移动记录当前子链表的最后一个位置。

　　　　  头指针.next=头结点，尾指针=尾结点

public ListNode partition(ListNode head, int x) {
       if(head == null) return head;
       ListNode leftDummy =  new ListNode(0);
       ListNode rightDummy =  new ListNode(0);
       ListNode left = leftDummy, right = rightDummy;
       while(head != null) {
           if(head.val < x) {
               left.next = head;
               left = head;
           } else {
               right.next = head;
               right = head;
           }
           head = head.next;
       }
       right.next = null;
       left.next = rightDummy.next;
       return leftDummy.next;
   }

 6　　链表排序

http://www.lintcode.com/zh-cn/problem/sort-list/#

注意点： 

错误点： sortList(ListNode head) 里if(head == null )而不判断head.next会报错，为啥？？？？？？

  private ListNode findMid(ListNode head) {
        ListNode slow = head, fast = head.next;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
        //  12345   return 2;
   }
   private ListNode merge(ListNode head1, ListNode head2) {
       //dummy是合并后主链表的头，tail是尾。head1或head2中每当有一个结点链入主链，那链入的那个结点就可以
       //在原先的链表中删除了，同时把原先的链表的头往后移。因为主链中加入了一个结点，所以主链的tail后移一次。
       ListNode dummy = new ListNode(0), tail = dummy;
       while(head1 != null && head2 != null) {
           if(head1.val < head2.val) {
               tail.next = head1;
               head1 = head1.next;
           } else {
               tail.next = head2;
               head2 = head2.next;
           }
           tail = tail.next;
       }
       //head1或head2有一个都链入主链后，把另一个非空的原先链表在链到主链尾部
       //（这时原先链表中的后面位置的结点并没有进行排序。）
       //最后返回的结果只是将head1或者head2进行排序了。（head1为空，则代表它完成排序了）
       //要保证最后都有序，则head1和head2必须先有序。
       if(head1 != null) {
           tail.next = head1;
       } else {
           tail.next = head2;
       }
       return dummy.next;
   }
   
   public ListNode sortList(ListNode head) {
       if(head == null || head.next == null) return head;
       ListNode mid = findMid(head);
       ListNode right = sortList(mid.next);
       mid.next = null; 
       ListNode left = sortList(head);
       return merge(left, right);
    }

7      重排链表

http://www.lintcode.com/zh-cn/problem/reorder-list/#

public void reorderList(ListNode head) {  
       if(head == null || head.next == null) return;
       ListNode mid = getMid(head);
       ListNode right = reverse(mid.next);
       mid.next = null;
       head = merge(head, right);        
    }
    
private ListNode getMid(ListNode head) {}
    //12345   15243 要找到3
    if(head == null || head.next == null) return head;
    ListNode slow = head, fast = head;
    while(fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}
private ListNode reverse(ListNode head) {
    if(head == null || head.next == null) return head;
    
    ListNode prev = null;
    while(head!= null ) {
        ListNode temp = head.next;
        head.next = prev;
        prev = head;
        head = temp;
    }
    return prev;
}
private ListNode merge(ListNode left, ListNode right) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while(left != null && right != null) {
        tail.next = left;
        left = left.next;
        tail = tail.next;
        tail.next = right;
        right = right.next;
        tail = tail.next;
    }
    if(left != null) tail.next = left;
    else tail.next = right;
    return dummy.next;
}

8    带环链表

http://www.lintcode.com/zh-cn/problem/linked-list-cycle-ii/#

注意点：快慢指针

public ListNode detectCycle(ListNode head) {  
    if(head == null || head.next == null) return null;
    ListNode slow1 = head, fast = head;
    while(fast.next != null && fast.next.next != null) {
        slow1= slow1.next;
        fast = fast.next.next;
        if(slow1 == fast) {
            ListNode slow2 = head;
            while(true) {
                if(slow1 == slow2) return slow1;
                slow2 = slow2.next;
                slow1 = slow1.next;
            }
        }
    }
    return null;
}

 9　 旋转链表

http://www.lintcode.com/zh-cn/problem/rotate-list/#

 public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null || k == 0) return head;
        int len = 0;
        ListNode temp = head;
        while( temp != null ) {
            len++;
            temp = temp.next;
        }
        k = k % len;
        if(k == 0) return head;
        ListNode tail= head;
        int i = 1;
        while( len - k != i) {
            i++;
            tail = tail.next;
        }
        ListNode newHead = tail.next, temp1 = newHead;
        tail.next = null;
        while(temp1.next != null) {
            temp1 = temp1.next;
        }
        temp1.next = head;
        return newHead;
    }
   //----------------------------------------------------
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length ++;
            head = head.next;
        }
        return length;
    }
    
    public ListNode rotateRight(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        
        int length = getLength(head);
        n = n % length;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        
        ListNode tail = dummy;
        //寻找倒数第n个结点(类似快慢指针实现的)
        for (int i = 0; i < n; i++) {
            head = head.next;
        }  
        while (head.next != null) {
            tail = tail.next;
            head = head.next;
        }
        
        head.next = dummy.next;
        dummy.next = tail.next;
        tail.next = null;
        return dummy.next;
    }

 10   合并k个排序链表

http://www.lintcode.com/zh-cn/problem/merge-k-sorted-lists/

//两两合并----------------------------------------------
    public ListNode mergeKLists(List<ListNode> lists) {  
        if(lists == null || lists.size() == 0) return null;
        
        while(lists.size() > 1) {
            List<ListNode> newList = new ArrayList<ListNode>();
            for(int i = 0; i + 1< lists.size() ; i+=2) {
                ListNode dummy = new ListNode(0);
                dummy.next = mergeTwo(lists.get(i), lists.get(i+1));
                newList.add(dummy.next);
            }
            if(lists.size() % 2 != 0) newList.add(lists.get(lists.size() - 1));
            lists = newList;
        }
        return lists.get(0);
    }
    
    private ListNode mergeTwo(ListNode node1, ListNode node2) {
        ListNode dummy = new ListNode(0), tail = dummy;
        while(node1 != null && node2 != null) {
            if(node1.val < node2.val) {
                tail.next = node1;
                node1 = node1.next;
            } else {
                tail.next = node2;
                node2 = node2.next;
            }
            tail = tail.next;
        }
        if(node1 != null) {
            tail.next = node1;
        } else {
            tail.next = node2;
        }
        return dummy.next;
    }
    //分治-------------------------------------------------
     public ListNode mergeKLists(List<ListNode> lists) {  
        if(lists == null || lists.size() == 0) return null;
        return mergeHelper(lists, 0, lists.size() - 1);
     }
     private ListNode mergeHelper(List<ListNode> lists, int start , int end) {
         if(start == end) return lists.get(start);
         int mid = start + (end - start) / 2;
         ListNode left = mergeHelper(lists, start, mid);
         ListNode right = mergeHelper(lists, mid+1, end);
         return mergeTwo(left, right);
     }
     
    private ListNode mergeTwo(ListNode node1, ListNode node2) {
        ListNode dummy = new ListNode(0), tail = dummy;
        while(node1 != null && node2 != null) {
            if(node1.val < node2.val) {
                tail.next = node1;
                node1 = node1.next;
            } else {
                tail.next = node2;
                node2 = node2.next;
            }
            tail = tail.next;
        }
        if(node1 != null) {
            tail.next = node1;
        } else {
            tail.next = node2;
        }
        return dummy.next;
    }

11   复制随机指针链表

http://www.lintcode.com/zh-cn/problem/copy-list-with-random-pointer/#

注意点：传入head并在另一个函数中操作时，并不会引起传入前的head的变化。 

　　　　见答案，不需要返回值　　http://www.jiuzhang.com/solutions/copy-list-with-random-pointer/

  public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return head;
         head = insert(head);
        RandomListNode dummy = new RandomListNode(0);
        dummy.next = head;
        while(head != null) {
            if(head.random == null) {
                head.next.random = null;
            } else {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
        dummy.next = remove(dummy.next);
        return dummy.next;
        
    }
    private RandomListNode insert(RandomListNode head) {
        if(head == null) return head;
        RandomListNode dummy = new RandomListNode(0);
        dummy.next = head;
        while(head != null) {
            RandomListNode temp = new RandomListNode(head.label);
            temp.next = head.next;
            head.next = temp;
            head = head.next.next;
        }
        return dummy.next;
    }
    private RandomListNode remove(RandomListNode head) {
        RandomListNode dummy = new RandomListNode(0);
        dummy.next = head.next;
        while(head.next.next != null) {
            RandomListNode temp = head.next.next;
            head.next.next = head.next.next.next;
            head = temp;
        }
        return dummy.next;
    }

 //-----------------------------------------------------------------------------------------------------------------

Arrays      拿到数组先排序，最快需要nlogn.(快排，归并，堆排)，然后看看排序是否有助于问题解决，是否满足复杂度要求。

　　　　数组和的问题，排序后，收尾指针依次中间移动，可以以O(n)的代价，遍历一次就能判断是否满足。

1    合并排序数组

注意点：可以从头开始合并，也可以从尾开始合并

http://www.lintcode.com/zh-cn/problem/merge-sorted-array/

 public void mergeSortedArray(int[] A, int m, int[] B, int n) {
       int index = m+n-1, i = m - 1, j = n - 1;
       while(i >=0 && j >=0) {
           if(A[i] > B[j]) {
               A[index--] = A[i--]; 
              
           } else {
               A[index--] = B[j--]; 
           }
       }
       while(i >= 0) {
           A[index--] = A[i--]; 
       } 
       while(j >= 0) {
           A[index--] = B[j--]; 
       }
       
    }

 2  两个排序数组的中位数

http://www.lintcode.com/zh-cn/problem/median-of-two-sorted-arrays/

注意点：找中点，就是找第k个数，依次剔除k/2, k/4,......1个数，剩下的就是要找的数。

              如果k个排序数组找中位数，则二分答案，判断此答案是否位于中间。

错误点： 需要double，则return时除的时候要 /2.0 而不是  /2

//  A = 2 3 4 5 6 7
 //  B = 1
 // 找中点，第k = 4大的数，则先去掉 k/2 = 2 个数，之后再从剩下的数中找第k-k/2 = 2大的数。
 //                             去2个数时，由于B不包含2个数，所以把A的前2个数去掉，剩下： 4 5 6 7  和 1;  
 // 从它们中找第2大的数就是结果。去掉的数不一定非要是A，B中最小的前几个数，只要保证去掉的数比要找的数小，那要找的数的相对位置就不会变。
 // 在4 5 6 7  和 1中找第2个大的数时，先去掉1个数，在从剩下的里面找第一个大的数就是结果。所以把1去掉，剩下了4 5 6 7 。这时第1个大的数是4，也就是最后结果。
 
 public double findMedianSortedArrays(int[] A, int[] B) {
    int len = A.length + B.length;
    if(len % 2 == 1) return findKth(A, 0, B, 0, len/2+1);
    else return (findKth(A, 0, B, 0, len/2) + findKth(A, 0, B, 0, len/2+1)) / 2.0;
}
//函数含义：A数组从AStart角标开始，B从BStart开始，寻找A，B中第k个大的数
private int findKth(int[] A, int AStart, int[] B, int BStart, int k) {
    if(AStart >= A.length) return B[BStart + k - 1];
    if(BStart >= B.length) return A[AStart + k - 1];
    
    if(k == 1) {
        return Math.min(A[AStart], B[BStart]);
    }
    
    //找第k个，先去掉前k/2个数,AValue和BValue不可能都是MAX_VALUE
    int AValue = AStart + k/2 - 1 < A.length ? A[AStart + k/2 - 1] : Integer.MAX_VALUE;
    int BValue = BStart + k/2 - 1 < B.length ? B[BStart + k/2 - 1] : Integer.MAX_VALUE;
    if(AValue <= BValue) {
        //去A的前k/2个数，则去掉后的角标从AStart+k/2开始
        return findKth(A, AStart+k/2, B, BStart, k - k/2);  //递归的终止条件是k-k/2=1,一定会走到1，因为1+2+...+ k/2 = k - 1 k是偶数，1+1+2+...+ k/2 = k - 1 k是奇数
    } else {
        return findKth(A, AStart, B, BStart + k/2, k - k/2);
    }
}

3  最大子数组2

http://www.lintcode.com/zh-cn/problem/maximum-subarray-ii/

衍生：最小子数组  http://www.lintcode.com/zh-cn/problem/minimum-subarray/#   把数组取反，求出最大子数组，再把结果取反即可。

　　　最大子数组差   http://www.lintcode.com/zh-cn/problem/maximum-subarray-difference/  左右求出最大最小子数组，因为不许重叠，所以找分割线依次比较。

错误点：a=1,b=2；错，要写成a=1；b=2；

　　　　int a =1, b = 2; 可以

注意点：见答案

//最大子数组答案    http://www.lintcode.com/zh-cn/problem/maximum-subarray/   
 public int maxSubArray(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int sum = 0, preFixSum = 0, max = Integer.MIN_VALUE;
    //理解不了的话，只需要知道这个操作能实现功能就行,死记代码
    for(int i = 0; i< nums.length; i++) {
        sum+= nums[i];
        max = Math.max(max, sum - preFixSum);
        preFixSum = Math.min(preFixSum, sum);
    }
    return max;
 }
 
 public int maxTwoSubArrays(List<Integer> nums) {
     if(nums == null || nums.size() <= 1) return 0;
     // i是分割线位置，i+1就是分割线之后的第一个位置的坐标
     int result = Integer.MIN_VALUE;
     for(int i = 0; i < nums.size() - 1; i++) {
         int max1 = Integer.MIN_VALUE, max2 = max1;
         int sum1 = 0, sum2 = 0, preFix1 = 0, preFix2 = 0;
         for(int j = 0; j <=i; j++) {
             sum1+=nums.get(j);
             max1 = Math.max(max1, sum1 - preFix1);
             preFix1 = Math.min(preFix1, sum1);
         }
         for(int j = i+1; j < nums.size(); j++) {
             sum2+=nums.get(j);
             max2 = Math.max(max2, sum2 - preFix2);
             preFix1 = Math.min(preFix2, sum2);
         }
         result = Math.max(result, max1+max2);
     }
     return result;
 }
 //O(n)---------------------------------------------
  public int maxTwoSubArrays(List<Integer> nums) {
      int[] left = new int[nums.size()];
      int[] right = new int[nums.size()];
      int sum = 0, preFixSum = 0, max = Integer.MIN_VALUE;
      for(int i = 0; i< nums.size(); i++) {
          sum+= nums[i];
          max = Math.max(max, sum - preFixSum);
          preFixSum = Math.min(preFixSum, sum);
          left[i] = max;
      }
      sum = 0, preFixSum = 0, max = Integer.MIN_VALUE;
      for(int i = nums.size() - 1; i >= 0; i--) {
          sum+= nums[i];
          max = Math.max(max, sum - preFixSum);
          preFixSum = Math.min(preFixSum, sum);
          right[i] = max;
      }
      int result = Integer.MIN_VALUE;
      for(int i = 0; i < nums.size() - 1; i++) {
          result = Math.max(result, left[i] + right[i+1]);
      }
      return result;
  }

4  买卖股票的最佳时机

http://www.lintcode.com/zh-cn/problem/best-time-to-buy-and-sell-stock/

http://www.lintcode.com/zh-cn/problem/best-time-to-buy-and-sell-stock-ii/

http://www.lintcode.com/zh-cn/problem/best-time-to-buy-and-sell-stock-iii/#

 注意点：包含DP

错误点：  ①profit = Math.max(profit, i - min);

　　         ②min = Math.min(min, i);            一二前后顺序的区别是是否每一轮至少要包含一个数。此题中盈利的计算，一开始是买入，没有盈利，所以也即一个数都不能包含，

　　　　　　　　　　　　　　　　　　　所以要先②后①。

//错误逻辑，思路都理不清，代码更写不出来。 
 public int maxProfit(int[] prices) {
    if(prices == null || prices.length <= 1) return 0;
    int profit = 0, min = 0;
    for(int i : prices) {
        min = Math.min(min, i);
        profit + =  i - min;    
    }
    return profit;
}
// 当天有盈利，代表着当天卖出和前一天买入。连续三天盈利，每隔天的买入卖出正好合下来是三天前买入，三天后卖出的情况。 1    2    3    4
public int maxProfit(int[] prices) {
    int profit = 0;
    for(int i = 0; i < prices.length- 1; i++) {
        int diff = prices[i + 1] - prices[i];
        if(diff > 0) profit += diff;
    }
    return profit;
}

 //-----------------------------------------------------------
    //  暴力破解
     public int maxProfit(int[] prices) { 
        if(prices == null || prices.length == 0) return 0;
        int max =0 ;
        for(int i = 1; i< prices.length; i++) {
            int sum = 0;
            for(int j = 0; j < i; j++) {            
                max= Math.max(max, prices[i] - prices[j]);
            }            
        }
        return max;
   }
 //------------------------------------------------------
   public int maxProfit(int[] prices) { 
      if(prices == null || prices.length == 0) return 0;
      int min = Integer.MAX_VALUE, profit = 0;
      for(int i : prices) {
          min = Math.min(i, min);   // min = i < min ? i : min;
          profit = Math.max(i - min, profit);
      }
      return profit;
   }
   
//股票二------------------------------------------
public int maxProfit(int[] prices) {
    int profit = 0;
    for(int i = 0; i < prices.length- 1; i++) {
        int diff = prices[i + 1] - prices[i];
        if(diff > 0) profit += diff;
    }
    return profit;
}

//股票三-----------------------------------------------
public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
            return 0;
        }

    int[] left = int[prices.length];
    int[] right = int[prices.length];
    
    //从左往右看，不依赖于右侧，能卖出的最大利润。通过更新买入的最小值(min)来计算  DP
    int min = prices[0], left[0] = 0;
    for(int i = 1; i < prices.length; i++) {
        min = math.min(min, prices[i]);
        left[i] = Math.max(left[i - 1], prices[i] - min);
    }
    
    //从右往左看，不依赖于左侧，能卖出的最大利润。通过更新卖出的最大值(max)来计算
    int max = prices[prices.length - 1], right[prices.length - 1] = 0;
    for(int i = prices.length -2; i>=0; i--) {
        max = Math.max(prices[i], max);
        right[i] = Math.max(right[i + 1], max - prices[i]);
    }
    
    //类似分割线，left和right不交叉
    int maxProfit = 0;
    for(int i = 0; i < prices.length; i++) {
        maxProfit = Math.max(maxProfit, left[i] + right[i]);
    }
    return maxProfit;
}

 5  两数和

http://www.lintcode.com/zh-cn/problem/two-sum/

衍生： 三数和  http://www.lintcode.com/zh-cn/problem/3sum/ 

　　　　4数　　　　http://www.lintcode.com/zh-cn/problem/4sum/ 

注意点：时间复杂度的计算：

　　　　　　排序模块的最优复杂度nlogn，找两数和的复杂度n，所以合并的复杂度是nlogn，即用这种方法的复杂度为nlogn。

　　　　　　如果放入map中，遍历一次数组，复杂度n,判断map是否包含，n，所以最后合并的复杂度n。

//O(n * n)---------------------------------------------------------------
 public int[] twoSum(int[] numbers, int target) { 
    if(numbers == null || numbers.length == 0) return new int[]{-1, -1};
    for(int i = 0; i < numbers.length - 1; i++) {
        for(int j = i +1; j < numbers.length; j++) {
            if(numbers[i] + numbers[j] == target) return new int[]{i +1, j+1};
        }
    }
    return new int[]{-1, -1};
    
 //O(nlogn)--------------------------
public int[] twoSum(int[] numbers, int target) { 
    //先排序，获得排序数组nlogn,下面的操作是O(n)，最后总体的时间复杂度nlogn.
    if(numbers == null || numbers.length <=1) return new int[]{-1, -1};
    for(int i = 0, j = numbers.length - 1; i < j;) {
        if(numbers[i] + numbers[j] == target) return new int[]{i + 1,j + 1};
        else if ( numbers[i] + numbers[j] < target) i++;
        else j--;
    }
    return new int[]{-1, -1};

}
//O(n)------------------------------
public int[] twoSum(int[] numbers, int target) { 
    if(numbers == null || numbers.length == 0) return null;
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int i = 0; i < numbers.length; i++) {    
        if(map.containsKey(numbers[i])) {
            return new int[] {map.get(numbers[i]) + 1, i+1};
        }
        map.put(target - numbers[i], i);
    }
    return null;

 6  数组划分 （类似快排）

http://www.lintcode.com/zh-cn/problem/partition-array/#

衍生：　　http://www.lintcode.com/zh-cn/problem/sort-letters-by-case/        Character.isUpperCase()  

　　　　　http://www.lintcode.com/zh-cn/problem/sort-colors/  

　　　　　http://www.lintcode.com/zh-cn/problem/sort-colors-ii/    （相当于给定k个不同的数的快排）

//报错，rainb里不设置startColo会排序出问题，所以这种换位的快排操作到底会产生什么结果？----------------------------------------------
public void sortColors2(int[] colors, int k) {
     if (colors == null || colors.length == 0) {
            return;
        }
    rainbowSort(colors, 0, colors.length - 1);

}
    
private void rainbowSort(int[] colors, int start, int end) {
    if(colors == null || colors.length <= 1) return;
    if(start >= end) return;
    int mid = start + (end - start) / 2;
    int k = colors[mid];
    int i = start, j = end;
    while(i <= j) {
        while(i <=j && colors[i] < k) i++;
        while(i <=j && colors[j] >= k) j--;
        if(i <= j) {
            int temp = colors[i];
            colors[i] = colors[j];
            colors[j] = temp;
            i++;
            j--;
        }
    }
    rainbowSort(colors, start, i - 1);
    rainbowSort(colors,i + 1, end);
} 
//能用--------------------------------------------------------------------------------- 
 public void sortColors2(int[] colors, int k) {
     if (colors == null || colors.length == 0) {
            return;
        }
    rainbowSort(colors, 0, colors.length - 1, 1,k);

}
    
private void rainbowSort(int[] colors, int start, int end, int startColor, int endColor) {
     if (startColor == endColor) {
            return;
        }
    if(colors == null || colors.length <= 1) return;
    if(start >= end) return;
    int midColor = (startColor + endColor)/2;
    int i = start, j = end;
    while(i <= j) {
        //为啥？？？？？？？？？？？？？？
        //这里必须 <= midColor, 不能是<
        while(i <=j && colors[i] <=  midColor) i++;
        while(i <=j && colors[j] >  midColor) j--;
        if(i <= j) {
            int temp = colors[i];
            colors[i] = colors[j];
            colors[j] = temp;
            i++;
            j--;
        }
    }
    //这里必须是midColor，不能是midColor+1
    rainbowSort(colors, start, i, startColor,  midColor);
    rainbowSort(colors,i,end,  midColor+1, endColor);
}

注意点： 两个指针一首一尾遍历数组        

　　　　死记住程序，条件统一写成 i <= j  ：这样返回的 i 始终是第一个大于等于k的位置，也正是题目所求。

　　　　if(i <= j) 调制完顺序后，i++，j--一下，减少下一次while里的操作。

数组划分

  public int partitionArray(int[] nums, int k) {
        if(nums == null | nums.length <= 0) return -1;
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            while(nums[i] < k) i++;
            while(nums[j] >= k) j--;
            if(i <= j) {
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
        return i;
   }

 7 最接近零的子数组和

http://www.lintcode.com/en/problem/subarray-sum-closest/

问题：最后利用减前缀和求结果的时候，怎么知道这样的结果就离0最近？ 难道是因为后一个肯定比前一个大，所以相减的结果一定大于0，最小的那个就是最接近0的？确实是这样。

　　　　　　-1，-3， -3，-2,1,4,；

 -1位置补0     -1，-3， -3，-2,1,4,   前缀和    -1，-4，-7，-9，-8，-4，排序后：-9，-8，-7，-4，-4，-1。

　子数组一共有O(n * n)个，这里两两相减也就O(n)个，不能全覆盖啊？

注意点：  实现Comparator比较器接口时，虽然接口中有俩抽象方法，但只需要实现compare方法就行，equals方法不用覆盖。

　　　　 此题对应的解法，在数组中有0时，会返回两次0的角标作为返回结果。

错误点： new int[]{0,1}  ，不要写错new int[2]{}

 class Pair {
     //记录前几个数的和
     int sum;
     int index;
     public Pair(int s, int i) {
         this.sum = s;
         this.index = i;
     }
 }
 
 public class Solution {
 
     public int[] subarraySumClosest(int[] nums) { 
        if(nums == null || nums.length == 0) return null;
        if(nums.length == 1) return new int[]{0, 0};
        //结果集数组
        int[] res = new int[2];
        
        int len = nums.length;
        //遍历一次nums，获得Pair数组,其中，前0个数的和是0
        Pair[] sums = new Pair[len + 1]; 
        sums[0] = new Pair(0,0);
        for(int i = 1; i <= len; i++) {
            sums[i] = new Pair(sums[i - 1].sum + nums[i - 1], i);
        }
        
        Arrays.sort(sums, new  Comparator<Pair>(){
            public int compare(Pair p1, Pair p2) {
                return p1.sum - p2.sum;
            }
        });
        
        //排序完成后，遍历sums数组，找到离0最近的子数组，从角标1开始。
        int ans = Integer.MAX_VALUE; //answer
        for(int i = 1; i <= len; i++) {
            if(ans > sums[i].sum - sums[i - 1].sum) { 
                ans = sums[i].sum - sums[i - 1].sum;
                //Pair 记录的是前几个数的和，前0,1,2个等等，对应nums中的角标需要-1；
                int[] temp = new int[]{sums[i].index - 1, sums[i - 1].index - 1};
                Arrays.sort(temp);
                //前5个数的和-前3个数的和离0最近，则需要返回的是第4，第5个的角标，所以temp[0]+1；
                res[0] = temp[0] + 1; 
                res[1] = temp[1];
            }
        }
        return res;
     }
 }

 8 子数组之和（求子数组，先写出来前缀和，sum(i,j) = sum(j) - sum(i - 1),然后看它和所求的关系）

http://www.lintcode.com/zh-cn/problem/subarray-sum/

注意点：子数组和为0，代表存在位置，sum（j) 等于sum（i-1）。

　　　　 　　既然需要sum(i - 1)，那为了求0位置的和同时能用到上面的递推关系，所以在-1位置放一个0；

　　　　　　两sum相等，相当于去重，hash表天然就是实现是否存在，相等问题的，所以使用hashMap存放数据。

public ArrayList<Integer> subarraySum(int[] nums) {
      if(nums == null || nums.length == 0) return null;
      ArrayList<Integer> res = new ArrayList<Integer>();
      Map<Integer, Integer> map = new HashMap();
      map.put(0, -1);
      int sum = 0;
      for(int i = 0; i < nums.length; i++) {
          sum += nums[i];
          if(map.get(sum) != null) {
              res.add(map.get(sum) + 1);
              res.add(i);
              return res;
          }
          map.put(sum, i);
      }
      return null;
  }

数据结构

1 带最小值操作的栈

http://www.lintcode.com/zh-cn/problem/min-stack/#

注意点： 用另一个栈依次记录最小值。

public class MinStack {
 
    //minStack的构造放到构造函数中比较好。
   Stack<Integer> minStack = new Stack<Integer>();
   Stack<Integer> s ;
    
    public MinStack() {
        // do initialize if necessary
       s = new Stack<Integer>();
    }

    public void push(int number) {
        // write your code here
        s.push(number);
        if(minStack.isEmpty() || minStack.peek() >= number) minStack.push(number);
    }

    public int pop() {
        // write your code here
        int number = s.pop();
        if(number == minStack.peek()) minStack.pop();
        return number;
    }

    public int min() {
        // write your code here
        
        return minStack.peek();
    }
}

2 用栈实现队列 

http://www.lintcode.com/zh-cn/problem/implement-queue-by-two-stacks/#

3 直方图最大矩形覆盖（栈）

http://www.lintcode.com/zh-cn/problem/largest-rectangle-in-histogram/#

注意点： 递增栈，每次角标出栈时才计算对应角标高度的直方图面积。(while循环里，栈内弹出一个数需要O(1)，弹出n个数需要O(n)，所以while的平均时间为O(1)，所以

　　　　总体时间就只是for的时间，O(n))。

　　　　高度中找左边和右边第一个比他小的位置，然后就是此高度对应的宽度。

 public int largestRectangleArea(int[] height) {
     if(height == null || height.length == 0) return 0;
     Stack<Integer> s = new Stack<Integer>();
     int max = 0;
     for(int i = 0; i <= height.length; i++) {
         int currHeight = (i == height.length)?-1:height[i];
         while(!s.isEmpty() && currHeight <= height[s.peek()]) {
             int h = height[s.pop()];
             int w = s.isEmpty()? i: i - s.peek() - 1;
             max = Math.max(max, h*w);
         }
         s.push(i);
     }
     return max;
 }

 

4 哈希表原理（增删查的复杂度O(1)，二叉查找树logn）

Cache （一个大的哈希表）：memory级别的访问， ns级别，500M/b
数据库：文件系统访问，硬盘，微秒级别，500k/b

public void hashFunc(String key) {
      //hash本身就是杂乱无章的表示。所以不要去理解表达的含义，大概类似于把key按33进制表示出来，同时让他最后的值处于HASH_TABLE_SIZE的范围中。
      int sum = 0;
      for(int i = 0; i < key.length(); i++ ) {
          sum = sum * 33 + (int)key.charAt(i);
          sum = sum % HASH_TABLE_SIZE;  //如果不包含这一步，则相当于把key当成33进制数表示出来。   1234 按十进制表达： ((1*10 + 2)*10+3)*10 + 4;      
                                        //HASH_TABLE_SIZE 表示开辟的数组大小，实际存储的数据size/HASH_TABLE_SIZE = 1/10 最好，否则size再大，
                                        //产生冲突的概率会增大。每一次操作都保证sum在HASH_TABLE_SIZE的范围内。
    
      }
      return sum;
  }    

5 重哈希（需要把所有的数重新计算插入一遍，很麻烦，所以尽量避免重哈希的出现，开始定义hash大小时数组开的空间大点。）

http://www.lintcode.com/zh-cn/problem/rehashing/

注意点： 增加链表时，一定要new，而且是· .next = new ListNode，不然赋值不过来。不知道地址传递到底是怎么传的。

 public ListNode[] rehashing(ListNode[] hashTable) {
        if(hashTable == null || hashTable.length == 0) return hashTable;
        ListNode[] newHash = new ListNode[hashTable.length * 2];
        int len = newHash.length;
        for(int i = 0; i < hashTable.length; i++) {
            ListNode node = hashTable[i];
            int index = 0;
            while(node != null ) {
                 index = (node.val%len + len) % len;
                 if(newHash[index] == null) {
                     newHash[index] = new ListNode(node.val);
                     node = node.next;
                     continue;
                 } 
                 ListNode head = newHash[index];
                 while( head.next != null) {
                     head = head.next;
                 }
                head = new ListNode(node.val);
          
                node = node.next;
            }
        }
        return newHash;
    }

 6 快乐数（hash）

http://www.lintcode.com/zh-cn/problem/happy-number/

注意点： 注意按位取元素的方法

private int getNextHappy(int n) {
        int sum = 0;
        while (n != 0) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    
    public boolean isHappy(int n) {
        HashSet<Integer> hash = new HashSet<Integer>();
        while (n != 1) {
            if (hash.contains(n)) {
                return false;
            }
            hash.add(n);
            n = getNextHappy(n);
        }
        return true;
    }

 7 LRU缓存策略

http://www.lintcode.com/zh-cn/problem/lru-cache/

注意点： node结点写在主类里面，因为它只需要在此类里暴露，不需要对外显示。

　　　　 一共有两种存储的数据结构，map存放指定容量的key，value数据，LinkedList存放各种数据的前后放入关系。所以操作数据时，要同时维护这两种数据结构，get方法只需要维护链表，set方法两个都需要维护。

(堆相关)

 8 数据流中位数  　　优先队列/heap ：O(log N) Add    O(log N) Remove   O(1) Min/Max    二叉树实现的，根节点是最值，每次移除根节点，都需要从剩下的结点中找到最值

　　　　　　　　　　再移到根上，所以remove是O(logn)。堆排序只能保证根是最大（最小），不能保证整体是按照顺序来排序的。

http://www.lintcode.com/zh-cn/problem/data-stream-median/ 

注意点： offer  poll方法

　　　　maxHeap里存放小于等于中位数的数字，minHeap里放大于中位数的数字。 中位数，则 maxHeap.size() == minHeap.size() 或者maxHeap.size() == minHeap.size()+1

 public int[] medianII(int[] nums) {
        // write your code here  
    if(nums == null || nums.length == 0) return null;
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(1, new Comparator<Integer>(){
        //@Override   可以不写，但是compare方法参数必须是Integer，不能是int
        public int compare(Integer x, Integer y) {
            return y - x;
        }
    });
    int[] res = new int[nums.length];
    res[0] = nums[0];
    maxHeap.offer(nums[0]);
    for(int i = 1; i < nums.length; i++) {
        if(nums[i] <= maxHeap.peek()) {
            maxHeap.offer(nums[i]);
        } else {
            minHeap.offer(nums[i]);
        }
        
        //开始进入两个元素时，size上，maxHeap = minHeap 或者 maxHeap = minHeap +2，经过下面的if语句，转变成maxHeap = minHeap 
        // 每一轮进来后，只会出现maxHeap = minHeap 或者maxHeap = minHeap +1两种情况。（类似一种递推的关系）
        if(maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if( maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        } 
        res[i] = maxHeap.peek();
    }
    return res;    
}

 9 堆化  (有点堆排序的意思)

http://www.lintcode.com/zh-cn/problem/heapify/

注意点：    0　　       1   　　     2   　　 3   　　 4　　    5　　   6      原序列

　　　　1 　 2      3       4       5      6  　　　　　　　　　　原序列元素对应的子树角标。

　　　　A[0]肯定是最小值。

　　　　 siftdown的O（n）遍历方式很独特，从中间开始遍历。

//   0 1 2 3 4 5 6 7  len = 8,   mid = 3     对于位置i，两个子树2i+1，2i+2；对于位置i-1，子树2(i-1) +1, 2(i-1) +2,即2i-1和2i。
                                             //也就是说 i-1,i-1恰好能连续覆盖掉2i-1,2i，2i+1，2i+2；
 //   0 1 2 3 4 5 6 7 8  len = 9, mid = 4
 
    public void heapify(int[] A) {
        // write your code here
        //O(n)完成，只遍历一次，但是遍历的方式不是简单的从头到尾，而是从中间往左。
        int mid = (A.length - 1)/2;
        for(int i = mid; i >=0; i--) {
            siftdown(A, i);
        }
        
    }
    
    private void siftdown(int[] A, int k) {
        int son = 0;
        while(2*k+1 < A.length) {   //从后往前保证 两个子树比根小，即有一定顺序。如果靠前的位置发生过swap，那也要保证swap之后，后面的位置还是有序
                                    //所以有k = son
            son = 2*k+1;
            if(2*k+2 < A.length && A[2*k+2] <= A[son] ) son = 2*k+2; //son是两个子树中的较小的一个
            
            if(A[son] < A[k]) {
                swap(A, son, k);
                k = son;
            } else {
                break;
            }
        }
        
    }
    private void swap(int[] A, int x, int y) {
        int temp = A[x];
        A[x] = A[y];
        A[y] = temp;
    }

 10 丑数

http://www.lintcode.com/zh-cn/problem/ugly-number/

http://www.lintcode.com/zh-cn/problem/ugly-number-ii/#

注意点： 不理解丑数2的话看代码里的解释。

 public int nthUglyNumber(int n) {
     int[] uglyArr = new int[n];
     uglyArr[0] = 1;
     //p2,p3,p5代表三个指针，指向uglyArr数组的索引。
     int p2 = 0, p3=0, p5 = 0;
     for(int i= 1; i < n; i++) {
         //  <= 说明此索引位置的丑数已经乘以过2了，即已有的丑数数组中已经包含由此位置丑数*2所对应的丑数了，
         //  那么下一轮再乘的时候，就不能用此位置的丑数*2了，要用下一个丑数来乘。
         //  所以p2表示：当前待乘以2来候选作为下一个丑数的数的角标
         //为啥不是用uglyArr[i - 1]来乘2呢，比如1， 2，，3 用 3 *2 显然比 2* 2大，所以下一个丑数不是3*2。
         //所以应该记录的是之前的丑数，1,2，3是否乘过2,3,5，p2= 1,p3= 1, p5 = 0表示5还没有乘过角标0的数，2没有乘过角标1的数,3没有乘过角标1的数。
         if(uglyArr[p2] * 2 <= uglyArr[i - 1]) p2++;
         if(uglyArr[p3] * 3 <= uglyArr[i - 1]) p3++;
         if(uglyArr[p5] * 5 <= uglyArr[i - 1]) p5++;
         
         //这一轮最小值是乘的2,3还是5会在下一轮通过if判断出来，判断出来后，p2,p3,p5中有且只有一个指针会移动1个位置。
         uglyArr[i] = Math.min(uglyArr[p2] * 2, 
                        Math.min(uglyArr[p3] * 3, uglyArr[p5] * 5));
     }
     return uglyArr[n - 1];
 }

 11.字符串查找

http://www.lintcode.com/zh-cn/problem/strstr/

注意点： O(n)实现 Rabin-Karp算法

　　1234  : 234=10(123-100)+4 = 123*10+4-1000 此处用的是后面的计算方式

　　(a+b)%b= (a%b+b%b)%b= a%b  这正是当hashcode<0时采取的做法，也就是对它取模，hashcode%HASH_SIZE=(hashcode+HASH_SIZE)%HASH_SIZE

/** 验证下面的结论是否普遍成立：
     *     1%11*10%11*10%11=100%11=1  power
     *     5%11*10%11*10%11= 5    =1 * 5 
     *  结论是：成立
     */
    public static void main(String[] args) {
        int HASH_SIZE=1000000;
        for(int numberSize = 2; numberSize < 10; numberSize++) {
            int power = 1;
            for(int i = 0; i <4; i++) {
                power = (power*31)%HASH_SIZE;
            }
            for(int i =1; i < 10; i++) {
                int count = 0;
                int num = i;
                int count0 = (num* power)%HASH_SIZE;
                for(int j = 0; j < 5; j++) {
                    if(j != 0) num = 0;
                    count = (count*31+num)%HASH_SIZE;
                }
                if(count != count0){
                    System.out.println(i);
                    break;
                }
            }
            System.out.println(numberSize+"::finish");
        }
    }

private int HASH_SIZE = 1000000;

    public int strStr(String source, String target) {
        // Write your code here
        if (source == null || target == null) {
            return -1;
        }
        int m = source.length();
        int n = target.length();
        if (n == 0) {
            return 0;
        }
        if (m == 0) {
            return -1;
        }
        int targetCode = 0;
        for (int i = 0; i < n; i++) {
            targetCode = (targetCode * 31 + target.charAt(i)) % HASH_SIZE;
        }
        int power = 1;
        for (int i = 0; i < n; i++) {
            power = (power * 31) % HASH_SIZE;
        }
        int hashCode = 0;
        for (int i = 0; i < m; i++) {
            //只有一开始i = n-1 时hashCode记录的是n个数的hash值，
            //之后一直记录的是n+1个数的值，所以power才要乘31^n 而不是31^(n-1)
            hashCode = (hashCode * 31 + source.charAt(i)) % HASH_SIZE;
            if (i < n - 1) {
                continue;
            }
            if (i >= n) {
                hashCode = hashCode - (source.charAt(i - n) * power)% HASH_SIZE ;
                //为啥可能出现hashcode<0? 因为新添加的一位导致hashcode的值>HASH_SIZE,出现了取模的情况，
                // 而 a%b = (a+b)%b,所以<0的情况，原本的hashcode计算方式应该是：
                // hashcode = hashCode + HASH_SIZE - (source.charAt(i - n) * power)% HASH_SIZE ;
                // 所以如果遇到<0的情况，加HASH_SIZE就好了。
                if (hashCode < 0) {
                    hashCode += HASH_SIZE;
                }
            }
            // 0~n-1  i=n-1, 0 = i - n+1
            // 1~n    i=n,   1 = i - n+1
            if (hashCode == targetCode) {
                if (source.substring(i - n + 1, i + 1).equals(target)) {
                    return i - n + 1;
                }

            }
        }
        return -1;
    }

 

graph and search

1 克隆图

http://www.lintcode.com/zh-cn/problem/clone-graph/#

拓扑排序

http://www.lintcode.com/zh-cn/problem/topological-sorting/#

注意点：图肯定要用hashMap

　　　　遍历完图的方式：while(start < res.size()) { start++}   res动态增长，size变化，所有结点都加入进去后，就不变了，而start也增长，实现遍历完全的目的。

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        //图的BFS，类似二叉树的BFS，不过需要统计邻居关系，避免已经访问过的邻居重复访问，所以用Map+ Queue实现。
        //Queue可以用ArrayList + 头索引的位置来表示
        if(node == null) return node;
        ArrayList<UndirectedGraphNode> list = new ArrayList();  //放原先的结点
        Map<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap();  //放复制节点和原先结点的映射关系
        int start = 0;
        
        list.add(node);
        map.put(node, new UndirectedGraphNode(node.label));
        while(start < list.size()) {
            UndirectedGraphNode curr = list.get(start++);
            for(int i = 0; i < curr.neighbors.size(); i++) {
                if(!map.containsKey(curr.neighbors.get(i))) {
                    list.add(curr.neighbors.get(i));
                    map.put(curr.neighbors.get(i), new UndirectedGraphNode(curr.neighbors.get(i).label));
                }
            }
        }
        
        // copy edge
        for(int i = 0; i < list.size(); i++) {
            UndirectedGraphNode curr = list.get(i);
            for(int j = 0; j < curr.neighbors.size(); j++) {
                map.get(curr).neighbors.add(map.get(curr.neighbors.get(j)));
            }
        }
        return map.get(node);
    }

 2 全排列（DFS）

http://www.lintcode.com/zh-cn/problem/permutations/

http://www.lintcode.com/zh-cn/problem/subsets/   子集

http://www.lintcode.com/zh-cn/problem/subsets-ii/#

http://www.lintcode.com/zh-cn/problem/permutations-ii/#

http://www.lintcode.com/zh-cn/problem/combination-sum/#     list里add一个元素，再做dfs，然后再remove掉

注意点： 写递归，想清楚两件事：

　　　　　　　　　　　　1.递归是做了一件什么样的事情，和参数的关系是什么

　　　　　　　　　　　　2.想清楚递归在什么时候return

　　　　　　　　　　　　3.想清楚递归关系，把大问题化解成小问题解决。

错误点：  返回  List<List<Integer>>，则声明为：List<List<Integer>> rst = new ArrayList<List<Integer>>();    List<Integer> list = new ArrayList<Integer>();

　　　　返回ArrayList<ArrayList<Integer>>，  声明为：ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();

　　　　　　　　　　　　　　　　　　　　　　　　　ArrayList<Integer> list = new ArrayList<Integer>();   按上面的声明无法通过编译

public List<List<Integer>> permute(int[] nums) {
    // write your code here
    if(nums == null) return null;
    List<List<Integer>> rst = new ArrayList<List<Integer>>();
    ArrayList<Integer> list = new ArrayList<Integer>();
    if(nums.length == 0) {
        rst.add(list);
        return rst;
    }
    helper(rst, list, nums );
    return rst;
}

public void helper(List<List<Integer>> rst, ArrayList<Integer> list, int[] nums){
    if(list.size() == nums.length) {
        //不能rst.add(list) 地址传递，最后内容都没了
        rst.add(new ArrayList<Integer>(list));
        return;
    }
    for(int i = 0; i < nums.length; i++) {    //假设nums={1,2,3,4}，最外的循环进来，for4次对应四种情况：     [ ]
                                              //                                                                |--[1]
                                              //                                                                |--[2]
                                              //                                                                |--[3]
                                              //                                                                |--[4]
                                              //对于每一种情况，比如[1]，又分为了三种  [1]
                                              //                                         |--[2]
                                              //                                         |--[3]
                                              //                                         |--[4]
                                              //......最后直到list.size()==nums.length,所有元素都放进去了，才作为一次结果返回。
        
        if(list.contains(nums[i])) {
            continue;
        }
        list.add(nums[i]);
        helper(rst, list, nums);
        list.remove(list.size() - 1);
    }
}

3 N皇后问题

http://www.lintcode.com/zh-cn/problem/n-queens/#

注意点：分成4块，每块函数各司其职

错误点：     (cols.get(i) == j)?sb.append('Q'):sb.append('.'); （错）    　sb.append(j == cols.get(i) ? 'Q' : '.');（对）  三目表达式，一个整体

 ArrayList<ArrayList<String>> solveNQueens(int n) {
    if(n <= 0) return null;
    ArrayList<ArrayList<String>> rst = new ArrayList<ArrayList<String>>();
    search(rst, new ArrayList<Integer>(), n);
    return rst;
        
 }

 private void search(ArrayList<ArrayList<String>> rst, ArrayList<Integer> cols, int n) {
     if(cols.size() == n) {
         rst.add(drawChess(cols));
         return;
     }
     for(int i = 0; i < n; i++) {
         if(!isValid(cols, i)) {
            continue; 
         }
         cols.add(i);
         search(rst, cols, n);
         cols.remove(cols.size() - 1);
     }
 }
 //查看第cols.size()行的第colIndex 列是否合法
 //根据cols元素的放法的定义，不可能出现同一行，只可能有同一列或者同一斜行的情况。
 private boolean isValid(ArrayList<Integer> cols, int colIndex) {
     int rowIndex = cols.size();
     for(int i = 0; i < rowIndex; i++) {
         if(cols.get(i) == colIndex) return false;
         // right-top  to left-down
        // 。Q 。 。
        // 。。 Q  。   左上到右下情况下的相同斜线：  (0, 1)  (1,2)  行序号-列序号的值相等。
        
        // 。。 。 Q
        // 。。 Q  。   右上到左下情况下的相同斜线：  (0, 3)  (1,2)  行序号+列序号的值相等。
         if(cols.get(i) + i == rowIndex + colIndex) return false;
         if(cols.get(i) - i == colIndex - rowIndex ) return false;
     }
     return true;
 }
 private ArrayList<String> drawChess(ArrayList<Integer> cols) {
     ArrayList<String> list = new ArrayList<String>();
     for(int i = 0; i < cols.size(); i++) {
         StringBuilder sb = new StringBuilder();
        for(int j = 0; j < cols.size(); j++) {
            //(cols.get(i) == j)?sb.append('Q'):sb.append('.');
            sb.append(j == cols.get(i) ? 'Q' : '.');
        }
        list.add(sb.toString());
     }
     return list;
 }

4 单词接龙

http://www.lintcode.com/zh-cn/problem/word-ladder/      BFS   找最短路

http://www.lintcode.com/zh-cn/problem/word-ladder-ii/#    找所有方案，需要DFS，同时也要找最短路对应的所有方案，所以是DFS+BFS

注意点： BFS，因为每次只变一步，可以画出一张单词变化图出来， lot-log-pog  

　　　　第一种方法超时了，差别主要在找下一个合法单词的方式上，一种是遍历dict，依次判断每个单词是否是合法的单词，另一种是先写出当前单词的所有的合法

　　　　改变单词来，然后判断它是否在dict中。结果是第二种方式更优，为啥??

 public int ladderLength(String start, String end, Set<String> dict) {
    // 超时了，dict很大的时候，isValidChange 用时过长。
    if(start == null || end == null || dict == null) return 0;
    if(isValidChange(start,end)) return 2;
    List<String> list = new ArrayList<String>();
    list.add(start);
    return searchValidChange(list, dict, end);
}
private int searchValidChange(List<String> list, Set<String> dict,String end) {
    int level = 1;
    int pos = 0;
    while(list.size() < dict.size() + 1) {
        int len = list.size();
        while(pos < len) {
            for(String s1 : dict) {
                if(list.contains(s1)) continue;
                if(isValidChange(list.get(pos), s1)) {
                    if(isValidChange(s1, end)) return level+2;
                    list.add(s1);
                }
            }
            pos++;
        }
        level++;
    }
    return 0;
}
private boolean isValidChange(String s1, String s2) {
    if(s1.length() != s2.length()) return false;
    int count = 0;
    for(int i = 0; i < s1.length(); i++) {
    if(s1.charAt(i) == s2.charAt(i)) continue;
        count++;    
        //if(count > 1) return false;
    }
    return count == 1;
}
//----------------------------------------------------
 public int ladderLength(String start, String end, Set<String> dict) {
        if (dict == null) {
            return 0;
        }

        if (start.equals(end)) {
            return 1;
        }
        
        dict.add(start);
        dict.add(end);

        HashSet<String> hash = new HashSet<String>();
        Queue<String> queue = new LinkedList<String>();
        queue.offer(start);
        hash.add(start);
        
        int length = 1;
        while(!queue.isEmpty()) {
            length++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                for (String nextWord: getNextWords(word, dict)) {
                    if (hash.contains(nextWord)) {
                        continue;
                    }
                    if (nextWord.equals(end)) {
                        return length;
                    }
                    
                    hash.add(nextWord);
                    queue.offer(nextWord);
                }
            }
        }
        return 0;
    }

    // replace character of a string at given index to a given character
    // return a new string
    private String replace(String s, int index, char c) {
        char[] chars = s.toCharArray();
        chars[index] = c;
        return new String(chars);
    }
    
    // get connections with given word.
    // for example, given word = 'hot', dict = {'hot', 'hit', 'hog'}
    // it will return ['hit', 'hog']
    private ArrayList<String> getNextWords(String word, Set<String> dict) {
        ArrayList<String> nextWords = new ArrayList<String>();
        for (char c = 'a'; c <= 'z'; c++) {
            for (int i = 0; i < word.length(); i++) {
                if (c == word.charAt(i)) {
                    continue;
                }
                String nextWord = replace(word, i, c);
                if (dict.contains(nextWord)) {
                    nextWords.add(nextWord);
                }
            }
        }
        return nextWords;
    }

//懒得看了，bfs写的就问题很大。用一个队列就能解决的问题，套了半天map，死循环，还绕。
private Map<String, Integer> map;
private int minLen = Integer.MAX_VALUE;
private List<List<String>> rsts;
private Set<String> dict;
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
    // write your code here  
    if(start == null || end == null) return null;
    rsts = new ArrayList<>();
    List<String> rst = new ArrayList<String>();
    rst.add(start);
    if(start.equals(end)) {
        rsts.add(new ArrayList<String>(rst));
        return rsts;
    }
    if(dict == null) return null;
    map = findShortestLen(dict, end);
    this.dict = dict;
    dict.add(end);
    //dict.add(start);
    dfs(rst, start, end);
    return rsts;
}
//dfs
private void dfs(List<String> rst,String start, String end) {
    if(map.get(start) != null && map.get(start) == 2 && rst.size() + 1 == minLen) {
        List<String> addRst = new ArrayList<String>(rst);
        addRst.add(end);
        rsts.add(addRst);
    }
    List<String> list = findNextWords(dict, start);
    for(String s : list) {
        //List<String> addList = new ArrayList<String>();
        if(!map.containsKey(s)) continue;
        if(minLen < rst.size() + map.get(s)) continue;
        else {
            minLen = rst.size() + map.get(s);    
            rst.add(s);
            dfs(rst, s, end );
            rst.remove(rst.size() - 1);    
        }
        
    }
    return;
}
//bfs    
private Map<String, Integer> findShortestLen(Set<String> dict, String end) {
    Map<String, Integer> map = new HashMap<>();
    map.put(end, 1);
    int len = 1;
    while(map.size() < dict.size()) {  ///zzz, abc, abd,   zzz永远也放不进map，死循环，先不管。    
        Map<String, Integer> temp = new HashMap<>();
        for(String s1 : map.keySet()) {
            if(map.get(s1) != len) continue;
            List<String> list = findNextWords(dict, s1);
            if(list == null) continue;
            for(String s2 : list) {
                if(map.containsKey(s2) || temp.containsKey(s2)) continue;
                temp.put(s2, len + 1);
            }
        }
        len++;
        map.putAll(temp);
    }
    return map;
}
private List<String> findNextWords(Set<String> dict, String end) {
    List<String> list = new ArrayList<String>();
    for(int i = 'a'; i <= 'z'; i++) {
        for(int j = 0; j < end.length(); j++) {
            if(i == end.charAt(j)) continue;
            String s = replaceOneChar(end, j, (char)i);
            if(dict.contains(s)) list.add(s);
        }
    }
    return list;
}
private String replaceOneChar(String end, int pos, char c) {
    char[] chars = end.toCharArray();
    chars[pos] = c;
    return Arrays.toString(chars);
}

public List<List<String>> findLadders(String start, String end, Set<String> dict) {
    List<List<String>> rsts = new ArrayList<>();
    List<String> rst = new ArrayList<String>();
    Map<String,List<String>> map = new HashMap(); 
    Map<String, Integer> distance = new HashMap();
    dict.add(start);
    dict.add(end); //避免dict中有无start和end造成的分类讨论
    bfs(map, distance, start , end, dict);
    dfs(rsts,map, distance,rst, end, start);
    return rsts;
}
//从end开始添加
private void dfs(List<List<String>> rsts, Map<String,List<String>> map, Map<String, Integer> distance, List<String> rst, String curr,
                 String start) {
    rst.add(curr);
    if(curr.equals(start)) {
        Collections.reverse(rst);
        rsts.add(new ArrayList(rst));
        Collections.reverse(rst);
        return;
    }
/*    不要这样取元素
    List<String> nexts = findNexts(dict, curr);
    for(String next : nexts) {
        if(distance.get(next) +1 == distance.get(curr)) {
            dfs(rsts,map, distance, rst, next, start, dict);
        }
    }*/
       /* 这样只能取出一种结果来
        List<String> list = map.get(curr);
        dfs(rsts,map, distance, rst, list.get(list.size() - 1) , start, dict);*/
        List<String> list = map.get(curr);
        for(String s : list) {
            if(distance.get(s) +1 == distance.get(curr)) {
                dfs(rsts,map, distance, rst, s , start);
            }
        }
    rst.remove(rst.size() - 1);
    
}
//计算每一个字符串到start的路径距离 
private void bfs(Map<String,List<String>> map, Map<String, Integer> distance, String start, String end, Set<String> dict) {
    Queue<String> q = new LinkedList();
    q.offer(start);
    distance.put(start, 0);
    for(String s : dict) {
        map.put(s, new ArrayList());
    }
    while(!q.isEmpty()) {
        String curr = q.poll();
        List<String> nexts = findNexts(dict, curr);
        for(String next : nexts) {
        /*    这样只能取出一种接过来
            if(distance.containsKey(next)) continue;
            distance.put(next, distance.get(curr) + 1);
            map.get(next).add(curr);
            q.offer(next);*/
            map.get(next).add(curr);
            if(!distance.containsKey(next)) {
                distance.put(next, distance.get(curr) + 1);
                q.offer(next);
            }
        }
    }
}
private List<String> findNexts(Set<String> dict, String curr) {
    List<String> nexts = new ArrayList();
    for(char ch = 'a'; ch <='z'; ch++) {
        for(int i = 0; i < curr.length(); i++) {
            if (ch == curr.charAt(i)) continue;
            String s = curr.substring(0, i) + ch + curr.substring(i+1);
            if(dict.contains(s)) {
                nexts.add(s);
            }
        }    
    }
    return nexts;
}