0. 三数之和： 题目：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。 例如：给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[ [-1, 0, 1], [-1, -1, 2]]。 思路：1. 排序：sort(nums.begin(),nums.end()); 2. nums[n1] + nums[n2] = - nums[n3]， for(int i = 0; i < nums.size() && nums[i]<=0 ; i++) 特殊情况[0,0,0],使用nums[i]<=0； 3. 先固定一个，再使用两头堵模型，j从i+1开始，k从nums.size()-1开始， for(int j = i+1, k = nums.size()-1; j < k; )； 4. 特殊情况考虑，[-4,-1,-1,0,2]和[-2,0,0,2] ，if(i > 0 && nums[i-1] == nums[i])和if(j-1 != i && nums[j-1] == nums[j])。

一. 最接近的三数之和： 题目：给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 例如：给定数组 nums = [-1，2，1，-4], 和 target = 1。 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2). 思路：1.排序： 2.特殊情况;nums没有三个数 3.初始化返回值 int ret = nums[0]+nums[1]+nums[2]; 4.先固定一个，再使用两头堵模型 for(int i = 0; i < nums.size()-2; i++)和 for(int j = i+1, k = nums.size()-1; j < k ;) 5.如果三数相加为target直接返回if((target) == (nums[i]+nums[j]+nums[k])) return target; 6.更新两指针j,k if(target < (nums[i]+nums[j]+nums[k])) k--;else j++; 7.更新返回值：if(abs(target-ret) > abs(target-nums[i]-nums[j]-nums[k])) ret = nums[i]+nums[j]+nums[k];

二. 两数相加： 题目：给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 例如：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807 思路： 1.思路一：定义两个指针，一个指针始终指向头，另一个指针修改链表 ListNode* ret = NULL; ListNode** tempNode = &ret; //空指针没有指向有意义的东西。将空指针直接赋值给指针时，是值传递，不会修改原指针的。如果我们想修改原指针而不是指针的副本，就需要传递指针的指针。 2.思路二;直接在一个链表上动刀子 ListNode* temp = l1; 通过temp指针修改内容 ... return l1;

三. 无重复字符的最长子串 题目：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1:输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2:输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3:输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 思路一（使用set）：1.特殊情况有:空字符串if(s.length() == 0) return 0;、 2.使用set来判断重复字符，seta; if(a.find(s[end])!=a.end())//表明有重复字符 3.定义两个指针下标，初始化为0，1，有重复移动start，无重复移动end 思路二(使用map优化)：（在保证ret之间没有重复字符下得到ret，所以需要start为最近一次更新没有重复字符的位置）a b a bcdef a s 1.map<char, int>a;
2.未存储过的字符存入map， a[(s[end])] = end+1; 并修改终值ret = max(ret, end - start + 1); start为最近一次更新没有重复字符的位置 3.储存过的利用a.find(s[end])->second得到此字符之前最新一次的位置，并更新ret = max(ret, end - start + 1);之后将现在的位置替换之前最新一次的位置a[(s[end])] = end+1;

四. 寻找两个有序数组的中位数 题目：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。 示例 1:nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5 思路;（使用归并排序）如果输入是一个有序序列，找到其中位数，应该是一个很简单的问题。但现在的输入是两个有序序列。 所以，要解决的第一个问题就是如何将两个有序序列合并成一个有序序列。 在考虑要求的时间复杂度的为O(log(m+n))的情况下，应考虑使用归并排序。归并排序的时间复杂度恰为O(log(m+n))。 所以，本题的解题思路为，先利用归并排序将两个有序序列合并为一个有序序列。然后求其中位数。 1.特殊情况：有一个为空，则直接求中位数 2.都存在时，先将两vector归并到一个vector中，然后求其中位数。

