讨论区Markdown好像用不了了

这道题目可以用普通的循环来做，也可以用动态规划来做，相比起来动态规划的思路更加清晰，代码逻辑更加紧密。 当n为1时，输出0,1，n为2时，输出00,01,11,10，当n为3时，输出00,01,11,10,110,111,101,100。 规律：11,10是在1,0高位上+1得到；110,111,101,100是在10,11,01,00高位上+1得到，代码如下： // // Created by jt on 2020/8/25. // class Solution { public: /** * * @param n int整型 * @return int整型vector */ vector&...

深度优先遍历，通过set进行去重： // // Created by jt on 2020/8/25. // class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { sort(S.begin(), S.end()); vector<int> vec; set<vector<int> > sv; dfs(S, vec, sv, 0); return vector<vector<int> >(s...

"求是否存在"，毫无疑问，又是一道动态规划题。设当前子序列为S1[0..i],S2[0..j],S3[0..i+j+1]，dp[i+1][j+1]==true表示S3[0..i+j]可以由S1[0..i]和S2[0..j]交叉组成，得到如下状态推导公式：  如果S1[i]==S3[i+j+1]&&S2[j]!=S3[i+j+1]，那么dp[i+1][j+1] = dp[i][j+1] 如果S1[i]!=S3[i+j+1]&&S2[j]==S3[i+j+1]，那么dp[i+1][j+1] = dp[i+1][j][k+1] 如果S1[i]==S3[i+j+1]&a...

用深度优先搜索，注意优化时间复杂度，否则会超时： 优化后 class Solution { public: vector<string> wordBreak(string s, unordered_set<string> &dict) { unordered_map<string, vector<string>> mp; vector<string> res = dfs(dict, s, mp); return res; } vector<string> dfs(unordered_set<string&gt...

“求子序列个数”，毋庸置疑，这是一道动态规划题。首先定义dp[i][j]的含义：S[0..j-1]中包含T[0..i-1]的子序列个数，接下来定义状态公式：  状况1: dp[i][j]=dp[i][j-1]（如果T[i-1]!=S[j-1]） 状况2：dp[i][j]=dp[i][j-1] + dp[i-1][j-1]（如果T[i-1]==S[j-1]） 基准条件1:dp[0][j]=1(j>=0) 基准条件2:dp[i][0]=0(i>0)  接下来详细解释以上四个等式：  如果T[i-1] != S[j-1]，那么子序列将不会包含S[j-1]，因此所有的不同子序列会包含在S[...

典型的动态规划问题：  对于每个位置i，以递增的方式找长度为1,3,5,7...的回文子串，然后找长度为2,4,6,8的回文子串； 假设回文子串的起始位置为idx_s，结束位置为idx_e，更新dp数组的公式为dp[idx_e] = min(dp[idx_s-1] + 1, dp[idx_e]) 考虑到idx_s=0的情况，我们将dp[0]置为-1  代码如下： // // Created by jt on 2020/8/23. // #include <vector> #include <string> using namespace std; class Solut...

引用华科平凡大佬的原话，很精辟：  如要输出所有的解，往往深度优先搜索；如要求出解的个数或最优解，往往动态规划  本题要求输出字符串的所有回文字串组合，因此用深度优先搜索（代码思路同样借鉴了大佬，判断回文的部分简直妙极了）： // // Created by jt on 2020/8/23. // #include <vector> #include <string> using namespace std; class Solution { public: /** * * @param s string字符串 * @return string字符串vector<...

非反转的常数级别空间复杂度解法：  首先计算出数字的位数 然后从数字两边向中间遍历，判断对称部位的数字是否相等  class Solution { public: /** * * @param x int整型 * @return bool布尔型 */ bool isPalindrome(int x) { // write code here if (x < 0) return false; int digits = 0, y = x; while(y) { ++digits; y /= 10; } for (int i = 0; i < digits/2; ++i) { int a...

总结二叉树的非递归实现：  先序遍历——采用栈和一个辅助指针，不断访问节点，并将左侧节点入栈，然后出栈访问右侧节点 中序遍历——采用栈和一个辅助指针，将左侧节点入栈，然后访问中间节点，最后再入栈右侧节点 后序遍历——最难的一个，采用栈和两个辅助指针，其中有一个辅助指针记录上一个访问的节点，如果是当前节点的右子节点，则访问当前节点  中序遍历如下： // // Created by jt on 2020/8/23. // #include <vector> #include <stack> using namespace std; class Solution { pub...

后序遍历的变体，先将左右子树的所有搭配方式到两个vector，然后再用根节点分别与左右子树搭配： // // Created by jt on 2020/8/23. // #include <vector> using namespace std; class Solution { public: /** * * @param n int整型 * @return TreeNode类vector */ vector<TreeNode *> generateTrees(int n) { // write code here return postOrder(1, n); }...

设值为n的情况下，可以组成f(n)个二叉搜索树，根据规律可知：  f(0) = 1 f(1) = 1 f(n) += f(k-1)*f(n-k), 其中k=1,2,...n  显然，这是一个动态规划问题，实现如👇： // // Created by jt on 2020/8/23. // #include <vector> using namespace std; class Solution { public: /** * * @param n int整型 * @return int整型 */ int numTrees(int n) { // write code here v...

利用后序遍历，如果左右子树均为二叉搜索树，且根节点与左右子树根节点的大小符合二叉树要求，则为整个树是二叉搜索树： // // Created by jt on 2020/8/23. // using namespace std; class Solution { public: /** * * @param root TreeNode类 * @return bool布尔型 */ bool isValidBST(TreeNode *root) { // write code here return postOrder(root); } bool postOrder(TreeNode *root)...

二叉搜索树的中序遍历是有序的，如果二叉搜索树中两个节点被互换了，那么其中序遍历中必定有两个节点“错位”，因此中序遍历是解题的关键。中序遍历本身不难，但是题目要求常数级别的空间复杂度，因此想到了线索二叉树。 总结下来两种思路:  空间复杂度为O(n)——线索二叉树 空间复杂度为O(logn)——递归，这里用了指针的引用这一特殊语法  线索二叉树 // // Created by jt on 2020/8/22. // #include <cstdio> using namespace std; class Solution { public: void recoverTree(Tre...