写在前面

华为面试题库刷题第六次整理。

739. 每日温度

根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

温度索引

因为温度的范围很小，我们建立一个下标是温度，内容存储索引的数组然后逆序遍历数组，求出温度+1到100之间的最小索引就行了。

代码：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& a) {
        if(a.empty()) return {};
        vector<int> res(a.size(),0);
        vector<int> temp(101,0);
        temp[a[a.size()-1]] = a.size()-1;
        for(int i=a.size()-2; i>=0; i--){
            int m = INT_MAX;
            for(int j = a[i]+1; j<=100; j++)
                if(temp[j]>0)
                    m = min(m,temp[j]);
            if(m!=INT_MAX) res[i] = m-i;
            temp[a[i]] = i;
        }
        return res;
    }
};

栈

用栈维护一个索引序列，保证序列索引对应的数值从栈顶开始升序，每次弹出比当前元素小的栈顶。

代码：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& a) {
        if(a.empty()) return {};
        vector<int> res(a.size(),0);
        stack<int> s;
        for(int i=a.size()-1; i>=0; i--){
            while(!s.empty() && a[i]>=a[s.top()])
                s.pop();
            res[i] = (s.empty())?0:s.top()-i;
            s.push(i);
        }
        return res;
    }
};

48. 旋转图像

给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

转置加翻转

观察一下旋转的规律，不难发现：先转置矩阵，然后翻转行，就可以得到答案。

代码：

class Solution {
public:
    void swap(int& a, int& b){
        int t = a;
        a = b;
        b = t;
    }
    void rotate(vector<vector<int>>& m) {
        if(m.empty()) return;
        int n = m.size();
        //transpose matrix转置矩阵
        for(int i=0; i<n; i++)
            for(int j=0; j<=i; j++){
                swap(m[i][j],m[j][i]);
            }
        //reverse row翻转行
        for(int i=0; i<n; i++)
            for(int j=0; j<n/2; j++)
                swap(m[i][j],m[i][n-j-1]);
        return;
    }
};

一次性转四个矩阵

继续观察样例，可以发现旋转的本质，其实是四个矩阵的旋转，我们可以把原矩阵分割成四个矩阵，然后旋转。

代码：

class Solution {
public:
    void rotate(vector<vector<int>>& m) {
        if(m.empty()) return;
        int n = m.size();
        for(int i=0; i<(n+1)/2; i++)
            for(int j=0; j<n/2; j++){
                int tmp = m[n-j-1][i];
                m[n-j-1][i] = m[n-i-1][n-j-1];
                m[n-i-1][n-j-1] = m[j][n-i-1];
                m[j][n-i-1] = m[i][j];
                m[i][j] = tmp;
            }
        return;
    }
};

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。编写一个算法来重建这个队列。
注意：
总人数少于1100人。

示例
输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解法：
这题的解法官方题解写的很清楚而且方法很巧妙，这里直接po
https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode/

代码：

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& a) {
        if(a.empty()) return a;
        sort(a.begin(),a.end(), [](vector<int>& l, vector<int>& r){
            return (l[0]==r[0])?l[1]<r[1]:l[0]>r[0];
        });
        vector<vector<int>> res(a.size(),vector<int>(2,-1));
        for(auto x:a){
            int idx = x[1];
            cout<<x[0]<<' '<<x[1]<<endl;
            if(res[idx][0]==-1){
                res[idx][0] = x[0];
                res[idx][1] = x[1];
            }
            else{
                cout<<"idx:"<<idx<<endl;
                for(int i=res.size()-1; i>idx; i--){
                    res[i][0] = res[i-1][0];
                    res[i][1] = res[i-1][1];
                }
                res[idx][0] = x[0];
                res[idx][1] = x[1];
            }
        }
        return res;
    }
};

LeetCode-华为面试题库做题笔记六

第六次