3/24

128 最長連續(xù)序列

本題基本的算法思想是并查集與哈希表
len[i]存儲數(shù)字i所在的最長連續(xù)序列，但其實無需將所有的數(shù)字都更新為序列長度，每次只需更新左右兩個端點的數(shù)字即可。
每次遍歷一個數(shù)，若曾經(jīng)出現(xiàn)過，則跳過。若沒有出現(xiàn)過，則令其與左右兩邊的集合合并，令新長度為len[i-1]+len[i+1]+1，更新左右兩個端點和len[i]的值。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        map<int,int> len;
        int max_len=0,cur_len;
        for(int i=0;i<nums.size();++i){
            if(len[nums[i]]==0){
                cur_len=len[nums[i]-1]+len[nums[i]+1]+1;
                len[nums[i]]=cur_len;
                len[nums[i]-len[nums[i]-1]]=cur_len;
                len[nums[i]+len[nums[i]+1]]=cur_len;
                max_len=max(max_len,cur_len);
            }
        }
        return max_len;
    }
};

3/25

200 島嶼的個數(shù)

圖的連通分量問題，我用dfs解決，評論區(qū)里也有用并查集的
并查集的find函數(shù)融合了查找和集合合并

dfs:

class Solution {
public:
    void dfs(vector<vector<bool>>& vis,vector<vector<char>> &grid,int x,int y){
        vis[x][y]=true;
        for(int i=-1;i<=1;++i){
            for(int j=-1;j<=1;++j){
                if((i+j==1||i+j==-1)&&x+i>=0&&x+i<grid.size()&&y+j>=0&&y+j<grid[0].size()){
                    if(grid[x+i][y+j]=='1'&&!vis[x+i][y+j]){
                        dfs(vis,grid,x+i,y+j);
                    }
                }
            }
        }
    } 
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0)return 0;
        int raws=grid.size(),cols=grid[0].size(),cnt=0;
        vector<vector<bool>> vis(raws,vector<bool>(cols,0));
        for(int i=0;i<raws;++i){
            for(int j=0;j<cols;++j){
                if(grid[i][j]=='1'&&!vis[i][j]){
                    dfs(vis,grid,i,j);
                    cnt++;
                } 
            }
        }
        return cnt;
    }
};

并查集:

class Solution {
public:
    vector<int> pre;
    int find(int x){
        if(x!=pre[x])pre[x]=find(pre[x]);//更新x的父親，壓縮路徑
        return pre[x];
    }
    int numIslands(vector<vector<char>>& grid) {
        int rows=grid.size();
        if(rows==0)return 0;
        int cols=grid[0].size();
        for(int i=0;i<rows*cols;++i)pre.push_back(i);
        for(int i=0;i<rows;++i){
            for(int j=0;j<cols;++j){
                int id=i*cols+j,rep;
                if(grid[i][j]=='0'){
                    pre[id]=-1;//若為海，則父親為-1
                    continue;
                }
                //更新邊角的“1”為新的父親節(jié)點
                if(i>0&&grid[i-1][j]=='1'){
                    rep=(i-1)*cols+j;
                    pre[find(id)]=find(rep);
                }
                if(j>0&&grid[i][j-1]=='1'){
                    rep=i*cols+j-1;
                    pre[find(id)]=find(rep);
                }
            }
        }
        map<int,bool> hs;
        int cnt=0;
        for(int i=0;i<rows;++i){
            for(int j=0;j<cols;++j){
                int id=i*cols+j;
                if(grid[i][j]=='1'&&hs[find(id)]==false){
                    hs[find(id)]=true;
                    cnt++;
                }
            }
        }
        return cnt;
    }
};

3/26

684 冗余連接

并查集

