Leetcode OJ 刷题

Valid Palindrome吐槽一下Leetcode上各种不定义标准的输入输出(只是面试时起码能够问一下输入输出格式。。。)，此篇文章不是详细的题解，是自己刷LeetCode的一个笔记吧，尽管没有代码，可是略微难一点的都会标出主要思路，便于以后复习

PS:题目中有“水题”两字的都是一遍AC,没有标注的都说明了问题,顺序依照Leetcode上时间倒序排列，少量题目因为和之前的题目有相关性，因此将其放在一起，比方12题和13题，因此中间可能会“缺少”几道题目，缺少的题目请自行ctrl + F

PSS:题眼下加"*"都是有点意思的题目，依据*的多少说明题目的有(kun)趣(nan)程度

PSSS：尽管一直计划刷Leetcode，可是各种懒得动笔，只是由于上周日(5.18号)听了Facebook在北大的宣讲会，听后决定还是早准备好，于是便有此文，边刷边更新吧，每天刷个至少5道题，计划一个月内刷完

1,Two Sum:

水题，排序，然后两个边界指针往中间查找，一次AC。题目不难，可是因为是第一道，因此搞了半天才弄懂输入输出，并且在为sort重载辅助类的“<”时犯了错误，详细看重载运算符和友元函数，通过这个错误还认识到了CONST成员函数

(*) 2.Median of Two Sorted Arrays

类似于二分吧，研一暑假实习去面试阿里时遇到该题的简单版本号(两个数组大小同样)，此题是在两个有序数组中找第k小的值的弱化版，只是写的时候突然脑子短路了，本来仅仅扔一个数组的一部分，我扔了两个数组(实习时的题目是两个都扔)，一直WA

3.Longest Substring Without Repeating Characters

水题，只是第一次提交时，我默认字符仅仅有a~z，结果RE了一次。注意substring是子串：要求连续；而subsequence是子序列：不要求连续

4.Add Two Numbers

主要是考指针操作。。由于没给输入输出例子，导致多种情况没考虑到，本质上不难

(*) 5. Longest
Palindromic Substring

第一反应是DP，结果TLE，然后去网上看了下有专门求最长回文字串的中心法，尽管两个理论上都是O(n^2)的算法，可是DP因为不能剪枝导致一定是严格O(n^2)的，而中心法则是仅仅有O(nm)的时间，m为最长回文字串的长度，而m在大多数情况都非常小。

PS：后来又对DP进行了改动，使其变成了O(0.5 *n^2)，AC，提醒了我在列状态方程时，要多想能否简化一些状态，比方将dp[start][end]改为dp[start][len].

6.ZigZag Conversion

水题，预计是考边界条件吧

7.Reverse Integer

将整数翻转输出。事实上题目要考虑的地方非常多，比如：

正负号
翻转后的前导0，以及恰好是0
翻转后数据溢出

可是因为此题有提示故非常easy过，假设是java的话能够直接用Long.parseLong(string)，假设是C++能够用stringstream库文件，这是一个C++中专门用来对string和其它类型互相转换的库函数，一次AC

8.String to Integer (atoi)

和上一道题类似，注意前导空白符号，能够用上一题的stringstream，也能够自己写，因为编译器不同CE了一次，然后改了下AC

9.Palindrome Number

推断回文数，和上面Reverse Integer类似，只是他要求负数不能是回文数，WA了一次

10.Regular Expression Matching

匹配正則表達式。。暴力法，只是要考虑比較多情况，WA了2次

(*) 11. Container With Most Water

水题，一開始我以为是一道和栈有关的题(第84题)，然后发现比那道题简单，開始用了先排序处理再找左右边界的算法，该算法AC后在Discuss里面发现还有O(n)的算法，略微思考后写的新算法也AC了，并且O(n)算法更看清本质。

12.Integer to Roman和13.Roman to Integer

水题，当做一个常识来做吧，没啥技巧。

14.Longest Common Prefix

水题，注意输入为空的情况

15.3Sum

