看见嘉然柚恩了

分类

/ 注册

全部文章（共100篇）

题解 | #牛群密码 - 有效回文#

知识点字符串，模拟思路此题有两个需要满足的条件字符种类数小于等于K 可以遍历字符串的每一位，并插入set中，set自动去重，若set.size()>k,则说明不符合题意删除某种字符后是回文字符串首先先写一个判断字符串是否是回文的函数，可以用双指针实现。然后，借助第一个条件的set...

2023-07-27

0 260

题解 | #牛群买卖计划III#

知识点动态规划思路我们可以反向考虑，因为买的一个东西到最后一天肯定要卖的，在此之前的所有情况可以归为：买买·····卖·····买买····卖····买买卖，所以只要逆序不断更新最大售价，并且减去成本即可。代码c++ class Solution { public: /** ...

2023-07-25

0 278

题解 | #牛群买卖计划II#

知识点动态规划线性思路这题是上一题的强化版本，不过只需要将3改为k即可。可以用dp[i][j][k]表示最大利润 f[i][j][k]， k取0或1，0表示手中无货，1表示手中有货， public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规...

2023-07-25

1 334

题解 | #完全平方数的草料#

知识点动态规划思路对于一个数n，它一定能由若干个完全平方数组成，对于j来说，它会由j-i*i转移过来。设dp[i]代表组成i的最小平方数个数，由于此题需要输出数量尽量少的平方数组合，那么，我们可以先预处理n的平方组成数，然后逆序从大到小地用平方数来组成n，合法条件为对dp[n-j * j...

2023-07-25

0 329

题解 | #最小三角路径和#

知识点多维路径动态规划思路我们可以考虑反向转移，dp[i][j]代表从最后一行到达第i行第j列的最小代价，dp[0][0]即为所求（注意下标从0开始）。转移方程：由题意，当前位置dp[i][j],只能由dp[i+1][j]和dp[i+1][j+1]转移过来。还要再加上自身的花费: dp[i...

2023-07-25

0 293

题解 | #编号子回文I#

知识点字符串思路暴力，对于每个点s[i]，依次向左右延伸，寻找以该点为中心的奇数长度回文字符串（长度至少为1），以及以该点与其右边点为中心的偶数长度回文字符串（长度至少为0）。每次向左右延伸，字符串长度增加2。每次在到达边界或者不构成回文时，使用现在字符串的长度与已储存的最长长度作比较，若当前...

2023-07-25

0 259

题解 | #递减种子序列#

知识点动态规划，数据结构优化思路此题数据范围较小，可以采用O(NxN)的做法，即每一次遍历到seeds[i]，都往回寻找最大的DP[1~i],其中dp[x]表示以第x位结尾的最大单调递减子序列长度，此方法较为简单。本题中，笔者采用数据结构优化，将时间复杂度降低至O（NlogN）。思路为：将s...

2023-07-25

0 338

题解 | #训练聪明的牛#

知识点动态规划思路用一个集合来存储所有单词，然后在s中枚举i~j位，并进行查找，找得到就把前j位标记为可以匹配，找不到的话肯定匹配不了了，答案为false 最后输出为dp[s.size()] 代码 class Solution { public: /** * 代码中的类名、方...

2023-07-24

0 272

题解 | #不能连续吃草的牛#

知识点一维线性动态规划思路第i天吃与不吃的选择，是由第i-1天和i-2天转移过来的。如果第i天不吃，那么可以从第i-1天的吃或不吃转移过来如果第i天吃，那么只能从第i-1天的不吃转移过来，此外还可以从第i-2天的吃转移过来。不妨用dp[n][2]表示状态，dp[i][k]中，i表示第i天...

2023-07-24

0 260

题解 | #奶牛的活动面积#

知识点二维动态规划思路我们考虑如何用O（nn）的时间复杂度，首先，对于land[i][j]，以它为右下角形成正方形，需要满足3个条件： land[i-1][j-1]也能以右下角形成正方形X， land[i][j]左侧的‘C’的数量（包括自己）需大于等于X的边长 land[i][j]上侧的‘C’...

2023-07-24

1 314