class Solution {
public:
    int pre[1010];
    int find(int x){
        if(x!=pre[x])pre[x]=find(pre[x]);
        return pre[x];
    }
    void merge(int a,int b){
        pre[a]>pre[b]?pre[a]=pre[b]:pre[b]=pre[a];
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<int> e(2,-1);
        for(int i=1;i<=edges.size();++i){
            pre[i]=i;
        }
        for(int i=0;i<edges.size();++i){
            int p1=find(edges[i][0]);
            int p2=find(edges[i][1]);
            if(p1==p2){
                e[0]=edges[i][0],e[1]=edges[i][1];//若兩個相連節(jié)點的父節(jié)點相同，即在同一個集合內(nèi)，則這條邊可去
            }
            merge(p1,p2);
        }
        return e;
    }
};

3/27

721 賬戶合并

這個代碼能不能過要看運氣，多提交幾次就過了
要將一個個賬戶抽象為一個個獨立的集合，用哈希表進行映射
然后使用并查集算法

class Solution {
public:
    int pre[1010];
    int find(int x){
        return x!=pre[x]?pre[x]=find(pre[x]):x;
    }
    bool same(int a,int b){
        return find(a)==find(b);
    }
    void unit(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b)return;
        pre[a]=b;
    }
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int num=accounts.size();
        for(int i=0;i<num;++i){
            pre[i]=i;
        }//init
        for(int i=0;i<num;++i){
            for(int j=0;j<i;++j){
                if(accounts[i][0]==accounts[j][0]&&!same(i,j)){//same name
                    bool flag=false;
                    for(int k=1;k<accounts[i].size()&&!flag;++k){
                        for(int t=1;t<accounts[j].size()&&!flag;++t){
                            if(accounts[i][k]==accounts[j][t]){
                                unit(i,j);
                                flag=true;
                            }
                        }
                    }
                }  
            }
        }
        
        vector<set<string> > res(num);//使用set可以去除冗余email并且按字典序排序
        for(int i=0;i<num;++i){
            pre[i]=find(i);
            for(int j=1;j<accounts[i].size();++j)
                res[pre[i]].insert(accounts[i][j]);
        }//union accounts
        vector<vector<string> > ans; 
        for(int i=0;i<num;++i){
            if(pre[i]==i){
                vector<string> one;
                one.push_back(accounts[i][0]);
                for(auto email:res[i]){
                    one.push_back(email);
                }
                ans.push_back(one);
            }//未被合并的集合,加入到ans中
        }
        return ans;
    }
};

3/28

924 盡量減少惡意軟件傳播

并查集

class Solution {
public:
    int pre[310];
    int vir[310];
    int num[310];
    int find(int x){
        if(x!=pre[x])pre[x]=find(pre[x]);
        return pre[x];
    }
    void unit(int a,int b){
        int p1=find(a);
        int p2=find(b);
        if(p1==p2)return;
        pre[p2]=p1;
    }
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        sort(initial.begin(),initial.end());
        int nodes=graph.size();
        for(int i=0;i<nodes;++i){
            pre[i]=i;
        }
        for(int i=0;i<nodes;++i){
            for(int j=i+1;j<nodes;++j){
                if(graph[i][j]){
                    unit(i,j);
                }
            }
        }
        for(int i=0;i<nodes;++i){
            int x=find(i);
            num[x]++;
        }
        for(int i=0;i<initial.size();++i){
            int x=find(initial[i]);
            vir[x]++;
        }
        int index=-1,les=0;
        for(int i=0;i<initial.size();++i){
            if(vir[pre[initial[i]]]==1&&num[pre[initial[i]]]>les){
                index=initial[i];
                les=num[pre[initial[i]]];
            }
            //cout<<num[pre[initial[i]]]<<" "<<initial[i]<<" "<<pre[initial[i]]<<endl;
        }
        return index==-1?initial[0]:index;
    }
};

3/29

947 移除最多同行或同列石頭

圖的連通分量問題，并查集即可解決
移除的最多的石頭數(shù)目=坐標點的數(shù)目-集合數(shù)目

