LeetCode 方法详解

1：两个数的和为一个定值

/a45872055555/article/details/36675507

题目描述：给一个序列，找到两个数的和为给定的值，返回这两个数的索引。

题目解析：

（1）暴力法：i从0...n-1；j从i+1...n。如果两个数的和等于给定值，就返回索引。时间复杂度高O(n^2)

（2）排序+扫描：将数组排序，然后i指针后移，j指针左移，直到找到两个数的和等于给定值。时间复杂度O(n logn)

（3）空间换时间：a+b = target。也就是在数组中找target - a。先将数组扫描一遍，建立一个hash表，然后再扫描数组，判断target-arr[i]是否在hash表中。时间复杂度O(n)。

2：找到两个有序数组的中间值，但时间复杂度要是O(log(m+n))

/a45872055555/article/details/36892719

题目解析：

（1）暴力法，但不满足题意

（2）二分查找+递归：比如A[m]和B[n]数组。我们找第k大的数的时候，就用A[k/2-1]和B[k/2-1]比较，如果是小于号，证明A的前k/2的数据都在合并后的数组的前半区。然后递归进行处理！

3、找出最长不连续的子串

/a45872055555/article/details/36901129

题目描述："abcabcbb"中"abc"最长。

题目解析：可以理解成一个滑动窗口，滑动窗口内的字符不重复，求最大的窗口大小。

（1）暴力法：以每一个字符为起点，向右遍历，找到最大的长度。

（2）哈希表：我们用一个26个字符的数组来表示该字符是否出现过。但这就带来了一个问题，abcbdef，当遍历到第2个b的时候，a数据应该清除掉的。那么这个时候，我们就用两个指针，i慢，j快。当发现重复的时候，就i++并且清楚hash表的相应位。

（3）哈希表：我们可以用26个字符的数组来存储该字符的位置。当发现重复的时候，就要将位置赋值成新的位置，但是其他位置要如何修改？由于len增加的时候是一个一个增加，而减小的时候，可以大幅度一次性减小。可以利用len = min(len+1,j-index)来推测新值。

4、两个链表相加

/a45872055555/article/details/37063555

题目描述：将一个数的每一位用链表的形式存储，现在要将两个数相加，求得最后的结果。

题目解析：就是简单相应的位相加，要注意进位。L1->data 、L2->data和carryover三个数相加，分两次运行，这样就不用同时满足L1和L2都不为空。简化代码的实现。

5、最长回文子串

/a45872055555/article/details/37119709

题目解析：

（1）暴力法：起始位置为i，让j从i+1到n遍历，针对每一个j判断i--j是否是回文字符串。O(n^3)

（2）动态规划：p[i,j] = (s[i] == s[j]) && p[i+1,j-1];

（3）中心扩展法：以每一个字符为中心，向两边扩展。注意要分奇偶扩展。

（4）Manacher算法：O(n)

6、锯齿形转换

/a45872055555/article/details/37130505

题目解析：

（1）通过数学分析找出规律，每行都有哪些元素坐标。

（2）用c++的容器，可以添加元素，就不用专门设数组。按照上下遍历即可。

7、翻转整数

/a45872055555/article/details/37315779

题目描述：将123变化成321，-123变化成-321

题目解析：

转换的思路倒不难，但是关于存储数据的方式一定要整理清楚：

（1）unsigned int temp = (unsigned int)n;必须要强制类型转换。

（2）输出数据的时候要用%u来输出无符号数据

（3）对于一个整数每一位进行描述，我们要么转化成字符串进行处理，要么通过数组来表示

8、回文数字

/a45872055555/article/details/37324565

题目解析：

（1）我们可以判断最高位和判断最低位是否相等，若相等，则去掉高位和去掉低位，剩余的数据再判断是不是回文数

（2）可以利用翻转来解决，当然这里要注意溢出的问题，不过我们可以用longlong类型，定义更大的数据，然后reverse = 10*reverse+curNum%10;

curNum /= 10; 最后，判断reverse == curNum。

（3）将整数转换成字符串或者数组来表示，然后用前后指针来判断是否相等。

（4）通过《左旋转字符串》得到启发，我们可以将"54322345"拆分成"5432"和"2345"，然后将其中一个翻转，判断两个数是否相等。

9、装最多的水

/a45872055555/article/details/37349623

题目描述：arr[n]的数组中，第i个位置的线的高度为arr[i]，任取两条线，求能装的最大容量。

题目解析：

（1）暴力方法：分别以每条线为起点，求得最大的容量。

（2）两个指针：i...j。求得体积后，小的边向多方移动一位，求面积更新。

（3）优化方案二：i....j。求得体积后，让小的边向对方移动，直到找到比它大的边停止，求值更新；再移动小的边……

10：整数转换为罗马数字

/a45872055555/article/details/37352755

题目解析：

对于一个整数，我们需要从高位向低位一点一点转换，由于罗马数字是有对应关系的，我们通过数组来表示即可。

int value[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
char *roman[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
char store[20] = {0};
int len = sizeof(value)/sizeof(int);
for(int i = 0;i < len;++i){
while(n >= value[i]){
n -= value[i];
strcat(store,roman[i]);
}
}

11、罗马数字转换成整数

/a45872055555/article/details/37360001

题目解析：

这里求解的时候要从罗马数字的低位向高位移动，碰到相应的字母就转换成相应的数字。但对于"IX"我们有10-1=9。也就是当str[i] < str[i+1]时，减去str[i]表示的数字。

arr['I'-'A'] = 1;
arr['V'-'A'] = 5;
arr['X'-'A'] = 10;
arr['L'-'A'] = 50;
arr['C'-'A'] = 100;
arr['D'-'A'] = 500;
arr['M'-'A'] = 1000;
result = arr[str[n-1]-'A'];
for(int i = n-2;i >= 0;--i){
if(arr[str[i]-'A'] >= arr[str[i+1]-'A'])
result = result + arr[str[i]-'A'];
else
result = result - arr[str[i]-'A'];
}

12、最长公共前缀

/a45872055555/article/details/37369133

一系列字符串中，两两比较，找到最短的前缀。

13、号码的字符串组合

/a45872055555/article/details/37515137

题目解析：

深度优先遍历的典型引用。对于每一个字符所代表的数字遍历，然后递归到下一个字符。

注意区别什么时候当前递归函数中需要加for循环，什么时候不需要加。当前字符有多重可能的时候，就for循环表示。

14、移除链表中倒数第n个结点

/a45872055555/article/details/37560715

题目解析：

很简单，但要注意输入参数的判断、链表个数以及临界条件。

15、括号匹配

/a45872055555/article/details/37561019

题目解析：

给定一个由左右括号组成的字符串，判断是否是匹配的。通过一个栈来实现，左括号就入栈，右括号时与出栈元素向匹配。

当然当匹配到最后的时候，还要判断栈是否为空，如果不为空也是匹配失败。

16、生成括号

/a45872055555/article/details/37562017

/gstc110/article/details/7583655------好方法！

题目解析：

（1）深度优先算法：

利用标记数组来标记哪些还没访问过。找到第一个没有被访问的位置i，然后在i+1,i+3,i+4....位置放置右括号。但是要注意，如果在j放了右括号后，j+1已经右括号了，就不再向右判断了！否则会出现重复的现象。

当退出当前循环的时候，第i的位置要清零。

void DFS(int *visited,char *buf,int n)
{
int i;
for(i = 0;i < n;i++){
if(visited[i] == 0)
break;
}
if(i == n){
puts(buf);
return;
}
visited[i] = 1;
buf[i] = '(';
for(int j = i+1;j < n;j+=2){
visited[j] = 1;
buf[j] = ')';
DFS(visited,buf,n);
visited[j] = 0; //清除标志
if(visited[j+1] == 1) //已经到达边界
break;
}
visited[i] = 0;<span style="white-space:pre"> </span>//清楚标志
}

（2）卡特兰级数

可以利用括号个数的特性，在任何时刻，left <=right。也就是不能先放右括号再放左括号。

所有对于第i个位置，如果left>0就能放')'，如果left<right，就能放'('。这也就是变相的0,1选择问题。

void generate(int leftNum,int rightNum,string s,vector<string> &result)
{
if(leftNum==0&&rightNum==0)
{
result.push_back(s);
}
if(leftNum>0)
{
generate(leftNum-1,rightNum,s+'(',result);
}
if(rightNum>0&&leftNum<rightNum)
{
generate(leftNum,rightNum-1,s+')',result);
}
}

扩展：

对于一个数组，打印出所有的入栈出栈序列。

17、合并k个链表

/a45872055555/article/details/37572667

题目解析：

（1）一个一个合并，时间复杂度为2n+3n+....kn = O(n*k*k);

（2）两两归并。我们可以用递归或者循环。for(int i = 0;i + half < size;i++) 时间复杂度O(nklogk),空间复杂度的话是递归栈的大小O(logk)。

（3）用堆进行排序：使用priority_queue，这个容器是用堆实现的，不过默认构建的是大顶堆，弹出最大值后，将该最大值后面的结点入队列。

18、将链表中的元素两两交换

/a45872055555/article/details/37575525

很简单，设置三个指针即可，但要注意null,一个结点，两个结点等情况。

19、从有序数组中移除重复的数据

/a45872055555/article/details/37583097

通过快排的第二种方法受到启发，设置两个指针变量i,j当不重复的时候，就将该数据放到i+1的位置，然后移动索引变量。

20、删除指定元素

/a45872055555/article/details/37584121

题目描述：从数组中删除指定的key元素。

题目解析：

（1）可以利用上一题的方法，i，j都从前向后移动，当j指向的不是key的时候，就向i赋值。

（2）也可以变通一下，i从左向右，j从右向左。当i移动到指向key的位置停止，j从右向左移动到不是key的位置，然后将该元素赋值给i位置。

21、在有序数组中找到插入位置

/a45872055555/article/details/37601981

题目解析：

（1）顺序查找

（2）二分查找：凡是碰到有序数组，并且让查找的，一般都要考虑用二分查找方式

22、查找数据出现的范围

/a45872055555/article/details/37603707

题目描述：[1,2,3,4,4,5]找数据4，返回[3,4]。

题目解析：

这道题是二分查找的加强版，二分查找的时候，当发现要查找的值的时候就立即退出，但这里是找范围，所有判断条件有所变化。

分两次二分查找，一次查找左边界，一次查找右边界：

（1）找左边界：arr[mid] >= key；hi = mid-1; 退出循环时，lo为左边界

（2）找右边界：arr[mid] <= key; lo = lo+1; 退出循环时，hi为右边界

23、下一个排列

/a45872055555/article/details/37662519

题目描述：2543--->3245

题目解析：

通过分析数组的形式，我们从后向前扫描直到找到第一对a[i]<a[i+1]的位置，然后将第i个元素和从后向前遍历的第一个最大的交换，然后将i后面的数据翻转。比如：23876654433-----（1）24876654333--------（2）24333456678

就得到了我们想要的结果。当然如果整个数据都是逆序的，那么就将整个数组翻转，输出最小的数即可。

24、最长有效的括号匹配

/a45872055555/article/details/38462951

题目描述：")()())" 返回 "()()" -----4

题目解析：

这里用栈来解决，但是栈中保存的不再是左右括号了，而是保存的是左括号的坐标位置，当碰到左括号就入栈，碰到右括号就出栈一个，并计算长度！比如((())，得到第二个右括号时为4-0。

有个小问题要解决：当栈退完时，就不能计算当前的长度了！比如栈从栈底到栈顶为2 3 4（1和0是一对括号已经退出），那么连续三个括号后已经退出了所有的元素，就不知道改真名计算有效的字符串长度了。不能简单的认为减去（2-1）。

解决方法是，先向栈中放一个标记-1。当在程序运行过程中，栈中只剩下一个元素了，并且还要出栈！（也就是碰到了右括号），就将-1弹出，并放入该右括号的坐标，代表这个右括号是不匹配的。

stack<int> S;
(-1);
for(int i = 0;i < n;i++){
if(str[i] == '('){ //为左括号，入栈
(i);
}
else{ //为右括号
if(()>1){ //当栈的元素多于一个的时候才能出栈
();
int temp = ();
if(i-temp > result)
result = i-temp;
}else{ //栈元素为1个，代表有效字符出栈完毕，且更新的为')'右括号的位置！
();
(i);
}
}
}

25、在旋转数组中查找

/a45872055555/article/details/38468255

题目解析：

这个是个典型的题目，在剑指offer上也有讲述。

（1）可以通过二分查找，先找的分割点，然后在根据target所在的范围，再次二分查找。

（2）通过局部有序来判断，当a[left] <= a[mid]的时候，这段区域是有序的，判断target是否在这个区域中，是的话，就更改right。

（3）递归思想！由于2中已经提到了，局部有序，那么可以判断target是否在这个区域内然后递归的进行查找。

26、统计并输出---count and say

/a45872055555/article/details/38470465

1,11,21,1211....

循环的判断每一个字符串中数据连续出现的次数和值

27、元素的和等于target

/a45872055555/article/details/38471027

题目描述：{2,3,6,7} --7 输出{7} {2,2,3}，数组中的元素可以重复

题目解析：

首先题目中并没有说数据是有序的，我们为了计算方便，先将数据进行排序。

对于每一个元素可以重复多次，有两种方法：

（1）递归调用，选取第i位的元素，并深度递归的时候还是选择i；然后不选第i位元素，深度递归的时候，从i+1开始。

（2）计算次数：通过将剩余的sum/arr[i]，来判断该元素最多能加上多少次，每加一次，就深度遍历。

我链接中的代码不太好，按说应该按照（1）那样选取和不选取，但我竟然用了for循环。导致插入一些额外条件来避免出现重复数据。

28、元素的和等于target ---2

题目描述：{1,1,2,5,6,7,10} -----8 输出：1,7 1,2,5 2,6 1,1,6

题目解析：

由于含有重复数据，但不能产生重复结果，所有这类题的通用解决方式是：有多个数x，当前面的x选择的时候，后面的x才能选择。

（1）可以利用我以前的笨方法，在单次循环中也使用for()，先选择该数据，深度递归，然后不选择该数据，那么下次的i要增加到指向的值和当前值不同的位置。 /a45872055555/article/details/38471311

（2）有个偷懒的方法，通过set集来求解。由于set不包含重复的数据，所以插入重复的结果的时候，就被忽略。

/pickless/article/details/9216251

（3）也可以仿照上一题的方法2，上面是不限制次数，所以用sum/arr[i]，但这里是有次数的，所以在递归遍历之前，先统计下每个元素重复的个数，并且将元数据去重！再按照27题的方法二来求解。

/xshalk/article/details/8162992

29、第一个缺失的正整数

/a45872055555/article/details/38472477

题目解析：

（1）遍历法：由于有n个数，数据最多是1...n。那么就用1....n一个一个去在数组中查找，直到找不到位置，如果第n个也能找到，就输出n+1

（2）排序+遍历法：向将数组排序，然后找到正数区域后，再判断数据间隔是否不等于1.

（3）空间换时间：hash表法，向将数据映射到hash表中，然后依次查找1...n。

（4）数组充当hash表：将a[k] = i的值放到a[i-1]的地方。不在1...n这个范围的数据就忽略掉。但要注意交换的时候的细节！

---------i)a[i] 要和a[a[i]-1]交换，不能通过简单的temp = a[i]; a[i] = a[a[i]-1]; a[a[i]-1] = temp；这期间会改变a[i]的值，所有要保存变量。

---------ii)当交换过以后，不进行i++；因为要重新审查a[i]的值要放在什么位置。所以，当a[i] != a[a[i]-1]的时候才进行交换。

30、柱子间存储的水容量

/a45872055555/article/details/38473205

题目解析：

找到第一个不为0的元素当起始位置。

然后遍历后续元素找到结束柱子，但要分情况：

1）如果比当前柱子高，就截止，计算面积。

2）如果没有比当前柱子高，就找到i+1...n的最大值。求中间面积。

31、跳跃游戏：

/a45872055555/article/details/38474197

在第i个位置，最多跳a[i]步，判断能否到达终点。

题目解析：

（1）可以利用递归的思想，要到达位置i，就可能从i-1,i-2...0过来，然后在能保证j能跳到i的情况下，递归fun(j)，返回真就代表能成功。

（2）我们可以正向思维，当我们在第i个位置的时候，判断我们从0...i过程中最远能跳多少。那么在每一步就i+a[i]，然后更新max。如果max>=n，就代表能成功！

32、实现指数次方

/a45872055555/article/details/38487543

上述链接里面，碰到了很多细小的问题，负数的转化。我们可以传递一半数值递归，那么就能解决最大负数的问题。

/a45872055555/article/details/31064731

最好的方法还是【剑指offer】上面的解析，通过unsigned int 来强制将数据转化成非负数。并且也有判0的过程。

33、顺时针打印矩阵

/a45872055555/article/details/38489051

题目解析：

（1）一圈一圈去打印，每一圈打印的时候还要分成四部分for循环。但要注意判断只有一行或一列的情况，这时只能由一个循环，四个循环都写的时候，会报错。

（2）可以利用深度优先算法，定义direct代表方向，然后按照→↓←↑来深度递归。不过递归的时候，不单纯是i=0;i<4;i++。决定方向时还要算上传进来的direct方向。程序会输出所有的数据后，然一点一点返回。

34、最后一个单词的长度

/a45872055555/article/details/38490477

题目解析：

要准备好各种测试用例：“#sdf#” “adf##” " adfa#sdfe"等等

当碰到空格时，先不要将count计数清零，当空格的下一个为字符的时候，才将count清零。

35、全排列

/a45872055555/article/details/38490763

深度遍历到第i个位置的时候，一次将i和i+1...n的位置交换，并深度优先。当交换下一个的时候，要恢复原来i位置的值，在交换。

36、找到全排列中的第k个排列

/a45872055555/article/details/38494985

通过数据分析：123以1开头的数据有两个，也就是(n-1)! 那么我们可以通过求k/(i-1)! 来得到要选出第几个元素，当我们选出这个元素之后，将后面的数据左移，也就构成了i-1长度的数据，找到k%(i-1)！的元素。

当然要用一个数组来初始化，a[i] = i+1；然后通过这种方式来选择。

37、唯一路径

/a45872055555/article/details/38495463

题目描述：从矩阵左上角走到右下角有多少种走法。

题目解析：

在位置[i,j]可以从[i-1,j]和[i,j-1]过来，可以利用动态规划思想求解。由于只用到相邻的两个元素，一维数组就能解决问题。

38、整数开方

/a45872055555/article/details/38497459

题目解析：

（1）可以采用二分法，在0...n/2之间找值，满足i*i<x<(i+1)^2。但要注意n为1的时候，

（2）上面用数据相乘，很可能会超出数据，得不到想要的结果，要换成unsigned long long 才行。我们能不能换个思路，不用相乘，判断i>x/i。利用除法来做。就能得到很好的效果。

39、爬楼梯

/a45872055555/article/details/38497779

一次只能走1步或2步，看到达n有多少中走法。

题目解析：动态规划方法，a[i] = a[i-1]+a[i-2]。由于只涉及到两个数据，用两个变量保存就行。

40、编辑距离

/a45872055555/article/details/38498939

题目描述：两个字符串可以通过插入删除替换，找到最少的步数来编程另一个字符串

题目解析：

碰到两个字符串之间的关系问题，一般都会通过动态规划来解决。如果A[i] == B[j]，那么num[i,j] = num[i-1,j-1]。如果不相等，就为num[i-1,j],num[i,j-1]或num[i-1,j-1]中的最小值+1。

41、矩阵相应行列清零

/a45872055555/article/details/38502553

题目描述：如果[i,j]为0，就将第i行和第j列清零。

题目解析：

题目中不让使用辅助空间，但对解决这道问题来说实在很复杂，我们就应该从借用辅助空间来入手，看能得到什么启发。

（1）设置m*n的数组，然后遍历原数组，碰到0，就将复制数组相应行列清零。

（2）正如n皇后问题中，我们完全不必设置矩阵，用两个一维的来标记该行或该列是否需要清零，最后进行相应的清楚。

（3）既然想到了标记数组，那么是否能用原矩阵的行列来标记？由于i行j列要清零，正好这两个数组是没用的，就让这两个标记即可。

--也可以让0行和0列来标记，但在使用之前，要先判断这两行是否需要清零。

42、在二维矩阵中查找

/a45872055555/article/details/38503471

题目描述，这个二维矩阵每一行都小于下一行，并且行内也是递增的。

题目解析：

（1）可以参考剑指offer上类似的解法，将每行第一个元素与target比较，找出所对应的行，然后在行内查找。

（2）每行的首元素也是递增的，因此可以利用二分查找，找到行后，在行内也利用二分查找。

（3）由于二维数组在内存中是按照行排列的，因此可以对整体进行二分查找。

43、荷兰国旗问题

/a45872055555/article/details/38510317

题目解析：

（1）可以利用两次快排，第一次将2排在右边，0和1排在左边；第二次将0和1分开。

（2）可以利用三个指针，i--j--k。

j指向0就和i的位置交换，i++;j++

j指向1，j++

j指向2，就和k的位置交换，然后k--就行，不用判断k的指向，交换后，j不变，下次循环的时候，让j再判断

44、排列

/a45872055555/article/details/38512929

将数组1...n中，选择k个数据，输出所有的方式

题目解析：

就是深度优先算法，对于i，可以选可以不选，当够了k个数据后，就退出。当然选够k个数据要在函数入口时判断，不要在添加一个数据后判断。

45、子集

/a45872055555/article/details/38513369

题目解析：

对于每一个元素可以选择可以不选择，就有2^n中方式。深度优先算法即可。

46、删除重复的数据_2

/a45872055555/article/details/38516037

一个数组中有重复的数据，删除多余的数据，使得最多有两个。

题目解析：

这里用个计数器即可，当大于2的时候，i就不再移动，判断j的指向是否和i的相等，不相等就交换。

47、删除链表中的重复数据

/a45872055555/article/details/38516943

解题方法类似，当相等的时候就删掉重复的数据。

48、链表中相同的数据结点都删除

/a45872055555/article/details/38518363

题目解析：

由于不是删除重复的，只要碰到重复结点值val，就将val的结点全部删除。这里比较难处理的是不重复结点的next指针。

很好的方法是，定义指针的指针ppNext = &(head->next)；该指针只是next的指向，很方便实用！

49、直方图中的最大矩形

题目描述：直方图中的每一个高度代表该面积，求解能够构成的最大矩形面积

题目解析：

（1）可以利用动态规划：maxarea[i,j] = min (maxarea[i,j-1] / (j-i) , hight[j] ) * (j-i+1)

/a45872055555/article/details/38520073

（2）利用栈来求解

方法巧妙：从左向右扫描高度值，当碰到的高度比栈顶高度大就入栈；当碰到高度比栈顶高度小，就出栈，并计算矩形面积，直到栈顶高度比当前高度小位置。也是就栈存储的是递增高度的索引值！这样方便我们进行矩形面积的求解。

/doc_sgl/article/details/11805519

50、归并有序数组

/a45872055555/article/details/38520709

题目描述：将两个数组A--B合并，A中有足够的空间

题目解析：像剑指offer中的替换空格一样，从后向前遍历即可

51、格雷码

/a45872055555/article/details/38523393

题目解析：

（1）深度优先遍历，当确定i元素后，遍历i+1及以后的元素，直到找到异或值只有一个1的元素，可以利用temp&(temp-1)。然后放到i+1位置，深度优先。

（2）格雷码有特点，000--001 || 011--010 |||| 110--111 || 101--100

int highbit = 0;
while(n--)
{
highbit = ();
for(int i= ()-1; i >= 0; i--)
res.push_back(highbit|res[i]);
}

（3）数学方法：从第0个开始，第i个gray code为：(i>>1)^i

vector<int> grayCode(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> res;
int num = 1<<n;
int i = 0;
while(i<num)
res.push_back((i>>1)^(i++));
return res;
}

52、带有重复数据的数组的子集

/a45872055555/article/details/38532893

这里就要小心重复数据带来的重复结果。我们还是利用count来计数，放入0...count个。有个小技巧，我们不要按照count....0来放，这样会有退栈操作，比较麻烦。

53、翻转链表2

/a45872055555/article/details/38533939

输入两个参数m和n，将m和n之间的链表翻转

一定要小心各种边界条件，m=1（做标记，最后处理首元素）；n=1; m>2时，找到m-1的位置。

54、判断是一个字符串不是由两个字符串顺序交叉构成

/a45872055555/article/details/38541393

题目解析：

（1）递归的方法：如果s1[i] == s2[j]，那么先让s1[i]和s3[k]相等，深度递归，如果不行，就返回让s2[j]和s3[k]相等，再判断

（2）动态规划：f[i][j] = (f[i][j-1] && s2[j-1] == s3[i+j-1]) || (f[i-1][j] && s1[i-1] == s3[i+j-1]);

--------两个字符串之间的关系，一定要想到动态规划

55、唯一二叉搜索树的个数

/a45872055555/article/details/38542587

给n个结点，判断能够构成多少个二叉搜索树。

题目解析：

像这种个数的问题，要通过举例子来判断个数。通过分析，选取i为根，则i-1个为左子树，n-i个位右子树。所有个数为num[i-1]*num[n-i]。

用递归会超时，这明显可以用动态规划。

56、二叉树的个数_2

/a45872055555/article/details/38545505

题目描述：紧接着上题，但要返回所有的二叉搜索树

题目解析：

既然是二叉树，就要联想到递归构建，我们依次选取1...n个结点为根结点，然后递归1..i-1 和 i+1...n，整个函数返回所有二叉树的构建情况。

因此我们可以将整体封装成模块：有了根结点，有了左子树的集合，有了右子树的集合。就需要我们用两层循环，构建以i为根结点的所有子树的情况。

57、有效的二叉搜索树

/a45872055555/article/details/38545993

题目解析：

（1）我们利用二叉搜索树的性质来判断：中序遍历得到的是有序数组。然后我们判断得到的数组是否有序即可。

（2）碰到树就要想到递归。那么递归如何实现呢？是从下到上还是从上到下判断？

从下到上，也就是分别返回左子树的最大值和右子树的最小值，然后判断根是否在这个中间。并且再返回给上一层的时候，要给左子树的最小值或右子树的最大值....很复杂，实现起来也有难度。

从上到下判断呢？通过设定上下界，根递归到左子树和右子树分别更新相应的上下界来递归判断。

58、相等的二叉树

/a45872055555/article/details/38548751

递归判断：根结点是否相等，是否都为空。

59、镜像树

/a45872055555/article/details/38549521

题目解析：

（1）递归方法：递归时传入p->left和q->right 以及 p->right和q->left

（2）非递归方法，使用队列：使用两个队列，一个按照左右入队列，另一个按照右左入队列

----------（3）错误的方法：中序遍历，如果得到的序列关于中心对称就代表是镜像树。观点错误！

60、依次输出每一层的结点值

/a45872055555/article/details/38556727

题目描述：[3] [9,20] [15,7]

题目解析：如果是层序遍历的话，直接做就好。但是要将不同层的数据分开，就要统计下一层结点的个数，然后依次出队列入队列。循环的时候只能用n不能动态获取 ()

61、二叉树的深度

/a45872055555/article/details/38556809

题目解析：

（1）递归方法

（2）队列统计

（3）栈的方法

62、前序和中序遍历构成二叉树

/a45872055555/article/details/38556825

根据前序遍历的第一个结点，在中序中找到分割点，就划分为左右子树

63、中序遍历和后序遍历构建二叉树

/a45872055555/article/details/38556851

跟上一题一样，用后序的最后一个结点来在中序遍历中分割左右子树

64、二叉树的层序输出_2

/a45872055555/article/details/38556879

从下层向上层输出

题目解析：依然按照层序遍历的方式，但从n-1 .....0输出即可

65、有序数组转换成平衡二叉树

/a45872055555/article/details/38558375

题目解析：二叉树被打破平衡后恢复原状比较繁琐，但是构建一个平衡树就比较容易了，直接选取n/2的结点当做根结点，然后遍历左右子树即可

66、有序链表转换成平衡二叉树

/a45872055555/article/details/38559821

题目解析：

（1）可以仿照上题，找到中间根然后遍历左右子树，但是时间复杂度高

（2）先创建左子树，再创建根结点，最后创建右子树。

TreeNode *toBST(ListNode *&h, int low, int up)
{
if (low > up) return nullptr;
int m = low + ((up-low)>>1);
TreeNode *lt = toBST(h, low, m-1);
TreeNode *r = new TreeNode(h->val);
h = h->next;
r->left = lt;
r->right = toBST(h, m+1, up);
return r;
}

67、判断是否为平衡二叉树

/a45872055555/article/details/38560415

题目解析：

我们既要知道子节点是否为平衡二叉树，有要知道子节点的高度，因此有两种方法：

（1）函数返回bool，参数中有一个变量返回子树的高度。

（2）bool值设置成私有变量，入口的地方先判断是否为true，不是的话就直接退出，不深入判断了

68、二叉树的最短路径

/a45872055555/article/details/38560651

题目描述：当左子树为空的时候，该树的深度为右子树的深度+1，不能直接就返回0！

题目解析：

因此当遍历某一个节点的左右子树的时候，如果一个深度返回0，就返回另一个深度值+1。

70、路径和

/a45872055555/article/details/38561153

题目描述：从根结点到叶节点的路径长度和等于sum

题目解析：

要考虑根结点为NULL，和结点信息为负数的情况，因此唯一判断成功的条件是： if (root->val == sum && root->left == NULL && root->right == NULL)

71、路径和2

/a45872055555/article/details/38561619

输出所有的路径

题目解析：我们可以用栈来实现，当然在C++中不能访问栈内除栈顶元素外的其他元素，我这里自己定义的结构体，可以访问。

更好的方法是用vector容器来放元素。并且当我们传递vector副本的时候就无序担心入栈出栈问题。

72、二叉树转化成链表

/a45872055555/article/details/38563269

题目解析：

这道题和剑指offer上的一个题类似，那里是先序遍历，而这里是中序遍历。

一定要有模块的思想，我们先将左子树进行转化，那么当前循环就能看成左子树已经是链表了，通过遍历找到尾结点即可。

73、不同的子序列

/a45872055555/article/details/38564297

题目描述：不改变相对位置的情况下，s通过删除元素转化成t，有多少中转化方式

题目解析：

（1）深度优先，当s[i] == t[j]的时候，可以选择可以不选择。时间复杂度太高

（2）对于两个子串的问题应该考虑动态规划：

动态规划和正常的深度优先相比，就跟从下到上和从上到下的关系一样。深度优先是遍历到结尾的时候再统计个数，而动态规划是在[i,j]为截止，统计个数，基于这个思想再尝试找动态规划方程。

当s[i] == t[j]时，可以选择s[i]可以不选： transArr[i][j] = transArr[i-1][j-1]+transArr[i-1][j];

当s[i] != t[j]时， transArr[i][j] = transArr[i-1][j];

最后也是很关键的一点是边界条件的确定。

74、树的每一层构成一个链表

/a45872055555/article/details/38570805

（1）利用队列，就有每一层的个数，一层一层链接

（2）也可以利用上一层已经链接好的链表，就能通过next找到下一层

75、杨辉三角

/a45872055555/article/details/38572475

看成二维数组，然后利用容器来添加。

if(j == 0 || j == i) cur.push_back(1);
else cur.push_back(ans[i - 1][j] + ans[i - 1][j - 1]);

76、类似杨辉三角的结构求最小路径和

/a45872055555/article/details/38581239

题目解析：

（1）递归方法：我们将每一个都遍历到根结点，然后更新路径和minsum

（2）可以利用贪心算法，第i层每一个结点都是根到该节点的最小路径和，那么求第i+1层的时候，就由两个父节点的最小值加上当前结点

int min = triangle[i-1][j] > triangle[i-1][j-1] ? triangle[i-1][j-1] : triangle[i-1][j];
triangle[i][j] += min;

------但是要注意边界，起始点和终止点只有一个父节点。

77、股票购买抛售问题

/a45872055555/article/details/38582193

题目描述：其实就是在一个数组中找到两个数，求最大值

题目解析：

（1）两层循环，以当前i为起点，找到i后的最大值做差。

（2）类似动态规划的问题，我们以i为终止点呢？那么就记录i前的最小值。

（3）逆向思维，我们从后向前遍历，记录i后的最大值，然后max - a[i]

78、股票购买抛售问题II

/a45872055555/article/details/38582675

题目描述：可以多次购买和抛售

题目解析：既然可以多次买进卖出，我们画出价格变动波形，其实就是让我们求所有上升曲线和

79、股票购买抛售问题III

/a45872055555/article/details/38685821

题目描述：最多两次购买，求最大收益

题目解析：

（1）既然两次购买，肯定这两次之间有中间值为分割点，那么我们就让一次让0...n为分割点，两边都求取一次买卖最大值然后求和。

（2）时间复杂度高，是否能通过辅助空间来优化？既然有[0...i]的最大值，求[0...i+1]就很方便了。但是求[i+1...n]就不可能了，不能将数组缩小。

但如果我们你想求出数组呢？也就是设置两个数组，一个正向的收益最大，一个逆向的收益最大，然后l[i]+r[i]就能立即求得该点的最大值。

80、二叉树的路径最大值

/a45872055555/article/details/38586355

路径可以是左子树路径加上根结点机上右子树路径

题目解析：

我们要求最大值，最好不要让函数直接返回最大值，这样就没办法求得左右子树的单条最长路径值。因此我们将最值设成私有变量，函数返回算上父节点的最大路径和。

而在函数中统计最大值的时候，就要考虑“单独父节点”“父节点加上左子树” “父节点加上右子树” “父节点加上左子树加上右子树” “已经求得的最大值” 几个之间选取最值更新max。

有个小点需要注意，要让最值初始化为INT_MIN / 2。不能为最大负整数，因为+/- 一个数后会越界。并且当传入的为空指针的时候要返回为0才更合适。

81、回文字符串

/a45872055555/article/details/38587269

只考虑字符串中的字母和数字，并且也要忽略大小写问题。

题目解析：

很简单，左右指针即可，注意判断条件就好。

82、最长连续序列

/a45872055555/article/details/38588635

题目描述：一个无序数组，找到“有序”状态下最长连续的程度，但要求时间复杂度为O(n)

题目解析：

如果通过排序的话就很好解决的了，但是时间复杂度不符合要求，就要通过空间换取时间的策略

（1）设置一个数据，用于hash表示，将所有的数组映射到上面后，然后遍历hash表进行统计最长。但是太浪费空间

（2）可以用c++中的unordered_set来表示，这个比set好，set是基于红黑树实现的，查找时间为logn。先将元素插入到里面，然后在找一个元素，找到后set集中该位置标记清除，并左右查找。

int findBound(int n,bool asc){
int count = 0;
while((n) != ()){
count++;
(n);
if(asc)
n--;
else
n++;
}
return count;
}

83、所有根结点到叶节点路径和的和

/a45872055555/article/details/38589371

递归求解即可，但要注意递归截止的条件是叶节点！也就是左右子树都为空的时候，这点容易判断失误

84、将一个子串划分成回文子串

/a45872055555/article/details/38590447

s = "aab"

可以分解成

["aa","b"],

["a","a","b"]

题目解析：

（1）递归算法：

这里就要在递归中用到for循环了。先选取i位置当前一个元素，然后递归回来后，找到一i其实位置的回文串，才从这个位置深度优先遍历。

（2）动态规划

由于上面肯定要重复计算[j,k]是否为回文串，这里就先通过数组进行预处理，判断[i,j]是否为回文串。注意，这里不是直接用动态规划来直接求结果，而是为了保存中间值。规则选取的不同，动态规划的计算方法也不同，甚至能不能用动态规划也要另说。

85、将一个子串划分成回文子串II

/a45872055555/article/details/38610915

题目描述：求最小的切割方法，使得每个子串都是回文子串

题目解析：

（1）利用上题的解法，求出所有的切割方式，然后找出容器中元素个数最少的一个，也就得到了最小切割数。

（2）动态规划，这里定义dp[i]为{i...n}的切割方法，我们还是要设置一个判断回文串的二维数组，那么我们就可以很容易的通过 s[i] == s[j] && (j-i<2 || matrix[i+1][j-1])知道中间点j划分成了左右两边。而对于统计个数的dp[i]我们则有 dp[i] = min(dp[i],dp[j+1]+1);

-----------贪心算法，一次让i向后遍历尽量多的长度得到回文串，然后剩余的求解最小切割。对于“aaabaa”会用到两次切割，但实际上一次就可以了。所以贪心算法是行不通的。

86、加油站

/a45872055555/article/details/38611601

题目解析：

优化点：虽然分了加多少油，耗费多少油，我们可以直接将其合并，转化为起始站有效加的油。

（1）每次都以一个结点当成起始点，然后向后遍历，当不符合的时候，再向后找。O(n^2)

（2）由于题目中的结果是唯一的，那么我们可以让其从0开始求和，当sum变为小于0的时候，就以后面的为新的起点求和，直到求到n位置。这里不用循环统计了，因为题目给的数据保证了结果的唯一性。

（3）我们可以选择任意一个为起点，当求和到0的时候，起点向前更新，并sum+=arr[--begin]。当大于0了，end还继续向后移动。这个方法很巧妙。

87、分配糖果问题

/a45872055555/article/details/38614051

题目解析：

（1）笨方法是递增的时候向前遍历，糖果依次增加，递减的时候先赋值1，然后再向前调整，时间复杂度高。

（2）两趟遍历：第一趟从前向后，只调整递增序列，当递减的时候都赋值为1。第二趟从后向前遍历，也只调整递增序列，不过判断条件要加强 arr[i]>arr[i+1] && num[i]<=num[i+1] ======> num[i] = num[i+1]+1

（3）通过记录到递增最大值的数，然后计算递减区域的数据……不时的更新……比较复杂，不多说了，但这个方法没有用到辅助空间。

88、单个数字

/a45872055555/article/details/38614499

通过异或来判断

89、单个数字II

/a45872055555/article/details/38614847

题目描述：数组中每个数据都重复了三遍，只有一个只出现了一次

题目解析：

（1）题目难度比较大，通过简单的异或是没办法想明白的。不过我们可以统计所有数字的每一位出现的次数，最后将每一位%3，再合并就能得到想要的结果。

（2）另一种方法很巧妙。

90、判断链表是否有环

/a45872055555/article/details/38615219

利用快慢指针即可

91、链表重新排序

/a45872055555/article/details/38616909

题目描述： Given {1,2,3,4} , reorder it to {1,4,2,3} .

题目解析：

先将链表分成两半，将后半段翻转，然后将两个链表合并就行了。

92、插入法排序链表

/a45872055555/article/details/38621633

和数组的插入排序一样，但要注意指针的赋值。

93、逆波兰式求值

/a45872055555/article/details/38622967

直接利用栈来求解就行。碰到运算符就出栈并把结果入栈。

但要注意将字符串转换成数字。

94、字符串中的单词序反转

/a45872055555/article/details/38625707

题目解析：

（1）字符串整体反序，然后将单词反序

（2）一个单词一个单词存入，并添加空格

95、三个数的和等于0

/a45872055555/article/details/38637031

其实可以利用两个数的和等于定值来求解类似题目

因为有重复数据，所有就要时刻考虑重复数据的问题。因此要经常加上while(i < j && num[i] == num[i-1])

96、找到三个数使其和与target最接近

/a45872055555/article/details/38637635

由于三个数不重复，我们让i指向了一个值，然后j指向i+1，k指向n-1，然后与上题类似，进行相应的左移右移，同时要更新最近差值

97、四个数的和

/a45872055555/article/details/38638045

和上一题的方法类似，固定两个点，然后前后指针指向第三个和第四个点。要注意去重问题，由于这里一共只能选固定的数，因此我们无论是固定的两个点，还是前后指针的点都要去重

98、k个结点一组翻转链表

/a45872055555/article/details/38640157

先遍历整个链表统计有多少个数据，然后决定翻转的次数，但是要注意断点的指向问题，要设置指针的指针来保存

99、两个数相除，但不能用乘除法

/a45872055555/article/details/38640517

通过加减法来做，并有一个计数器，但是一个一个相加就会超时。我们可以用二分法：一次加上上次求和的倍数，那么count += count。如果求和大于被除数的时候，就剪掉sum，恢复除数的值，并从1开始计数。

100、链接所有单词的子串

/a45872055555/article/details/38642143

我们用map来查找单词，并且还要不能使中间的数据重复，因此要定义两个map来计数。

map<string,int> word_count; //记录L字符串中每一个元素出现的个数
int word_size = L[0].size();
for(int i = 0;i < l_size;i++)
++word_count[L[i]];
map<string,int> counting; //记录查找过程中的个数
for(int i = 0;i <= (int)()-l_size*word_size;i++){
();
int j;
for(j = 0;j < l_size;j++){
string word = (i+j*word_size,word_size);
if(word_count.find(word) != word_count.end()){
++counting[word];
if(counting[word] > word_count[word])
break;
}else
break;
}
if(j == l_size)
res.push_back(i);
}

101、字符串相乘

/a45872055555/article/details/38644835

（1）模拟整数的乘法

（2）先乘法操作，然后求和处理进位

102、跳跃游戏II

/a45872055555/article/details/38647555

（1）借助于跳跃游戏I里面的方法，我们从i开始跳的时候，能跳转到i+a[i]，那么在这个之间的时候就一直更新maxlen，不再count++，当超过i+a[i]的时候，count+1，并且终点取max = maxlen

（2）贪心算法

从从前向后遍历，碰到第一个可以一口气超过n-1的位置，然后以这个位截止点，在从第一个开始遍历。

103、旋转图像

/a45872055555/article/details/38655857

（1）画出图形一个一个点的移动即可。

（2）巧妙的方法：沿着副对角线翻转，再沿着中间的水平线翻转

104、合并区间间隔

/a45872055555/article/details/38657353

先对区间进行排序，然后判断即可

105、插入区间

/a45872055555/article/details/38657921

如果新插入的范围能够使原始范围合并，就合并之。但要注意分情况：整体在i结点前，整体在i结点后，< 以及>=。

----也可以将插入的区间，连同原始区间进行排序再合并，就转化成上面的情况了

106、螺旋矩阵填充数据

/a45872055555/article/details/38658237

行列一个一个填充即可

107、循环右移链表

/a45872055555/article/details/38661097

题目解析：

Given 1->2->3->4->5->NULL and k = 2 ,
return 4->5->1->2->3->NULL .

题目很好理解，不过最后一个元素的指针要指到头结点，不用遍历两遍，找到分割结点后再遍历后面的。当我们第一遍求个数的时候，就将最后一个结点给处理了，让他指到头结点。

108、唯一路径II

/a45872055555/article/details/38661927

题目描述：如果矩阵中有障碍物，判断一共有多少路径到达终点

题目解析：

（1）将全矩阵初始化为0.

（2）如果出发点就有障碍物就一定不可达。

（3）初始化第一个行和第一列，但要注意：如果某一个结点有障碍物，则其后或其下全为0。

（4）整个遍历数组，当没有障碍物的时候，为上面的数和左面的数之和。

109、最小路径和

/a45872055555/article/details/38662505

找一条路径，从左上到右下使其和最小。

还是利用动态规划：f[i][j] = min(f[i-1][j], f[i][j-1]) + a[i][j]

110、合并两个链表

/a45872055555/article/details/38662741

（1）避免空指针的输入

（2）为了简化判断，循环前处理好头结点

111、二进制相加

/a45872055555/article/details/38663835

从后向前一点一点相加，注意一个长一个短，还有进位的情况。利用string来做的话很方便， res = (char)(tmp+'0') + res;

112、数组表示的数字加1

/a45872055555/article/details/38664699

和整数的加法一样，但容器在头操作要用insert函数。

113、partition方法处理链表

/a45872055555/article/details/38665947

将链表分成两个结点后再合并是个很好的思路。不过整个分割后，可能其中一个链表为null，并且当处理到大结点的时候，可能最后一个大节点的next指针不为空，也应该处理。题目不难，要处理好细节。

114、译码方式

/a45872055555/article/details/38678563

动态规划方式来做：

典型是要求什么，那么我们就设辅助方程代表的是什么，还有找寻i+1和i之间的关系，关系的确定一般通过数据的取值范围来分情况求和。

先不考虑边界，就考虑一般情况：

[i+1] == '0'，如果S[i]为'1'或者'2'，F[i+1] = F[i]，否则无解；

2.如果S[i]为'1'，F[i+1] = F[i] + F[i-1]（例如"xxxxxx118"，可以是"xxxxxx11" + "8"，也可以是"xxxxxx1" + "18"）；

3.如果S[i]为'2'，当S[i+1] <= '6'时，F[i+1] = F[i] + F[i-1] （最大的Z为"26"，"27""28""29"不存在），当S[i+1] > '6'时，F[i+1] = F[i] （例如"xxxxxx28"，只能是"xxxxxx2" + "8"）。

115、字符交换

/a45872055555/article/details/38679759

   great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

不能利用树的前序中序后序等遍历方法。因为那里要求找到后对其，但这里由于交换多次不会造成对其。

（1）暴力求解方法，以某个点i分割，然后递归判断。

（2）动态规划优化：

dp[i][j][k] 代表了s1从i开始，s2从j开始，长度为k的两个substring是否为scramble string。

有三种情况需要考虑：

1. 如果两个substring相等的话，则为true

2. 如果两个substring中间某一个点，左边的substrings为scramble string，同时右边的substrings也为scramble string，则为true

3. 如果两个substring中间某一个点，s1左边的substring和s2右边的substring为scramble string, 同时s1右边substring和s2左边的substring也为scramble string，则为true

116、恢复ip地址

/a45872055555/article/details/38683237

深度优先算法，一个一个递归的去判断，如果在深度为4的时候，能遍历到最后一个元素，就正确。当然中间还要判断三位数的时候的范围。

117、恢复二叉搜索树

/a45872055555/article/details/38685035

由于二叉搜索树有两个结点被交换，请恢复

做题要看研究的对象，既然是二叉搜索树，那么前序遍历就会得到有序的数据。如果借用数组的话，就将结点输出，然后找到两个不符顺序的点将其交换。通过这里仔细分析数组，可以得到启发，前序遍历中，找到第一个当前结点小于前一个结点的，那么前一个结点要交换；再遍历，找到也是当前结点小于前一个结点的，那么当前结点要交换。至于怎么选取设置标记即可。

118、单词梯

/a45872055555/article/details/38688063

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",

题目解析：图的最短路径问题，我们可以构建一个无向图，判断可达性。但由于数据太大的时候，很多比较是没必要的。

我们可以用“树的深度优先”来判断。改变数据的每一位，如果在数组中，就将改变的单词添加到队列中，当计数个数变为0的时候，就level++，进入下层的查找。

119、单词梯II

/a45872055555/article/details/38691523

输出所有的最短路径

可以利用深度优先得出路径结果，再从容器中选出最短的路径值。

120、包围的区域

/a45872055555/article/details/38695007

利用深度优先或广度优先，将外围的区域都赋值为另一个字母，最后对所有的进行处理。

121、克隆图

/a45872055555/article/details/38702849

利用map来处理，第一遍创建结点，第二遍的时候再进行链接

122、赋值带有随机指针的链表

/a45872055555/article/details/38704081

其余详见：

/a45872055555/article/category/2374471

秒客网

LeetCode 方法详解

相关文章