水题，题目不难，排序后利用2Sum，关键点是怎样不反复，须要一点小预处理，定义next[i] = j表示: min{ j >i && num[i] != num[j] } ，注意next求法是从大往小求的，O(n)就能够求完，类似能够比較KMP算法中的预处理

(*) 16, 3Sum Closest

水题，和上题类似，这道题是找和目标近期的一个，因此关键点是"在算出三个整数之和后，假设不和目标相等该怎么移动指针去找下一组"，trick是找两遍:第一遍找不小于target的三元和，第二遍找小于target的三元和，问题迎刃而解。后来在Discuss发现，事实上直接套用2Sum移动指针就能够，简单证明白实如此。。。不用这么麻烦

(*) 17,4Sum

水题，2(3)Sum的拓展，排序后枚举前两个，然后利用2Sum的的左右指针查找，类似的注意要求求得的数组不反复。PS：4Sum是O(n^3)的复杂度，而3Sum仅仅有O(n^2)，但两个在OJ上跑的时间基本同样，可能数据量不一样

18,Letter Combinations of a Phone Number

没啥意思。。只是WA了一次。。由于没看清题目= =导致每一个数字相应的字母有问题。。。

19.Remove Nth Node From End of List和60Rotate List

水题，但也是经典题目，两个指针，一个先从头走n步之后还有一个才開始从头走，当第一个走到末尾时，后一个指针相应的节点就是要删除的节点，注意考虑边界情况。

20.Valid Parentheses

水题，相同经典题目，用栈就可以解决。

21.Generate Parentheses

水题，上一道题的对偶题

22.Merge k Sorted Lists和64Merge Two Sorted Lists

水题，经典题目，K路归并的链表形式，能够用分治法做，也能够用堆，此外注意使用指针的边界情况

23.Swap Nodes in Pairs

水题，主要考怎样交换相邻两个节点

(*)24.Reverse Nodes in k-Group

水题，题目不难，可是链表题。。。特别恶心= =考虑了非常久，尽管一次AC了，可是花费时间非常多，要是面试遇到肯定挂了

25.Remove Duplicates from Sorted Array 和 26.Remove
Element和80.Remove Duplicates from Sorted Array II

水题

27.Implement strStr()

KMP算法，水题

(*)28.Divide Two Integers

题目类型非常经典，水题，可是一些边界情况想了一点时间：用位运算实现一些特殊计算，本题是实现除法，要注意涉及到INT_MAX和INT_MIN的特殊情况，相关文章可见位运算之美

29.Substring with Concatenation of All Words

一上来被唬住了。。。以为有非常复杂的算法，事实上就是暴力法= =。。。只是RE了一次，由于忘了STL.size()返回的是unsigned int，结果导致做减法后，出现了4294967295(0xffffffff)

30.Next Permutation

此题分析起来还是非常有意思的，水题，对于一个排列A，从后往前看A的每一个数，则得到的后缀一定属于以下两种情况：

先升序(可相等)，然后在严格降序，我们记为xab...d，当中x < a，但a >=b >= ... >=d，此时在a~d中寻找大于x的最小值(一定存在，由于a>x)，记为c，则将xab...d换为cB，当中B是由x,a...d中除c以外的数字组成的最小数，A的其余部分不变，该排列即为解。

一直升序(可相等)，则这个排列是最大排列，仅仅须要将其翻转得到最小排列输出就可以。

31.Longest Valid Parentheses

上来先写了个O(n^2)的算法，结果TLE(有个输入1s才跑完)，然后又去琢磨O(n)的算法，结果想了半小时没找到，然后就回寝室了。。。回去的路上考虑对原来算法剪枝，发现了一个剪枝技巧：我们查找最长串的本质是在已经找到一个合法串A的基础上，在末尾继续加入字符a,会出现3种情况：

Aa中'('个数等于')'，此时Aa为合法串，更新答案长度，继续搜索

Aa中'('个数小于')'，Aa不合法，此时终止这次搜索

