46. 全排列
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<bool> st;
vector<vector<int>> permute(vector<int>& nums) {
path = vector<int>(nums.size());
st = vector<bool>(nums.size());
dfs(nums, 0);
return ans;
}
void dfs(vector<int>& nums,int u){
if(u == nums.size()){
ans.push_back(path);
return;
}
for(int i = 0; i < nums.size(); i++){
if(!st[i]){
path[u] = nums[i];
st[i] = true;
dfs(nums, u + 1);
st[i] = false;
}
}
}
};
知识点: dfs
47. 全排列 II
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<int> st;
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n = nums.size();
path = vector<int> (n);
st = vector<int> (n);
dfs(nums,0);
return ans;
}
void dfs(vector<int>& nums,int u){
if(u == nums.size()){
ans.push_back(path);
return;
}
for(int i = 0 ; i < nums.size(); i++){
if(!st[i]){
if(i && nums[i] == nums[i - 1] && st[i - 1]) continue;
st[i] = true;
path[u] = nums[i];
dfs(nums,u + 1);
st[i] = false;
}
}
}
};
if(i && nums[i] == nums[i - 1] && st[i - 1]) continue;
存在疑惑
48. 旋转图像
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
y = x 上半部分与下半部分交换
// n - 1 和 n 都可,这里是 n - 1
for(int i = 0 ; i < n - 1; i ++){
for(int j = i + 1; j < n; j ++){
swap(matrix[i][j],matrix[j][i]);
}
}
// 左右两边交换
for(int i = 0 ; i < n; i ++){
for(int j = 0, k = n - 1; j < k; j ++, k--){
swap(matrix[i][k],matrix[i][j]);
}
}
}
};
49. 字母异位词分组
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> hash;
// 字符串排序
for(auto str: strs){
string nstr = str;
sort(nstr.begin(),nstr.end());
hash[nstr].push_back(str);
}
// 将 second 作为答案提取出来
vector<vector<string>> res;
for(auto item: hash){
res.push_back(item.second);
}
return res;
}
};
50. Pow(x, n)
class Solution {
public:
double myPow(double x, int n) {
typedef long long ll;
bool is_minus = n < 0;
double res = 1;
for(ll k = abs(ll(n)); k ; k >>= 1){
if(k & 1) res *= x;
x *= x;
}
if(is_minus) return 1 / res;
return res;
}
};
知识点: 快速幂