**Tags:** Array, Hash Table

题意是让你从给定的数组中找到两个元素的和为指定值的两个索引，最容易的当然是循环两次，复杂度为`O(n^2)`，首次提交居然是2ms，打败了100%的提交，谜一样的结果，之后再次提交就再也没跑到过2ms了。

题意是让你从给定的数组中找到两个元素的和为指定值的两个索引，最容易的当然是循环两次，复杂度为`O(n^2)`，首次提交居然是 2ms，打败了 100%的提交，谜一样的结果，之后再次提交就再也没跑到过 2ms 了。

classSolution {

}

利用HashMap作为存储，键为目标值减去当前元素值，索引为值，比如`i = 0`时，此时首先要判断`nums[0] = 2`是否在map中，如果不存在，那么插入键值对`key = 9 - 2 = 7, value = 0`，之后当`i = 1`时，此时判断`nums[1] = 7`已存在于map中，那么取出该`value = 0`作为第一个返回值，当前`i`作为第二个返回值，具体代码如下所示。

利用 HashMap 作为存储，键为目标值减去当前元素值，索引为值，比如`i = 0`时，此时首先要判断`nums[0] = 2` 是否在 map 中，如果不存在，那么插入键值对`key = 9 - 2 = 7, value = 0`，之后当`i = 1`时，此时判断`nums[1] = 7` 已存在于 map 中，那么取出该`value = 0`作为第一个返回值，当前`i`作为第二个返回值，具体代码如下所示。

