LeetCode每日一题


LeetCode每日一题

1.994. 腐烂的橘子

method1:BFS+Set,腐烂入队列,健康入集合。取出队头元素,进行上下左右四个方向查找是否有健康的果子,如果有,集合删除掉健康果子,并将其入队列,依次类推。最后看集合中是否有果子,如果有果子,表示没有结果,否则有结果,返回层(或者说分钟数)。

class Solution {
private:
    int direct[4][2] = {
        {0,1},
        {0,-1},
        {1,0},
        {-1,0}
    };
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int res = 0;
        int m = grid.size();
        int n = grid[0].size();

        queue<pair<int,int>> rot;
        multiset<pair<int,int>> good;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 2) rot.push(make_pair(i,j));
                if(grid[i][j] == 1) good.insert(make_pair(i,j));
            }
        }
        while(!rot.empty()){
            int size = rot.size();
            int flag = 0; 
            // 遍历每一层
            for(int i = 0; i < size; i++){
                auto [x,y] = rot.front(); rot.pop();
                for(int i=0;i<4;i++){
                    auto tmp = make_pair(x+direct[i][0],y+direct[i][1]);
                    if(good.find(tmp) != good.end()){ //找到有与腐烂橘子相邻的好橘子
                        good.erase(tmp);    //好橘子被传染,从好橘子集合移除
                        rot.push(tmp);      //加入坏橘子队列
                        flag = 1;
                    }
                }
            }
            if(flag) res+=1;
        }
        if(good.size() > 0) return -1;
        return res;
    }
};

method2:BFS 可以看成是层序遍历。从某个结点出发,BFS 首先遍历到距离为 1 的结点,然后是距离为 2、3、4…… 的结点。因此,BFS 可以用来求最短路径问题。BFS 先搜索到的结点,一定是距离最近的结点。

再看看这道题的题目要求:返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。翻译一下,实际上就是求腐烂橘子到所有新鲜橘子的最短路径。那么这道题使用 BFS,应该是毫无疑问的了。

是用 BFS 来求最短路径的话,这个队列中第 1 层和第 2 层的结点会紧挨在一起,无法区分。因此,我们需要稍微修改一下代码,在每一层遍历开始前,记录队列中的结点数量 n ,然后一口气处理完这一层的 n 个结点。

class Solution {
private:
    int direct[4][2] = {
        {0,1},
        {0,-1},
        {1,0},
        {-1,0}
    };
    int m,n;
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int res = 0;
        m = grid.size();
        n = grid[0].size();

        queue<pair<int,int>> q;
        int count = 0;   // 新鲜橘子的数量
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(grid[i][j]==1) {
                    count++;
                } else if(grid[i][j] == 2) {
                    q.push(make_pair(i,j));
                }
            }
        }
        int t=0;
        while(count>0 && !q.empty()) {
            t++;
            int n = q.size();
            // 遍历每一层
            for(int i=0;i<n;i++) {
                auto [x,y] = q.front();
                q.pop();
                for(int j=0;j<4;j++){
                    int newX = x+direct[j][0];
                    int newY = y+direct[j][1];
                    if(inArea(newX,newY)) {
                        if(grid[newX][newY] == 1) {
                            grid[newX][newY] = 2;
                            count--;
                            q.push(make_pair(newX,newY));
                        }
                    }
                }
            }
        }
        if(count>0) return -1;
        return t;
    }
    bool inArea(int x,int y) {
        return x>=0 && x<m && y>=0 && y<n; 
    }
};

2.面试题59 - II. 队列的最大值

在queue出队中,我们需要尽可能快的获得最大值,是对本题的优化点,所以需要一个deque来空间换时间!
设计原则:若deque中的队尾元素小于当前元素,则deque出队即可,这样每次deque维护的是pop_front这一阶段的最大值。

class MaxQueue {
private:
    // deque 保存下一个最大值
    // queue 保存正常数据流
    queue<int> q;
    deque<int> dq;
public:
    MaxQueue() {

    }

    int max_value() {
        return !dq.empty() ? dq.front() : -1;
    }

    void push_back(int value) {
        q.push(value);
        while(!dq.empty() && dq.back()<value) {
            dq.pop_back();
        }
        dq.push_back(value);
    }

    int pop_front() {
        if(q.empty()) return -1;
        if(q.front() == dq.front()) {
            dq.pop_front();
        }
        int res = q.front();
        q.pop();
        return res;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

3.322. 零钱兑换

method1:递归法

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        return recursion(coins,amount);
    }

    int recursion(vector<int>& coins,int n) {
        if(n==0) return 0; 
        if(n<0) return -1;
        int res = INT_MAX;
        // 每个硬币个数不限
        for (auto coin : coins) {
            int sp = recursion(coins,n-coin);
            // 当前硬币不满足,遍历下一个
            if (sp==-1) continue;
            /// 加上当前硬币个数
            res = min(res,1 + sp);
        }
        return res!=INT_MAX ? res : -1;
    }
};

