每日打卡

楼主30号fb一面，20号google oa，另有ipsy的ml intern.
用本帖来记录并鼓励自己，同时记录心得

38. Count and Say
不断存入字符，使用递归。
class Solution {
public:
    string countAndSay(int n) {
        
        
        return find("1",n);
    }
   
    string find(string str, int n){
        if(n==1)return str;
        n--;
        int count=1;
        string res="";
        for(int i=0;i<str.size()-1;i++){
            if(str[i]==str[i+1])count++;
            else {res+=count+'0';res+=str[i];count=1;}
        }
        res+=count+'0';res+=str[str.size()-1];
        return find(res,n-1);
    }
};

398. Random Pick Index
使用rand（）%cnt；非常精彩的地方！！
class Solution {
public:
    Solution(vector<int> nums): v(nums) {}
   
    int pick(int target) {
        int cnt = 0, res = -1;
        for (int i = 0; i < v.size(); ++i) {
            if (v[i] != target) continue;
            ++cnt;
            if (rand() % cnt == 0) res = i;
        }
        return res;
    }
private:
    vector<int> v;
};

377. Combination Sum IV

回看 使用dp
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; ++i) {
            for (auto a : nums) {
                if (i >= a) dp[i] += dp[i - a];
            }
        }
        return dp.back();
    }
};

上午十点才起，磨蹭到下午开个会，现在四点了，今天希望能快速过一遍leetcode fb tag题目

314 Binary Tree Vertical Order Traversal ：
难点在于如何初始化数组序列，无法轻易向前加元素：使用map<int,vector<int>>m 从而避免下标从0开始的问题，之后用auto a:m a.second 来组成返回vector；
可是为什么要用quene？没发现必要性，待解决。


补充内容 (2018-11-25 06:50):
queue has the attribute of first in first out, therefore it could be use as loop

补充内容 (2018-11-25 08:09):
void bfs(queue<pair<int,TreeNode*>>& q,map<int,vector<int>>& m){
        if(q.empty())return;
        int n=q.size();
        for(int i=0;i<n;i++){
            auto a=q.front();
            q.pop(...

另外 找组织 找队友一起刷题

abandon 10 regular expression match
这道题很难，准确说有很多细节需要讨论：
时间本来不多 我何必折磨自己

301 此题需要了解矩阵的乘法，然后如果相乘的元素之一为0，跳转下一次，复杂度虽然相同，但是省掉很多步骤

543：Diameter of Binary Tree
遍历所有子节点和root节点，找出左深度和右深度和最大的值

278 first bad version
使用二分法找到a[i]bad but a[i-1]不是bad。
简单题真是快啊

277 find the celebrity
用最简单的遍历方法

680 valid palindrome
双向遍历，如何不对，各自删除，继续遍历，如果正确，返回true，否则false