classSolution {

题意我也是看了好久才看懂，就是以链表表示一个数，低位在前，高位在后，所以题中的例子就是`342 + 465 = 807`，所以我们模拟计算即可。

题意我也是看了好久才看懂，就是以链表表示一个数，低位在前，高位在后，所以题中的例子就是`342 + 465 = 807`，所以我们模拟计算即可。

题意是计算不带重复字符的最长子字符串的长度，开辟一个hash数组来存储该字符上次出现的位置，比如`hash[a] = 3`就是代表`a`字符前一次出现的索引在3，遍历该字符串，获取到上次出现的最大索引（只能向前，不能退后），与当前的索引做差获取的就是本次所需长度，从中迭代出最大值就是最终答案。

题意是计算不带重复字符的最长子字符串的长度，开辟一个 hash 数组来存储该字符上次出现的位置，比如`hash[a] = 3`就是代表`a` 字符前一次出现的索引在 3，遍历该字符串，获取到上次出现的最大索引（只能向前，不能退后），与当前的索引做差获取的就是本次所需长度，从中迭代出最大值就是最终答案。

classSolution {

**Tags:** String

题意是寻找出字符串中最长的回文串，所谓回文串就是正序和逆序相同的字符串，也就是关于中间对称。我们先用最常规的做法，依次去求得每个字符的最长回文，要注意每个字符有奇数长度的回文串和偶数长度的回文串两种情况，相信你可以很轻易地从如下代码中找到相关代码，记录最长回文的始末位置即可，时间复杂度的话，首先要遍历一遍字符串，然后对每个字符都去求得最长回文，所以时间复杂度为`O(n^2)`。

如果利用暴力法遍历所有字串是否回文的情况这道题肯定是`Time Limit Exceeded` 的，那么我们是否可以把之前遍历的结果利用上呢，那么动态规划的想法就呼之欲出了，我们定义`dp[i][j]` 的意思为字符串区间`[i, j]`是否为回文串，那么我们分三种情况：

如果利用暴力法遍历所有字串是否回文的情况这道题肯定是`Time Limit Exceeded` 的，那么我们是否可以把之前遍历的结果利用上呢，那么动态规划的想法就呼之欲出了，我们定义`dp[i][j]` 的意思为字符串区间`[i, j]`是否为回文串，那么我们分三种情况：

1. 当`i == j` 时，那么毫无疑问`dp[i][j] = true`；

马拉车算法(Manacher's Algorithm)

3. s = "abcde"，最长回文长度为`1`，即单个字符本身。

这个问题等同于LeetCode上的[Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring)，其相关题解可以查看这里：[传送门](https://github.com/Blankj/awesome-java-leetcode/blob/master/note/005/README.md)

这个问题等同于 LeetCode 上的[Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring)，其相关题解可以查看这里：[传送门](https://github.com/Blankj/awesome-java-leetcode/blob/master/note/005/README.md)

以上问题的传统思路大概是遍历每一个字符，以该字符为中心向两边查找，其时间复杂度为`O(n^2)`，效率很差。

1975年，一个叫 Manacher 的人发明了 Manacher 算法（中文名：马拉车算法），该算法可以把时间复杂度提升到`O(n)`，下面我以我理解的思路来讲解其原理。

1975 年，一个叫 Manacher 的人发明了 Manacher 算法（中文名：马拉车算法），该算法可以把时间复杂度提升到`O(n)`，下面我以我理解的思路来讲解其原理。

题意是给你一个整型数，求它的逆序整型数，而且有个小坑点，当它的逆序整型数溢出的话，那么就返回0，用我们代码表示的话可以求得结果保存在long中，最后把结果和整型的两个范围比较即可。

题意是给你一个整型数，求它的逆序整型数，而且有个小坑点，当它的逆序整型数溢出的话，那么就返回 0，用我们代码表示的话可以求得结果保存在 long 中，最后把结果和整型的两个范围比较即可。

classSolution {

题意是把一个字符串转为整型，但要注意所给的要求，先去除最前面的空格，然后判断正负数，注意正数可能包含`+`，如果之后存在非数字或全为空则返回`0`，而如果合法的值超过int表示的最大范围，则根据正负号返回`INT_MAX`或`INT_MIN`。

题意是把一个字符串转为整型，但要注意所给的要求，先去除最前面的空格，然后判断正负数，注意正数可能包含`+`，如果之后存在非数字或全为空则返回`0`，而如果合法的值超过 int 表示的最大范围，则根据正负号返回`INT_MAX` 或`INT_MIN`。

classSolution {

**Tags:** Math

题意是判断一个有符号整型数是否是回文，也就是逆序过来的整数和原整数相同，首先负数肯定不是，接下来我们分析一下最普通的解法，就是直接算出他的回文数，然后和给定值比较即可。

}

好好思考下是否需要计算整个长度，比如1234321，其实不然，我们只需要计算一半的长度即可，就是在计算过程中的那个逆序数比不断除10的数大就结束计算即可，但是这也带来了另一个问题，比如10的倍数的数10010，它也会返回`true`，所以我们需要对10的倍数的数再加个判断即可，代码如下所示。

好好思考下是否需要计算整个长度，比如 1234321，其实不然，我们只需要计算一半的长度即可，就是在计算过程中的那个逆序数比不断除 10 的数大就结束计算即可，但是这也带来了另一个问题，比如 10 的倍数的数 10010，它也会返回`true`，所以我们需要对 10 的倍数的数再加个判断即可，代码如下所示。

publicboolean isPalindrome(int x) {

**Tags:** String, Dynamic Programming, Backtracking

题意是让让你从判断`s`字符串是否正则匹配于`p`，这道题和[Wildcard Matching][044]很是相似，区别在于`*`，通配符的`*`是可以随意出现的，跟前面字符没有任何关系，其作用是可以表示任意字符串；而正则匹配的`*`不能单独存在，前面必须具有一个字符，其意义是表明前面的这个字符个数可以是任意个数，包括0个。首先我们用递归的方式来实现，其思路如下：

题意是让让你从判断`s`字符串是否正则匹配于`p`，这道题和[Wildcard Matching][044]很是相似，区别在于`*`，通配符的`*`是可以随意出现的，跟前面字符没有任何关系，其作用是可以表示任意字符串；而正则匹配的`*`不能单独存在，前面必须具有一个字符，其意义是表明前面的这个字符个数可以是任意个数，包括 0 个。首先我们用递归的方式来实现，其思路如下：

* 如果`s`和`p`都为空，那么返回`true`；

* 如果`s` 和`p`都为空，那么返回`true`；

* 如果`p`的长度为1，当`s`的长度也为1，并且他们首位匹配则返回`true`，否则返回`false`；

* 如果`p` 的长度为 1，当`s` 的长度也为 1，并且他们首位匹配则返回`true`，否则返回`false`；

* 如果`p`的第二个字符不为 '*'，如果`s`为空，那就返回`false`，首位匹配则返回递归调用他们去掉首位的子字符串，否则返回`false`；

* 如果`p`的第二个字符不为 '*'，如果`s`为空，那就返回`false`，首位匹配则返回递归调用他们去掉首位的子字符串，否则返回`false`；

* 如果`p`的第二个字符为 '*'，循环当`s`不为空，且首位匹配，如果递归调用是否匹配`s`字符串和`p`去掉前两位的子字符串，则返回`true`，否则`s`去掉首字母继续循环；

* 如果`p`的第二个字符为 '*'，循环当`s`不为空，且首位匹配，如果递归调用是否匹配`s`字符串和`p`去掉前两位的子字符串，则返回`true`，否则`s`去掉首字母继续循环；

* 返回递归调用`s`字符串和`p`去掉前两位的子字符串是否匹配。

* 返回递归调用`s`字符串和`p`去掉前两位的子字符串是否匹配。

classSolution {

我们可以把上面的思路更简单化，如下：

* 如果`s`和`p`都为空，那么返回`true`；

* 如果`s` 和`p`都为空，那么返回`true`；

* 如果`p`的第二个字符为`*`，由于`*`前面的字符个数可以为任意，那么我们先递归调用个数为0的情况；或者当`s`不为空，如果他们的首字母匹配，那么我们就递归调用去掉去掉首字母的`s`和完整的`p`；

* 如果`p`的第二个字符为`*`，由于`*`前面的字符个数可以为任意，那么我们先递归调用个数为 0 的情况；或者当`s`不为空，如果他们的首字母匹配，那么我们就递归调用去掉去掉首字母的`s`和完整的`p`；

* 如果`p`的第二个字符不为`*`，那么我们就老老实实判断第一个字符是否匹配并且递归调用他们去掉首位的子字符串。

* 如果`p`的第二个字符不为`*`，那么我们就老老实实判断第一个字符是否匹配并且递归调用他们去掉首位的子字符串。

classSolution {

}

另一种思路就是动态规划了，我们定义`dp[i][j]`的真假来表示`s[0..i)`是否匹配`p[0..j)`，通过思路1，我们可以确定其状态转移方程如下所示：

另一种思路就是动态规划了，我们定义`dp[i][j]`的真假来表示`s[0..i)`是否匹配`p[0..j)`，通过思路 1，我们可以确定其状态转移方程如下所示：

* 如果`p[j - 1] == '*'`,`dp[i][j] = dp[i][j - 2] || (pc[j - 2] == sc[i - 1] || pc[j - 2] == '.') && dp[i - 1][j];`；

* 如果`p[j - 1] == '*'`,`dp[i][j] = dp[i][j - 2] || (pc[j - 2] == sc[i - 1] || pc[j - 2] == '.') && dp[i - 1][j];`；

* 如果`p[j - 1] != '*'`，`dp[i][j] = dp[i - 1][j - 1] && (pc[j - 1] == '.' || pc[j - 1] == sc[i - 1]);`。

* 如果`p[j - 1] != '*'`，`dp[i][j] = dp[i - 1][j - 1] && (pc[j - 1] == '.' || pc[j - 1] == sc[i - 1]);`。

classSolution {

题意是罗马数字转整型数，范围从1到3999，查看下百度百科的罗马数字介绍如下：

题意是罗马数字转整型数，范围从 1 到 3999，查看下百度百科的罗马数字介绍如下：

* 相同的数字连写，所表示的数等于这些数字相加得到的数，如 Ⅲ=3；

* 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如 Ⅷ=8、Ⅻ=12；

* 小的数字（限于 Ⅰ、X 和 C）在大的数字的左边，所表示的数等于大数减小数得到的数，如 Ⅳ=4、Ⅸ=9。

那么我们可以利用map来完成罗马数字的7个数字符号：I、V、X、L、C、D、M和整数的映射关系，然后根据上面的解释来模拟完成即可。

那么我们可以利用 map 来完成罗马数字的 7 个数字符号：I、V、X、L、C、D、M 和整数的映射关系，然后根据上面的解释来模拟完成即可。

classSolution {

题意是让你从字符串数组中找出公共前缀，我的想法是找出最短的那个字符串的长度`minLen`，然后在`0...minLen`的范围比较所有字符串，如果比较到有不同的字符，那么直接返回当前索引长度的字符串即可，否则最后返回最短的字符串即可。

题意是让你从字符串数组中找出公共前缀，我的想法是找出最短的那个字符串的长度`minLen`，然后在`0...minLen`的范围比较所有字符串，如果比较到有不同的字符，那么直接返回当前索引长度的字符串即可，否则最后返回最短的字符串即可。

classSolution {

题意是让你从数组中找出所有三个和为0的元素构成的非重复序列，这样的话我们可以把数组先做下排序，然后遍历这个排序数组，用两个指针分别指向当前元素的下一个和数组尾部，判断三者和与0的大小来移动两个指针，其中细节操作就是注意去重。

题意是让你从数组中找出所有三个和为 0 的元素构成的非重复序列，这样的话我们可以把数组先做下排序，然后遍历这个排序数组，用两个指针分别指向当前元素的下一个和数组尾部，判断三者和与 0 的大小来移动两个指针，其中细节操作就是注意去重。

classSolution {

**Tags:** String, Backtracking

题意是给你按键，让你组合出所有不同结果，首先想到的肯定是回溯了，对每个按键的所有情况进行回溯，回溯的终点就是结果字符串长度和按键长度相同。

}

还有一种思路就是利用队列，根据上一次队列中的值，该值拼接当前可选值来不断迭代其结果，具体代码如下。

题意是让你删除链表中的倒数第n个数，我的解法是利用双指针，这两个指针相差n个元素，当后面的指针扫到链表末尾的时候，自然它前面的那个指针所指向的下一个元素就是要删除的元素，即`pre.next = pre.next.next;`，但是如果一开始后面的指针指向的为空，此时代表的意思就是要删除第一个元素，即`head = head.next;`。

题意是让你删除链表中的倒数第 n 个数，我的解法是利用双指针，这两个指针相差 n 个元素，当后面的指针扫到链表末尾的时候，自然它前面的那个指针所指向的下一个元素就是要删除的元素，即`pre.next = pre.next.next;`，但是如果一开始后面的指针指向的为空，此时代表的意思就是要删除第一个元素，即`head = head.next;`。

题意是判断括号匹配是否正确，很明显，我们可以用栈来解决这个问题，当出现左括号的时候入栈，当遇到右括号时，判断栈顶的左括号是否何其匹配，不匹配的话直接返回`false`即可，最终判断是否空栈即可，这里我们可以用数组模拟栈的操作使其操作更快，有个细节注意下`top = 1;`，从而省去了之后判空的操作和`top - 1`导致数组越界的错误。

题意是判断括号匹配是否正确，很明显，我们可以用栈来解决这个问题，当出现左括号的时候入栈，当遇到右括号时，判断栈顶的左括号是否何其匹配，不匹配的话直接返回`false`即可，最终判断是否空栈即可，这里我们可以用数组模拟栈的操作使其操作更快，有个细节注意下`top = 1;`，从而省去了之后判空的操作和`top - 1`导致数组越界的错误。

classSolution {

**Tags:** Linked List, Divide and Conquer, Heap

题意是合并多个已排序的链表，分析并描述其复杂度，我们可以用分治法来两两合并他们，假设`k`为总链表个数，`N`为总元素个数，那么其时间复杂度为`O(Nlogk)`。

题意是合并多个已排序的链表，分析并描述其复杂度，我们可以用分治法来两两合并他们，假设`k`为总链表个数，`N`为总元素个数，那么其时间复杂度为`O(Nlogk)`。

}

还有另一种思路是利用优先队列，该数据结构用到的是堆排序，所以对总链表个数为`k`的复杂度为`logk`，总元素为个数为`N`的话，其时间复杂度也为`O(Nlogk)`。

还有另一种思路是利用优先队列，该数据结构用到的是堆排序，所以对总链表个数为`k`的复杂度为`logk`，总元素为个数为`N`的话，其时间复杂度也为`O(Nlogk)`。