七牛云笔试

感觉已经没什么机会了 但还是做一下吧

• 记录行数和列数，分别置0

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0
     * @param matrix int整型vector<vector<>> m行n列矩阵
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > setZeroes(vector<vector<int> >& matrix) {
        vector<int> row,col;
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[i].size();j++){
                if(matrix[i][j]==0){
                    row.push_back(i);
                    col.push_back(j);
                }
            }
        }
        for(auto v:row){
            for(int j=0;j<matrix[v].size();j++){
                matrix[v][j]=0;
            }
        }
        for(auto v:col){
            for(int i=0;i<matrix.size();i++){
                matrix[i][v]=0;
            }
        }

        return matrix;
    }
};

• 不太清楚数据范围,不过应该不大 就直接暴力了，枚举每个点，check每个点bfs能否都走到m和n

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 输入一个二叉树，和两个int值，返回最底层公共父节对应的值。
     * @param root TreeNode类 二叉树的根节点
     * @param m int整型 第一个值
     * @param n int整型 第二个值
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int m, int n) {
        return dfs(root,m,n);
    }
    bool check(TreeNode* root,int m,int n){
        if(!root) return false;
        queue<TreeNode*> q;
        q.push(root);
        int cnt=0;
        while(q.size()){
            TreeNode* u=q.front();
            q.pop();
            if(u->val==m||u->val==n) cnt++;
            if(u->left) q.push(u->left);
            if(u->right) q.push(u->right);
        }
        return cnt==2;
    }
    int dfs(TreeNode* root,int m,int n){
        if(check(root->left,m,n)) return dfs(root->left,m,n);
        if(check(root->right,m,n))   return dfs(root->right,m,n);
        return root->val;
    }

};

• 正解应该是dp，没给数据范围试了一发暴力居然过了......

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weights int整型vector 酒的重量
     * @return int整型
     */
    bool check(int x,int sz){
        vector<int> res;
        for(int j=0;j<sz;j++){
            res.push_back(x>>j&1);
        }
        res.push_back(x&1);//第0位
        for(int i=1;i<res.size();i++){
            if(res[i]==1&&res[i]==res[i-1]) return false;
        }
        return true;
    }
    int maxWine(vector<int>& weights) {
        int ans=0;
        for(int i=0;i<(1<<weights.size());i++){
            if(!check(i,weights.size())) continue;
             int res=0;
            for(int j=0;j<weights.size();j++){
                if(i>>j&1){
                    res+=weights[j];
                }
            }
            ans=max(ans,res);
        }
            return ans;
    }

};