class Solution {
public:
    int pre[1010];
    bool num[1010];
    int find(int x){
        if(x!=pre[x])pre[x]=find(pre[x]);
        return pre[x];
    }
    void unit(int a,int b){
        int p1=find(a);
        int p2=find(b);
        if(p1==p2)return;
        pre[p1]=p2;
    }
    int removeStones(vector<vector<int>>& stones) {
        fill(num,num+1010,0);
        for(int i=0;i<stones.size();++i){
            pre[i]=i;
        }
        for(int i=1;i<stones.size();++i){
            for(int j=0;j<i;++j){
                if(stones[i][0]==stones[j][0]||stones[i][1]==stones[j][1]){
                    unit(i,j);
                }
            }
        }
        int cnt=0;
        for(int i=0;i<stones.size();++i){
            if(!num[find(i)]){
                num[find(i)]=true;
                cnt++;
            }
        }
        return stones.size()-cnt;
    }
};

3/30

990 等式方程的可滿足性

并查集，相等的變量放在一個集合里，然后遍歷所有的!=，如果發(fā)現(xiàn)某一組的變量在一個集合中，return false

class Solution {
public:
    int pre[1000];
    int find(int x){
        if(x!=pre[x])pre[x]=find(pre[x]);
        return pre[x];
    }
    void unit(int a,int b){
        int p1=find(a);
        int p2=find(b);
        if(p1==p2)return;
        pre[p1]=p2;
    }
    int charToNum(char x){
        return x-'a';
    }
    bool equationsPossible(vector<string>& equations) {
        for(int i=0;i<100;++i){
            pre[i]=i;
        }
        for(int i=0;i<equations.size();++i){
            if(equations[i][1]=='='){
                unit(charToNum(equations[i][0]),charToNum(equations[i][3]));
            }
        }
        for(int i=0;i<equations.size();++i){
            if(equations[i][1]=='!'){
                if(find(charToNum(equations[i][0]))==find(charToNum(equations[i][3]))){
                    return false;
                }
            }
        }
        return true;
    }
};

160 相交鏈表

先將遍歷兩個鏈表，使兩者等長，再一起遍歷

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int num1=1,num2=1;
        bool flag=true;
        if(headA==NULL||headB==NULL)return NULL;
        ListNode* a=headA;
        ListNode* b=headB;
        while(a->next!=NULL){
            num1++;
            a=a->next;
        }
        while(b->next!=NULL){
            num2++;
            b=b->next;
        }
        if(num1<num2)flag=false;
        if(flag){
            for(int i=0;i<num1-num2;++i){
                headA=headA->next;
            }
        }else{
            for(int i=0;i<num2-num1;++i){
                headB=headB->next;
            }
        }
        while(headA&&headB&&headA!=headB){
            headA=headA->next;
            headB=headB->next;
        }
        return headA;
    }
};

拓撲排序：用于DAG（有向無環(huán)圖）

拓撲排序是一個有向無環(huán)圖的線性排列，每個頂點有且僅出現(xiàn)一次，若一個頂點存在A到B的路徑，則排序中A一定在B前面
寫出一個圖的拓撲排序方法：選定一個沒有前驅(qū)節(jié)點的起點，刪除這個節(jié)點并不斷遞歸的尋找以它為起點的有向邊，直到圖為空或者沒有無前驅(qū)的節(jié)點為止，后面的情況說明這個圖必存在環(huán)。并且一個DAG的拓撲排序可能有多個。

207 課程表

課程表使用bfs實現(xiàn)的拓撲排序，判斷是否存在環(huán)
主要有三步：
1.初始化所有節(jié)點的度
2.將度為0的節(jié)點入隊
3.bfs,將訪問過的節(jié)點設(shè)為-1表示刪除，將所有相連的節(jié)點的度減一，將度為0的節(jié)點入隊

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> indegree(numCourses,0);//前度數(shù)組
        for(int i=0;i<prerequisites.size();++i){
            auto course=prerequisites[i];
            indegree[course.first]++;
        }
        queue<int> zeros;
        for(int i=0;i<numCourses;++i){
            if(indegree[i]==0)zeros.push(i);
        }
        int cnt=0;
        while(!zeros.empty()){
            cnt++;
            int node=zeros.front();
            zeros.pop();
            indegree[node]=-1;//刪除的節(jié)點置為-1
            for(int i=0;i<prerequisites.size();++i){
                auto temp=prerequisites[i];
                if(temp.second==-1)continue;
                if(temp.second==node){
                    indegree[temp.first]--;
                    if(indegree[temp.first]==0){
                        zeros.push(temp.first);
                    }
                }
            }
        }
        return cnt==numCourses;
    }
};

