1. 一最多的行
送分题
class Solution {
public:
vector<int> rowAndMaximumOnes(vector<vector<int>>& mat) {
int m =mat.size(); int n = mat[0].size();
int res = 0;
int index = 0;
for(int i=0;i<m;i++){
int count = 0;
for(int j=0;j<n;j++){
if(mat[i][j]==1) count++;
}
if(count>res){res = count; index = i;}
}
return {index,res};
}
};
2. 找出可除性得分最大的整数
送分题
class Solution {
public:
int maxDivScore(vector<int>& nums, vector<int>& divisors) {
sort(nums.begin(),nums.end());
int res = 0;
int num = divisors[0];
for(int i=0;i<divisors.size();i++){
int score = 0;
for(int j=0;j<nums.size();j++){
if(nums[j]%divisors[i]==0) score++;
}
if(score>res){res=score; num = divisors[i];}
else if(score==res&&divisors[i]<num) num = divisors[i] ;
}
return num;
}
};
3. 构造有效字符串的最少插入数
拆分问题+递归子字符串
class Solution {
public:
int addMinimum(string word) {
if(word.size()==0) return 0;
else if(word.size()==1) return 2;
if(word[0]<word[1]){
if(word.size()==2) return 1;
else if(word[1]<word[2]) return addMinimum(word.substr(3));
else return 1+addMinimum(word.substr(2));
}
else return 2+addMinimum(word.substr(1));
}
};
4. 最小化旅行的价格总和
分析：选择不相邻节点减半价格并最小化价格
涉及到图的选择的问题，考虑使用回溯法，选择为当前节点减半或者不减半，并递归搜索相邻节点
不过该题首先要知道哪些点走了几次，可以根据路径选择事先用回溯法得到每个点的访问次数
然后根据访问次数与价格生成权重，使用权重做后面的减半回溯搜索，找到最小化解
class Solution {
public:
vector<vector<int>> graph;//无向邻接表
vector<int> cnt;//走完指定路径每个点通过的次数
vector<int> weight;//顶点的代价
bool confirm;
int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
graph.resize(n);
for (auto& edge : edges) {//初始化
int from = edge[0];
int to = edge[1];
graph[from].push_back(to);
graph[to].push_back(from);
}
cnt.resize(n);
for (auto& edge : trips) {//用路径初始化经过点的次数
int from = edge[0];
int to = edge[1];
confirm = 0;//当前路径是否找到
dfs(from, to, -1);//根据起点终点对经过的点计数
}
weight.resize(n);
for (int i = 0; i < n; i++)
weight[i] = cnt[i] * price[i];//计算某顶点的代价
int res = reduce(0, 0, -1);//再次深度优先计算最小路径和
return res;
}
void dfs(int start, int end, int from) {//计算经过各顶点的次数
if(start==end){cnt[end]++; confirm = 1; return;}
if (confirm) return;//如果其他路径找到了，就不需要再找了，直接剪枝
cnt[start]++;//选择当前路径，计数起点
int n = graph[start].size();
for (int i = 0; i < n; i++) {
if (graph[start][i] == from) continue;//不从原路返回
dfs(graph[start][i], end, start);//选择下一个节点作为起始节点
}
if (confirm) return;//当前路径找到了，不需要再撤回
cnt[start]--;//撤销选择
}
long reduce(bool before, int cur, int from) {
int n = graph[cur].size();
if (n == 1 && graph[cur][0] == from) {//边界条件，只有一条边，且刚从那边过来
if (before == 0) return weight[cur] / 2;
else return weight[cur];
}
//权重为0无所谓区不区分,全按不减半处理
if(weight[cur]==0) {
int res = 0;
for (int i = 0; i < n; i++) {//当前节点减半
if (graph[cur][i] == from) continue;
res += reduce(0, graph[cur][i], cur);
}
return res;
}
//当前节点减半
int half = INT_MAX;
if (before == 0) {//前一个节点没有减半
half = weight[cur] / 2;
for (int i = 0; i < n; i++) {//当前节点减半
if (graph[cur][i] == from) continue;
half += reduce(1, graph[cur][i], cur);
}
}
//当前节点全值
int total = weight[cur];//当前节点不减半
for (int i = 0; i < n; i++) {
if (graph[cur][i] == from) continue;
total += reduce(0, graph[cur][i], cur);
}
return min(half, total);
}
};