五. 最长回文子串 题目：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1：输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2：输入: "cbbd" 输出: "bb" 思路一： 1.空串处理 （一般） 2.ne = s.rfind(s[i], f);从右开始找匹配的字符，找到判断是否为回文子串，没找到i++;f=s.length()-1 3.判断是否回文，for(j = i, k = ne; k > j; j++, k--) if(s[j] != s[k]) 不是回文找s[i]下一个匹配点 4.优化if(ret.length() >= (ne-i+1))则直接i++;f=s.length()-1 思路二（动态规划）：建立二维数组，存放状态，例如 dp[i][j]=1;表明i~j回文。以长度为迭代单元，判断下一个长回文s[i]==s[j]&&dp[i+1][j-1]==1 (一般) 1.if(len==0||len==1) return s; 2.dp[i][i]=1;//单个字符是回文串 dp[i][i+1]=1 if s[i]=s[i+1];//连续两个相同字符是回文串 3.int start=0;//回文串起始位置 int max=1;//回文串最大长度 4.for(int l=3;l<=len;l++)//l表示检索的子串长度，等于3表示先检索长度为3的子串 for(int i=0;i+l-1<len;i++) int j=l+i-1;//终止字符位置 if(s[i]==s[j]&&dp[i+1][j-1]==1)//状态转移 dp[i][j]=1; start=i; max=l; 思路三（中心扩展法）：回文中心的两侧互为镜像。因此，回文可以从他的中心展开，并且只有2n-1个这样的中心(一个元素为中心的情况有n个，两个元素为中心的情况有n-1个)。 int len1=expendaroundcenter(s,i,i);//一个元素为中心 int len2=expendaroundcenter(s,i,i+1);//两个元素为中心 int expendaroundcenter(string s,int left,int right) //计算以left和right为中心的回文串长度 { int L=left; int R=right; while(L>=0 && R<s.length() && s[R]==s[L]) { L--; R++; } return R-L-1; }

六. Z字形变换 题目： 将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下： L C I R E T O E S I I G E D H N 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。 示例 2:输入: s = "LEETCODEISHIRING", numRows = 4 输出: "LDREOEIIECIHNTSG" 思路一：（使用二维数组坐中间量） （一般、简单） 1.特殊情况： if(s.length() == 0 || s.length() <= numRows || numRows == 1) return s; 2.建立二维数组，存放每行的子串，空字符用空格表示 vector<vector> a(numRows, vector(s.length())); 3.最终返回值 char* ret = new char[s.length()+1]; //必须多一个来作为终止符！！！ 4.最后需要 //添加终止符 ret[ret_len] = 0; 思路二：按行访问:按照与逐行读取 Z 字形图案相同的顺序访问字符串。 算法:首先访问 行 0 中的所有字符，接着访问 行 1，然后 行 2，依此类推... 行 0 中的字符位于索引 K(2numRows-2); 行 numRows-1 中的字符位于索引 k(2numRows-2)+numRows-1; 内部的 行 i中的字符位于索引 k(2numRows-2)+i以及(k+1)(2*numRows-2)-i 处;

七.整数反转：（注意变量别写错了） 题目：给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。 实例：-123 得到-321 思路：1.考虑溢出则其数值范围为 [-2^31, 2^31 - 1]。 if(ret<= (0-pow(2,31)) || ret >= (pow(2,31)-1)) return 0; 2.先得到整数的位数while((int)(x / pow(10 , weishu))) weishu++; 3.再根据位数得到值

八.回文数：（注意使用一个temp变量去改变，不要动x的值！！） 题目：判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 实例： -121 得到121-所以为false，121是为true 思路：先反转，再判等

九.盛最多的水的容器：（双指针，夹逼法） 题目：给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 实例：输入: [1,8,6,2,5,4,8,3,7] 输出: 49 思路一：两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。所以每次将指向较短线段的指针向较长线段那端移动一步。与之前面积比较. 思路二：//使用冒泡排序思想,但是超出时间限制

十.整数转罗马数字：（看清题目取值范围） 题目：给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。 思路：使用对照法 代码：class Solution { public: string intToRoman(int num) { vector values={1000,900,500,400,100,90,50,40,10,9,5,4,1}; vector strs={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}; string res; for(int i = 0; i < values.size(); i++){ while(num >= values[i]){ res += strs[i]; num -= values[i]; } } return res;

			} 
		};

十一.罗马数字转整数 代码： //建立一个哈希表，然后一一判断，若前面的罗马数值比后面的罗马数值小，则将结果加上两者的正差值，若前面的罗马数值比后面的罗马数值大，则直接加上该罗马的对应数值。

	class Solution {
	public:
		int romanToInt(string s) {
			int result=0;//存放结果
			map<char,int> luomab;//建立罗马表
			//插入对应关系
			luomab.insert(map<char,int>::value_type('I',1));
			luomab.insert(map<char,int>::value_type('V',5));
			luomab.insert(map<char,int>::value_type('X',10));
			luomab.insert(map<char,int>::value_type('L',50));
			luomab.insert(map<char,int>::value_type('C',100));
			luomab.insert(map<char,int>::value_type('D',500));
			luomab.insert(map<char,int>::value_type('M',1000));
			for(int i=0;i<s.length();i++)
			{
				if(luomab[s[i]]>=luomab[s[i+1]])   //string的最后一个为'\0'所以不用担心访问越界，luomab['\0'] = 0；map不存在则默认为0
					result+=luomab[s[i]];
				else
				{
					result+=(luomab[s[i+1]]-luomab[s[i]]);
					i++;
				}
			}
			return result;
		}
	};

