2020-09-05 刷题3

60 第k个排列

从高到低，依次确定每一位的取值。首先，对于第n位来说, 每(n-1)！对应一个数，所以用k除以(n-1)！，来确定第n位的数；对于n-1位来说，每(n-2)！对应一个数。用一个布尔数组记录每个元素是否被用过，因为n最大是9，因此每次遍历布尔数组，来确定当前的元素。

class Solution {
public:
    bool used[9] = {0};
    int factoral(int n){
        int prod = 1;
        while(n > 0){
            prod *= n;
            n--;
        }
        return prod;
    }
    char find_idx(int idx, int n){
        for(int j = 0; j < n; j++){
            if(used[j])
                continue;
            if(idx == 0){
                used[j] = true;
                return j + 1 + '0';
            }
            idx--;
        }
        return '0';
    }

    string getPermutation(int n, int k) {
        if(n == 1)
            return "1";
        k--;
        string prem = "";
        for(int i = n - 1; i > 0; i--){
            int n_mod = factoral(i);
            int idx = k / n_mod;
            k = k % n_mod;
            prem += find_idx(idx, n);
        }
        prem += find_idx(0, n);
        return prem;
    }
};

238 除自身以外数组的乘积

这种左右遍历两遍的做法非常巧妙啊，，
设置两个数组，分别记录每个元素左边的乘积以及右边的乘积，最后合起来就可以。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int num_size = nums.size();
        vector<int> left_dot(num_size, 1), right_dot(num_size, 1);
        // left to right
        for(int i = 1; i < num_size; i++)
            left_dot[i] = left_dot[i - 1] * nums[i - 1];
        for(int i = num_size - 2; i >= 0; i--)
            right_dot[i] = right_dot[i + 1] * nums[i + 1];
        for(int i = 0; i < num_size; i++)
            left_dot[i] *= right_dot[i];
        return left_dot;
    }
};

题目中还有一个拓展要求是空间复杂度为O(1)，这里指的是不包括输出的。所以可以只保留left_dot，把right_dot用一个int来维护，非常简洁。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int num_size = nums.size();
        vector<int> dot(num_size, 1);
        // left to right
        for(int i = 1; i < num_size; i++)
            dot[i] = dot[i - 1] * nums[i - 1];
        int right_dot = 1;
        for(int i = num_size - 2; i >= 0; i--){
            right_dot *= nums[i + 1];
            dot[i] *= right_dot;
        }
        return dot;
    }
};

54 螺旋矩阵

思路很简单，维护四个变量，分别为left，right，top和bottom，代表了当前未打印矩阵的边界；每圈从[top][left]开始，向右，下，左，上遍历一遍为一圈，在遍历的过程中更新四个变量的值来缩小范围。最后一圈有可能走不完，所以在while循环中间也要判断是否到达了退出的条件。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> results;
        if(matrix.size() == 0)
            return results;
        int row_num = matrix.size(), col_num = matrix[0].size();
        int left = 0, right = col_num - 1, top = 0, bottom = row_num - 1;
        while(left <= right && top <= bottom){
            for(int j = left; j <= right; j++)
                results.push_back(matrix[top][j]);
            top++;
            if(top > bottom)
                break;
            for(int i = top; i <= bottom; i++)
                results.push_back(matrix[i][right]);
            right--;
            if(left > right)
                break;
            for(int j = right; j >= left; j--)
                results.push_back(matrix[bottom][j]);
            bottom--;
            if(top > bottom)
                break;
            for(int i = bottom; i >= top; i--)
                results.push_back(matrix[i][left]);
            left++;
        }
        return results;
    }
};