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

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

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

可是因为此题有提示故非常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的每一个数，则得到的后缀一定属于以下两种情况：

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

31.Longest Valid Parentheses

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

1. Aa中'('个数等于')'，此时Aa为合法串，更新答案长度，继续搜索
2. Aa中'('个数小于')'，Aa不合法，此时终止这次搜索
3. 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

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

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

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

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

水题。。

依据中序遍历和前序(后序)遍历还原二叉树(已知无反复元素，假设有二叉树不唯一)。。。基础内容，不能有误，要求一次AC，水题

108.Convert
Sorted Array to Binary Search Tree  和 

109.Convert
Sorted List to Binary Search Tree

水题，一開始没反应过来Height Balanced BST是啥。。。孤沟了一下。。

110.Balanced Binary Tree

水题，理由同100，只是这几道题都要求是父节点到叶子节点，因此要对递归略微加点限制

112.Path Sum 和 113.Path
Sum I

水题，理由同100

114.Flatten Binary Tree to Linked List

水题，注意在递归时，须要同一时候记录生成链表的头和尾

115.Distinct Subsequences

水题，同72的DP

116.Populating Next Right Pointers in Each Node和

水的令人发指，由于没有规定输入0时输出什么，所以两道题各WA一次

120.Triangle

水题，经典DP题

121.Best Time to Buy and Sell Stock和

122.Best Time to Buy and Sell Stock II 和

第一题非常水，第二题DP能够AC可是有更好的算法(弄懂问题的本质是求全部上升子段的高度和)，第三题也非常easy，先DP，然后以i为分界点，分别算左右两边最大利润的和就可以，可是关键是假设第三题扩展要求最多买k次有没有好的算法

124Binary Tree Maximum Path Sum

弄懂本质是后序遍历就可以，WA了一次，提醒我以后设定最小值可能是INT_MIN，而不一定是0(依据问题解是否非负而定)

125.Valid Palindrome

水题

126.Word Ladder和

127.Word Ladder II

一看题目就知道本质上是图的最短路径问题。。。然后认为写起来太麻烦，面试时真遇到非常有可能20分钟写不出来。。。认为没太大意义，随便贴了别人代码交上去了，以后有兴趣再回来写吧

128.Longest Consecutive Sequence

这道题想了非常久没想到好的方法，然后看了提示大家都是用HashSet过的。。。认为没啥意思。。。

129.Sum Root to Leaf Numbers

水题

130.Surrounded Regions

水题，宽搜

131.Palindrome Partitioning和

132.Palindrome Partitioning II

水题

133.Clone Graph

题目没啥意思，随便贴份代码上去·

134.Gas Station

水题，本来还以为有多高深的算法。。简单剪枝的纯模拟。。。一直TLE以为算法错了。。。发现题目尽管说保证解唯一可是没有说明一定有解

135.Candy

本质上是找最高点和最低点的高度差，WA了一次，由于我输出的最多一个人的糖果不是全部人的糖果