心空之上

分类

/ 注册

全部文章（共68篇）

题解 | #没有重复项数字的全排列#

递归和回溯递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是...

2023-04-20

0 275

题解 | #买卖股票的最好时机(三)#

多个整体状态的DP数组应该保存什么？此题跟打家劫舍（二）的环形房屋都有多状态，环形房屋有两种情况的状态，一个是只选第一个房子不选最后一个房子，一个是只选最后一个房子不选最后一个房子，最后比较这两种状态的DP数组的最大值。由于本题最多只能进行两次股票买卖，因此需要分多个整体状态来分析最大收益值，因此需...

2023-04-19

0 245

题解 | #买卖股票的最好时机(一)#

DP数组应该保存什么？题目要求的是根据价格数组买卖股票的最大收益，但是DP数组不能简单的设置成在第i天卖出股票能获得的最大收益（这样类似于贪心的做法，无法依赖于前面的状态）。DP数组应该设置为当天持股dp[i][1]或不持股dp[i][0]所能获得的最大收益，这样当天持股或不持股的收益依赖于前一天持...

2023-04-19

0 246

题解 | #打家劫舍(二)#

如何思考环形问题？对于每一家，可以选择偷或者不偷，然后比较这两个情况的最大值得出可以盗取的最大金额：max(dp[i-1], nums[i] + (i-2 >= 0 ? dp[i-2] : 0))由于环形问题，第一家和最后一家不能同时取到，因此要分两种情况设置两种情况的dp数组：只偷第一家不偷...

2023-04-19

0 250

题解 | #最长的括号子串#

方法一：栈括号匹配问题可以用栈的先进后出特性解决，传统括号匹配中栈中存放的是左括号，而现在要求的是最长的括号子串，那么栈中应该存放左括号的下标，用当前右括号下标减去左括号下标可得到匹配的括号子串的长度。当前右括号下标应该减去的是弹出当前栈顶左括号下标后剩下的栈顶左括号下标，因为弹出当前左括号下标表示...

2023-04-19

0 330

题解 | #正则表达式匹配#

DP数组应该保存什么?两个字符串应该考虑使用二维DP数组，题目所求的是字符串str是否匹配模式串pattern，则dp[i][j]应该保存字符串从开头到第i个字符的子串匹配模式串从开头到第j个字符的子串的情况，如果不匹配保存false，匹配则保存true。（保存布尔值的DP数组在进行状态转移时可能要...

2023-04-14

0 0

题解 | #编辑距离(一)#

DP数组应该保存什么？两个字符串的问题可以考虑用二维DP数组，由于题目要求str1转换为str2所需要的最小操作数，因此dp[i][j]应该设置为str1中从开头到第i个字符的子串转换为str2中从开头到第j个字符的子串所需要的最小操作数。最小子问题当str1为空串时，即i等于0时，str2每增加一...

2023-04-12

0 244

题解 | #数字字符串转化成IP地址#

暴力枚举法将字符串的分割视为"."的插入，由于要分割出四个数字，所以要插入三个"."。分割的数字最多只有三个，所以第一个"."只能在前三个字符后面插入，后面的两个"."都在前一个"."的后三个字符后面插入。分割的数字范围在[0, 255]范围内，每次分割完要判断分割后的每个数字是否符合范围，如果都符...

2023-03-30

0 404

题解 | #最长回文子串#

中心扩散法当字符串只有一个字符时，这个字符串必然为回文串。中心扩散法将字符串中的每个字符作为中心，看这个字符串左右两边的字符是否相等，如果相等说明这两个字符和该字符组成的子串也是回文串，则更新这个字符所能组成的回文子串的最大长度，并继续向左右外扩一个字符，直到这两个字符不相等为止。但是中心扩...

2023-03-29

1 540

题解 | #连续子数组的最大和#

易错分析DP数组定义的是以当前位置arr[i]结尾时的所有连续子数组的最大和，因为是连续数字的数组，所以增加arr[i]后这个arr[i]必须保证在连续子数组中，所以更新的dp[i]应该要包含arr[i]才能保证arr[i]和前面的数字连续，如果更新中包含了dp[i-1]，当前位置i结尾的所有连续子...

2023-03-28

0 310