3/31

210 課程表II

拓撲排序

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> indegree(numCourses,0);
        vector<int> ans,emp;
        for(int i=0;i<prerequisites.size();++i){
            indegree[prerequisites[i].first]++;
        }//初始化所有節(jié)點的度
        queue<int> zeros;
        for(int i=0;i<numCourses;++i){
            if(indegree[i]==0)zeros.push(i);
        }//將度為0的節(jié)點入隊
        while(!zeros.empty()){
            int node=zeros.front();
            zeros.pop();
            ans.push_back(node);
            indegree[node]=-1;
            for(int i=0;i<prerequisites.size();++i){
                auto temp=prerequisites[i];
                if(temp.second==node){
                    if(--indegree[temp.first]==0)zeros.push(temp.first);
                }
            }
        }
        return ans.size()==numCourses?ans:emp;
    }
};

997 找到小鎮(zhèn)的法官

法官的入度應(yīng)該為N-1，出度應(yīng)該為0

class Solution {
public:
    int findJudge(int N, vector<vector<int>>& trust) {
        vector<bool> isTrust(N+1,true);
        vector<int> num(N+1,0);
        for(int i=0;i<trust.size();++i){
            isTrust[trust[i][0]]=false;
            num[trust[i][1]]++;
        }
        int index=-1;
        for(int i=1;i<N+1;++i){
            if(isTrust[i]&&num[i]==N-1)index=i;
        }
        return index;
    }
};

4/1

42 接雨水

維護一個單調(diào)遞減棧，當(dāng)出現(xiàn)一根柱子大于save.top()時記錄其值并pop，如果此時棧為空，則無法接雨水，退出循環(huán)，否則取最小高度乘以x方向上的距離

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> save;
        int num=0,floor=0;
        for(int i=0;i<height.size();++i){
            while(!save.empty()&&height[save.top()]<=height[i]){
                floor=height[save.top()];
                save.pop();
                if(save.empty())break;
                num+=(min(height[save.top()],height[i])-floor)*(i-save.top()-1);
            }
            save.push(i);
        }
        return num;
    }
};

4/2

84 柱狀圖中的最大矩形

單調(diào)棧問題，維持一個遞增的單調(diào)棧,當(dāng)有小的數(shù)出現(xiàn)時不斷pop，但是這樣無法處理最后一根柱子，所以一開始要給數(shù)組最后加一個長度為0的柱子。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0);
        stack<int> st;
        int area=0;
        for(int i=0;i<heights.size();++i){
            while(!st.empty()&&heights[st.top()]>heights[i]){
                int k=st.top();
                st.pop();
                area=max(area,heights[k]*(st.empty()?i:(i-st.top()-1)));
            }
            st.push(i);
        }
        return area;
    }
};

4/4

15 三數(shù)之和

用三個指針i,j,k 使得nums[i]+nums[j]=-nums[k]，將三數(shù)之和轉(zhuǎn)化為兩數(shù)之和，可以用雙指針法解決問題。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans; 
        if(nums.size()<3) return ans;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;++i){
            int l=i+1,r=nums.size()-1;
            while(l<r&&(i==0||(i>0&&nums[i]!=nums[i-1]))){
                while(r>l&&nums[l]+nums[r]!=-nums[i]){
                if(nums[l]+nums[r]>-nums[i])r--;
                    else l++;
                }
                if(r>l&&nums[l]+nums[r]==-nums[i]){
                    ans.push_back({nums[i],nums[l],nums[r]});
                    while(r>l&&nums[l]==nums[l+1])l++;
                    while(r>l&&nums[r]==nums[r-1])r--;
                    l++;
                }
            } 
        }
        return ans;
    }
};

4/5

16 最接近的三數(shù)之和

