Valid Palindrome吐槽一下Leetcode上各种不定义标准的输入输出(只是面试时起码能够问一下输入输出格式。。。),此篇文章不是详细的题解,是自己刷LeetCode的一个笔记吧,尽管没有代码,可是略微难一点的都会标出主要思路,便于以后复习
PS:题目中有“水题”两字的都是一遍AC,没有标注的都说明了问题,顺序依照Leetcode上时间倒序排列,少量题目因为和之前的题目有相关性,因此将其放在一起,比方12题和13题,因此中间可能会“缺少”几道题目,缺少的题目请自行ctrl + F
PSS:题眼下加"*"都是有点意思的题目,依据*的多少说明题目的有(kun)趣(nan)程度
PSSS:尽管一直计划刷Leetcode,可是各种懒得动笔,只是由于上周日(5.18号)听了Facebook在北大的宣讲会,听后决定还是早准备好,于是便有此文,边刷边更新吧,每天刷个至少5道题,计划一个月内刷完
1,Two Sum:
(*) 2.Median of Two Sorted Arrays水题,排序,然后两个边界指针往中间查找,一次AC。题目不难,可是因为是第一道,因此搞了半天才弄懂输入输出,并且在为sort重载辅助类的“<”时犯了错误,详细看重载运算符和友元函数,通过这个错误还认识到了CONST成员函数
3.Longest Substring Without Repeating Characters类似于二分吧,研一暑假实习去面试阿里时遇到该题的简单版本号(两个数组大小同样),此题是在两个有序数组中找第k小的值的弱化版,只是写的时候突然脑子短路了,本来仅仅扔一个数组的一部分,我扔了两个数组(实习时的题目是两个都扔),一直WA
4.Add Two Numbers水题,只是第一次提交时,我默认字符仅仅有a~z,结果RE了一次。注意substring是子串:要求连续;而subsequence是子序列:不要求连续
主要是考指针操作。。由于没给输入输出例子,导致多种情况没考虑到,本质上不难
(*) 5. Longest Palindromic Substring
6.ZigZag Conversion第一反应是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].
水题,预计是考边界条件吧
将整数翻转输出。事实上题目要考虑的地方非常多,比如:
- 正负号
- 翻转后的前导0,以及恰好是0
- 翻转后数据溢出
8.String to Integer (atoi)可是因为此题有提示故非常easy过,假设是java的话能够直接用Long.parseLong(string),假设是C++能够用stringstream库文件,这是一个C++中专门用来对string和其它类型互相转换的库函数,一次AC
9.Palindrome Number和上一道题类似,注意前导空白符号,能够用上一题的stringstream,也能够自己写,因为编译器不同CE了一次,然后改了下AC
10.Regular Expression Matching推断回文数,和上面Reverse Integer类似,只是他要求负数不能是回文数,WA了一次
(*) 11. Container With Most Water匹配正則表達式。。暴力法,只是要考虑比較多情况,WA了2次
水题,一開始我以为是一道和栈有关的题(第84题),然后发现比那道题简单,開始用了先排序处理再找左右边界的算法,该算法AC后在Discuss里面发现还有O(n)的算法,略微思考后写的新算法也AC了,并且O(n)算法更看清本质。
12.Integer to Roman和13.Roman to Integer
水题,当做一个常识来做吧,没啥技巧。
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
19.Remove Nth Node From End of List和60Rotate List没啥意思。。只是WA了一次。。由于没看清题目= =导致每一个数字相应的字母有问题。。。
20.Valid Parentheses水题,但也是经典题目,两个指针,一个先从头走n步之后还有一个才開始从头走,当第一个走到末尾时,后一个指针相应的节点就是要删除的节点,注意考虑边界情况。
21.Generate Parentheses水题,相同经典题目,用栈就可以解决。
水题,上一道题的对偶题
22.Merge k Sorted Lists和64Merge Two Sorted Lists
水题,经典题目,K路归并的链表形式,能够用分治法做,也能够用堆,此外注意使用指针的边界情况
水题,主要考怎样交换相邻两个节点
(*)24.Reverse Nodes in k-Group
水题,题目不难,可是链表题。。。特别恶心= =考虑了非常久,尽管一次AC了,可是花费时间非常多,要是面试遇到肯定挂了
25.Remove Duplicates from Sorted Array 和 26.Remove Element和80.Remove Duplicates from Sorted Array II
水题
KMP算法,水题
(*)28.Divide Two Integers
题目类型非常经典,水题,可是一些边界情况想了一点时间:用位运算实现一些特殊计算,本题是实现除法,要注意涉及到INT_MAX和INT_MIN的特殊情况,相关文章可见位运算之美
29.Substring with Concatenation of All Words
一上来被唬住了。。。以为有非常复杂的算法,事实上就是暴力法= =。。。只是RE了一次,由于忘了STL.size()返回的是unsigned int,结果导致做减法后,出现了4294967295(0xffffffff)
此题分析起来还是非常有意思的,水题,对于一个排列A,从后往前看A的每一个数,则得到的后缀一定属于以下两种情况:
- 先升序(可相等),然后在严格降序,我们记为xab...d,当中x < a,但a >=b >= ... >=d,此时在a~d中寻找大于x的最小值(一定存在,由于a>x),记为c,则将xab...d换为cB,当中B是由x,a...d中除c以外的数字组成的最小数,A的其余部分不变,该排列即为解。
- 一直升序(可相等),则这个排列是最大排列,仅仅须要将其翻转得到最小排列输出就可以。
32Search in Rotated Sorted Array和81Search in Rotated Sorted Array II上来先写了个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
二分的变种,WA了一次
34Search Insert Position二分法变种,水题
还是二分法。。。递归比迭代麻烦多了,只是还是所实用迭代写的
35Valid Sudoku和36Sudoku Solver
= =纯模拟题,水题,没啥意思
38.Combination Sum 和39Combination Sum II水题,纯模拟,题目第一次竟然没读懂
水题。。。还是递归模拟即可了
(*)40.First Missing Positive
此题第一反应是排序后比較,可是不满足题目要求的线性时间。细致分析后我们仅仅是要求找第一个没出现的正整数,不须要所有排序,因此一个思路是,我们将其“部分排序”,使得从i = 0開始时,A[i] = i + 1,当第一次不满足这个要求时得到的i即为所求,所以此题的本质类似于置换。RE了两次(事实上是一次。。。第一次RE后,改动BUG的时候大脑短路本来想打>结果打了<)
42Multiply Strings水题
(*)43Wildcard Matching大整数乘法,由于大一写过大整数乘法,实在不想再费劲了(真面试遇到这样的题,我就糊面试官的熊脸)。。。所以随便粘了份代码交上去了。。。
(*)44.Jump Game II和54Jump Game基本类似第10题,TLE后把递归改成非递归就过了
第一反应是DP,TLE。。。然后发现dp[i]在这道题里面是递增的,因此加了一个剪枝就过了,这道题还是提醒我们DP后发现TLE,多去找剪枝,一般能DP的题都是能过的,仅仅只是写的太麻烦,类似的还有第5题和31题。45Permutations和46.Permutations II
水题,注意求给定数字的所有排列有个经典的递归算法47.Rotate Image
找到规律后非常easy,水题48.Anagrams
48.Pow(x, n)题目叫做怎样使用STL。。。。用multimap就可以解决,只是对multimap不熟,WA了几次
52.Maximum SubarrayN皇后问题。。。回溯法,好久没写非递归了(面试官非常爱考递归转伪递归)。。。所以花了一个小时去琢磨伪递归。。。发现差点儿相同忘完了。。。以后再练练
以为有什么好算法。。事实上就是区间排序后合并即可了,水题57Length of Last Word
水题,不多说59.Permutation Sequence
61Unique Paths 62Unique Paths II和63Minimum Path Sum水题,抓住问题本质,从高位往低位排序就可以。
水题,DP经典问题65Add Binary
66Valid Number水题。。。远不如大整数乘法
没啥技术含量,就是依据測试例子调BUG67.Plus One
70.Climbing Stairs本来想直接循环找,结果TLE,然后改成牛顿法过了。。。看来以后得找个时间看看《算法心得》了
水题,斐波那契数列71.Simplify Path
用栈完美解决,因为C++标准里面没有string.split,有几个方法能够替代:1.用strtok 2.用sstream 和 getline()72.Edit Distance
73.Set Matrix Zeroes经典DP
74Search a 2D Matrix由于写完没跑例子就交上去了,RE了一次。。发现打错了一个符号,改动AC。尽管要求常数空间,可是题目不难
二分搜索的矩阵版本号,水题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]内的数待排序。水题
77.Combinations要求O(n)时间,仅仅能用动态规划了,dp[i]表示以s[i]开头的子串中能包括T的最小长度,然后就非常easy做了。(因为是一维的DP且是O(n)的,所以DP本质上是双指针法,类似可对照题1)
78Subsets水题,能够对照题目59(输出所有排列)
79.Word Search上一题的升级版本号,输出所有子集,忘了空集了。。WA了一次。此外能够见91题,对这个问题有较为具体的分析。推荐一下这篇文章对Sort函数有个比較好的归纳
水题。。普通的回溯就可以。。。
(*)84.Largest Rectangle in Histogram重点还是指针操作,水题
经典问题,能够和下一题以及11题比較一下。解决算法是:从左往右遍历Rectangle,用栈保存之前遍历的长方形的编号,栈中元素满足:不论什么一个元素代表的长方形比它以下元素代表的长方形高。在遍历时,假设当前长方形比栈顶的长方形的高度低时,更新面积:即以栈顶代表的长方形高度为所求长方形高度,以栈顶以下一个元素代表的长方形为右边界(假设不存在则以最左边为左边界),以当前遍历到的长方形之前的一个长方形为右边界,计算所得到的面积。然后弹出栈顶元素,反复这步直到栈空或者栈长方形高度不小于当前长方形高度。PS:有更简单的处理方法,即栈里面保存用一个二元组,二元组保存长方形高度和它相应的左边界,这种话能够简化代码
经典问题,最大子段和的2D版本号,WA了一次86.Partition List
水题。。
88.Merge Sorted Array上来就用递归算法,TLE了一次,然后考虑了半天没有找到好的解法(原解法是指数级的)。。。然后回来考虑剪枝,加入了一个预处理的剪枝后(即比較两个串所含字符是否全然同样),52ms AC。。。还是和曾经的观点,TLE了多考虑剪枝。
89.Gray Code水题=。=合并有序数组B到A。。。倒着排序就可以,即从大往小插入到A里面,O(1)空间,O(n)时间
90.Decode Ways格雷码。。生成格雷码有特定方法,依照该方法就可以。。。WA了一次。。。原因是题目觉得n = 0 时应该输出0.。。。
91.Subsets II递归后TLE。。。然后改成DP,各种WA,事实上这道题的本质是推断哪个输入合法= =。。。
92.Reverse Linked List II2种解法:此外另一个技巧是利用set把找到的解存起来,然后再最后转成vector输出,这样能够不用不论什么多于处理保证找到的集合不反复,可是这样对思考没有太大帮助,不建议使用。注意一下for_each的多种使用方法
- 78题的升级版,即先生产后面的集合,然后在把前面的数据加进去,此方法耗费空间非常大,但时间快,每次调用辅助函数都能在ans里面增加多个结果。
- DFS,此方法简单粗暴,代码easy,空间小(实际上和上一个方法空间是可比的,没有数量级的差距),时间慢,每次调用dfs仅仅能增加一个结果。
93.Restore IP Addresses水题
94.Binary Tree Inorder Traversal类似输入格式推断,WA了几次,只是主要还是因为题目没有说明详细需求
95.Unique Binary Search Trees 和96Unique Binary Search Trees II=.=上来就把题目看错了。。。求的是中序遍历,当成先序做了。。。二叉树的遍历仅仅能说是基础的基础了,尤其是非递归版本号的。。。怎么说都得5分钟内写出来吧
97.Interleaving String水题,96题WA了一次。。=。=由于输入是0的时候竟然要求输出根节点为空的二叉树。。。
98.Validate Binary Search Tree水题,DP就能够,类似72题
99.Recover Binary Search Tree本来以为是水题。。。结果代码中忘了把根节点和所有儿子节点作比較(不能简单的和左子树的最小节点或者右子树的最大节点直接比較,由于输入的子树可能是非法的)。。。
100.Same Tree注意交换节点有3种情况:1.某个节点的左后代和右后代交换 2.某个节点和左后代交换 3.某个节点和右后代交换 。 WA了两次,第一次是仅仅考虑了第一种情况,第二次是忘了能够和随意后代交换,所以遍历子树时要完整。
101.Same Tree水题。。。二叉树假设能够用递归,非常多题都能够秒破
102.Binary Tree Level Order Traversal 和水题,理由同100
104.Maximum Depth of Binary Tree和水题,前两题要求用数组返回宽搜,每一个数组代表一层,那么将每层按层数的奇偶区分,用两个队列就可以分别保存奇数层和偶数层就可以。第三题特别SB=。=,仅仅要把第一题的结果翻转一遍输出就可以了
两道水题,理由同100
108.Convert Sorted Array to Binary Search Tree 和依据中序遍历和前序(后序)遍历还原二叉树(已知无反复元素,假设有二叉树不唯一)。。。基础内容,不能有误,要求一次AC,水题
109.Convert Sorted List to Binary Search Tree
110.Balanced Binary Tree水题,一開始没反应过来Height Balanced BST是啥。。。孤沟了一下。。
112.Path Sum 和 113.Path Sum I水题,理由同100,只是这几道题都要求是父节点到叶子节点,因此要对递归略微加点限制
114.Flatten Binary Tree to Linked List水题,理由同100
115.Distinct Subsequences水题,注意在递归时,须要同一时候记录生成链表的头和尾
116.Populating Next Right Pointers in Each Node和水题,同72的DP
水题,类似题目102,尽管102中的方法没有达到的常数空间的要求,事实上稍作思考后改动一下就可以。。。第一次遇到了OLE。。。然后发现指针没初始化,
120.Triangle水的令人发指,由于没有规定输入0时输出什么,所以两道题各WA一次
121.Best Time to Buy and Sell Stock和水题,经典DP题
122.Best Time to Buy and Sell Stock II 和
124Binary Tree Maximum Path Sum第一题非常水,第二题DP能够AC可是有更好的算法(弄懂问题的本质是求全部上升子段的高度和),第三题也非常easy,先DP,然后以i为分界点,分别算左右两边最大利润的和就可以,可是关键是假设第三题扩展要求最多买k次有没有好的算法
125.Valid Palindrome弄懂本质是后序遍历就可以,WA了一次,提醒我以后设定最小值可能是INT_MIN,而不一定是0(依据问题解是否非负而定)
126.Word Ladder和水题
127.Word Ladder II
128.Longest Consecutive Sequence一看题目就知道本质上是图的最短路径问题。。。然后认为写起来太麻烦,面试时真遇到非常有可能20分钟写不出来。。。认为没太大意义,随便贴了别人代码交上去了,以后有兴趣再回来写吧
129.Sum Root to Leaf Numbers这道题想了非常久没想到好的方法,然后看了提示大家都是用HashSet过的。。。认为没啥意思。。。
130.Surrounded Regions水题
131.Palindrome Partitioning和水题,宽搜
132.Palindrome Partitioning II
133.Clone Graph水题
134.Gas Station题目没啥意思,随便贴份代码上去·
135.Candy水题,本来还以为有多高深的算法。。简单剪枝的纯模拟。。。一直TLE以为算法错了。。。发现题目尽管说保证解唯一可是没有说明一定有解
本质上是找最高点和最低点的高度差,WA了一次,由于我输出的最多一个人的糖果不是全部人的糖果