数组中未出现的最小正整数 题目： 给定一个无序整型数组arr，找到数组中未出现的最小正整数。 要求时间复杂度为O(N)空间复杂度为O(1)。 例如： arr=[-1,2,3,4]。返回1。 arr=[1,2,3,4]。返回5。 找到自然数从1-n中，第一个没有出现在给定数组中的 题解一（空间复杂度O（n））： 我们知道数组的长度为n，最后的结果一定在1-n+1之间。我们创建一个长度为n的数组pos，元素初始化为0，之后遍历给定的数组，数组如果有数字i出现，就置pos[i-1]=1。最后遍历一遍pos，发现有pos[i]=0的话，那么最后结果就为i+1。如果在遍历过程中没有返回结果，那么返回n+...

NC48 在旋转过的有序数组中寻找目标值 题意分析： 在数组中查找target 题解一（直接遍历）： 直接遍历判断有没有target，有返回下标，没有返回-1； 代码实现如下 int search(vector<int> &nums, int target) { for (int i = 0; i < nums.size(); i++) { if (target == nums[i]) { return i; } } return -1; } 时间复杂度：，n为数组长度. 空间复杂度： 题...

NC46 加起来和为目标值的组合 题意分析： 在给定的数组中找到一些子集，这些子集的和等于target 题解一（回溯）： 枚举出所有子集，判断这些子集里面的元素和是不是等于target，等于就加入到最后结果中。 代码实现如下： void backtrace(vector<int>&nums,vector<int>tmp,int index,vector<vector<int>>&ret,int sum,int target){ //tmp保存生成的组合，sum为生成的组合总和，index指向num数组要添加的位置 ...

NC45 实现二叉树先序，中序和后序遍历 题意分析： 实现二叉树的先序，中序，后续遍历 题解一（递归遍历）： 比如有二叉树 先序遍历：按照访问树根，左子树，右子树的顺序对树进行遍历，子树同样遵守这个遍历顺序 如图所示的二叉树：先序遍历结果为4,2,1,3,5. 代码实现如下： void preOrder(TreeNode *root, vector<int> &ret) { if (!root) { return; } ret.push_back(root->val); preOrder(root->left,...

NC44 通配符匹配 题意分析： 给定字符串S，模式串P，判断S是否能够被P所匹配，通配符只有？和*，？可以匹配任意一个字符，*可以匹配任意长度的字符串 题解一（动态规划）： 设置表示字符串S的(0-i)部分是否被字符串P的(0-j)部分匹配 初始化： ，字符串s的(0-0)为空，那么只要字符串P的(0-j)的部分开始为*就为true ，模式串(0-0)为空，根本没发匹配， 状态转移 如果P[j]=="*"，并且 ==true​，或者 ==true​，那么 如果p[j]!="*"，分两种情况 当p[j]=="?"时候，s[i...

NC42 有重复项数字的所有排列 题意分析： 生成所给数字的所有排列。 这一题与JZ27字符串的排列基本一样将字符换成了数字 题解一（暴力回溯）： 回想一下高中所学的排列组合知识：有3个红球，2个白球，1个黑球，请问有多少中排列方式。 我们的计算方式是：一个有6个位置，先选择3个位置放红球，再从剩下的3个位置中选择2个位置放白球，最后剩下一个位置放黑球。总共的排列数有种。 我们这题就是要用代码生成这些排列。 我们从左往右依次填入给定的数字，每个字符使用一次。 当我们使用完了所有的数字，那么就可以将生成的数组加入到最终结果中。当我们没有使用完数字，考虑下一步应该使用什么字符呢？之前使用过的数字不...

NC38 螺旋矩阵 题意分析： 以顺时针螺旋方式打印出矩阵所有的元素 题解一（模拟法）： 以螺旋的方式进行遍历矩阵。 使用深度优先搜索，初始时，我们向右搜索，到达边界或者下一个元素已经访问过了，就转变搜索方向。搜索方向的顺序为向右，向下，向左，向右。我们定义一个方向向量vector<pair<int,int>>direct = {{0,1},{1,0},{0,-1}, {-1,0}};，用于转变方向 代码实现如下：过程写在代码注释里 vector<pair<int, int>> direct = {{0, 1}, ...

NC37 合并区间 题意分析： 将所给的多个区间，将重叠的区间的进行合并。 题解一（贪心）： 如有区间如下： [[10,30],[20,60],[80,100],[150,180]]合并的结果为： [[10,60],[80,100],[150,180]]区间[10，30]和区间[20，60]有重叠的部分，合并后就成为了[10，60]。合并过程如下 将区间[10，30]的end和区间[20，60] 的start比较，30>20，说明有重叠，更新区间[10，30]的end 为区间[10，30]的end和区间[20，60]的end的较大值。 如果两个区间没有交集，如区间[10，60]和区间[...

NC34 求路径 题意分析： 算出从起点到终点的路径数目。 题解一（动态规划）： 假设机器人站在点(i，j)处，其可以从(i-1，j)向下移动一行走到，也可以从向右移动一步走到。因此到达位置(i，j)出路径的数目等于到达位置(i-1，j)的路径数目 与达到(i，j-1)的路径数目之和。我们假设dp[i,j]表示到达点(i，j)的路径数目，那么dp[i,j] = dp[i-1,j]+dp[i,j-1]。我们新建一个二维表格dp，计算dp里面每一个值，最后返回目标位置的dp即可。 初始化，第一行和第一列的dp值全部为1，这些位置可以确定只有一条路径。表格的其他位置，根据转移方程，进行填充即可。如下...

NC33* 合并有序链表 题意分析： 将两个有序的链表合并 题解一： 我们新建4个指针，dummy用于返回最后结果，p用于遍历链表1，q用于遍历链表2，r用于指示生成的新链表末端。 举个如下例子： 开始拿指针p与指针q比较，指针p所指元素比较小，那么将r->next = p，p = p->next，r = r->next,r->next = NULL。链表变化如下： 重复步骤1，拿指针p与指针q比较，指针q所指元素比较小，那么将r->next=q，q = q->next，r = r->next，r->next = NULL。链表变化...

NC32 求平方根 题意分析： 实现一个sqrt函数 题解一（二分法）： 该哪题可以转化为求满足不等式的最大k值。k的取值范围可以确定是。可以通过二分法，寻找到k。 设置左端点l和右端点r，取其中间值得平方与x比较，如果等于x，返回mid；如果小于x，左端点更新为mid+1；如果过大于x，右端点更新为mid-1； 重复上面步骤。 代码实现： int sqrt(int x) { int l = 0, r = x; int mid; while (l <= r) { mid = l + (r - l) / 2; //取中点作为比较 ...

NC31 第一个只出现一次的字符 题意分析： 找出字符串中只出现过一次，且最先出现字符的下标。 示例：google返回：4解释：字符l只出现了一次，且在是第一次出现，l的下标为4。 题解一（暴力）： 我们假设某个位置的字符是最后结果，与其他字符做比较，如果发现没有相同的，直接返回，有，则判断下一个 int FirstNotRepeatingChar(string str) { for(int i=0;i<str.size();i++){ //假设位置i处为最后结果，与其他位置做比较 int j = 0; ...

NC29 矩阵查找 题意分析： 实现一个对有序矩阵查找函数 题解一（暴力查找）： 对矩阵的每一行进行查找，由于矩阵的每一行都是有序的，因此我们可以对每一行进行二分查找。 代码实现如下 bool searchMatrix(vector<vector<int> >& matrix, int target) { for(int i=0;i<matrix.size();i++){ if( binary_search(matrix[i].begin(), matrix[i].end(), target)){ ...

NC28 最小覆盖子串 题意分析： 有字符串S和T，在S中找出包含T的所有字符的最短的子串 示例：S = "XDOYEZODEYXNZ"，T = "XYZ" S有多个子串包含XYZ，如XDOYEZ，YXNZ等等，其中YXNZ是最小的。 题解一（暴力）： 只要枚举出包含T的所有子串，比较他们的长度，找出最小的那个。 bool check(string T, string S) { //检查S是否为t的子串 map<char, int> m; for (int i = 0; i < S.size(); i++) { ...