與15相似，雙指針法

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int inf=100000;
        int ans;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;++i){
            int j=i+1,k=nums.size()-1;
            while(j<k){
                while(abs(nums[i]+nums[j]+nums[k]-target)>inf&&j+1<k){
                    if(nums[i]+nums[j]+nums[k]-target<0)j++;
                    else k--;
                }
                //cout<<i<<" "<<j<<" "<<k<<" "<<ans<<endl;
                if(abs(nums[i]+nums[j]+nums[k]-target)<inf){
                    inf=abs(nums[i]+nums[j]+nums[k]-target);
                    ans=nums[i]+nums[j]+nums[k];
                }
                if(nums[i]+nums[j]+nums[k]-target<0)j++;
                else k--;
            }
        }
        return ans;
    }
};

4/6

3 無重復(fù)字符的最長字串

最重要的一步是用哈希表存儲每個字符最后出現(xiàn)的位置

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left=0;
        int m[256]={0};
        int res=0;
        for(int i=0;i<s.size();++i){
            if(left>m[s[i]]||m[s[i]]==0){
                res=max(res,i-left+1);
            }else{
                left=m[s[i]];
            }
            m[s[i]]=i+1;
        }
        return res;
    }
};

4/8

338 比特位計數(shù)

關(guān)于計數(shù)的小技巧:i&(i-1)可以去掉二進制的i最右邊的1，由于去掉之后的數(shù)比i小，所以可以用之前算出來的加1得到。
同樣，i>>1可以將1向右移一位，得到的值同樣比i小，如果最右邊有1，則加上1，沒有則不加，可以用res[i>>1]+(i&1)
算數(shù)運算 > 移位運算 > 位運算 > 邏輯運算，所以一定要加括號

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res(num+1,0);
        for(int i=1;i<=num;++i){
            res[i]=res[i&(i-1)]+1;
        }
        return res;
    }
};

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res(num+1,0);
        for(int i=1;i<=num;++i){
            res[i]=res[i>>1]+(i&1);
        }
        return res;
    }
};

4/9

1011 在D天內(nèi)送達包裹的能力

二分法，最小化可行的值，注意C(l)永遠是false，所以要返回r

class Solution {
public:
    bool C(int x,int D,vector<int>& weights){
        int j=0;
        for(int i=0;i<D;++i){
            int t=x;
            while(j<weights.size()&&t>=weights[j]){
                t-=weights[j++];
            }
            if(j==weights.size())return true;
        }
        return false;
    }
    int shipWithinDays(vector<int>& weights, int D) {
        int r=100000,l=1,mid;
        while(l+1!=r){
            mid=(r+l)/2;
            if(C(mid,D,weights)){
                r=mid;
            }else{
                l=mid;
            }
            //cout<<l<<" "<<r<<" "<<mid<<endl;
        }
        return r;
    }
};

4/10

528 按權(quán)重隨機選擇

class Solution {
private:
    vector<int> weight;
    vector<int> sum;
public:
    int random(int x){
        return rand()%(x);
    }
    Solution(vector<int>& w) {
        weight=w;
        if(w.size()>0)sum.push_back(w[0]);
        for(int i=1;i<w.size();++i)sum.push_back(w[i]+sum[i-1]);
    }
    bool C(int mid,int choose){
        return sum[mid]>=choose;
    }
    int pickIndex() {
        int choose=random(sum.back());
        int l=0,r=sum.size()-1;
        while(l<r-1){
            int mid=(r+l)/2;
            if(C(mid,choose))r=mid;
            else l=mid;
        }
        if(choose<sum[l])return l;
        return r;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

或者直接用stl里的upper_bound()

class Solution {
public:
    Solution(vector<int> w) {
        sum=vector<int>(w.size(),0);
        if(sum.size()>0)sum[0]=w[0];
        for(int i=1;i<w.size();i++) sum[i]=sum[i-1]+w[i];
    }
    
    int pickIndex() {
        int x=rand()%sum.back();
        int pos=upper_bound(sum.begin(),sum.end(),x)-sum.begin();
        return pos;
    }
 
private:
    vector<int> sum;
};

4/11

575 分糖果

哈希表或者set

class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        map<int,bool> hst;
        int cnt=0;
        for(int i=0;i<candies.size();++i){
            if(!hst[candies[i]]){
                hst[candies[i]]=true;
                cnt++;
            }
        }
        return min(cnt,int(candies.size()/2));
    }
};

