二分法 static int BinarySearch(int[] a,int tar){ //n是最后一个下标，tar是要找的数         int i = 0, j = a.length-1;         while(i<=j){            int mid = i + (j-i)/2;            if(a[mid] == tar) return mid;            if(a[mid] > tar) j = mid-1;            else i = mid+1;         }         return -1;        }

上面就是一个典型的二分法.    核心思想是： 不断的化小值所在的范围。 

二分法有几个需要关注的点：

1. mid = i + (j-i)/2.   防止越界.

2. return i, or j, or mid.

3. a[mid] < tar or a[mid] <= tar.

下面就以上问题进行详细的解释.      简单的二分法，根据以上的变化，可以变化出不同奇特的效果.

例子 ： 找大于等于target的最小下标。

public static void main(String[] args) {

// TODO Auto-generated method stub

int a[] = {1,2,3,3,3,3,4,5};

  System.out.println(BinarySearch(a,3));

static int BinarySearch_findfristless(int[] a,int tar){         int i = 0, j = a.length-1;         while(i<=j){            int mid = i + (j-i)/2;            if(tar<=a[mid]) //等于往左走              j = mid-1;            else i = mid+1;            System.out.println("mid = " + mid+ "i = " + i+ "j=" + j);         }         System.out.println("i = " +i + "j=" + j);         return i;  //返回i（i比j大）        }//output mid = 3i = 0j=2mid = 1i = 2j=2mid = 2i = 2j=1i = 2j=12

算法思想： 只要是大于或等于tar. 范围就缩小.    [.....]xyz     x>=tar.  最后i和j一定会有equal的时候，mid == i. i=mid+1.  i 刚好是第一个大于等于tar的值.

所以  return i; 在详细点说    1,2,3,3,3,3,4,5,6,7   aid[mid]<=tar  then j = mid -1.  最后 j 一定是在2出现.  类比，如果  aid[mid] < tar.  j 一定最后在最后一个3出现

 

找到最后一个3的位置.

public static void main(String[] args) {

// TODO Auto-generated method stub

int a[] = {1,2,3,3,3,3,4,5};

  System.out.println(BinarySearch(a,3));

static int BinarySearch_findfristless(int[] a,int tar){         int i = 0, j = a.length-1;         while(i<=j){            int mid = i + (j-i)/2;            if(tar

 

例子：题目：在数组中，数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中，数对之差的最大值是11，是16减去5的结果。

分析：于是我们接下来可以想到让每一个数字逐个减去它右边的所有数字，并通过比较得到数对之差的最大值。由于每个数字需要和它后面的O(n)个数字作减法，因此总的时间复杂度是O(n2)。用二分法优化：通常蛮力法不会是最好的解法，我们想办法减少减法的次数。假设我们把数组分成两个子数组，我们其实没有必要拿左边的子数组中较小的数字去和右边的子数组中较大的数字作减法。

数对之差的最大值只有可能是下面三种情况之一：（1）被减数和减数都在第一个子数组中，即第一个子数组中的数对之差的最大值；（2）被减数和减数都在第二个子数组中，即第二个子数组中数对之差的最大值；（3）被减数在第一个子数组中，是第一个子数组的最大值。减数在第二个子数组中，是第二个子数组的最小值。这三个差值的最大者就是整个数组中数对之差的最大值。

（3）被减数在第一个子数组中，是第一个子数组的最大值。减数在第二个子数组中，是第二个子数组的最小值。这个是难点所在: 解决的办法是:记录左数组的最大值和右数组的最小值 如何解决呢？  这个地方就很精彩了！ 因为用到了递归，可以用一个引用来记录跟踪Max和min.

int max, min;    return MaxDiffCore(numbers, numbers + length - 1, &max, &min);

public final class test {       static int MaxDiffCore(int[] numbers,int start, int end, int[] a)    {        if(end == start)        {            a[0] = a[1] = numbers[start];            return 0x80000000;        }             int middle = start + (end - start) / 2;             int[] L= {Integer.MAX_VALUE,Integer.MIN_VALUE};        int leftDiff = MaxDiffCore(numbers,start, middle,L);             int[] R= {Integer.MAX_VALUE,Integer.MIN_VALUE};;        int rightDiff = MaxDiffCore(numbers,middle + 1, end, R);             //int crossDiff = maxLeft - minRight;        int crossDiff = L[0] - R[1];             a[0] = (L[0] > R[0]) ? L[0] : R[0];        a[1] = (L[1] < R[1]) ? L[1] : R[1];             int maxDiff = (leftDiff > rightDiff) ? leftDiff : rightDiff;        maxDiff = (maxDiff > crossDiff) ? maxDiff : crossDiff;        return maxDiff;    }        public static int MaxDiff_Solution1(int numbers[])    {        int length = numbers.length;            if(numbers == null || length < 2)            return 0;             int[] a = {Integer.MAX_VALUE,Integer.MIN_VALUE};        return MaxDiffCore(numbers,0,length-1,a);    }                public static void main(String[] args) {           int[] input = {2, 4, 1, 16, 7, 5, 11, 9};        System.out.print(MaxDiff_Solution1(input));        //for(int i : input)        //System.out.print(i+" ");    }       }

这也属于递归总结中的 先递归再处理.  但时间复杂度都是O(n)（第一种解法的时间复杂度可以用递归公式表示为v，所以总体时间复杂度是O(n)）。

 如果是 T(n)=2(n/2)+O(n) 就是nlogn

 这道题也是一个经典的动态规划题目

既然我们可以把求最大的数对之差转换成求子数组的最大和，而子数组的最大和可以通过动态规划求解，那我们是不是可以通过动态规划直接求解呢？下面我们试着用动态规划法直接求数对之差的最大值。我们定义diff[i]是以数组中第i个数字为减数的所有数对之差的最大值。也就是说对于任意h（h < i），diff[i]≥number[h]-number[i]。diff[i]（0≤i
     
      < i），满足number[h]减去number[i]之差是最大的，也就是number[h]应该是number[i]之前的所有数字的最大值。当我们求diff[i+1]的时候，我们需要找到第i+1个数字之前的最大值。第i+1个数字之前的最大值有两种可能：这个最大值可能是第i个数字之前的最大值，也有可能这个最大值就是第i个数字。第i+1个数字之前的最大值肯定是这两者的较大者。我们只要拿第i+1个数字之前的最大值减去number[i+1]，就得到了diff[i+1]。分析比动手去写要重要！ dynamic programming
     

int MaxDiff_Solution3(int numbers[], unsigned length){    if(numbers == NULL || length < 2)        return 0;     int max = numbers[0];    int maxDiff =  max - numbers[1];     for(int i = 2; i < length; ++i)    {        if(numbers[i - 1] > max)            max = numbers[i - 1];         int currentDiff = max - numbers[i];        if(currentDiff > maxDiff)            maxDiff = currentDiff;    }     return maxDiff;}

 

 

平衡树:

不得不先说一下  Red-Black tree.  

红黑树是每个节点都带有颜色属性的，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3. 所有叶子都是黑色（叶子是NIL节点）。

性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有都包含相同数目的黑色节点。

 

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。

 

 

很多牛逼的数据结构都是red-black 实现的, 下面,让我们来总结一下Set.

Set  a.  HashSet.   b. LinkedHashSet.  c.  TreeSet(red-black 实现)

 

 

 

HashMAp:

一般用来解决 又想跟踪value和index的问题.

two sum :

public class Solution {    public int[] twoSum(int[] numbers, int target) {        // Start typing your Java solution below        // DO NOT write main() function        HashMap
     
       map = new HashMap
      
       ();        int[] ret = new int[2];        int length = numbers.length;        for(int i =0; i
      
     

 

3sum 从数组中找3个元素和为target；

 

无论有没有负数，都有时空复杂度为O(n^2)+O(1)的解法。思路是排序，然后用三个指针（3sum）i，j，k扫描数组，i指针从0~n-3，对于每个i，j都初始化为i+1，k都初始化为n-1，j和k相向的逼近对方，每次判断sum[i]+sum[j]+sum[k]跟target的大小关系，如果sum==target，那么解出来了；如果sum
     
      target，同理，k--。这样就可以保证检测过了所有可能的解。
     

 

 

 

 

class Solution {public:    vector
     
      
        > threeSum(vector
       
         &num) {        sort(num.begin(),num.end());        vector
        
         
          > result;        for(int i=0;i<(int)num.size()-2;i++){            int j = i+1, k=(int)num.size()-1;            while(j
          

()); result.back().push_back(num[i]); result.back().push_back(num[j]); result.back().push_back(num[k]); } if(sum<=0){ j++; while(j

j&&num[k+1]==num[k]) k--; } } while(i<(int)num.size()-2&&num[i+1]==num[i]) i++; } return result; }};