method2:记忆化搜索

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,0);
        return recursion(coins,amount,dp);
    }

    int recursion(vector<int>& coins,int n,vector<int> &dp) {
        if(n==0) return 0; 
        if(n<0) return -1;
        if(dp[n]!=0) return dp[n];
        int res = INT_MAX;
        // 每个硬币个数不限
        for (auto coin : coins) {
            int sp = recursion(coins,n-coin,dp);
            // 当前硬币不满足,遍历下一个
            if (sp==-1) continue;
            /// 加上当前硬币个数
            res = min(res,1 + sp);
        }
        dp[n] = res!=INT_MAX ? res: -1;
        return dp[n];
    }
};

method3:dp动态规划

每次都有选与不选两种决策。
以dp[i]记录 钱为i时,所需的最少硬币个数

选择 此时就是 (i-当前硬币价值)所需要的最少硬币个数(dp[i-coin])加上当前选择的这个硬币个数(1) 也就是dp[i-coin] + 1
不选择 不选择当前硬币,此时还是剩i,所以此时的价值就是dp[i]。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,amount+1);
        // 没有钱凑不出来了
        dp[0] = 0;
        // 有钱就开始凑
        for(int i=1;i<dp.size();i++) {
            // i表示还有多少钱
            // 拿出硬币
            for(auto coin : coins) {
                if(i-coin<0) continue;
                // 每次都有选与不选,不选此时钱还是i,否则此时钱就变为i-coin
                // dp[i]表示剩余钱为i的时候所需的最少硬币个数
                dp[i] = min(dp[i],1 + dp[i-coin]);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }

};

4.543. 二叉树的直径

直接递归,每次返回左右子树高度最大值,并在返回之前更新路径最大值,不然就出问题咯。例如:直接递归思路

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        return leftDepth+rightDepth;
    }
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return 1 + max(maxDepth(root->left),maxDepth(root->right));
    }
};

上述没有考虑[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2],不一定过根节点。。。所以不能按照上述来,而是递归放在子树中去比较大小。

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        int res=0;
        helper(root,res);
        return res; 
    }
    int helper(TreeNode* root,int& res) {
        if(!root) return 0;
        int lRes = root->left ? helper(root->left,res) + 1 : 0;
        int rRes = root->right ? helper(root->right,res) + 1: 0;
        res =  max(res,lRes+rRes);
        return max(lRes,rRes);
    }
};

5.1013. 将数组分成和相等的三个部分

直接累加。

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& A) {
        int sum = accumulate(A.begin(),A.end(),0);
        if(sum%3!=0) return false;
        int count =0,subSum = 0;
        for(int i=0;i<A.size();i++) {
            subSum+=A[i];
            if(subSum==sum/3) {
                count++;
                subSum=0;
            }
        }
        // / count不一定等于3,例如[1,-1,1,-1,1,-1,1,-1]
        return count>=3;
    }
};

6.300. 最长上升子序列

method1:dp[i] 表示以 nums[i] 结尾的「上升子序列」的长度。注意:这个定义中 nums[i] 必须被选取,且必须是这个子序列的最后一个元素

在下标 i 之前严格小于 nums[i] 的所有状态值中的最大者 + 1。

动态规划:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // dp[i] = max(dp[i-1]+1,dp[i-1])
        int len = nums.size();

        if(len < 2) return len;

        vector<int> dp(len,1);

        for(int i=1;i<len;i++) {
            for(int j=0;j<i;j++) {
                if(nums[j]<nums[i]) {
                    // 自身,前面最大加上自身
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }

        int res=0;
        for(auto elem : dp) {
            res = max(res,elem);
        }
        return res;
    }
};

method2:二分查找法,如果已经得到的上升子序列的结尾的数越小,遍历的时候后面接上一个数,就会有更大的可能性构成一个更长的上升子序列;既然结尾越小越好,我们可以记录在长度固定的情况下,结尾最小的那个元素的数值,这样定义也是为了方便得到「状态转移方程」。tail[i] 表示长度为 i 的所有上升子序列的结尾的最小值。

以输入序列[10,9,2,5,3,4] 为例:

第一步插入 10,tails[0]=[10];

第二步插入 9,tails[0]=[9];

第三步插入 2,tails[0]=[2];

第四步插入 5,tails[1]=[5];

第五步插入 3,tails[1]=[3];

第二步插入 4,tails[2]=[4];

最终得到最大递增子序列长度为 2+1=3。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = 0, n = (int)nums.size();
        if (n == 0) return 0;
        vector<int> tails(n, 0);
        tails[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > tails[len]) tails[++len] = nums[i];
            else{
                int l = 0, r = len, pos = 0;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (tails[mid] < nums[i]) {
                        pos = mid + 1;
                        l = mid + 1;
                    }
                    else r = mid - 1;
                }
                tails[pos] = nums[i];
            }
        }
        return len + 1;
    }
};

更多内容,订阅公众号

文章作者: light-city
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 light-city !
评论
  目录