第91场周赛
860. 柠檬水找零
题解：根据描述，有三种类型的钞票，如果是5元的，可以直接收，如果是10元的，那么则需要给对方一张5元的，收到一张10元的，如果是20元的，那么需要给对方一张10元和5元或者3张5元的。思路就出来了，判断有没有足够的5元的
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0;//记录手上的5元和10元面值张数
for (int i : bills) {
if (i == 5) five++;
else if (i == 10)
{
five--;
ten++;
}
else if(i == 20){
if(ten>0&&five>0){ten--;five--;}
else five-=3;
}
if (five < 0) return false;
}
return true;
}863. 二叉树中所有距离为 K 的结点
题解：根据藐视，只需要把二叉树转成无向图，在target点，进行K维广搜即可。
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
vector<vector<int> >graph(501);
vector<int>ret;
genGraph(root,graph);
BFS(graph,ret,target->val,K);
return ret;
}
void genGraph(TreeNode* root,vector<vector<int>>&graph){
//根据二叉树生成图，由于值不重复，且均不大于500，用邻接矩阵构图
if(!root) return;
if(root->left){
graph[root->val].push_back(root->left->val);
graph[root->left->val].push_back(root->val);
genGraph(root->left,graph);
}
if(root->right){
graph[root->val].push_back(root->right->val);
graph[root->right->val].push_back(root->val);
genGraph(root->right,graph);
}
}
void BFS(vector<vector<int>>&graph,vector<int>&ret,int &target,int &K){//广度优先搜索，k表收缩圈数
queue<int>q;
q.push(target);
set<int>s;
s.insert(target);
while(K>0){
int len = q.size();
for(int i=0;i<len;i++){
int tmp = q.front();
s.insert(tmp);
for(auto j:graph[tmp]){
if(s.find(j)==s.end()) q.push(j);
}
q.pop();
}
K--;
}
while(!q.empty()){
ret.push_back(q.front());
q.pop();
}
}861. 翻转矩阵后的得分
题解：根据描述，难点在于什么时候是最多的，若采用枚举的方法，把所有可能性枚举出来，之后统计出最大的情况，这显然是不得行的。那么什么时候是最大呢？
只需要保证第一列全部为1，对于其他的。。。。我不知道怎么解释了，这代码肯定不是我写的。
int matrixScore(vector<vector<int>>& A) {
int ret = 0;
int R = A.size(),C = A[0].size();
for(int i = 0; i <C; i++) {
int col = 0;
//遍历每一行，
for (int j = 0; j <R; j++)
col += A[j][i] ^ A[j][0];
ret+=max(col,R-col)*(1<<(C-i-1));
/*遍历每一行，用每一行的除第一个元素
与行内的其他元素异或，统计出每一列的含1的数目
*/
}
return ret;
}862. 和至少为 K 的最短子数组
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录