第 192 场周赛

Posted on | In , | |
Words count in article: 580 | Reading time ≈ 3

5428. 重新排列数组

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> res(2*n);
        int z = 0;
        for(int i=0; i<n; i++) {
            res[z++] = nums[i];
            res[z++] = nums[i+n];
        }
        return res;
    }
};

5429. 数组中的 k 个最强值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> getStrongest(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        int mid = 0, n = arr.size();
        mid = arr[(n-1)/2];
        sort(arr.begin(), arr.end(), [&](int a, int b){
            return (abs(a-mid)>abs(b-mid)) || ((abs(a-mid) == abs(b-mid)) && a > b);
        });
        vector<int> res;
        for(int i=0; i<k ;i++) {
            res.push_back(arr[i]);
        }
        return res;
    }
};

5430. 设计浏览器历史记录

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
class BrowserHistory {
public:
    int curid = 0;
    vector<string> cot;
    
    BrowserHistory(string homepage) {
        cot.push_back(homepage);
    }
    
    void visit(string url) {
        while((curid+1) < cot.size()) {
            cot.pop_back();
        }
        cot.push_back(url);
        curid++;
    }
    
    string back(int steps) {
        int n = curid-steps;
        if(n < 0) {
            curid = 0;
            return cot[0];
        } else {
            curid = n;
            return cot[n];
        }     
    }
    
    string forward(int steps) {
        int n = curid + steps;
        if(n >= cot.size()) {
            curid = cot.size()-1;
            return cot[curid];
        } else {
            curid = n;
            return cot[curid];
        }
    }
};

5431. 给房子涂色 III

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
#define inf 1e8
class Solution {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        //inf排除不可能的值
        vector<vector<vector<int>>> dp(m,vector<vector<int>>(n+1,vector<int>(target+1,inf)));
        //初始化
        if(houses[0]!=0) dp[0][houses[0]][1]=0;
        else{
            for(int i=1;i<=n;i++){
                dp[0][i][1]=cost[0][i-1];
            }
        }
        
        //dp状态转移
        for(int i=1;i<m;i++){
            if(houses[i]==0){//为0，穷举j1和j2
                for(int j1=1;j1<=n;j1++){
                    for(int k=1;k<=target;k++){
                        for(int j2=1;j2<=n;j2++){
                            //在穷举j1和j2中也会有j1==j2，注意哟
                            if(j1==j2) dp[i][j1][k]=min(dp[i][j1][k],dp[i-1][j2][k]+cost[i][j1-1]);
                            else dp[i][j1][k]=min(dp[i][j1][k],dp[i-1][j2][k-1]+cost[i][j1-1]);
                        }
                    }
                }
            }else{//不为0，穷举j2
                for(int k=1;k<=target;k++){
                    for(int j2=1;j2<=n;j2++){
                        int j1=houses[i];
                        if(j1==j2) dp[i][j1][k]=min(dp[i][j1][k],dp[i-1][j2][k]);
                        else dp[i][j1][k]=min(dp[i][j1][k],dp[i-1][j2][k-1]);
                    }
                }
            }
        }
        int ans=1e8;
        for(int i=1;i<=n;i++) ans=min(ans,dp[m-1][i][target]);
        if(ans==1e8) ans=-1;
        return ans;
    }
};
Donate? comment?