LeetCode算法总结

本文主要总结LeetCode题目的C++解法，日常更新两篇

算法思想

二分查找

对于有序数组而言，二分查找速度快

//在数组array中查找key 找到返回其index 无返回-1
int BinarySearch(int* array,int length,int key) 
{
  if(array==NULL) return -1;
  int start=0,end=length-1;
  while(start<=end)
  {
    int mid=start+(end-start)/2  //防止越界
    if(key<array[mid]) end=mid-1;
    else if(key>array[mid]) start=mid+1;
    else return mid;
  }
  return -1;
}

求开方

Leetcode:69.Sqrt(x)(Easy)

int mySqrt(int x) {
  if(x==0) return 0;  
  if(x<=1) return 1;
  int start=1,end=x;
  while(start<=end)
  {
    int mid=start+(end-start)/2;  
    if(mid>x/mid) end=mid-1;
    else if(mid<x/mid){
       if((mid+1)>x/(mid+1)) return mid;
       else start=mid+1;
    }
    else return mid;
   }
}

思路：
1.数x的开方肯定在0-x之间，0-x为有序数组，可使用二分查找
2.处理特殊情况(x==0/x==1)
3.使用mid=start+(end-start)/2代替mid=(start+end)/2，防止(start+end)越界溢出
4.使用mid与x/mid作比较代替midmid与x作比较，防止midmid越界溢出

摆硬币

Leetcode:441.Arranging Coins(Easy)

int 

思路：
1.能摆的层数h肯定在0-x之间，0-x为有序数组，可使用二分查找

数据结构