CroMarmot

分类

未归档(12) 题解(138) 题解总结(4)

/ 注册

全部文章（共154篇）

题解 | #最长上升子序列(三)#

最长上升子序列(三)（动态规划）题意给定一个正整数数组，求它的最长上升子序列，如果有多个，求数值字典序最小的思路分析上升子序列先不考虑最长，先考虑如何找到一个上升子序列每次对于一个值，去找它前面比它小的值就能构成最后把链输出就能得到上升子序列 for(int i = 0;i<ar...

C++ 动态规划

2022-01-31

1 428

题解 | #兑换零钱(一)#

兑换零钱（一）（动态规划）题意给定一个正整数数组，和一个目标值，问最少选取多少个数组中的值能使得其和等于目标值。其中每个值可以被选任意次思路分析最优关系的数学推导假设对于值aim有一个最优方案，这个最优方案中有选一次x,那么上述最优方案中去掉x的剩余的数，是aim-x的一个最优方案。 ...

C++ 动态规划

2022-01-30

0 361

题解 | #最长回文子串#

最长回文子串（遍历）题意给定字符串中最长回文子串有多长思路分析判断回文串对于是不是回文串，可以通过从字符串的两边开始比较对称位置 for(int i = 0;i < s.length();i++){ if(s[i] != s[s.length()-1-i])return fa...

C++ 数组遍历

2022-01-30

0 370

题解 | #子数组最大乘积#

子数组最大乘积（贪心）题意一个有正负和零的double数组中，最大的子数组乘积为多少思路分析快速运算乘积如果数组中没有零计算数组一段的乘积，相当于计算从数组起始到结束的乘积，除以起始到数组开始之前的积 f(i,j) = premul[j] / premul[i-1] 局部最优对于选...

C++ 贪心

2022-01-29

0 464

动态规划用法总结（一）

动态规划用法总结（一）动态规划是一个相对高级的工具，有些本身是动态规划的题可以用动态规划以外，当你无法一眼看穿最优解法时，你可以考虑直接使用动态规划。动态规划最常见的解法思路步骤是设计状态设计转移方程对转移方程时间空间优化大多数可以改写为递推边界处理实现优点是，基于状态和状态转...

动态规划题解

2022-01-29

0 555

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

连续子数组的最大和（贪心）题意给一个数字数组，求子数组和的最大值思路分析对于长度大于1的任意答案，考虑能否从这个答案眼花出更优的答案如果答案选择数组两端有负数那么把负数去掉，会得到更大的答案，所以两端一定都不是负数如果答案两端外还有正数那么包含这些正数，会得到更大的答案，所以答案...

C++ 贪心数组

2022-01-29

0 396

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

最长的括号子串（栈）题意给一个只包含左右括号的字符串，求其中正确匹配子串的最大长度。思路分析正确的括号匹配如果题目给的括号序列是正确的,如(())，或者检查是否是正确的那么匹配过程是遇到左括号，把左括号压入栈中遇到右括号，把左括号顶部的移出栈中注意到栈中只会存左括号，于是可以简...

C++ 栈

2022-01-28

1 500

题解 | #通配符匹配#

通配符匹配（动态规划）题意给一个字符串，和一个通配符表达式，问该字符串是否满足通配符表达式。其中，通配符表达式除了字符外，只支持两种通配符 ?匹配一个任意字符 *匹配任意个任意字符思路分析字符串相等比较如果直接比较两个字符串相等，是按位比较 for(int i = 0;i < le...

C++ 动态规划字符串

2022-01-28

0 499

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

买卖股票的最好时机(一)（贪心）题意给一个股票的价格变化值数组，问进行一次购买后再进行一次卖出，问能获取的最大差值是多少思路分析以题目样例数据[8,9,2,5,4,7,1]为例什么时候卖假设到达某一天时，我已经持有了股票，那么什么时候卖呢？如图所示，不论我当前持有的股票的买入价格是多...

C++ 贪心

2022-01-28

1 370

题解 | #求路径#

求路径（动态规划）题意一个m⋅nm\cdot nm⋅n的地图,从左上角，只能向右或向下，走到右下角，有多少种方案。思路分析什么叫不同的方案呢? 如果把走动的方向，变成序列，两个序列不同，则是不同的方案。如图中红色的走动变成序列是(向右,向右,向右,向右,向下,向下,向下) 蓝色的走动序...

C++ 动态规划数学组合数

2022-01-28

0 328