十二：最长公共前缀： 题目：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。 实例：输入: ["flower","flow","flight"] 输出: "fl" 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 思路：1.数组为0，子串为0（在求最短子串长度时考虑）； 2.求最短字串长度； 3.for(i = 0; i < min_len; i++) a = strs[0][i]; for(int j = 0; j <strs.size(); j++) if(strs[j][i] != a) goto BREAK;

十三.电话号码的字符组合： 题目：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 实例：输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 思路：1.特殊情况为“”则返回{} 2. 首先求出返回值的总容量，分配好空间； 3.使用一个中间数组temp辅助组合；temp存放的是上一次res组合的数据，根据temp，在res重新组合数据。 4.例如“23”： 第一步我们会得到capacity=9；然后res分配9个空间 当digits[i]=='2',temp根据res分配一个空间为空，最后res=[a,b,c]; 当digits[i]=='3',temp=[a,b,c],res=[aa,ab,ac,ba,bb,bc,ca,cb,cc]

十四.删除链表的倒数第N个节点;（一定要考虑头结点） 题目：给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。说明：给定的 n 保证是有效的。 示例：给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 思路一；先遍历链表有多少个，然后判断删除的是否为头结点if(n == count)，否则使用临时指针指向要删除节点的前一个节点，然后。。。。 思路二：（只遍历一遍就删除要删节点）我们可以使用两个指针而不是一个指针。 1.先将第一个指针从列表的开头向前移动 n 步 2.要判断此时的if(0 == temp2)//此时temp2如果等于NULL，说明删除的是头结点 3将两个指针同时移动，直到while((temp2->next) != NULL) 4.此时此时temp1则为要删除的节点的前一个节点

十五.有效的括号：（stack的用法，还有switch注意事项） 题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 实例：输入: "()" 输出: true 输入: "([)]" 输出: false 思想：使用stack压栈出栈temp.push(s[i]); temp_char = temp.top(); temp.pop(); //弹出栈顶元素 最后要判断是否temp是否为空，不为空，则return false；

