专栏首页LC刷题第91场周赛

第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 的最短子数组

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 第93场周赛

    题解:根据描述,只需要找到两个1之间的距离即可。但又问题的是,如果某数的二进制表达只有一个1,不存在满足题目要求,这是,需要设计一个标记

    用户1145562
  • 第94场周赛

    题解:根据描述,只需要深度遍历两颗树,把叶子节点都存到两个向量中,判定两个向量是不是一模一样。

    用户1145562
  • 第88场周赛

    第二反应:根据上述这个模拟超时过程,想一优化,shifts数组后面开始,逐个偏移,根据描述,后面的偏移会加到前面。于是有了后缀和这一说法。

    用户1145562
  • 【leetcode】Binary Tree Maximum Path Sum

    Given a binary tree, find the maximum path sum.

    阳光岛主
  • LeetCode 938 Range Sum of BST

    给予一颗二叉搜索树, 返回区间 L - R 之间的所有值的总和. 二叉搜索树中没有重复值.

    一份执着✘
  • MySQL 连接

    给予一颗二叉搜索树, 返回区间 L - R 之间的所有值的总和. 二叉搜索树中没有重复值.

    一份执着✘
  • MySQL之mysqladmin客户端

    在我们日常操作中,drop操作应该谨慎一些,可以看到,mysql也友好的给出了提醒。

    AsiaYe
  • c++ LeetCode (网易面试题和链表以及树篇) 五道算法例题代码详解(三)

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

    徐飞机
  • 贪心算法-LeetCode 134、111(递归算法,异或性质,贪心)

    对于swap函数使用中间变量的形式大家都不陌生了,但是对于面试官来说这种方法不出奇,并不是面试官想要的!有没有不使用中间变量的呢? 在swap2函数中,我们可以...

    算法工程师之路
  • LeetCode 450: 删除二叉搜索树中的节点 Delete Node in a BST

    给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节...

    爱写bug

扫码关注云+社区

领取腾讯云代金券