191. Number of 1 Bits --E

 Q:

Write a function that takes the binary representation of a positive integer and returns the number of 

set bits

 it has (also known as the Hamming weight).

 

Example 1:

Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

Example 2:

Input: n = 128

Output: 1

Explanation:

The input binary string 10000000 has a total of one set bit.

Example 3:

Input: n = 2147483645

Output: 30

Explanation:

The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

 

Constraints:

• 1 <= n <= 231 - 1

A:

class Solution {

public:

int hammingWeight(int n) {

int res = 0;

while(n){

n = n & (n-1);

++res;

}

return res;

}

};

279. Perfect Squares ----M

Q:

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

 

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

 

Constraints:

• 1 <= n <= 104

A:

明显就是个 DP 问题

class Solution {

public:

int numSquares(int n) {

int seed = 1;

vector<int> squares;

while(seed * seed <=n){

squares.push_back(seed * seed);

seed++;

}

// DP

vector<int> minSquare(n+1,INT_MAX);

minSquare[0] = 0;

for(int i =1;i<=n;i++){

for(const auto c : squares){

if( i - c >=0){

minSquare[i] = min(minSquare[i], minSquare[i-c] +1);

}

}

}

return minSquare[n];

}

};

28. Find the Index of the First Occurrence in a String E ！！！需要动手写

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

 

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

 

Constraints:

• 1 <= haystack.length, needle.length <= 104
• haystack and needle consist of only lowercase English characters.

A:

就是Rabin-Karp string matching algorithm 来过滤。 有个KMP 算法，太难了，不考虑

我靠，还是出了好多处错误。

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = needle.size(), n = haystack.size();
        if(m > n){
            return -1;
        }
        // find a prime number to speed up , 797 is another good choice
        int prime = 3319;
        int vN = 0, vM = 0, rm = 1;// remainder of first letter position
        for(int i =0; i<m;i++){
            vN = (vN * 26 + (needle[i] - 'a')) % prime;
            vM = (vM * 26 + (haystack[i] - 'a')) % prime;
            if(i<m-1){
                rm = (rm*26) % prime;
            }
        }
        if(vN == vM && haystack.substr(0,m) == needle){
            return 0;
        }
        for(int i = m; i<n;i++){
            vM = (( vM - (haystack[i-m] -'a') * rm) * 26 + (haystack[i]-'a') )% prime;
            vM = (vM % prime + prime) % prime; // this is NEEDED, since VM can be negative. fuck
            if(vN == vM && haystack.substr(i-m+1, m) == needle){
                return i-m+1;
            }
        }
        return -1;
    }
};

最经典，也是下次还是容易犯错的：

就是 

            if(i<m-1){
                rm = (rm*26) % prime;
            }

这个一开始没想到。 确实是水平不行 阿。 

234. Palindrome Linked List E

Given the head of a singly linked list, return true if it is a 

palindrome

 or false otherwise.

 

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

 

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

 

Follow up: Could you do it in O(n) time and O(1) space?

A:

就是简单的读2遍，然后一个从后往前，一个从前往后。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> v;
        ListNode* runner = head;
        while(runner){
            v.push_back(runner->val);
            runner = runner->next;
        }
        runner = head;
        while(runner){
            int val = v.back();
            v.pop_back();
            if(val != runner->val){
                return false;
            }
            runner = runner->next;
        }
        return true;
    }
};

Follow up:

Could you do it in O(n) time and O(1) space?

1：  reverse后半段。

2： 利用 recursive  的call stack,来对比