Aa中'('个数大于')，TLE的代码中没有剪枝。算法的低效原因就在这：比方以某个位置为出发点时，发现前面搜索的差点儿全是'('，这样导致我们会一直搜索到末尾，此时才发现')'个数太少以至于不能形成合法串，浪费了大量时间。所以我加入了新的剪枝，定义neg[j]:代表以j开头的字串(能够为空)中，')'个数减去'('个数的最大值(假设为负数，则置为0)，这样当我们搜索字串S[i,j]时，利用neg[j]发现眼下已经累计的'('的个数不足以从j開始的')'抵消，则终止这次搜索。经过这个剪枝92ms AC

32Search in Rotated Sorted Array和81Search
in Rotated Sorted Array II

二分的变种，WA了一次

33Search for a Range

二分法变种，水题

34Search Insert Position

还是二分法。。。递归比迭代麻烦多了，只是还是所实用迭代写的

35Valid Sudoku和36Sudoku Solver

= =纯模拟题，水题，没啥意思

37.Count and Say

水题，纯模拟，题目第一次竟然没读懂

38.Combination Sum和39Combination Sum II

水题。。。还是递归模拟即可了

(*)40.First Missing Positive

此题第一反应是排序后比較，可是不满足题目要求的线性时间。细致分析后我们仅仅是要求找第一个没出现的正整数，不须要所有排序，因此一个思路是，我们将其“部分排序”，使得从i = 0開始时，A[i] = i + 1，当第一次不满足这个要求时得到的i即为所求，所以此题的本质类似于置换。RE了两次(事实上是一次。。。第一次RE后，改动BUG的时候大脑短路本来想打>结果打了<)

41Trapping Rain Water

水题

42Multiply Strings

大整数乘法，由于大一写过大整数乘法，实在不想再费劲了(真面试遇到这样的题，我就糊面试官的熊脸)。。。所以随便粘了份代码交上去了。。。

(*)43Wildcard Matching

基本类似第10题，TLE后把递归改成非递归就过了

(*)44.Jump Game II和54Jump Game

第一反应是DP，TLE。。。然后发现dp[i]在这道题里面是递增的，因此加了一个剪枝就过了，这道题还是提醒我们DP后发现TLE，多去找剪枝，一般能DP的题都是能过的，仅仅只是写的太麻烦，类似的还有第5题和31题。

45Permutations和46.Permutations II

水题，注意求给定数字的所有排列有个经典的递归算法

47.Rotate Image

找到规律后非常easy，水题

48.Anagrams

题目叫做怎样使用STL。。。。用multimap就可以解决，只是对multimap不熟，WA了几次

48.Pow(x, n)

求幂，分治法经典题目，水题，注意INT_MIN和INT_MAX

50.N-Queens和51.N-Queens II

N皇后问题。。。回溯法，好久没写非递归了(面试官非常爱考递归转伪递归)。。。所以花了一个小时去琢磨伪递归。。。发现差点儿相同忘完了。。。以后再练练

52.Maximum Subarray

最大子段和。。。应该是最经典的几个DP问题了吧，水题

53.Spiral Matrix和58.Spiral Matrix II

旋转矩阵。。。。经典题目

55Merge Intervals和56.Insert Interval

以为有什么好算法。。事实上就是区间排序后合并即可了，水题

57Length of Last Word

水题，不多说

59.Permutation Sequence

水题，抓住问题本质，从高位往低位排序就可以。

61Unique Paths 62Unique Paths II和63Minimum
Path Sum

水题，DP经典问题

65Add Binary

水题。。。远不如大整数乘法

66Valid Number

没啥技术含量，就是依据測试例子调BUG

67.Plus One

水题

68Text Justification

模拟题。。。主要是边界条件处理。。。然后理解错题意了。。。WA了非常久

69Sqrt(x)

本来想直接循环找，结果TLE，然后改成牛顿法过了。。。看来以后得找个时间看看《算法心得》了

70.Climbing Stairs

水题，斐波那契数列

71.Simplify Path

用栈完美解决，因为C++标准里面没有string.split，有几个方法能够替代：1.用strtok 2.用sstream 和 getline()

72.Edit Distance

经典DP

73.Set Matrix Zeroes

由于写完没跑例子就交上去了，RE了一次。。发现打错了一个符号，改动AC。尽管要求常数空间，可是题目不难

74Search a 2D Matrix

二分搜索的矩阵版本号，水题

75.Sort Colors

题目提示能够在O(2n)内用计数排序排完，但该算法还有O(1*n)的算法：能够用类似40题置换置换的思想，将数组分成4部分：下标在[0,i-1]内的数全为0，下标在[i,i+j-1]内的数全为1，在[k,n-1]内全为2，而剩下的在[i+j,k-1]内的数待排序。水题

(*)76.Minimum Window Substring

要求O(n)时间，仅仅能用动态规划了，dp[i]表示以s[i]开头的子串中能包括T的最小长度，然后就非常easy做了。(因为是一维的DP且是O(n)的，所以DP本质上是双指针法，类似可对照题1)

77.Combinations

水题，能够对照题目59(输出所有排列)

78Subsets

上一题的升级版本号，输出所有子集，忘了空集了。。WA了一次。此外能够见91题，对这个问题有较为具体的分析。推荐一下这篇文章对Sort函数有个比較好的归纳

79.Word Search

水题。。普通的回溯就可以。。。

82.Remove Duplicates from Sorted List 和 83.Remove
Duplicates from Sorted List II

重点还是指针操作，水题

(*)84.Largest Rectangle in Histogram

经典问题，能够和下一题以及11题比較一下。

解决算法是：从左往右遍历Rectangle，用栈保存之前遍历的长方形的编号，栈中元素满足：不论什么一个元素代表的长方形比它以下元素代表的长方形高。在遍历时，假设当前长方形比栈顶的长方形的高度低时，更新面积：

即以栈顶代表的长方形高度为所求长方形高度，以栈顶以下一个元素代表的长方形为右边界(假设不存在则以最左边为左边界)，以当前遍历到的长方形之前的一个长方形为右边界，计算所得到的面积。然后弹出栈顶元素，反复这步直到栈空或者栈长方形高度不小于当前长方形高度。

PS：有更简单的处理方法，即栈里面保存用一个二元组，二元组保存长方形高度和它相应的左边界，这种话能够简化代码

85.Maximal Rectangle

经典问题，最大子段和的2D版本号,WA了一次

86.Partition List

水题。。

87.Scramble String

上来就用递归算法，TLE了一次，然后考虑了半天没有找到好的解法(原解法是指数级的)。。。然后回来考虑剪枝，加入了一个预处理的剪枝后(即比較两个串所含字符是否全然同样)，52ms AC。。。还是和曾经的观点，TLE了多考虑剪枝。

88.Merge Sorted Array

水题=。=合并有序数组B到A。。。倒着排序就可以，即从大往小插入到A里面,O(1)空间，O(n)时间

89.Gray Code

格雷码。。生成格雷码有特定方法，依照该方法就可以。。。WA了一次。。。原因是题目觉得n = 0 时应该输出0.。。。

90.Decode Ways

递归后TLE。。。然后改成DP，各种WA，事实上这道题的本质是推断哪个输入合法= =。。。

91.Subsets II

2种解法：

78题的升级版，即先生产后面的集合，然后在把前面的数据加进去，此方法耗费空间非常大，但时间快，每次调用辅助函数都能在ans里面增加多个结果。

DFS，此方法简单粗暴，代码easy，空间小(实际上和上一个方法空间是可比的，没有数量级的差距)，时间慢，每次调用dfs仅仅能增加一个结果。

此外另一个技巧是利用set把找到的解存起来，然后再最后转成vector输出，这样能够不用不论什么多于处理保证找到的集合不反复，可是这样对思考没有太大帮助，不建议使用。注意一下for_each的多种使用方法

92.Reverse Linked List II