高频面试系列

接雨水、旋转图像、颠倒字符串中的单词、缺失的第一个正数、螺旋矩阵、比较版本号、Pow(x, n)、数组中的逆序对

42.接雨水

备忘录优化

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if(n==0) return 0;
        int res = 0;
        //数组充当备忘录
        vector<int> l_max(n);
        vector<int> r_max(n);

        // base case
        l_max[0] = height[0];
        r_max[n-1] = height[n-1];

        //从左往右计算 l_max
        for(int i=1;i<n;i++){
            l_max[i] = max(l_max[i-1], height[i]);
        }
        //从右往左计算 r_max
        for(int i=n-2;i>=0;i--){
            r_max[i] = max(r_max[i+1], height[i]);
        }

        //计算答案
        for(int i=1;i<n-1;i++){
            res += min(l_max[i], r_max[i])-height[i];
        }
        return res;
    }   
};
//时间复杂度：O(n)
//空间复杂度：O(n)

双指针解法

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        if(n==0) return 0;

        int l_max = height[0];
        int r_max = height[n-1];

        int left=0;
        int right=n-1;
        int res=0;
        while(left<=right){
            //l_max 是 height[0...left] 中的最高的柱子高度
            l_max = max(l_max, height[left]);
            //r_max 是 height[right...n-1]中的最高的柱子高度
            r_max = max(r_max, height[right]);

            //res += min(l_max, r_max)-height[i];
            if(l_max<r_max){
                res += l_max-height[left];
                left++;
            }else{
                res += r_max-height[right];
                right--;
            }
        }
        return res;
    }   
};
//时间复杂度：O(n)
//空间复杂度：O(1)

48.旋转图像

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        //思路：先水平翻转，再沿主对角线翻转
        int n=matrix.size();

        for(int i=0;i<n/2;i++){
            for(int j=0;j<n;j++){
                swap(matrix[i][j], matrix[n-i-1][j]);
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

151.颠倒字符串中的单词

class Solution {
public:
    string reverseWords(string s) {
        int i=s.size()-1;
        string res;
        while(i>=0){      //从后往前遍历s
            int count=0;   //记录每个单词的长度  
            while(i>=0 && s[i]==' ') i--;   //空格跳过
            while(i>=0 && s[i]!=' '){       //非空格，则count++
                i--;
                count++;
            }
            if(count) res += s.substr(i+1, count) + " ";  
        }
        return res.substr(0, res.size()-1); //目的是去掉尾随空格
    }
};

41.缺失的第一个正数

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;i++){
            while(nums[i]>0 && nums[i]<=n && nums[nums[i]-1]!=nums[i]){
                swap(nums[i], nums[nums[i]-1]);
            }
        }
        for(int i=0;i<n;i++){
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return n+1;
    }
};

54.螺旋矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        vector<int> res;
        if(m==0 || n==0) return res;

        //定义左右上下边界的位置
        int left = 0;
        int right = n-1;
        int up = 0;
        int down = m-1;
        
        while(true){
            
            //从左往右走
            for(int i=left;i<=right;i++) res.push_back(matrix[up][i]);
            if(++up > down) break; //更新上边界
            
            //从上往下走
            for(int i=up;i<=down;i++) res.push_back(matrix[i][right]);
            if(--right<left) break; //更新右边界

            //从右往左走
            for(int i=right;i>=left;i--) res.push_back(matrix[down][i]);
            if(--down<up) break; //更新下边界

            //从下往上走
            for(int i=down;i>=up;i--) res.push_back(matrix[i][left]);
            if(++left>right) break; //更新左边界
        }
        return res;
    }
};

165.比较版本号

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int m=version1.size();
        int n=version2.size();
        int i=0, j=0;
        while(i<m || j<n){
            long num1=0, num2=0;
            // 将一段连续的字符串转换成数字, num = num*10 是为了去前导 0
            while(i<m && version1[i]!='.') num1=num1*10 + version1[i++]-'0';
            while(j<n && version2[j]!='.') num2=num2*10 + version2[j++]-'0';
            if(num1>num2) return 1;
            else if(num1<num2) return -1;
            i++;
            j++;
        }
        return 0;
    }
};

50.Pow(x, n)

class Solution {
public:
    double myPow(double x, int n) {
        //快速幂+递归
        long long N=n;
        return N>=0 ? helper(x, N) : 1.0/helper(x, -N);
    }
    double helper(double x, long long N){
        if(N==0){
            return 1.0;
        }
        double y=helper(x, N/2);
        return N%2 == 0 ? y*y : y*y*x;
    }
};

剑指offer51.数组中的逆序对

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int n=nums.size();
        vector<int> temp(n);
        return mergeSort(nums, temp, 0, n-1);
    }

    //归并排序
    int mergeSort(vector<int>& nums, vector<int>& temp, int low, int high){
        if(low>=high) return 0;
        int mid=low+(high-low)/2;
        int res = mergeSort(nums, temp, low, mid) + mergeSort(nums, temp, mid+1, high);

        int i=low;
        int j=mid+1;
        for(int k=low;k<=high;k++){
            temp[k]=nums[k];
        }

        for(int k=low;k<=high;k++){
            if(i==mid+1){
                nums[k]=temp[j++];
            }else if(j==high+1){
                nums[k]=temp[i++];
            }else if(temp[i]<=temp[j]){
                nums[k]=temp[i++];
            }else{
                nums[k]=temp[j++];
                res += mid-i+1;
            }
        }
        return res;
    }
};

386.字典排序

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res(n);
        int number=1;
        for(int i=0;i<n;i++){
            res[i]=number;
            if(number*10<=n){
                number*=10;
            }else{
                while(number%10==9 || number+1>n){
                    number/=10;
                }
                number++;
            }
        }
        return res;
    }
};

440.字典序的第k小数字

class Solution {
public:
    int findKthNumber(int n, int k) {
        int cur=1;
        --k; //初始化为 cur=1，k需要自减1
        while(k>0){
            long long step=0, first=cur, last=cur+1;
            //统计这颗子树下所有节点数（step）
            while(first<=n){
                 //不能超过n的值，并不是所有节点都有十个子节点
                step += min((long long)n+1, last)-first;  
                first *= 10;
                last *= 10;
            }
            if(step<=k){ //不在子树中
                ++cur;
                k -= step;
            }else{ //在子树中，进入子树
                cur *= 10;
                --k;
            }
        }
        return cur;
    }
};

43.字符串相乘

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1=="0" || num2=="0") return "0";

        int m=num1.size();
        int n=num2.size();
        vector<int> res(m+n);

        for(int i=m-1;i>=0;i--){
            int x = num1[i]-'0';
            for(int j=n-1;j>=0;j--){
                int y = num2[j]-'0';
                res[i+j+1] += x * y;
            }
        }
        //进位
        for(int i=m+n-1;i>0;i--){
            res[i-1] += res[i]/10;
            res[i] = res[i]%10;
        }
        
        //将数组res转换成字符串
        //最高位为0，则索引从1开始，否则从0开始
        int index = res[0] == 0 ? 1 : 0;
        string s;
        while(index < m+n){
            s.push_back(res[index]+'0');
            index++;
        }

        return s;
    }
};

7. 整数反转

class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while(x){
            if(res>INT_MAX/10 || res<INT_MIN/10){
                return 0;
            }
            res = res*10 + x%10;
            x = x/10;
        }
        return res;
    }
};