成都微信网站建设报价,网站底部关键词指向,全国新闻媒体发稿平台,鸿川建设工程有限公司官方网站1--全排列#xff08;46#xff09; 主要思路1#xff1a; 经典全排列#xff0c;每次枚举每一位时#xff0c;重头开始枚举#xff0c;用一个访问数组记录当前已经被访问过的数字#xff1b; 这道题不包含重复数字#xff0c;所以不需要进行树层上的剪枝#xff1b; …1--全排列46 主要思路1 经典全排列每次枚举每一位时重头开始枚举用一个访问数组记录当前已经被访问过的数字 这道题不包含重复数字所以不需要进行树层上的剪枝 #include iostream
#include vectorclass Solution {
public:std::vectorstd::vectorint permute(std::vectorint nums) {if(nums.size() 0) return res;std::vectorbool vis(nums.size(), false);std::vectorint tmp;dfs(nums, vis, tmp);return res;}void dfs(std::vectorint nums, std::vectorbool vis, std::vectorint 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::vectorstd::vectorint res;
};int main(int argc, char *argv[]){std::vectorint test {1,2,3};Solution S1;std::vectorstd::vectorint 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 algorithmclass Solution {
public:std::vectorstd::vectorint permute(std::vectorint 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::vectorint nums){int n nums.size();// 找到第一个顺序对int i;for(i n - 2; i 0; i--){if(nums[i] nums[i1]) 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[i1] ~ nums.end()std::reverse(nums.begin() i 1, nums.end());return true;}private:std::vectorstd::vectorint res;
};int main(int argc, char *argv[]){std::vectorint test {1,2,3};Solution S1;std::vectorstd::vectorint 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 algorithmclass Solution {
public:void rotate(std::vectorstd::vectorint 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::vectorstd::vectorint 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 主要思路
