wy的leetcode刷题记录_Day74

2024-01-10 11:34:04

wy的leetcode刷题记录_Day74

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间:2024-01-10

前言

2696. 删除子串后的字符串最小长度

今天的每日一题是:2696. 删除子串后的字符串最小长度

题目介绍

给你一个仅由 大写 英文字符组成的字符串 s 。

你可以对此字符串执行一些操作,在每一步操作中,你可以从 s 中删除 任一个 “AB” 或 “CD” 子字符串。

通过执行操作,删除所有 “AB” 和 “CD” 子串,返回可获得的最终字符串的 最小 可能长度。

注意,删除子串后,重新连接出的字符串可能会产生新的 “AB” 或 “CD” 子串。

示例 1:
输入:s = “ABFCACDB”
输出:2
解释:你可以执行下述操作:

  • 从 “ABFCACDB” 中删除子串 “AB”,得到 s = “FCACDB” 。
  • 从 “FCACDB” 中删除子串 “CD”,得到 s = “FCAB” 。
  • 从 “FCAB” 中删除子串 “AB”,得到 s = “FC” 。 最终字符串的长度为 2 。 可以证明 2 是可获得的最小长度。

示例 2:
输入:s = “ACBBD”
输出:5
解释:无法执行操作,字符串长度不变。

思路

难得一道简单题:我的想法就是用栈去模拟一遍,很类似后缀表达式的符号栈,只要符合规则就出栈否则就入栈,最后栈中剩余元素个数就是不符合规则的个数。

代码

class Solution {
public:
    int minLength(string s) {
        int n=s.size();
        stack<char> stk;
        for(int i=0;i<n;i++)
        {
            if(stk.empty())
            {
                stk.push(s[i]);         
            }
            else if((s[i]=='B'&&stk.top()=='A')||s[i]=='D'&&stk.top()=='C')
            {
                stk.pop();
            }
            else
                stk.push(s[i]);
        }
        return stk.size();
    }
};

收获

熟练了栈的应用

64. 最小路径和

64. 最小路径和

题目介绍

给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例 1:图片来自leetcode

输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。

示例 2:
输入:grid = [[1,2,3],[4,5,6]]
输出:12

思路

与上一篇文章中的不同路径十分类似,都是二维动态规划,同样的只能向下或者向右遍历因此递推公式没有变, 不过需要计算最小的路径代价,于是我使用一个二维数组来代表path[i][j]来表示到(i,j)所需要的代价,最后返回path[m-1][n-1]

代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>> path(m,vector<int>(n));
        path[0][0]=grid[0][0];
        for(int i=1;i<n;i++)
        {
            path[0][i]+=path[0][i-1]+grid[0][i];
        }
        for(int i=1;i<m;i++)
        {
            path[i][0]+=path[i-1][0]+grid[i][0];
        }

        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                path[i][j]=min(path[i-1][j],path[i][j-1])+grid[i][j];
            }
        }
        return path[m-1][n-1];
    }
};

收获

巩固动态规划

63. 不同路径 II

63. 不同路径 II

题目介绍

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1:
在这里插入图片描述
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径:

  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右

示例 2:
在这里插入图片描述
输入:obstacleGrid = [[0,1],[0,0]]
输出:1

思路

与不同路径I相同的递归方法,不过多了一个条件就是障碍物,当路径上出现障碍物的时候那么表示这条路径不可通立马将path[i][j]置为0即可。

收获

巩固了动态规划

文章来源:https://blog.csdn.net/m0_54015435/article/details/135497001
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。