204. Count Primes M ！！

Q:

Given an integer n, return the number of prime numbers that are strictly less than n.

 

Example 1:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 0

 

Constraints:

• 0 <= n <= 5 * 106

A:

挨个过滤，看是否能被已经发现的prime Number整除。 LTE

class Solution {

public:

int countPrimes(int n) {

if(n<=2)

return 0;

int res = 0;

vector<int> P{2};

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

bool found = false;

for(const auto & val : P){

if(i % val ==0){

found = true;

break;

}

}

if(! found){

P.push_back(i);

}

}

return P.size();

}

};

*****************用筛法********************* 

• Time complexity: O(n log log n)

这个仅仅beat 了40% 的

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> M(n,true); // M[i] means, if value i is prime number
        int count = 0;
        for(int i =2;i<n;i++){
            if(M[i]){
                ++count;
                int nextCount = i+i;
                while(nextCount<n){
                    M[nextCount] = false;
                    nextCount += i;
                }
            }
        }
        return count;
    }
};

进一步的更改是， 在内层的循环里 不从2*i 开始， 而是从 i * i 开始， 好好想想，这是为什么呢？  beat 95% 

class Solution {

public:

int countPrimes(int n) {

if(n<3)

return 0;

vector<int> M(n, 1); // M[i] means, if value i is prime number

for(int i =2; i*i < n;i++){

if(M[i]){

for(int j = i*i; j<n ; j+=i)

M[j] = 0;

}

}

return std::accumulate(M.begin(), M.end(), 0) -2;

}

};

Mistakes:
最新的，需要考虑 n <=0 的情况。 艹。 之前没有的


bool A[n+1]; // n is not included           有些时候，C++不会将其设为默认值。i.e. 会有error:

Runtime error: load of value 127, which is not a valid value for type 'bool'

See this page: https://stackoverflow.com/questions/1920430/c-array-initialization

202. Happy Number （easy)

Q:

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 

Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

A:
就是用个Set来检查是否出现 endless loop。

class Solution {
public:
    bool isHappy(int n) {
        set<int> s;
        while(true)
        {
            int val = helper(n);
            if(val == 1)
            {
                return true;
            }
            if(s.find(val) != s.end()) // already found, 
                return false; 
            
            s.insert(val);            
            n = val;
        }
        return false;        
    }
private:
    int helper(int n)
    {
        int res = 0;
        while(n!=0)
        {
            int v = n %10;
            n /= 10;
            res += v*v;
        }
        return res;
    }
};

Mistakes:

又一次，栽在了while loop的条件上。

201. Bitwise AND of Numbers Range -----------M

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: [5,7]
Output: 4

Example 2:

Input: [0,1]
Output: 0

A:
其实就是挨个查看，该位是否在为全1.

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int res = 0;
        for(int i = 31;i>=0;i--){
            long mask = 1<<i;
            if( m>=mask && n <=mask+mask-1){
                res += (int)mask;
                m -= mask;
                n -= mask;
            }
        }
        return res;
    }
};

Mistakes:
1:  当时，感觉，如果高位不在全1 区间。就可以break了。
   但是，没有考虑，还可能是 全0 ， 因此不能break。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

我们先从题目中给的例子来分析，[5, 7]里共有三个数字，分别写出它们的二进制为：

101　　110　　111

相与后的结果为100，仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，如果上面那个例子不太明显，我们再来看一个范围[26, 30]，它们的二进制如下：

11010　　11011　　11100　　11101　　11110

发现了规律后，我们只要写代码找到左边公共的部分即可，我们可以从建立一个32位都是1的mask，然后每次向左移一位，比较m和n是否相同，不同再继续左移一位，直至相同，然后把m和mask相与就是最终结果，代码如下：

public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int mask = Integer.MAX_VALUE;
        for(int i =0;i<31;i++){
            if( (mask & m) == (mask&n))
                break;
            mask = mask << 1;
        }
        return mask & m;
    }
}

200. Number of Islands -M

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

A:

 简单的dfs罢了。

根据fb面试的失败教训，建议每次发现一个‘1’， 先设‘0‘， 再dfs。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if(m ==0 )
            return 0;
        int n = grid[0].size();
        int res = 0;
        for(int i =0;i<m;++i)
        {
            for(int j =0;j<n;++j)
            {
                if(grid[i][j]=='1')
                {
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }
private:    
    void dfs(vector<vector<char>>& grid,int i, int j) {
        grid[i][j]='0';
        int m = grid.size(), n = grid[0].size();
        if(i>0&&grid[i-1][j] =='1')
            dfs(grid,i-1,j);
        
        if(i+1<m&&grid[i+1][j] =='1')
            dfs(grid,i+1,j);
        
        if(j>0&&grid[i][j-1] =='1')
            dfs(grid,i,j-1);
        
        if(j+1<n&&grid[i][j+1] =='1')
            dfs(grid,i,j+1);
    }
};

199. Binary Tree Right Side View ----M

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

A:
 我所能想到的，就是简单的bfs (dfs)

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new LinkedList<Integer>();
        Queue<TreeNode> queue = new LinkedList();
        if(root == null)
            return list;
        queue.add(root);
        while( queue.isEmpty() == false){
            Queue<TreeNode> newQueue = new LinkedList();
            boolean isFirst = true;
            
            while( ! queue.isEmpty()){
                TreeNode node = queue.poll();
                if(isFirst){
                    list.add(node.val);
                    isFirst = false;
                }
                if(node.right != null)
                    newQueue.add(node.right);
                if(node.left != null)  
                    newQueue.add(node.left);
            }
            queue = newQueue;
        }
        return list;
    }
}

***********dfs ****************

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        helper(root, 1, res);
        return res;
    }
private:
    void helper(TreeNode * root, int depth, vector<int> & res){
        if(!root)
            return;
        if(res.size() < depth){
            res.push_back(root->val);
        }
        helper(root->right, depth+1, res);
        helper(root->left, depth+1, res);
    }
};

Mistakes:



Learned: