请注意，此文章尚未完成。 当此文章完结时，此声明将被删除。

因为我在做LeetCode的时候，是断断续续的做的，周期比较长。

所以有时候做到后面，前面的就忘了怎么做了。

算法的训练也需要一个反复巩固的过程，所以就有了这篇文文章。

这篇文章主要记录Leetcode题目的问题概要和解决思路，不包含代码，只当做一个HINT。

思路标题上有*的是我认为比较重要的思路，要记得。

1. 两数之和

1. 问题

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

1.2. 思路1

暴力，能过，不解释。

1.3. 思路2*

搞一个map，key为数值，value为这个数值对应的索引。

遍历原数组，每遍历到一个元素a，看看 target - a 在不在map里，在的话这这俩数对应的索引就是答案。如果不在的话，就把a和其索引加入map。

2. 两数相加

2.1. 问题

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

2.2. 思路

模拟加法操作，逐位相加就可以。

同时遍历两个链表，都有值就相加，如果其中一个是null了，就记0。

注意下进位，然后全加完最后还要再看看有没有进位。

3. 无重复字符的最长子串

3.1. 问题

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

注意下是子串，不是子序列。

3.2. 思路*

滑动窗口思想，用一个映射 int index[128] 记录每个字符上一次出现位置的下一个索引。如未出现的字符，上一个出现位置的下一个索引是0；如一个字符 k上一次出现位置索引为2，则 index[k] = 3。

遍历字符串，假设当前记录长度的起点索引为 i。

每遍历到一个字符alpha，设当前索引为j，看看index[alpha]是不是0。

如果是0，说明alpha从未出现过，记录这次出现的下一个索引 index[alpha] = j + 1，继续遍历。

如果不是0，说明这个字符出现过了，比较一下和当前起点i 和 index[alpha] 的大小关系。如果i < index[alpha]，说明这个字符在当前记录的长度中出现过，则修改起点i = index[alpha]，重新记长；若i >= index[alpha]，说明这个字符是在当前记录长度的起点前出现的，不用理。这一步的两种情况，无需特意判断，只需要i = max(i, index[alpha]) 就可以了。

上面的过程，记录长度每次增加记得更新最大长度。

映射也可以用Map，写法略有差别，思想一样。

7. 整数反转

7.1. 问题

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

注意题目中说假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。，所以不能把原数转成long类型再做，虽然简单。

7.2. 思路

设初始结果为0，每次弹出最低位，然后把当前算完的结果乘10，加上这个最低位。

注意如果原数是负数，负号其实是不需要单独处理的，因为每次取余的结果都是负责，乘10和加法后还是负的，不用特意处理，如-100 % 3 = -1。

问题在于如果处理溢出，以上溢为例，记int类型最大数为MAX_VALUE，当前结果为ans，原数在当前步骤为x（因为每步后会有x /= 10，所以看当前步骤的x）。

那么如果ans < MAX_VALUE / 10，当前步骤完成后一定不会溢出，因为 ans * 10 + x % 10不可能溢出；如果ans > MAX_VALUE / 10，那么当前步骤完成后一定会溢出，因为ans * 10已经溢出了，再加x % 10也是溢出的；如果ans = MAX_VALUE / 10，那么ans * 10 以后，加x % 10，如果X % 10 <= 7不会溢出，x % 10 > 7就会溢出。

下溢同理，只是最后的判断阈值不是7，而是-8。

9. 回文数

9.1. 问题

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

9.2. 思路1

负数肯定不是回文数。

对于非负数，把它转成字符串，然后双指针比较两头的元素。

一旦出现有不同的数字，返回false，如果双指针都到中间了还没有返回false，就返回true。

9.3. 思路2

负数肯定不是回文数。

对于非负数，直接把数字反转，例如123反转后为((0*10+3)*10+2)*10+1即321，用这个方法反转出来一个新数，比较新数和原数，如果相等说明原数是回文数。

注意原数翻转后可能的溢出问题，不过Java或C/C++等语言溢出后会来个“轮回”，正数变负数，负数变正数，所以肯定与原数不相等，所以溢出问题也可以不处理。

9.4. 思路3*

负数肯定不是回文数。

对于非负数，我们反转一半，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。

要判断下什么时候反转完一半了，当原始数字小于反转后的数字时，就意味着我们已经处理了一半位数的数字。

注意一下，这种方法对于以0结尾，但不是0的数不适用，所以要特殊处理下这类数，这类数肯定不是回文数。

13. 罗马数字转整数

13.1. 问题

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

13.2. 思路

