文章目录
唠嗑
第一次参加leetcode周赛，心情有点小激动，给我的感觉是，前两题送分，第三题可能暴力枚举，也可能是dp，第四题上难度，代码量迅速上升。这次的周赛，前三题几乎送分，看了答案后，第三题的大佬答案真的又给了我一种不一样的思考方式！！！最后一题暂时不考虑。。看不懂。。。只能说看了这个答案给了我另一种对第三题的枚举思路。
第三题的两种枚举方式
题目
建立关系后，dfs枚举(我的憨批办法
解题思路:
- 建立学生和每个导师的值的大小矩阵，用于方便查值。
- dfs回溯
class Solution {
public:
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
int n= students.size();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
relationT[i][j] = solve(students[i],mentors[j]);
}
}
dfs(students.size(),0,0);
return res;
}
private:
int res = 0;
int relationT[8][8] = {0};
bool mt[8] = {false};
int solve(vector<int>&s,vector<int>&t){
int cnt = 0;
for(int i=0;i<s.size();i++){
if(s[i]==t[i])
cnt++;
}
return cnt;
}
void dfs(int n,int k,int sum){
if(k==n)
{
res = max(sum,res);
return;
}
for(int j=0;j<n;j++){
if(!mt[j]){
mt[j] = true;
dfs(n,k+1,sum+relationT[k][j]);
mt[j] = false;
}
}
}
};
枚举导师的排列组合(大佬的姿势
class Solution {
public:
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
vector<int> vec;
int m = students.size();
int n = students[0].size();
for(int i = 0; i < m; ++i){
vec.push_back(i);
}
int ans = 0;
do{
int cur = 0;
//记录每次导师选择情况下的值的情况，答案为其中的最大值
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
if(students[i][j] == mentors[vec[i]][j]){
++cur;
}
}
}
ans = max(ans, cur);
}while(next_permutation(vec.begin(), vec.end()));
return ans;
}
};