198. House Robber

相邻不能打劫，取利益最大化。

思想：当前值和前一个和的总数   与  前一个和    做大小比较，取最大值，重复该步骤。

class Solution {public:    int rob(vector
     
      & nums) {        const int n = nums.size();        if (n == 0) return 0;        if (n == 1) return nums[0];        if (n == 2) return max(nums[0], nums[1]);        vector
      
        f(n, 0);        f[0] = nums[0];        f[1] = max(nums[0], nums[1]);        for (int i = 2; i < n; ++i)            f[i] = max(f[i-2] + nums[i], f[i-1]);        return f[n-1];    }};
      
     

 

202. Happy Number

class Solution {public:    bool isHappy(int n) {        unordered_map
     
       tmp;                while(n != 1)        {            if(tmp[n] == 0)   //如果出现了循环，则直接返回false                tmp[n]++;            else                return false;                        int sum = 0;            while(n != 0)            {                sum += pow(n % 10,2);                n = n / 10;            }                        n = sum;        }                return true;    }};///class Solution {public:    int next(int n)    {        int sum = 0;                while(n != 0)        {            sum += pow(n % 10,2);            n = n / 10;        }                return sum;    }public:    bool isHappy(int n) {        int slow = next(n);        int fast = next(next(n));                while(slow != fast)        {            slow = next(slow);            fast = next(next(fast));        }                return fast == 1 ;    }};
     

 

204. Count Primes

思路：在i × i 的基础上递进 i，这些都不是素数;

class Solution {public:    int countPrimes(int n) {        //Sieve of Erantothoses        vector
     
       check(n+1,true);       //Because 0 and 1 are not primes      check[0]=false;      check[1]=false;      //OPtimization 2: Do only till rootn since all numbers after that are handled      //The remaining values are already true      for(int i=2;i*i<=n;i++)       {        //If already visited        if(check[i]==false) continue;  //访问过的不重复        //Optimation 1 : 3*2 is already handled by 2*3. Toh directly start from 9        int j=i*i;        while(j<=n)         {            check[j]=false;            j = j+i;   ##以i*i基础上每次增加i，这些都可以化为i的倍数，所以不是素数        }      }    int count=0;    //Checking all the numbers which are prime (less than n)      for(int i=1;i
     

 

 

 

219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

思路：固定窗口滑动，左窗口利用erase来滑动，右边利用i来滑动。

class Solution {public:    bool containsNearbyDuplicate(vector
      
       & nums, int k)    {       unordered_set
       
         s;              if (k <= 0) return false;       if (k >= nums.size()) k = nums.size() - 1;              for (int i = 0; i < nums.size(); i++)       {           if (i > k) s.erase(nums[i - k - 1]);           if (s.find(nums[i]) != s.end()) return true;           s.insert(nums[i]);       }              return false;    }};
       
      

 

231. Power of Two

Power of 2 means only one bit of n is '1', so use the trick n&(n-1)==0 to judge whether that is the case

class Solution {public:    bool isPowerOfTwo(int n) {        if(n<=0) return false;        return !(n&(n-1));    }};

 

234. Palindrome Linked List

思路:中间为界，翻转后半部分，对照前半部分是否相等;  定位中界使用快慢指针。

class Solution {public:    bool isPalindrome(ListNode* head) {        if(head==NULL||head->next==NULL)            return true;        ListNode* slow=head;        ListNode* fast=head;        while(fast->next!=NULL&&fast->next->next!=NULL){            slow=slow->next;            fast=fast->next->next;        }        slow->next=reverseList(slow->next);        slow=slow->next;        while(slow!=NULL){            if(head->val!=slow->val)                return false;            head=head->next;            slow=slow->next;        }        return true;    }    ListNode* reverseList(ListNode* head) {        ListNode* pre=NULL;        ListNode* next=NULL;        while(head!=NULL){            next=head->next;            head->next=pre;            pre=head;            head=next;        }        return pre;    }};