192周赛.md

783 / 3614

题目： LeetCode 1470. 给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。

//好的
class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> ret;
        for (int i = 0; i < n; ++ i)
        {
            ret.push_back(nums[i]);
            ret.push_back(nums[i+n]);
        }
        return ret;
    }
};
//我的
class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> ans(nums.size(),0);
        int m = nums.size()/n;
        for(int i = 0; i < n ; i++){
            for(int j = 0; j < m; j++){
                ans[i*m+j] = nums[j*n+i];
            }
        }
        return ans;
    }
};

题目： LeetCode 1471. 给你一个整数数组 arr 和一个整数 k 。设 m 为数组的中位数，只要满足下述两个前提之一，就可以判定 arr[i] 的值比 arr[j] 的值更强：

• |arr[i] - m| > |arr[j] - m|
• |arr[i] - m| == |arr[j] - m|，且 arr[i] > arr[j]

请返回由数组中最强的 k 个值组成的列表。

class Solution {
public:
    int abs(int x){
        if(x < 0) return -1*x;
        return x;
    }
    vector<int> getStrongest(vector<int>& arr, int k) {
        int n = arr.size();
        sort(arr.begin(),arr.end());
        int m = arr[(n-1)/2];
        vector<int> ans(k,0);
        int left = 0, right = n-1;
        for(int i = 0; i < k; i++){
            if(abs(arr[left]-m)<=abs(arr[right]-m) ){
                ans[i] = arr[right];
                right--;
            }else if(abs(arr[left]-m)>abs(arr[right]-m)){
                ans[i] = arr[left];
                left++;
            }
        }
        return ans;
    }
};
//排序后，找到中位数，从数组两头开始找。

题目： LeetCode1472. 设计浏览器历史记录. 你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。

class BrowserHistory {
public:
    
    vector<string> s;
    int pos;
    
    BrowserHistory(string homepage) {
        s.clear();
        s.push_back(homepage);
        pos = 0;
    }
    
    void visit(string url) {
        s.resize(pos+1);
        s.push_back(url);
        pos ++;
    }
    
    string back(int steps) {
        pos -= steps;
        if (pos < 0) pos = 0;
        return s[pos];
    }
    
    string forward(int steps) {
        pos += steps;
        if (pos >= s.size()) pos = s.size()-1;
        return s[pos];
    }
};

题目： 1473. 给房子涂色 III. 在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ）。有的房子去年夏天已经涂过颜色了，所以这些房子不需要被重新涂色。

我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 houses = [1,2,2,3,3,2,1,1] ，它包含 5 个街区  [{1}, {2,2}, {3,3}, {2}, {1,1}] 。）

给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target ，其中：

houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色。 cost[i][j]：是将第 i 个房子涂成颜色 j+1 的花费。 请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区。如果没有可用的涂色方案，请返回 -1 。

//dp[i][j][k] 动态规划
//第i个房子染成j个颜色，形成k个街区的开销
//第
#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]);
                    }
                }
            }
        }
        //遍历以下所有的j，寻找答案
        int ans=1e8;
        for(int i=1;i<=n;i++) ans=min(ans,dp[m-1][i][target]);
        if(ans==1e8) ans=-1; //注意处理一下不存在答案，我就忘了，wa一次，嘤嘤嘤了
        return ans;
    }
};