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)开始寻找循环节，循环节的长度一定是4for(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;}
}

3--字母异位词分组（49）

主要思路：