本题是动态规划的一道典型题目，也被收录在《算法导论》中当做动态规划章节的学习例题，是非常重要的一道题，可以很好锻炼到动态规划的思路模式。 思路 题目分析 题目给出了两个字符串，要求我们从这两个字符串中，找出最长的公共部分组成子串 需要注意的是，最终的子串中的元素必须在两个初始字符串中都出现 而且最终的子串中的数字前后相对位置和原来两个字符串中的前后相对位置一致 我们最终的目的就是找到这样的子串 我们设定字符串s1的长度为m，s2的长度为n，用一个二维数组来作为动态规划dp数组。 其中dp[i][j]表示字符串s1[0...i-1]和s2[0...j-1]的最长公共子序列的长度 dp...

思路 题目分析 题目首先给出了一个数组，要求在这个数组中找出仍然保留相对前后顺序，并且成递增规律的最长的子数组 我们首先需要有一个概念，这种求序列最长最短子序列的问题可以考虑动态规划，因为通常情况下都符合动态规划的子问题结构的特征，本题就可以从这个点入手。 处理最长递增子序列问题是典型的动态规划问题，因为该问题中存在子问题结构，当前的最长递增子序列可以由前面的转换，因此也有了状态转移方程 设定dp[i]表示包括arr[i]在内的最长递增子序列的长度 状态转移方程为： 方法一：动态规划（双循环无优化）（超时未通过） 在对状态方程进行更新的时候采用双循环的方式，时间代价较高 cl...

思路 动态规划（k棋n层）：dp(k,n)表示有k个棋子n层楼需要尝试的次数，题干要求的是dp(k,n)的结果，我们现在选择在第i层扔棋子 如果棋子碎了，则剩下k-1个棋子，此时找的楼层更新为i-1（低楼层），即应该继续尝试的次数为dp(k-1,i-1) 如果棋子没碎，则剩下k个棋子，此时要找的楼层更新为n-i（高楼层），即应该继续尝试的次数为dp(k,n-i) 这两者我们应该取一个大的值，因为是对于未知的i来说最保险的尝试次数，则应该取尝试次数现在应该为1+max(dp(k-1,i-1), dp(k,n-i)) 我们这么多从第i层选择扔棋子的方案跟层高n有关，所以想要得到其中最少的次数...

思路 用两个栈来实现 一个是普通栈，处理入栈出栈的问题 另一个是最小栈，装的是普通栈中目前的最小值，随着普通栈的入栈退栈进行同时变化 方法一：利用已有栈写法（c++） 关键是一定要保证最小值栈在实时跟随普通栈的变化，这样维护的最小值栈的栈顶才能随时返回来题干中要求的最小值 class Solution { public: stack<int> s1; //用于栈的push 与 pop stack<int> s2; //用于存储最小min void push(int value) { s1.push(value); ...

思路 python利用split函数分隔单词成列表，倒置列表后改变大小写，最终串成一个最终的字符串 双指针来取单词前后位置 方法一：借助list 用split函数分隔成单词列表，倒置的方法很好写 class Solution: def trans(self, s, n): # write code here l = s.split(' ') # 将原字符串按照空格分隔成list l = l[::-1] # 翻转list内的所有单词 ...

思路 本题是一个排序问题，可选的排序方案很多，其中冒泡、选择等O(n^2)时间的排序方案代价较高，选用快排、堆排、分治算法是比较省时的方案。直接调用c++内置sort函数是最好的办法。 ###方法一：调用sort函数排序 class Solution { public: static bool cmp(const int& a, const int& b) { // 设定比较规则，大数靠前 return a > b; } int findKth(vector<int> a, int n, int K) {...

思路 我们知道string类型是重载了比较符的，所以可以直接用比较符进行比较，比较规则就是按字典序。因此我们只需要调用sort函数重载cmp函数指定比较规则即可 方法一：sort重载cmp函数 cmp函数中要规定两字符串的比较规则是： s1 + s2 < s2 + s1保证这样的字典序才可以，最终将排序后的字符串组连接起来即可 class Solution { public: /** * * @param strs string字符串vector the strings * @return string字符串 */ sta...

思路 暴力搜索，双重循环遍历 依据有序性按照一定顺序来查找 方法一：暴力搜索 双重循环直接遍历所有元素找到指定元素 class Solution { public: vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) { // write code here for(int i = 0; i < n; i++) { // 遍历行 for(int j = 0; j &l...

思路 最直观的思路就是将所有的结点数一遍，这样得到最终结果的时间代价就是O(N) 上面一个方法忽略了我们的树是完全二叉树这一性质，完全二叉树满足的特点就是要么是一个满二叉树，要么除了最后一层以外其它层全满，最后一层的叶子结点必须从左到右不间隔的排布。 虽然完全二叉树没有计算结点的方法 但是满二叉树的结点数量满足2 ^ h - 1这一公式（h为树高），因此我们要在左右子树上对完全二叉树的情况进行简化数数的代价 方法一：直接数 class Solution { public: int nodeNum(struct TreeNode* head) { if(head ...

思路 最简单的思路就是暴力进行计算，时间上可能会比较久，尤其是在给定的滑动窗口较大的情况下。 刷题比较多的小伙伴可以发现这是一道单调队列的典型题目，什么情况才满足双端队列呢？ 滑动窗口如果只进元素的话，我们其实不用双端队列，只要保存一个最大值就可以了 但是滑动窗口如果是要退元素的话，就麻烦了起来，没有办法通过只保存一个值的方式来满足短时间复杂度的要求 所以考虑单调队列，并利用双端队列的性质维护这个单调队列 方法一：暴力解决 对每个滑动窗口都进行最大值的计算，最终结果返回到输出中 class Solution { public: vector<int> maxInWind...

思路 此题是一类动态规划问题，具有重叠子问题和最优子结构的特点，通过找到状态转移方程式来解决问题 方法一：动态规划 我们可以定义一个动态规划数组dp[i]，其表示的是从索引0到索引i位置为止，这一段区间存在的子数组的最大乘积保存在dp[i]中，因此对于一个n长的数组，最终返回结果为max(dp[0]...dp[n])，我们每一次计算dp[i]时候都要在dp[i-1]的基础上进行操作，通过子问题的方式逐步解决问题。 有了这一思路之后，还需要处理正负数的问题。如果仅仅按照上一条的说法，对于数组[-2,3,-4]，对应的dp数组会首先认为dp[0] = -2，之后dp[1] = 3（因为乘3的话只...

思路 既然题中的树是二叉搜索树，所以中序遍历顺序即为从小到大的访问顺序。这一点要直接反应过来！！！知道是中序遍历后就采用递归或非递归两种方法都可以了 方法一：递归中序遍历 递归中序的函数结构为 递归左子树 访问当前结点 递归右子树 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solut...

###思路 题目要求我们将同一层按照从左到右的顺序进行合并整理成输出，我们将题目解读并翻译为层序遍历问题 通过层序遍历的方式进行顺序访问 维护一个队列结构，队列可以帮助我们实现先进先出，因此只要层序访问入队出队即可 方法一：非递归层序遍历 具体做法 首先处理特殊情况，比如指针为空的情况，直接返回空结果[] 维护一个队列，其中存储的信息是当前层的结点指针，队列一直在第二个while循环内重复的工作就是出队当前队首结点，同时将其左右子节点入队。 在层与层之间，通过第二次while循环之前的当前队列容量大小来控制层之间的间隔。 层序遍历进行每一层的结点添加统计 以下为c++代码展示 /* st...