Leetcode-第12场双周赛

发表于 分类于 阅读次数：

1243. 数组变换

解法：

1.flag记录当前天的数组与上一天的数组是否相同，当相同时跳出循环

2.last记录上一天数组，now记录当前天数组，当当前天数组更新完毕后，要更新last数组为now数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<int> transformArray(vector<int>& arr) {
        int n=arr.size();
        vector<int> last(arr.begin(),arr.end());
        vector<int> now(arr.begin(),arr.end());
        int flag=1;
        while(flag)
        {
            for(int i=1;i<n-1;i++)
            {
                if(last[i]>last[i-1]&&last[i]>last[i+1])
                {
                    now[i]--;
                }
                else if(last[i]<last[i-1]&&last[i]<last[i+1])
                {
                    now[i]++;
                }
            }
            flag=0;
            for(int i=1;i<n-1;i++)
            {
                if(now[i]==last[i])
                {
                    continue;
                }
                last[i]=now[i];
                flag=1;
            }
        }
        return now;
    }
};

1244. 力扣排行榜

解法：

读懂题目意思很简单。实现类接口。。注意top()函数，按得分排序，得分为0的点不计入在内

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Leaderboard {
private:
     vector<int>res;
public:
    Leaderboard() {
        vector<int> res_(10010,0);
        res=res_;
    }
    
    void addScore(int playerId, int score) {
        res[playerId]+=score;
    }
    
    int top(int K) {
        int sum=0;
        vector<int> temp(res.begin(),res.end());
        sort(temp.begin(),temp.end());
        int j=temp.size()-1;
        for(int i=0;i<K;i++)
        {
            sum+=temp[j];
            j--;
        }
        return sum;
    }
    
    void reset(int playerId) {
        res[playerId]=0;
    }
};

/**
 * Your Leaderboard object will be instantiated and called as such:
 * Leaderboard* obj = new Leaderboard();
 * obj->addScore(playerId,score);
 * int param_2 = obj->top(K);
 * obj->reset(playerId);
 */

1245. 树的直径

解法：两次BFS

先从一点BFS遍历到最远的一点，然后从最远的那一点进行BFS记录能遍历到的最深距离即为树的直径

注意：

1.用邻接表记录每个点的连接,（不要用邻接矩阵，内存会爆掉的。。。亲身经历= =）

2.bool数组记录走过的点，防止进入死循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    int treeDiameter(vector<vector<int>>& edges) {
        int n=edges.size()+1;
        vector<vector<int>> e(n,vector<int>());
        vector<bool> used(n,false);
        for(auto edge:edges)
        {
            e[edge[0]].push_back(edge[1]);
            e[edge[1]].push_back(edge[0]);
        }
        queue<int> que;
        que.push(0);
        used[0]=true;
        int res=0;
        int q;
        while(!que.empty())
        {
            int size=que.size();
            for(int i=0;i<size;i++)
            {
                q=que.front();que.pop();
                for(auto y:e[q])
                {
                    if(used[y]!=true)
                    {
                        used[y]=true;
                        que.push(y);
                    }
                }
            }
        }
        for(int i=0;i<n;i++) used[i]=false;
        used[q]=true;
        que.push(q);
        while(!que.empty())
        {
            res++;
            int size=que.size();
            for(int i=0;i<size;i++)
            {
                q=que.front();que.pop();
                for(auto y:e[q])
                {
                    if(used[y]!=true)
                    {
                        used[y]=true;
                        que.push(y);
                    }
                }
            }
        }
        return res-1;
    }
};

1246. 删除回文子数组

同样的第四题，同样的靠二哥的讲解

解法：区间dp