摸鱼学大师

分类

未归档(8) 题解(541)

/ 注册

TA的专栏 547篇文章 2人订阅

孤帆远影碧空尽

547篇文章 10912人学习

全部文章（共550篇）

题解 | #打家劫舍(一)# 来自专栏

题目主要信息: 给定一个数组，其中代表每家拥有的钱数小偷每次不能偷取数组中相邻位置的钱，只要不相邻的钱都可以偷求最多能偷到钱数具体思路: 或许有人认为利用贪心思想，偷取最多人家的钱就可以了，要么偶数家要么奇数家全部的钱，但是有时候会为了偷取更多的钱，或许可能会连续放弃两家不偷，因此这种方案...

C++ 动态规划

2022-02-19

3 648

题解 | #最小花费爬楼梯# 来自专栏

题目主要信息: 给定一个数组，其中每个元素代表该级楼梯向上爬需要支付的费用，下标从0开始一旦支付费用，可以任意选择爬一级或是二级需要求爬到顶楼，即越过数组末尾元素所需要的最小花费可以从下标为0或是1的台阶开始具体思路: 可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就...

C++ 动态规划

2022-02-19

4 1057

题解 | #正则表达式匹配# 来自专栏

题目主要信息: 一个正常字符串str，可能为空，只包含小写字母一个模式串pattern，可能为空，只包含小写字母和‘*’与‘.’ 模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）求str与pattern是否能完全匹配具体思路: 如果是只...

C++ 动态规划

2022-02-19

1 346

题解 | #最长上升子序列(一)# 来自专栏

题目主要信息: 给定一个数组，求其中最长的严格上升子序列的长度子序列是指数组去掉或不去掉元素后的数组，不要求在原本数组中全部相邻，但是在原数组中的相对位置不能改变严格上升指子序列严格单调递增具体思路: 要找到最长的递增子序列长度，常用方法是动态规划，用dp[i]dp[i]dp[i]表示到元...

C++ 动态规划

2022-02-18

0 393

题解 | #求路径# 来自专栏

题目的主要信息：给定一个m*n的矩阵，要求从矩阵的左上角走到右下角的不同路径数量每次只能往下或者往右走这道题非常典型，我们可以考虑多种方式。方法一：递归具体做法：首先我们在左上角第一个格子的时候，有两种行走方式：如果向右走，相当于后面在一个(n−1)∗m(n-1)*m(n−1)∗m...

C++ 递归动态规划

2022-02-18

0 538

题解 | #编辑距离(一)# 来自专栏

题目主要信息: 给定两个长度可能不同的字符串，可以对第一个字符串增删改字符求增删改的最少次数，让第一个字符串变成第二个字符串字符串中只出现大小写字母具体思路: 把第一个字符串变成第二个字符串，我们需要逐个将第一个字符串的子串最少操作下变成第二个字符串，这就涉及了第一个字符串增加长度，状态转...

C++ 动态规划

2022-02-18

3 650

题解 | #盛水最多的容器# 来自专栏

题目主要信息: 输入一个数组，其中每个元素代表水桶边界高度水桶容积为边界较短的一边高度乘上两边界的距离（数组下标表示距离）求在数组中选取两个边，求最大容积具体思路: 这道题类似接雨水问题，还是利用了水桶的短板原理，较短的一边控制最大水量，因此直接用较短边长乘底部两边距离就可以得到当前情况下...

C++ 双指针贪心

2022-02-18

0 542

题解 | #接雨水问题# 来自专栏

题目主要信息: 给定一个整型数组，数组每个元素表示下图所示的每列灰色柱子高度，数值都是非负数在雨水（图中蓝色部分）不超过边界的情况下，问最多能有多少蓝色的格子数组以外的区域高度视为0 具体思路: 我们都知道水桶的短板问题，控制水桶水量的是最短的一条板子。这道题也是类似，我们可以将整个图看成...

C++ 双指针

2022-02-18

0 436

题解 | #矩阵最长递增路径# 来自专栏

题目主要信息: 给定一个矩阵，矩阵中所有元素都是非负整数需要在矩阵中找到一条最长路径，路径中的元素都是递增的，求其最长长度查找路径时，只能向上下左右四个方向查找，不能超出边界，且每个格子最多走一次具体思路: 既然是查找最长的递增路径长度，那我们首先要找到这个路径的起点，起点不好直接找到，就...

C++ 递归

2022-02-17

0 565

题解 | #字符串的排列# 来自专栏

题目主要信息: 给定一个长度为n的字符串，求其中所有字符的全排列字符串中可能有重复字符，打印顺序任意字符串中只包含大小写字母具体思路: 都是求元素的全排列，字符串与数组没有区别，一个是数字全排列，一个是字符全排列，因此大致思路与有重复数字的全排列类似，只是这道题输出顺序没有要求。但是为了便...

C++ 递归

2022-02-17

0 417