NC26 括号生成 题意分析： 给定数字n，枚举出n对括号可组成的合法组合。 题解一（暴力枚举）： n对括号，一共2n个字符。用这2n个字符生成个序列，并且检查每一个序列是否时合法的括号序列。生成序列我们可以使用递归。判断生成的可以使括号序列用一种平衡的思想。假设一个括号序列有值。左括号（对值贡献为+1，右括号对值贡献-1。一个合法的括号序列每一部分都是平衡的，为0。如果在遍历判断括号序列是否合法的时候，发现此时的值小于0，说明右括号数目比左括号数目多如：())(。遍历到第三个位置，括号序列的值为-1。这时就可以认为该括号序列是不合法的。在遍历结束的时候，如果括号序列值不为0，我们也可以认为其...

NC25 删除有序链表中重复的元素-I 题意分析： 给一个有序的链表，删除其中的重复的元素。 题解一（遍历）： 我们初始化两个指针，指针flag指向当前编制元素，代表有其他指针的值与其相同的标志点。设置指针p，用于遍历链表。 当flag==p时候，p指向其下一个元素 当flag!=p时候，我们需要检查指针flag和指针p指向的值是否相同。如上图中间一部分，指针p和指针flag虽然指向不同的位置，但是其值相等，这是我们需要删除指针p指向的元素，我们的删除步骤如下： 首先flag指针的指向的下一个元素指向p的下一个元素。 删除指针p指向的元素 将指针p指向flag指向的下一个元素 通过上面...

NC24 删除有序链表中重复的元素-II 题意分析： 给一个有序的链表，删除其中出现的重复元素 示例：链表1→2→3→3→4→4→5, 删除重复元素后，变为1→2→5。解释：在原有链表中，3和4出现了多次，因此把所有的3,4都删除，最后返回了1→2→5。 题解一（遍历）： 在NC25中，我们删除了重复的元素，并且保留了一个，在这一题中，我们需要将所有出现的重复元素删除，我们可以在NC25上更进一步，在最后把重复元素删掉之后，再删掉保留的重复元素。 在中间一幅图删掉1后，变成第三张图。这是我们发现指针flag与p不相同且值不同，这时就要删除掉flag指向的元素。但flag是链表头元素，删掉就没...

jz30 连续子数组的最大和 题意分析 找出数组中连续部分的最大和。 示例输入：input = [1,-2,3,10,-4,7,2,-5]返回：18解释：input数组有多个连续子数组，如[1,-2,3]，[3,10,-4,7,2]。在输入数组的所有子数组中，子数组的最大和为18，该数组为[3,10,-4,7,2]。 题解一（暴力）： 我们将所有的子数组都求出来，求出他们的和，找出最大的和。 int FindGreatestSumOfSubArray(vector<int> array) { int ret = INT_MIN; for (int i = 0; i ...

jz29 最小的K个数 题意分析 找出数组中最小的K个数 示例输入：input = [4,5,1,6,2,7,3,8]，4返回：[1,2,3,4]解释：很明显输入数组最小的4个元素为1,2,3,4。 题解一（堆） 堆可以看做是一个二叉树。其父节点和子节点有这一定的数量关系。 大根堆：也叫最大堆，每个父节点大于其子节点。 小根堆：也叫最小堆：每个父节点小于其子节点。 对于本题，我们使用最大堆。在c++中，可以使用 priority_queue作为声明一个大根堆。 算法过程：首先将input数组前k个数插入到大根堆中，之后的数依次和大根堆的堆顶进行比较。如果当前的数比堆顶的数要小，那么就把堆顶的弹...

JZ28 数组中出现次数超过一半的数字 题意分析 找出数组中出现次数大于数组长度一半的数字。 示例输入：input = [1,2,3,2,2,2,5,4,2]返回：2解释：在input数组中，数组的长度为9,数字2出现的次数为5，大于。因此返回值为2； 题解一（数字统计）： 我们对给定的数组进行数字统计，对于示例输入，统计结果如下： 数字 1 2 3 4 5 个数 1 5 1 1 1 数据结构使用哈希表即可。对数字和其出现的次数建立一个k-v键对。使用stl的map进行统计。 int MoreThanHalfNum_Solution(vector<int> numb...

JZ27 字符串的排列 题意分析 将字符串中的字符进行排列组合，生成所有的字符串。 示例输入：input = "ab"返回：["ab","ba"]解释：字符a和b可以排列组合生成ab和ba。 题解一（暴力回溯）： 回想一下高中所学的排列组合知识：有3个红球，2个白球，1个黑球，请问有多少中排列方式。 我们的计算方式是：一个有6个位置，先选择3个位置放红球，再从剩下的3个位置中选择2个位置放白球，最后剩下一个位置放黑球。总共的排列数有种。 我们这题就是要用代码生成这些排列。 我们从左往右依次填入给定的字符，每个字符使用一次。 当我们使用...

jz 26 题意描述 题目大意：将二叉搜索树转换成一个双向链表 基础知识：二叉搜索树（BST），它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树的示例图如下： 在结点4的位置看其左孩子(2)和其右孩子(4)。左孩子(2)小于根结点4，右孩子(5)大于根节点4。树中的其他结点满足同样的要求。 中序遍历:为对二叉树作 “左、根、右” 顺序遍历，递归伪代码实现如下： dfs(root): if(root==NULL) ...

JZ50 数组中重复的数字 题意分析： 找出数组中重复的元素。 示例输入：[2,3,1,0,2,5,3]返回：数组中2和3都出现了多次，返回2或3都可以。 题解一（map统计）： 我们使用map<int,int>进行统计即可。如果m[i]>0,说明元素i是我们要的结果。如果m[i]==0,m[i]++; int duplicate(vector<int> &numbers) { map<int, int> m; for (int i = 0; i < numbers.size(); i++) { if (m...

JZ49 把字符串转换成整数 题意分析： 将给的合法字符串转化为整数 示例输入："+2147483647"返回：2147483647 示例输入："1a33" 返回值：0。输入是不合法的，因此结果是0 题解一（枚举各种情况）： 在字符串的开头，可能有如下几种情况 空格打头：删除空格 符号打头：记录符号 数字打头：直接开始处理 非以上三种情况：return 0； 我们遍历字符串，然后将数字不断添加到结果中，添加语句为ret = ret*10+s[i]。 我们不知道到最后生成的数字有多大，因此我们使用long long存储ret。 int StrToInt...

JZ48 不用加减乘除做加法 题意分析 自己实现一个没有使用加减乘除的加法。 示例输入：1,2返回：1+2=3 题解一：（投机取巧）： 不建议使用，没有学习到只是点。 int Add(int num1, int num2) { vector<int> v = {num1, num2}; return accumulate(v.begin(), v.end(), 0); } 题解二（位运算）： 想象小学所用的算术加法流程，指定位数字相加，进位。这里我们把提供的数字当做二进制数，模拟二进制加法即可。比如3+7，过程如下： 模拟一个二进制加法即可。但是上面取模加法也不...

JZ47 求1+2+3+...+n 题意分析： 求连加到n的和。 示例输入：5返回：1+2+3+4+5=15 题解一（高斯公式）： 。 int Sum_Solution(int n) {// return n * (n + 1) / 2; } 值得注意的是，该解法不满足题意要求 题解二(循环)： 循环叠加即可。 intSum_Solution(int n) { int ret = 0; for (int i = 1; i <= n; i++) ret += i; return ret; } 这种解法也不满足题意。 题解三（修改循环） 上面循...

JZ46 孩子们的游戏(圆圈中最后剩下的数) 题意分析： 这是一个著名问题约瑟夫环问题。 示例输入：n=5,m=3返回：3现在有5个小孩，围成一圈，编号从0-4。编号0的孩子从0开始报数，当有小孩报到3-1=2时，该小孩出局。一直到最后剩下的3号小孩。 过程图如下： 题解一（模拟）： 我们使用数组模拟这一过程。新建一个数组长度为n。每次数到m-1，就把该元素弹出。 我们使用tmp = (tmp+ m-1+l.size())%l.size()找出我们应该删除哪一个元素。这看上去有规律可循。我们在初始化tmp=0，根据公式，我们下一步删除的是索引为2的元素。下一次，根据公式，我们要删除的是ve...