做一个map映射，key为字母，value为字母对应的数值。

遍历字符串，每遇到一个字符就加上其对应的数值，如果发现前一个字母比当前字母小，就减去两倍的前一个字母对应的数值，因为一共多加了两次。

14. 最长公共前缀

14.1. 问题

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

14.2. 思路

以第一个字符串长度为基准，对于第一个字符串的第i, (0<i<第一个字符串长度)个字符，遍历剩下的所有字符串。

如果对应i位置的字符都相等，则当前最大长度加1。

如果在第一个字符串时就没元素了，或者在其他字符串对应的i位置，发现不与第一个字符串的相等， 那么当前记录的最大长度就是最长公共前缀的长度。

用当前记录的最大长度截取任意一个字符串，一般第一个就行，并返回。

此题貌似网络上有挺多思路，但是时间复杂度都为O(S)，S为所有字符串中的所有字符和。因为没有时间复杂度上的优化，所以我认为研究太多种算法不必要，会一种就可以了。

19. 删除链表的倒数第N个节点

19.1. 问题

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

19.2. 思路*

双指针法。两个指针同时指向头结点，其中一个指针先走n个结点，然后两个指针一起走，当先走的指针到达最后一个结点时，后走的指针指向的就是要删除结点的前一个结点，删除就可以了。

20. 有效的括号

20.1. 问题

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

20.2. 思路

用一个栈，遇到左括号就入栈，遇到右括号就栈顶左括号出栈，比对一下，匹配就pass，不匹配就直接返回false。

如果顺利遍历完整个字符串，再最后看一下栈有没有清空，空了就返回true，反之返回false。

21. 合并两个有序链表

1. 问题概要

给定两个有序的链表，要求合并成一个有序链表（不新建结点），返回新有序链表头结点。

2. 思路1

搞一个新链表头结点，比较两个原链表第一个结点。

把小的结点用尾插法插到新链表上，然后从原链表中摘掉这个结点。

重复上面的操作，直到有一个原链表为空，然后再把还有元素的那个原链表直接接到新链表后面。

3. 思路2*

搞一个新链表头结点，接到第一个链表前。

然后不断地把第二个链表中的结点，插入到第一个链表对应的位置上。

4. 思路3*

用递归的思想，比较两个链表的第一个结点，返回小的那个结点。

在返回这个结点前，设这个结点是P，则令p.next等于，以p.next为第一个结点的链表和另一个链表，两个链表第一个结点中小的那个。

如果一个链表为空，则直接返回另一个链表第一个结点。

26. 删除排序数组中的重复项

26.1. 问题

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

26.2. 思路

双指针，快慢指针。两个指针都从头开始，快指针遍历数组，把不重复的元素赋值到慢指针的位置，然后两个指针一起后移一下。

27. 移除元素

27.1. 问题

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

27.2. 思路

双指针，快慢指针与上一题类似。

两个指针都从头开始，快指针遍历不等于val的元素，赋值到慢指针的位置上，然后俩指针一起后移。

28. 实现 strStr()

28.1. 问题

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

这个题的需求有现成的库，但是这个题要是用库就没意义了。

28.2. 思路1

朴素匹配算法，暴力，不解释。

28.3. 思路2*

KMP算法。

28.4. 思路3*

Rabin-Karp算法。

32. 最长有效括号

32.1. 问题

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

32.2. 思路1

之前写过一个题，Leetcode 20. 有效的括号，知道怎么判断一个括号字符串是不是有效的。

纯暴力，很简单，对所有子串组合应用一次上面题目的算法，找最长的，不解释。

32.3. 思路2*

