最长的括号子串（栈） 题意 给一个只包含左右括号的字符串，求其中正确匹配子串的最大长度。 思路分析 正确的括号匹配 如果题目给的括号序列是正确的,如(())，或者检查是否是正确的 那么匹配过程是 遇到左括号，把左括号压入栈中 遇到右括号，把左括号顶部的移出栈中 注意到栈中只会存左括号，于是可以简化为记录数量即可 int cnt = 0; for(auto ch:s){ if(ch == '(')cnt++; // 计数+1 else if(ch == ')'){ if(cnt == 0)return false; // 匹配失败 cnt --...

通配符匹配（动态规划） 题意 给一个字符串，和一个通配符表达式，问该字符串是否满足通配符表达式。 其中，通配符表达式除了字符外，只支持两种通配符 ?匹配一个任意字符 *匹配任意个任意字符 思路分析 字符串相等比较 如果直接比较两个字符串相等，是按位比较 for(int i = 0;i < len;i++){ if(s[i] != t[i])return false; } return true; 相邻字符关联关系 注意到 当发生字符串不匹配时，直接返回false 所以 要尝试匹配一个位置的字符串匹配的前提是，之前所有位置的已经完成匹配，也就是上一个位置是匹配成功的 用valid数组来...

买卖股票的最好时机(一)（贪心） 题意 给一个股票的价格变化值数组，问进行一次购买后再进行一次卖出，问能获取的最大差值是多少 思路分析 以题目样例数据[8,9,2,5,4,7,1]为例 什么时候卖 假设到达某一天时，我已经持有了股票，那么什么时候卖呢？ 如图所示，不论我当前持有的股票的买入价格是多少，从今往后，越高的价格对我卖出来说能获得的差值会越大。 什么时候买 虽然实际操作上先买后卖，但从数学上，可以逆着时间考虑。 假设到达某一天时，我卖出了股票，那么这张股票什么时候买能获得最大差值呢？ 如图所示，不论我当前卖价是多少，在卖出之前，越低的买价对我卖出来说能获得的差值会越大。 也就是 当前...

求路径（动态规划） 题意 一个m⋅nm\cdot nm⋅n的地图,从左上角，只能向右或向下，走到右下角，有多少种方案。 思路分析 什么叫不同的方案呢? 如果把走动的方向，变成序列，两个序列不同，则是不同的方案。 如图中 红色的走动变成序列是(向右,向右,向右,向右,向下,向下,向下) 蓝色的走动序列是(向下,向下,向下,向右,向右,向右,向右) 相邻格子的方案关系 对于从左上角走到某一个格子，那么到这个格子的上一步，一定是来自上方或者来自左方，如果来自上方，则是通过向下走到这个格子，如果是来自左方则是通过向右走到这个格子。 根据上面的序列不同则方案不同结论，这必定是不同的方案. 所以走到一...

题意 给定数字字符串ABCDEFG..., 判断A+B+C+D+E+F+G...,A-B-C-D-E-F-G...,A*B*C*D*E*F*G... 三个值中,是否存在等于target的值的 限制: 字符串长度不超过10 方法 分别记录字符串和运算结果,分别计算 对于加法,减法,和乘法,分别处理 每次处理,用一个变量记录字符串,一个变量记录结果值. 最后比较结果值和目标值是否一致,如果一致则满足题意. 以题目样例数据"123",6为例 方法 下标 字符串 结果 加法 0 1 1 - 1 1+2 3 - 2 1+2+3 6(满足) 减法 0 1 1 - 1 1-2 ...

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

题意 一个环上，每经过第i个点，增加A[i]再减少B[i], 要求每个结果不小于零 限制： 环长度不大于10410^4104, 增减值不大于10510^5105 方法 枚举起点 直接按照题意，枚举所有起点. 对于每次枚举起点，模拟行驶一周，判断是否会出现油量为负的情况。 如果找到能让油量始终非负的起点，输出即可。 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param gas int整型vector * @param co...

题意 n个石头，轮流取1-3三个，谁把最后取空谁获胜。问谁能获胜 限制： 初始个数不超过10910^9109 方法 递归（TLE） 因为是轮流取1-3个，所以除了取的时候个数不同，其它是公平的 如果一个人要取时剩余不到3个，那么全部取走获胜。 对于其它情况考虑一个人取的时候剩下n个，那么他取后，他的对手可以是n-1,n-2,n-3个三种情况 如果其中每种情况，他的对手都必胜，那么他就必败。 否则选择他对手必败的情况即可。 所以有递归关系 f(n)=!(f(n−1)&f(n−2)&f(n−3)) f(n) = !(f(n-1) \& f(n-2) \& f(n-3...

题意 给只包含ATGC的字符串，求其中长度恰好为10且出现过大于1次的字符串 限制： 字符串总长度不大于10510^5105 方法 unordered_map+string 建立两个辅助unordered_map和一个排序数组 记录每个长度为10的字符串出现的次数 记录每个长度为10的字符串上次出现的位置 记录所有大于一次出现的pair<首次出现位置，字符串> 这样利用stl的性质，可以知道是否出现次数大于1次 最后对数组进行排序输出即可。 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接...

题意 给点之间的依赖关系，求拓扑排序 限制： 点的个数不大于2000 方法 循环遍历(TLE) 每次枚举点，找入度为零的，找到则标记。 如此循环直到找不到或者完全输出. 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param prerequisites int整型vector<vector<>> * @param n int整型 * @return int整型vector */...

题意 求逆波兰表达式的值 限制： 表达式长度不大于10410^4104 值绝对值不大于200 方法 栈+遇到符号求值 逆波兰表达式和日常书写的表达式区别是符号会后置。 注意到逆波兰式没有括号，每次符号相当于对最后两个数值进行计算，所以我们可以用栈来记录还未被计算的值。 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param tokens string字符串vector * @return int整型 */ ...

题意 给一个非负数组，问能否把数组分成两部分，让两部分的和相等 限制： 数组长度不大于200 数组的每个值不大于100 方法 递推 要让分割的两部分和相等，也就是其中一部分的和等于整个数组的和的一半。 那么可以考虑去求一部分数组能达成哪些和 考虑用aval[i][j]=true/false表示，前i个值，能否选取一部分，使得它们的和为j 那么如果aval[i][j]可行，对于第i+1个值，分别是选择第i+1个值和不选择它两种方案。 不选择时aval[i+1][j] = true 选择时aval[i+1][j+nums[i+1]] = true 最后只需要检查aval[最后一个位置][sum/2...

题意 给一个数组，选取数值中一段连续区间排序后，整个数组是有序的，求最短的连续区间长度 限制： 数组长度不大于10410^4104 方法 枚举排序起始结束位置 （TLE) 直接按照题意，要找最短的区间，我们每次枚举一段区间进行排序，如果排序后，整个数组有序，那么更新这个最短值 最后输出这个最短值即可。 以题目样例数据[2,6,4,8,10,9,15]为例 - 0(结束) 1 2 3 4 5 6 0(起始) 无序 无序 无序 无序 无序 有序(最短值6) 有序(最短值6) 1 - 无序 无序 无序 无序 有序(最短值5) 有序(最短值5) 2 - - 无序 无序 无序 无...

题意 给定一个数组，每个值表示当前位置能向后移动的最远距离，同时也表示得分。 求从数组开始跳到数组结束的最大得分 限制： 数组长度不大于10000 方法 枚举遍历 使用一个辅助数组，记录每个位置能得到的最大得分。 遍历原数组，对于每个可行位置，更新这个位置之后的最大得分的值。 最终输出重终点的值即可。 以题目样例[2,4,2,1,0,100]为例 下标 值 操作 辅助数组 初始化 - - [2,-1,-1,-1,-1,-1] 0 2 更新当前位置后2个位置的值 [2,6,4,-1,-1,-1] 1 4 更新当前位置后4个位置的值 [2,6,8,7,6,106] 2 ...