LeetCode

最近在刷C++primer，数据结构更新的更慢了。。基本把排序做完了，二叉树写了一点点。。懈怠了！但是没并没有写到博客，也刷了一些LeetCode上面的题目，发现自己有思路，但是实现一个算法真的好难。。而且效率不一定高。。下面就把我最近刷的一些题目贴出来

1。moveZeros这个主要看重的是这个tag的设置，它可以帮助我们移动最少的步数

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        vector<int>::iterator beg = nums.begin();
        unsigned int tag = 0;
        decltype(nums.size()) len = nums.size();
        for (int i = 0; i < len; ++i){
            if (*(beg + i) != 0 && tag != 0)*(beg + i - tag) = *(beg + i);
            if (*(beg + i) == 0)++tag;
        }
        for (int j = len - tag; j < len; ++j){
            *(beg + j) = 0;
        }
    }
};

2。firstBadVersion采用二分法查找啦

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
          int start=1,end=n;
          int middle;
          while(start<=end){
              middle=start+(end-start)/2;
              if(isBadVersion(middle))end=middle-1;
              else start=middle+1;
          }
          return end+1;
    }
};

3.hIndex先排序再找，这个我击败了100%的人呢~

class Solution {
public:
    int hIndex(vector<int>& citations) {
        vector<int>::iterator beg = citations.begin(), end = citations.end();
        sort(beg, end);
        auto len = citations.size();
        if(len==0)return 0;
        if (*beg >= len) return len;
        int i;
        for (i = len; i>=1; --i){
            if (*(end - i) >= i && *(end - i- 1) <= i)return i;
        }
        return 0;
    }
};

4.missingNumber，先求总的，然后看缺的是哪个数

class Solution {
public:
    int missingNumber(vector<int>& nums) {
      int sum=0;
      for(int i=1;i<=nums.size();++i)
      sum+=i;
      for(auto i:nums)
      sum-=i;
      return sum;
    }
};

5.addDigits这个是个规律，按照1~9一直循环但是9%9=0，所以先-1，最后再+1

class Solution {
public:
    int addDigits(int num) {
      return (num - 1) % 9 + 1;
    }
};

6.isPowerOfTwo，这个就是直接除除除啦。。发现如果有余数就不是2的n次幂，直接跳出

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n<=0)return false;
        while(n!=1&&n!=0)
        {
            if(n%2)return false;
            n=n/2;
        }
        if(n==1)return true;
        else return false;
    }
};

7.mySqrt这个注意不要用乘法或者加法，很容易导致溢出，从而导致结果不正确

class Solution {
public:
    int mySqrt(int x) {
        if(x<=0) return 0;
        int end=x/2+1;
        int begin=1;
        int half;
        int com;
        while(begin<end-1){
               half=(begin+end)/2;
               com=x/half;
              if(half==com)return half;
              if(half<com){
              begin=half;
              }
              else
              end=half;
        }
        return begin;
    }
};