class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        int n = candies.size()/2;
        set<int> intS(candies.begin(), candies.end());
        return min((int)intS.size(), n);
    }
};

4/12

17 電話號碼的字母組合

暴力搜就完事

class Solution {
public:
    vector<string> ans;
    map<char,string> hst;
    void dfs(string digits,int depth,string res){
        if(depth==digits.size()){
            ans.push_back(res);
            return;
        }
        for(int i=0;i<hst[digits[depth]].size();++i){
            dfs(digits,depth+1,res+hst[digits[depth]][i]);
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)return ans;
        hst['2']="abc";
        hst['3']="def";
        hst['4']="ghi";
        hst['5']="jkl";
        hst['6']="mno";
        hst['7']="pqrs";
        hst['8']="tuv";
        hst['9']="wxyz";
        dfs(digits,0,"");
        return ans;
    }
};

4/14

292 Nim game

一道博弈論，如果取一塊石頭，贏。
取兩塊石頭，贏。
三塊石頭，贏。
四塊石頭，輸。
五塊石頭

class Solution {
public:
    bool canWinNim(int n) {
        if(n%4)return true;
        return false;
    }
};

4/15

747 至少是其他數(shù)字兩倍的最大數(shù)

今天偷懶做水題

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        int first_max=0,second_max=0,max_index=-1;
        for(int i=0;i<nums.size();++i){
            if(nums[i]>first_max){
                second_max=first_max;
                first_max=nums[i];
                max_index=i;
            }else if(nums[i]>second_max){
                second_max=nums[i];
            }
        }
        return first_max>=(second_max<<1)?max_index:-1;
    }
};

4/16

319 燈泡開關(guān)

首先翻譯一下題目，即求1~n中因子是奇數(shù)的數(shù)的個數(shù)，若一個數(shù)的因子是奇數(shù)，它的充要條件是它是個完全平方數(shù)，簡要證明：非完全平方數(shù)的因子都是成對出現(xiàn)，例如10：1，10 2，5，而完全平方數(shù)除了成對出現(xiàn)的因子外還存在它開方的數(shù)：如16：1，16 2，8 4，4。
而判斷一個數(shù)是否是完全平方數(shù)，只需將它開方取證再平方，觀察它與原來的值是否相等。而A~B中的完全平方數(shù)個數(shù)就是B的平方數(shù)個數(shù)減去A的平方數(shù)個數(shù)。一個數(shù)從1~A中的平方數(shù)個數(shù)為

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

4/17

349 兩個數(shù)組的交集

雙指針

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        if(nums1.empty()||nums2.empty()) return ans;
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        map<int,bool> isok;
        int ptr=0;
        for(int i=0;i<nums1.size();++i){
            while(ptr<nums2.size()&&nums2[ptr]<nums1[i])ptr++;
            if(ptr<nums2.size()&&nums2[ptr]==nums1[i]&&!isok[nums1[i]]){
                isok[nums1[i]]=true;
                ans.push_back(nums1[i]);
                ptr++;
            }
        }
        return ans;
    }
};

4/18

590 N叉樹的后序遍歷

DFS+回溯即可

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> ans;
    void dfs(Node* node){
        if(node==NULL)return;
        for(int i=0;i<node->children.size();++i)dfs(node->children[i]);
        ans.push_back(node->val);
    }
    vector<int> postorder(Node* root) {
        dfs(root);
        return ans;
    }
};

589 N叉樹的前序遍歷

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    vector<int> ans;
    void dfs(Node* node){
        if(node==NULL)return;
        ans.push_back(node->val);
        for(int i=0;i<node->children.size();++i)dfs(node->children[i]);
    }
    vector<int> preorder(Node* root) {
        dfs(root);
        return ans;
    }
};