Leetcode刷题笔记--Hot21-30

1--全排列（46）

主要思路1：

经典全排列，每次枚举每一位时，重头开始枚举，用一个访问数组记录当前已经被访问过的数字；

这道题不包含重复数字，所以不需要进行树层上的剪枝；

#include <iostream>
#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> permute(std::vector<int>& nums) {
        if(nums.size() == 0) return res;
        std::vector<bool> vis(nums.size(), false);
        std::vector<int> tmp;
        dfs(nums, vis, tmp);
        return res;
    }

    void dfs(std::vector<int>& nums, std::vector<bool>& vis, std::vector<int> &tmp){
        if(tmp.size() == nums.size()){
            res.push_back(tmp);
            return;
        }
        for(int i = 0; i < nums.size(); i++){
            if(vis[i] == true) continue;
            tmp.push_back(nums[i]);
            vis[i] = true;
            dfs(nums, vis, tmp);
            // 回溯
            tmp.pop_back();
            vis[i] = false;
        }
    }
private:
    std::vector<std::vector<int>> res;
};

int main(int argc, char *argv[]){
    std::vector<int> test = {1,2,3};
    Solution S1;
    std::vector<std::vector<int>> res = S1.permute(test);
    for(auto v : res){
        for(auto i : v) std::cout << i << " ";
        std::cout << std::endl;
    }
}

主要思路2：

可以利用下一个排列的思想来枚举全排列，首先需要将数组进行从小到大排序，然后不断求解下一个排列，一个下一个排列就是一个新的排列，直到最大的排列为止；

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> permute(std::vector<int>& nums) {
        if(nums.size() == 0) return res;
        std::sort(nums.begin(), nums.end()); // 从小到大排列
        res.push_back(nums); // 记录最小的排列
        while(nextp(nums)){
            res.push_back(nums);
        }
        return res;
    }

    bool nextp(std::vector<int>& nums){
        int n = nums.size();
        // 找到第一个顺序对
        int i;
        for(i = n - 2; i >= 0; i--){
            if(nums[i] < nums[i+1]) break;
        }
        if(i == -1) return false; //已经是最大排列了

        // 找到一个nums[j] > 上面的nums[i]
        int j;
        for(j = n - 1; j > i; j--){
            if(nums[j] > nums[i]) break;
        }

        // 交换nums[i] 和 nums[j]
        std::swap(nums[i], nums[j]);
        // 反转num[i+1] ~ nums.end()
        std::reverse(nums.begin() + i + 1, nums.end());
        return true;
    }

private:
    std::vector<std::vector<int>> res;
};

int main(int argc, char *argv[]){
    std::vector<int> test = {1,2,3};
    Solution S1;
    std::vector<std::vector<int>> res = S1.permute(test);
    for(auto v : res){
        for(auto i : v) std::cout << i << " ";
        std::cout << std::endl;
    }
}

2--旋转图像（48）

主要思路：

按层（圈）来旋转，对于坐标为(r, c)的值，其旋转后的坐标为(c, n - 1 - r)，且每四个（上，右，下，左）为一个循环节，循环交换循环节中四个元素即可，视频讲解参考：旋转图像

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    void rotate(std::vector<std::vector<int>>& matrix) {
        int n = matrix.size();
        // 按层（圈）处理
        for(int L = n; L > 0; L -= 2){
            // 左上角起始元素
            int row = (n - L) / 2;
            int col = row;

            // 当前这一行，顶行的前 L-1 个元素
            for(int k = 0; k < L - 1; k++){
                // 当前元素
                int r = row, c = col + k;
                int tmp = matrix[r][c];
                // 从(r, c)开始寻找循环节，循环节的长度一定是4
                for(int i = 0; i < 4; i++){
                    // 旋转后的坐标
                    int rr = c;
                    int cc = n - 1 - r;
                    // 旋转
                    std::swap(tmp, matrix[rr][cc]);
                    r = rr;
                    c = cc;
                }
            }
        }
    }
};
int main(int argc, char *argv[]){
    std::vector<std::vector<int>> test = {{1,2,3}, {4,5,6}, {7,8,9}};
    Solution S1;
    S1.rotate(test);
    for(auto v : test){
        for(auto i : v) std::cout << i << " ";
        std::cout << std::endl;
    }
}