动态规划。dp[i]表示以第i`个字符结尾的最长有效括号长度。

原字符串s中，s[i]如果是(，则dp[i]一定是0，因为Java中int数组中值默认就是0，所以不用管。

如果s[i]是)，就有两种情况，s[i - 1]是(或s[i - 1]也是)。前者dp[i]就是dp[i - 2] + 2；后者除了有dp[i - 2] + 2外，还要假设以再往前一个位置字符结尾的最长有效括号长度。

注意不要越界就行了。

32.4. 思路3*

使用栈，栈底元素为当前计算有效括号长度起点的前一个位置，初始为-1，其他元素为左括号索引。

遇到左括号，就入栈这个左括号的索引。

遇到右括号，栈顶元素出栈（这个出栈元素就不要了）。此时如果栈未空，当前栈顶元素就是这个右括号对应左括号的前一个索引，相减即为这一段有效括号的长度；如果此时栈空，说明这个右括号没有对应的左括号，匹配失败，就把这个右括号的索引入栈，作为新的有效括号长度计算起点位置的前一个索引。

32.5 思路4

Leetcode上的解法4，写下来是因为这个算法与其他算法在时间复杂度同是O(n)的情况下，它的空间复杂度是O(1)。下面的思路摘自Leetcode官方题解。

在这种方法中，我们利用两个计数器 leftleft 和 rightright 。首先，我们从左到右遍历字符串，对于遇到的每个(，我们增加 leftleft 计算器，对于遇到的每个)，我们增加 rightright 计数器。每当 leftleft 计数器与 rightright 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。如果 rightright 计数器比 leftleft 计数器大时，我们将 leftleft 和 rightright 计数器同时变回 00。

接下来，我们从右到左做一遍类似的工作。

35. 搜索插入位置

35.1. 问题

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

35.2. 思路1

顺序查找就ok。

35.3. 思路2*

二分法。

38. 外观数列

38.1. 问题

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

1
2
3
4
5
1
11
21
1211
111221

1 被读作 "one 1" ("一个一") , 即 11。

11 被读作 "two 1s" ("两个一"）, 即 21。

21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。

注意：整数序列中的每一项将表示为一个字符串。

38.2. 思路1

n的范围不大，可以打表枚举。

38.3. 思路2

模拟拼接字符串就行，注意Java用StringBuffer/StringBuilder会快一些。

50. Pow(x, n)

50.1. 问题

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

50.2. 思路*

这个题给的范围很大，但是数据没有那么大，也没要求取余。

就是快速幂的思想。不管次方是正还是负，都当正数算，如果是负数就最后取倒数。

-

注：

Java 中 的 >>，保持符号位不变，除符号位，空位补 0，就相当于除以 2。

Java 中对 -1 进行 >> 操作，结果始终为 -1（特例）。

Java 中的负数取余，余数为正，等价于不看负号，当成正数取余，最后再加上负号。

因此，if 的判断条件不可为 pp % 2 == 1，因为当 pp 为负时，pp % 2 可能为 -1，或改条件为 pp % 2 != 0。

常规对 pp 的右移操作，应改为 pp /= 2，避免 pp >>= 1 导致 pp 恒为 -1，死循环。

-

另官方解法：使用 long 类型转换 n，避免 int 最小值取反溢出问题。

取反 n 后采用常规快速幂，结果取倒数。

53. 最大子序和

53.1. 问题

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

53.2. 思路1*

一次遍历，动态规划思想，可以在原数组上操作。

将nums[i]的含义改为到以nums[i]为最后一个元素的最大子序和。

如果nums[i - 1] > 0，那令nums[i] += nums[i - 1]就是以nums[i]为最后一个元素的最大子序和；

如果nums[i - 1] < 0，那nums[i] + nums[i - 1] < nums[i]，此时以nums[i]为最后一个元素的最大子序和就是nums[i]本身，毕竟一个数加上一个负数肯定是变小的，什么都不做就好。

每遍历过一个元素，就更新一次当前记录的最大子序和。

53.3. 思路2

进阶提示里的，让你用更好的分治法。

我没有学这个方法，虽然进阶提示称分治法更好，但官方题解给出的分治算法不仅思路难、代码量大、而且时间复杂度也不不如动态规划，只有空间复杂度好一点。

通常来说我们更常用以空间换时间，所以这个分治法我直接放弃了。

58. 最后一个单词的长度

58.1. 问题

给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。

如果不存在最后一个单词，请返回 0 。

说明：一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。

58.2. 思路

先把首尾的空格删了，就很简单了，不解释。

66. 加一

66.1. 问题

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

66.2. 思路

在原数组上模拟加法操作就行，注意进位。

如果形如999这样的数，加1后多一位，就要新new一个数组来放答案。

70. 爬楼梯

70.1. 问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

70.2. 思路1

这个题有规律的，斐波那契数列。

70.3. 思路2*

不考虑规律，就按规则算，是个动态规划问题。

令dp[i]表示跳到第i阶的总方法数，慢慢递推到最后就好了。

状态转移方程为dp[i] = dp[i - 1] + dp[i - 2]，因为第i阶可以从第i - 1阶跳过来，也可以从第i - 2阶跳过来。

动态规划思想得到的状态转移方程其实就是斐波那契数列的算法，也算是验证了思路1。

130. 被围绕的区域

130.1. 问题

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

130.2. 思路*

这是一个比较简单的DFS问题。

要注意的一个技巧就是从边缘上的O为DFS起点，标记所有遇到的O，比较简单。

*写了但未写完的题目序号*

28