思路： 题目的主要信息：  在数组中，选取一组序列，使和最大 选取的数中，位置不能相邻 可以不选或是选一个数  方法一：递归（超时）具体做法：对于n个元素的数组，如果最后一个数字被选择了，则前一个数字必不会被选，那就是n-2的结果加上最后一个数字，如果最后一个数字没有被选择，则是n-1的结果，选取其中最大值即可。由此将一个n的问题，划分成了n-1和n-2的子问题，因此可以用递归解决， 返回点即是0和1的时候。  class Solution { public: long long subsequence(int n, vector<int>& array) { //0 和 ...

思路： 题目的主要信息：  求两个矩阵相乘结果，两个矩阵一定存在，不用排除特殊情况 两个矩阵都为的矩阵  方法一：暴力法具体做法：直接遍历二维矩阵的每个元素，其中等于a b两个矩阵的行乘列叠加即可。 class Solution { public: vector<vector<int> > solve(vector<vector<int> >& a, vector<vector<int> >& b) { int n = a.size(); vector<vector<int> > r...

思路： 题目的主要信息：  重复字符串是由两个相同的字符串首尾拼接而成，不存在覆盖 返回的是字串长度，为重复部分的2倍，必为偶数 若不存在任何重复字符子串，则返回0  方法一：暴力解法（超时）具体做法：n记录最长的重复字串的重复长度，从字符串长度一半开始，然后依次比较后面的n个字符及再后面的n个字符是否相等，若是相等返回即可，若是不等则需要将n减一，相当于缩短重复字串长度继续。 class Solution { public: int solve(string a) { int n = a.length() / 2; //记录最长的重复字串的重复长度，从字符串长度一半开始 bool flag ...

思路： 题目的主要信息：  判断字符串是否是回文字符 回文字符即首尾相互往中靠，字符都是相同的  方法一：首尾依次比较法具体做法：两个指针，一个在字符串首，一个在字符串尾，在首的指针往后走，在尾的指针往前走，依次比较路过的两个字符是否相等，直到两指针在中间相遇。（我们这里用下标代替指针）  class Solution { public: bool judge(string str) { int left = 0; //首 int right = str.length() - 1; //尾 while(left < right){ //首尾往中间靠 if(str[left] != str...

思路： 题目的主要信息：  给数组排序 不要求稳定与否  就十分普通的排序问题，不考虑时间空间，常见的排序算法都可以，以下介绍几种。 方法一：sort函数（快排）具体做法：直接调用sort函数排序。 class Solution { public: vector<int> MySort(vector<int>& arr) { sort(arr.begin(), arr.end()); //直接调用排序函数 return arr; } };复杂度分析：  时间复杂度：，快排的时间复杂度 空间复杂度：，没有额外空间  方法二：冒泡排序法（超时）具体做法：两层循环，内...

思路： 题目的主要信息：  从0到n-1（首尾相接）中每次去掉第m个数，下一次从去掉数的下一个开始，直到剩下最后一个数 返回的是最后一个数 有数为0的特殊情况  方法一：递归具体做法：n个数相后去掉第m个数，还剩下n-1个数，依然要继续去掉第m个数。由此，从(n,m)的问题变成了(n-1,m)的子问题，其中若是(n-1,m)的子问题返回的最后一个数是x，则(n,m)返回的结果就是，其中边界是n==1的时候返回0.因此，用递归解决。  class Solution { public: int function(int n, int m) { if (n == 1) return 0; int x...

思路： 题目的主要信息：  矩阵内是非负数，求最长的递增路径的长度 移动方向可以是上下左右，不能超出边界，这将是递归的判定条件 同一条路径不能有重复的单元格，需要有记忆  方法一：深度优先搜索具体做法：使用一个dp二维数组作为缓存，记忆该单元格是否访问过的同时记录以该单元为起点的最长路径是多少（0就是未访问过），由此深度优先搜索的时候就不会重复计算很多内容。遍历矩阵，对矩阵中每一个点进行dfs寻找最长递增路径，每次更新最大值即可得到。 class Solution { public: int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//记...

思路： 题目的主要信息：  支持+ - *三种符号的运算器，其中优先级+ - 是一级，*更高一级 支持括号运算  方法一：栈 + 递归具体做法：对于上述两个要求，我们要考虑的是两点，一是处理运算优先级的问题，二是处理括号的问题。  优先级处理我们可以借助栈，当遇到符号的时候如果是+，正常入栈，如果是-，则将其相反数入栈，如果是*，则将栈中内容弹出与后一个元素相乘再入栈，最后将栈中所有元素相加即可。 括号的处理我们可以借助递归，将括号内的运算视为一个子问题，由此来简化。  class Solution { public: vector<int> function(string s, ...

思路： 题目的主要信息：  利用二叉树中序遍历结果及先序遍历结果构建一棵二叉树 打印二叉树的右视图，即二叉树每层最右边的结点元素 节点值互不相同  可以发现解这道题，我们有两个步骤：  建树 打印右视图  首先建树方面，先序遍历是根左右的顺序，中序遍历是左根右的顺序，因为节点值互不相同，我们可以根据在先序遍历中找到根节点（每个子树部分第一个就是），再在中序遍历中找到对应的值，从其左右分割开，左边就是该树的左子树，右边就是该树的右子树，于是将问题划分为了子问题。打印右视图即找到二叉树每层最右边的结点元素，我们可以采取dfs或者bfs两种方式遍历树，根据记录的深度找到最右值。 方法一：递归建树+深...

思路： 题目的主要信息：  统计32位整型有符号数二进制中1的个数 因负数用补码表示，故不能用连除法  方法一：循环按位比较法具体做法：可以直接循环检查二进制的每一位是否为1.  1 << i： 用于移位 & ：与运算比较是否为1  class Solution { public: int NumberOf1(int n) { int res = 0; for (int i = 0; i < 32; i++) { if ((n & (1 << i)) != 0) { //按位比较 res++; } } return res; } };复杂度分析： ...

##思路： 题目的主要信息：  对于一个给定无序数组，返回最小的k个元素，顺序由小到大 k和数组有特殊情况需要单独讨论  方法一：sort排序法 具体做法： 这是最能想到，也是最简单的方法。利用sort函数对数组进行由小到大排序，然后取前k个值入vector即可。 class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int> res; if(k == 0 || input.size() == 0) //排除特殊情况 r...

思路： 题目的主要信息：  逆序对：前面的数字比后一个数字大，构成一对逆序对 答案可能会非常大，因此用到了取余1000000007 不用考虑相同的数字  最能想到思路，莫过于依次比较数组中每两个数，然后统计逆序对的数量。但是既然答案都会非常大了，数据量最大也可能达到10510^5105，依次比较可能会超时。 方法一：暴力法(超时） 具体做法： 两层遍历，依次比较该数与后续其他数的大小关系，统计逆序对数量。 不出意外，这种方法超时了。 class Solution { public: int InversePairs(vector<int> data) { int res = 0; ...

思路： 题目的主要信息：  合并（相加）二叉树位置相同的结点 缺少的结点用另一棵树来补，若都缺则返回NULL  方法一：递归先序遍历 同时先序遍历两棵树即可完成。 具体做法： 首先判断t1与t2是否为空，若为则用另一个代替，若都为空，返回的值也是空。然后依据先序遍历的特点，根左右的顺序递归访问。 class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { //若只有一个结点返回另一个，两个都为NULL自然返回NULL if (t1 == NULL) return t2; if (t2 == NULL) ...

思路： 题目的主要信息：  字母到数字分别为1-26映射，没有0 输入的数字是字符串，故非常大，超过了long long的表示范围 但凡出现11-19，21-26的就可能出现两种译码结果 求总后的译码结果种类  方法一：递归（超时） 具体做法： 遍历字符串，每到一位，可以查看它是可以跨越两步还是只能跨越一步，只有11-26（除20外）之间才有两种情况，由此分为两种情况再对之后的字符进行判断，因此可以用递归，每一位为一个子问题。  class Solution { public: int backtrack(string& s, int idx){ //inx记录当前字符的位数 int ...