CroMarmot

题解

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

/ 注册

全部文章 / 题解（共138篇）

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

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

C++ 贪心数组

2022-01-29

0 396

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

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

C++ 栈

2022-01-28

1 500

题解 | #通配符匹配#

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

C++ 动态规划字符串

2022-01-28

0 498

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

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

C++ 贪心

2022-01-28

1 370

题解 | #求路径#

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

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

2022-01-28

0 328

题解 | #给表达式添加运算符#

题意给定数字字符串ABCDEFG..., 判断A+B+C+D+E+F+G...,A-B-C-D-E-F-G...,A*B*C*D*E*F*G... 三个值中,是否存在等于target的值的限制: 字符串长度不超过10 方法分别记录字符串和运算结果,分别计算对于加法,减法,和乘法,分别处理每...

C++ 数学

2022-01-08

0 562

题解 | #将二叉搜索树改为累加树#

题意把二叉搜索数改为累加树限制: 节点数不大于10410^4104 方法从大到小找节点并加和因为原树是二叉搜索树,所以节点大小关系为左<根<右现在题目要求把每个节点的值,变为比原树中更大节点之和.因此按照, 右->根->左的顺序遍历按大到小找出节点, 最后进行加和即...

C++ 排序树数学二叉树

2022-01-08

0 441

题解 | #加油站#

题意一个环上，每经过第i个点，增加A[i]再减少B[i], 要求每个结果不小于零限制：环长度不大于10410^4104, 增减值不大于10510^5105 方法枚举起点直接按照题意，枚举所有起点. 对于每次枚举起点，模拟行驶一周，判断是否会出现油量为负的情况。如果找到能让油量始终非负的起...

C++ 数学数组

2022-01-06

0 483

题解 | #Nim游戏#

题意 n个石头，轮流取1-3三个，谁把最后取空谁获胜。问谁能获胜限制：初始个数不超过10910^9109 方法递归（TLE）因为是轮流取1-3个，所以除了取的时候个数不同，其它是公平的如果一个人要取时剩余不到3个，那么全部取走获胜。对于其它情况考虑一个人取的时候剩下n个，那么他取后，他的...

C++ 数学

2022-01-05

10 652

题解 | #重复的DNA序列#

题意给只包含ATGC的字符串，求其中长度恰好为10且出现过大于1次的字符串限制：字符串总长度不大于10510^5105 方法 unordered_map+string 建立两个辅助unordered_map和一个排序数组记录每个长度为10的字符串出现的次数记录每个长度为10的字符串上次出...

C++ 数学数组

2022-01-05

0 464