第91场周赛

用户1145562

发布于 2020-10-23 04:11:33

24000

代码可运行

文章被收录于专栏：LC刷题LC刷题

运行总次数：0

代码可运行

传送门

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;
    }