蓝桥杯学习笔记08-回溯
目录
蓝桥杯学习笔记08-回溯
c++中的queue数据结构
q.empty()判断队列是否为空
q.front()访问队头元素
q.pop()删除队头元素
q.push(1)添加元素
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
if(root == nullptr) return {};
q.push(root);
while(!q.empty()){
vector<int> tem;
int size = q.size();
for(int i=0;i<size;i++){
TreeNode* head = q.front(); //访问队头元素
tem.push_back(head->val);
q.pop(); //删除队头元素
if(head->left!=nullptr) q.push(head->left);
if(head->right != nullptr) q.push(head->right);
}
res.push_back(tem);
}
return res;
}
};回溯篇
匹配相关的题目
vector里面可以嵌pair，然后是用emplace_back插入
vector<pair<int,int>> from,to;
int minimumMoves(vector<vector<int>>& grid) {
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[i].size();j++){
if(grid[i][j]){
for(int k=1;k<grid[j][j]){
from.emplace_back(i,j);
}
}else{
to.emplace_back(i,j);
}
}
}
}next_permutation的使用，不能对二维数组
1. next_permutation 的使用问题
next_permutation函数的作用是生成下一个字典序更大的排列。在你的代码中，students是一个二维数组，next_permutation不能直接对二维数组进行操作。- 如果你想通过排列来尝试所有可能的组合，可以尝试对
mentors的索引进行排列，而不是直接对students进行排列。
class Solution {
public:
int ans = 0;
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
int len = students.size();
//初始化导师的索引数组
vector<int> Index;
for(int i=0;i<len;i++){
Index.push_back(i);
}
do{
int total = 0;
for(int i=0;i<len;i++){
for(int j=0;j<students[i].size();j++){
if((students[i][j] == mentors[Index[i]][j])){
total += 1;
}
}
}
ans = max(ans,total);
}while(next_permutation(Index.begin(),Index.end()));
return ans;
}
};