LeetCode.192场周赛

5428.重新排列数组

给你一个数组 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> ans;
        
        for(int i = 0; i<n; i++){
            ans.push_back(nums[i]);
            ans.push_back(nums[i+n]);
        }
        return ans;
    }
};

5429.数组中的k个最强值

给你一个整数数组 arr 和一个整数 k 。
设 m 为数组的中位数，只要满足下述两个前提之一，就可以判定 arr[i] 的值比 arr[j] 的值更强：
|arr[i] - m| > |arr[j] - m|
|arr[i] - m| == |arr[j] - m|，且 arr[i] > arr[j]
请返回由数组中最强的 k 个值组成的列表。答案可以以 任意顺序 返回。

中位数 是一个有序整数列表中处于中间位置的值。形式上，如果列表的长度为 n ，那么中位数就是该有序列表（下标从 0 开始）中位于 ((n - 1) / 2)的元素。

• 例如 arr = [6, -3, 7, 2, 11]，n = 5：数组排序后得到 arr = [-3, 2, 6, 7, 11] ，数组的中间位置为 m = ((5 - 1) / 2) = 2 ，中位数 arr[m] 的值为 6 。
• 例如 arr = [-7, 22, 17, 3]，n = 4：数组排序后得到 arr = [-7, 3, 17, 22] ，数组的中间位置为 m = ((4 - 1) / 2) = 1 ，中位数 arr[m] 的值为 3 。

分析

先找中位数，然后把数组中每个数与中位数处理后的值以及该数本身存到pair中，自定义一个cmp比较函数对pair数组进行排序，输出前k个pair的second即可。

class Solution {
pair<int,int> a[100010];
public:
    static bool cmp(pair<int,int> a,pair<int,int> b){
        if(a.first>b.first) return true;
        else if(a.first==b.first) return a.second>b.second; 
        return false;
    }
    
    vector<int> getStrongest(vector<int>& arr, int k) {
        int n = arr.size();
        
        sort(arr.begin(),arr.end());
        int m = arr[(n-1)/2];
        
        for(int i = 0; i<n; i++){
            int x = abs(arr[i]-m), y = arr[i];
            a[i] = {x,y};
        }
        
        sort(a,a+n,cmp);
        
        vector<int> ans;
        
        for(int i = 0; i<k; i++)ans.push_back(a[i].second);
        
        return ans;
    }
};

5430.设计浏览器的历史记录

你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。
请你实现 BrowserHistory类：

• BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
• void visit(string url) 从当前页跳转访问 url 对应的页面 。执行此操作会把浏览历史前进的记录全部删除。
• string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。
• string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进 至多 steps步以后的 url 。

分析

模拟。利用一个string数组来模拟访问记录，因为visit后会清楚所有历史中前进记录，所有利用一个变量now来记录当前访问的位置，如果visit新的网页，直接加在now位置后即可，类似于模拟一个栈。

class BrowserHistory {
string h[10000];
int cnt;
int now;
public:
    BrowserHistory(string homepage) {
        cnt = 1;
        h[cnt++] = homepage;
        now = 1;
    }
    
    void visit(string url) {
        h[++now] = url;
        cnt = now+1;
    }
    
    string back(int steps) {
        //cout<<now<<endl;
        if(steps<=now-1) {
            now -= steps;
            return h[now];
        }
        now = 1;
        return h[now];
    }
    
    string forward(int steps) {
        if(now + steps <= cnt -1){
            now += steps;
            return h[now];
        }else{
            now = cnt-1;
            return h[now];
        }
    }
};

/**
 * Your BrowserHistory object will be instantiated and called as such:
 * BrowserHistory* obj = new BrowserHistory(homepage);
 * obj->visit(url);
 * string param_2 = obj->back(steps);
 * string param_3 = obj->forward(steps);
 */

5431.给房子涂色Ⅲ

在一个小城市里，有 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 。

闫式DPnb！！！

分析

状态表示： dp[ i ][ j ][ k ] 表示涂完了前 i 个房子，且目前有 j 个街区，第 i 个房子涂色为k的所有方案中的最小花费

状态计算：第 i 个房子颜色已经确定为k，所以我们以第 i -1个房子的颜色为标准分类，可以分成n类，设第i -1个房子的颜色为u (u∈[1,n]）

• u == k dp(i,j,k) = dp(i-1, j,u) 因为第i-1个房子和第i个房子同属于一个街区。
• u \ =k dp(i,j,k) = dp(i-1,j-1,u) 第i个房子独占一个街区，前i-1个房子只有j-1个街区

时间复杂度

const int inf = 1e9; 
class Solution {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        vector<vector<vector<int>>> f(m+1,vector<vector<int>>(target+1,vector<int>(n+1,inf)));
        //f[i][j][k] 表示涂完前i个房子，且现在有j个街区，第i个房子涂色为k的所有方案，属性为min

        //初始化
        if(houses[0]) f[0][1][houses[0]] = 0;  //第0(1)个房子已经涂色，不需要涂色，花费为0
        else{
            for(int i = 1; i<=n; i++) f[0][1][i] = cost[0][i-1];  //未涂色，在所有方案中找最小值
        }

        //状态计算
        for(int i = 1; i<m; i++){
            for(int j = 1; j<=target; j++){
                if(houses[i]){  //第i个房子颜色已经涂过
                    int k = houses[i];
                    for(int u = 1; u<=n; u++){
                        if(k == u) f[i][j][k] = min(f[i][j][k], f[i-1][j][u]); //第i-1个房子和第i个颜色相同，同属一个街区
                        else f[i][j][k] = min(f[i][j][k], f[i-1][j-1][u]);
                    }
                }else{
                    for(int k = 1; k<=n; k++){
                        for(int u = 1; u<=n; u++){
                            if(u == k) f[i][j][k] = min(f[i][j][k], f[i-1][j][u] + cost[i][k-1]);
                            else f[i][j][k] = min(f[i][j][k], f[i-1][j-1][u] + cost[i][k-1]);
                        }
                    }
                }
            }
        }

        int ans = inf;
        for(int i = 1; i<=n; i++) ans = min(ans,f[m-1][target][i]);
        
        if(ans == inf) return -1;
        return ans;
    }
};