十六.合并两个有序链表：（递归思想做或归并排序的思想做） 题目：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 思路：递归思想做或归并排序的思想做 递归代码：/* 思想;倒着想，每次保证l1指向是最小的，返回给上一层,要考虑特殊情况 / class Solution { public: ListNode mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1 == nullptr) return l2; if(l2 == nullptr) return l1; if(l1->val > l2->val) //交换两个指针，保证l1最小 { ListNode* temp = l1; l1 = l2; l2 = temp; } l1->next = mergeTwoLists(l1->next, l2); return l1; } };

十七.不含重复元素的全排列和含重复元素的全排列----递归思想： 一、不含重复元素的全排列 算法思路： (1)n个元素的全排列=（n-1个元素的全排列）+（另一个元素作为前缀）； (2)出口：如果只有一个元素的全排列，则说明已经排完，则输出数组； (3)不断将每个元素放作第一个元素，然后将这个元素作为前缀，并将其余元素继续全排列，等到出口，出口出去后还需要还原数组

二、含重复元素的全排列
	算法思路：核心思想:
	因为排序是前缀加后缀，所以要保证前缀每次不一样，才能行，也就是交换后不能重复，所以在交换前要检查！！
	只要从start开始到end中间的元素与end元素相等，那么前缀就有可能相同，所以要去掉！！！
	去掉重复符号的全排列：在交换之前可以先判断两个符号是否相同，不相同才交换，这个时候需要一个判断符号是否相同的函数。也就是下面的IsSwap（）；
	例如：
	对122，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。
	去掉重复的规则：
	去重的全排列就是与头元素i交换的元素j不能与i~j之间的元素（包括i）一样，这样才能保证前缀不一样！！！

十八.括号生成-----回溯法 题目： 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。 例如： 给出 n = 3，生成结果为：["((()))","(()())", “(())()”, “()(())”, “()()()”] 思路： 方法一：暴力法 思路： 因为最后的结果必然是2n长度的字符串！！！ 我们可以生成所有 2^{2n}个 ‘(’ 和 ‘)’ 字符构成的序列。然后，我们将检查每一个是否有效。 算法： 为了生成所有序列，我们使用递归。长度为 n 的序列就是 ‘(’ 加上所有长度为 n-1 的序列，以及 ‘)’ 加上所有长度为 n-1 的序列。 为了检查序列是否为有效的，我们会跟踪 平衡，也就是左括号的数量减去右括号的数量的净值。如果这个值始终小于零或者不以零结束，该序列就是无效的，否则它是有效的。

	方法二：回溯法
	思路和算法：
		每次判断左括号数<n，右括号数<左括号数！！！
		只有在我们知道序列仍然保持有效时才添加 ‘(’ or ‘)’，而不是像 方法一 那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，
		如果我们还剩一个位置，我们可以开始放一个左括号。 如果它不超过左括号的数量，我们可以放一个右括号。
	代码：（方法二）

十九.两两交换链表中的节点----递归思想 题目； 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例: 给定 1->2->3->4, 你应该返回 2->1->4->3. 解题思路： **只要head和head->next存在（也是终止条件）**就交换内容，每次递归使head=head->next->next；

二十.K个一组翻转链表---递归+循环 题目： 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 示例 : 给定这个链表：1->2->3->4->5 当 k = 2 时，应当返回: 2->1->4->3->5 当 k = 3 时，应当返回: 3->2->1->4->5 当 k = 4 时，应当返回:4->3->2->1->5 思路： 递归每次首先找到第k个节点，然后与第一个节点head交换，然后将head变成temp->next再次递归； 递归返回后，考虑head节点到temp节点之间的交换！

二十一.移除重复元素---双指针用法 题目： 给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。 示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。 注意这五个元素可为任意顺序。 你不需要考虑数组中超出新长度后面的元素。 思路： 思路1：使用快慢双指针i,j：i指向等于val的元素，j指向后面不等于val的元素（前提是存在），然后将j指向的元素和i指向的元素交换 思路2（好）:使用快慢双指针i,j：j快指针，i慢指针 // for(j = 0; j<nums.size();j++) // { // if(nums[j] != val) // { // nums[i] = nums[j]; // i++; // } // } // return i;

二十二.两数相除----使用二分查找的思想divisor_temp = (dividend_temp + remain_temp)/2； 题目： 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。 示例 1: 输入: dividend = 10, divisor = 3 输出: 3 示例 2: 输入: dividend = 7, divisor = -3 输出: -2 说明: 除数不为 0。假设我们的环境只能存储 32 位有符号整数，其数值范围是 [-2^31, 2^31 - 1]。本题中，如果除法结果溢出，则返回 2^31 - 1。 思路：使用 bool flag = ( (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0))来表示最终的符号;0表示最终符号为负数 关于溢出的问题，可以都先使用long存储结果，再进行判断 采用二分查找的思想，divisor_temp = (dividend_temp + remain_temp)/2； 做法:每次dividend_temp -= divisor_temp;，每次dividend_temp<0时,使dividend_temp += divisor_temp;divisor_temp=divisor再开始运算，每次dividend_temp>0时divisor_temp += divisor_temp;每次dividend_temp=0；break

二十三.字符串转换整数 (atoi) 题目;首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。 当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。 该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。在任何情况下，若函数不能进行有效的转换时，请返回 0。 说明： 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，qing返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。 示例 1: 输入: "42" 输出: 42 示例 2:输入: " -42" 输出: -42 示例 3: 输入: "4193 with words" 输出: 4193 示例 4: 输入: "words and 987" 输出: 0 示例 5: 输入: "-91283472332" 输出: -2147483648 解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (-2^31) 。 思路：先找到第一个非空字符，然后判断是否为数字或'+'或'-',然后除去数字串前面的所有0！！！ 使用flag来表示正负号；使用一个vecotr存储数字 使用vector最后拼接成一个数

二十四.正则表达式匹配 题目：　给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '' 的正则表达式匹配。'.' 匹配任意单个字符'' 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。 说明: s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 。 示例 1: 输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。 示例 2: 输入: s = "aa" p = "a" 输出: true 解释: 因为 '' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。 示例 3: 输入: s = "ab" p = "." 输出: true 解释: "." 表示可匹配零个或多个（''）任意字符（'.'）。 示例 4: 输入: s = "aab" p = "cab" 输出: true 解释: 因为 '' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。 示例 5: 输入: s = "mississippi" p = "misisp." 输出: false 思路： 方法一：回溯法 //1.如果没有星号（正则表达式中的 * ），问题会很简单——我们只需要从左到右检查匹配串 s 是否能匹配模式串 p 的每一个字符。 //2.如果模式串中有星号，它会出现在第二个位置，即 p[1]。（简化：不管 N 是多少，当前的选择只有两个：出现 0 次、出现 1 次。）这种情况下，我们可以直接忽略模式串中这一部分（即忽略p[0]、p[1]），或者(大前提：s[0]存在，不存在，只能用第一种)删除匹配串s的第一个字符(前提是它能够匹配模式串p当前位置字符，即 p[0])。 如果两种操作中有任何一种使得剩下的字符串能匹配，那么初始时，匹配串和模式串就可以被匹配。 s=="aa" p=="caa" p=="aa" p=="a*" *不可能连续出现!!! 方法二：优化 //用 dp(i, j) 来应对剩余相同参数的函数调用，这帮助我们节省了字符串建立操作所需要的时间 方法三：（动态规划） //将 dp(i,j,s,p)中间结果存入备忘录，避免重复计算。 //用 dp(i,j) 表示 text[i:] 和 pattern[j:]是否能匹配。

二十五.串联所有单词的子串 题目：给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。 示例 1：输入：s = "barfoothefoobarman",words = ["foo","bar"] 输出：[0,9] 解释：从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。输出的顺序不重要, [9,0] 也是有效答案。 示例 2：输入： s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] 输出：[] 思路一（只能通过大部分，少部分超时）：首先将words的全排列，然后将每个排列都组成一个string放在一个vector(即ret_str)中然后将即ret_str中的元素一一在s串中循环寻找
思路二（通过率比前面的高，简单）：因为单词word的长度一样,所以可以截取s子串做成map，与words做成的map相比较，相等则为结果中的一个！！！ map自动排序，并可去重,所以不能直接插入，得判断是否存在，存在则值+1 例如：输入"wordgoodgoodgoodbestword" 输出 ["word","good","best","word"] 思路三：思路三:优化，每次在构造sub_map时，先检测是否在words_map中，不在则直接pass掉 if(words_map.find(str_temp) == words_map.end()) //表明不在words中 goto conti;

二十六.最长有效括号 题目：给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。 示例 1:输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2:输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()" 方法一（暴力法）:考虑给定字符串中每种可能的非空偶数长度子字符串，检查它(非空偶数长度子字符串)是否是一个有效括号字符串序列。为了检查有效性，我们可以使用栈的方法，栈占用时间多，所以可以使用left记录(个数即可。 方法二（压栈下标）：栈存(的下标，首先在栈底放-1，标志从头的下一个位置开始计算匹配的括号数；当遇到多余)时，弹出-1，更换为此时的下标，表明从此位置的下一个位置开始往后计算匹配的括号数！！！ //具体做法：对于遇到的每个 ‘(’，我们将它的下标放入栈中。 对于遇到的每个 ‘)’，我们弹出栈顶的元素，当此时栈不为空时，将当前元素的下标与此时栈顶元素下标作差，得出当前有效括号字符串的长度，为空时，将此时下标压入栈中，continue。通过这种方法，我们继续计算有效子字符串的长度，并最终返回最长有效子字符串的长度。 方法三：双计数器，两次遍历 //在这种方法中，我们利用两个计数器 left 和 right 。首先，我们从左到右遍历字符串，对于遇到的每个‘(’，我们增加 left计算器，对于遇到的每个‘)’，我们增加 right计数器。每当 left 计数器与 right计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。如果 right计数器比 left计数器大时，我们将 left和 right计数器同时变回0。 //当从左向右遍历后，再做一次从右向左遍历，过程类似！！目的: 从左向右遍历'(()'这样的不会得到值，因为不闭合！！！

二十七.搜索旋转排序数组 题目：假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。 示例 1:输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4 示例 2:输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1 思路：要求时间复杂度必须是 O(log n)，所以需要用二分查找法. //总共有以下几种情况：一.nums总长度为0，二.数组为升序排列，三.数组有旋转：1.target存在则只有可能出现在大数端；2.target存在则只有可能出现在小数端 //当数组有旋转，且出现在大端时，注意将范围缩小到大端做法：(nums[hight] <= nums[nums_len-1]) && (nums[(low+hight)/2] < nums[hight])//表明中间点还在小的一端

二十八.在排序数组中查找元素的第一个和最后一个位置 题目：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。 示例 1:输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4] 示例 2:输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1] 方法一：先使用二分查找法查找出一个匹配的位置，然后使用双指针方法寻找上界和下界 方法二：使用递归实现二分查找法，当nums[mid] == target时使用二分查找法寻找第一个匹配的元素和最后一个匹配的元素位置

二十九.搜索插入位置 题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。 示例 1: 输入: [1,3,5,6], 5 输出: 2 示例 2: 输入: [1,3,5,6], 2 输出: 1 示例 3: 输入: [1,3,5,6], 7 输出: 4 思路：变种二分查找法,有三种情况：一。当begin>end时，表明nums为空，则直接ret=0；二。当(begin == end - 1) || (begin == end)时，为正常二分查找到最后，需判断begin或end是否==target，或判断插入位置；三。递归二分查找

三十.有效的数独 题目：判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 示例 1: 输入: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: true 示例 2: 输入: [ ["8","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: false 解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。 方法一（三次迭代）：分别写三个验证函数，行验证，列验证，3*3验证 方法二：使用三个存放map的vecotr来一次遍历

三十一.解数独 题目：编写一个程序，通过已填充的空格来解决数独问题。 一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 方法一 ：递归（不成功就返回到前一个添值的地方）：首先提取当前有的元素，放在三个vector<map<int,int>>，然后在使用普通递归的方法找出答案，solve(board, row, col, sub, 0, 0, flag); //必须立一个flag，因为当递归到最后，还需要返回到上一次，而之后的代码还原了board，所以需要判断是否需要还原！！！

三十二.报数 题目：报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下： 1. 1 2. 11 3. 21 4. 1211 5. 111221 解释： 1 被读作 "one 1" ("一个一") , 即 11。 11 被读作 "two 1s" ("两个一"）, 即 21。 21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。 给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。注意：整数顺序将表示为一个字符串。 思路：使用一个vecotrtemp1存储每次报数的数，如第一次存1，第二次存的是11，....，每次通过vecotrtemp2来更新,当报数到n时，停止，并将temp1中数字转换为字符串； //求取下一次报数的数:每次判断temp1[j]是否等于temp1[j+1]，等于则将计数器加1；不等于说明同一个数结束，此时将count和temp1[j]压入temp2中。

三十三.组合总和 题目：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。 说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] 示例 2: 输入: candidates = [2,3,5], target = 8, 所求解集为: [[2,2,2,2],[2,3,3],[3,5] ] 思路：使用递归回溯的方法求出所有接 关于去重方法：1.使用map（太复杂，且效果不好）2.在递归的时候将start也传入

三十三：组合总和2 题目：给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。 说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。 示例 1:输入: candidates = [10,1,2,7,6,1,5], target = 8,所求解集为:[[1, 7], [1, 2, 5],[2, 6],[1, 1, 6]] 思路;在前一题基础上加上判断if(i>start&&candidates[i-1]==candidates[i]) continue;

三十四.缺失的第一个正数 题目：给定一个未排序的整数数组，找出其中没有出现的最小的正整数。 示例 1:输入: [1,2,0] 输出: 3 示例 2:输入: [3,4,-1,1] 输出: 2 示例 3:输入: [7,8,9,11,12] 输出: 1 说明:你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。 思路一：首先将数组排序；在进行情况分析：一。nums为空或最大的数小于1或最小的数大于1。二。nums长度为1。三。nums长度大于1且最大>1最小<1，此时需要二分查找找到接近1的位置，然后再进行依次查找到不存在的最小数 思路二（四次遍历O(n)）：1.先查找是否有1，没有直接返回1 //2.有就将负数，大于nums.size的数置1， //3.然后借用哈希表思想（，设定例如，nums[2] 元素的负号意味着数字 2 出现在 nums 中。nums[3]元素的正号表示 3 没有出现在 nums 中。）遍历一遍数组，将出现的元素对应的下标所在位置的元素置为负数， //4.最后在遍历一遍数组，第一个为正数的位置（即下标）就是缺失的第一正数！！！

三十五.接雨水 题目：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 实例：输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6 思路一：思路一：从头开始循环，每次找到<=height[i]的数（没找到，则使用次高点计算），去掉中间的高度，剩下的就是这块区域（i~next）的大小，然后i=next继续 思路二（和盛最多的水类似）：双指针法：因为积水总是受到叫低的一端影响，所以可以每次将较低的指针朝着较高的一方移动，会到更高的就停止，将较低的指针移动，每次统计当前块的积水量

三十六.字符串相乘 题目：给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 示例 1:输入: num1 = "2", num2 = "3" 输出: "6" 示例 2:输入: num1 = "123", num2 = "456" 输出: "56088" 说明：num1 和 num2 的长度小于110。num1 和 num2 只包含数字 0-9。num1 和 num2 均不以零开头，除非是数字 0 本身。不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。 思路一（递归累成、累加）；除特殊情况:首先将num2的每位与num1相乘等到的字符串存入v_temp中，然后将v_temp中的字符串累加

三十七.通配符匹配 题目：给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '' 的通配符匹配。'?' 可以匹配任何单个字符。'' 可以匹配任意字符串（包括空字符串）。两个字符串完全匹配才算匹配成功。 说明: s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 。 示例 1:输入:s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。 示例 2::s = "aa" p = "" 输出: true 解释: '' 可以匹配任意字符串。 示例 3:输入:s = "cb" p = "?a" 输出: false 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。 思路一：双指针法：每次遇到就记录此时的两个位置，首先将忽略继续查找，当不匹配后回到记录的位置的下一个位置，并将记录对应s串中的位置+1，以备下次失配时，回来匹配多个字符 思路二：递归回溯法：思想类似于正则匹配，但是此方法只能通过一半的例子

三十八.跳跃游戏2 题目:给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例:输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 思路:本题只需得到最小的跳数，不需要求路径。因此只需要得到每一跳可到达的范围即可。初始情况可设为第0跳，范围是 0~0；第i+1跳范围则是： 第i跳的最远距离+1 ~ 第i跳范围中每个点可达的最远距离当第i跳的最远距离到达数组尾端即停. 每个点只访问一次，时间复杂度o(n)，空间复杂度o(1)

三十九.旋转图像 题目:给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。 说明：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。 示例:给定 matrix = [[1,2,3],[4,5,6],[7,8,9]], 原地旋转输入矩阵，使其变为:[[7,4,1],[8,5,2],[9,6,3]] 思路:转置加翻转:最直接的想法是先转置矩阵，然后翻转每一行。这个简单的方法已经能达到最优的时间复杂度O(N^2)。

四十.字母异位词分组 题目:给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。 示例:输入: ["eat", "tea", "tan", "ate", "nat", "bat"],输出:[["ate","eat","tea"],["nat","tan"],["bat"]] 说明：所有输入均为小写字母。不考虑答案输出的顺序。 思路:使用multimap的特性，自动排序，key值可以重复！！！

四十一.下一个排列----找规律 题目：实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。 实例：以下是一些例子，输入位于左侧列，其相应输出位于右侧列。1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 思路:先考虑特殊情况，数组为从大到小排序的，例如：3->2->1，这种直接将数组反转变成从小到大 当为1->4->6->5->3->2时，将从右到左第一个a[i] > a[i-1]的a[i-1]替换成右边略大于他的数a[j]，然后将a[j]右边的数从小到大排序，例如：将4替换成5，然后将3->2从小到大排序

四十二.N皇后问题---递归回溯 题目: n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。(上下左右斜对角) 输入: 4 输出: [ [".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."] ] 思路: (递归回溯)因为每个皇后占一行,所以当放了N行时就结束;放皇后是从每行的第一个位置开始尝试,放皇后时需要检查此位置是否合格,不合格就尝试这一行的下一个位置;位置检查:分为正上检查\左上检查\右上检查.

四十三.最大子序和 题目: 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 方法一：（保证了每次计算和都是从正数开始）拿当前的和temp判断， <0则更新ret并且将temp=nums[j]，>0则继续累加，更新ret 方法二：分治法：其实就是它的最大子序和要么在左半边，要么在右半边，要么是穿过中间，对于左右边的序列，情况也是一样，因此可以用递归处理。中间部分的则可以直接计算出来，时间复杂度应该是 O(nlogn)-----递归