LeetCode 题解

LeetCode OJ is a platform for preparing technical coding interviews.

LeetCode OJ 是为与写代码有关的技术工作面试者设计的训练平台。

LeetCode OJ:http://oj.leetcode.com/

默认题目顺序为题目添加时间倒叙,本文题解顺序与OJ题目顺序一致(OJ会更新,至少目前一致。。。)。 习惯大括号换行,遇到大括号默认不换行的样例代码,导致有的换行有的没换行,实在懒得一个个改……


2015.11.17更新:今天又看leetcode,发现题目列表终于有编号了。 咦,新题目加锁了,要25 dollar一个月的捐赠……


Made By:CSGrandeur: LeetCode 题解


208.Implement Trie (Prefix Tree)

20170209

基本字典树

207.Course Schedule

20170208

先构造个图。一开始没想拓扑排序的事,就用DFS来判断的,标记-1表示尚未考察,0表示暂没结果,1表示确认可选修

206.Reverse Linked List

20170208

好像又是老题

205.Isomorphic Strings

20170208

思路一是两个map互相映射,出现矛盾则说明不同构。两个map用于解决其中一个串可能有多个字符对应另一个串同一个字符,只用一个map则会掉这个坑。、

思路二是把俩字符串按同一规则转换,转换后字符串直接比较。

204.Count Primes

20170208

筛素数,以前比赛时候写的滚瓜烂熟的,现在竟然忘了还复习一下…… 从2开始把每个其倍数都标记成合数,然后往后枚举,枚举到的没标记的一定是素数(如果它是合数,它的质因数肯定比它小,而比它小的质数的倍数都已经标记过了),继续标记其所有倍数。

203.Remove Linked List Elements

20170208

好像又是老题,开头加个哨兵节点就不用担心head节点被删除的情况了。

202.Happy Number

20170208

直接思路是用哈希记录判循环,降低空间复杂度可以用两个值一个每次算一步,另一个每次算两步来判循环。 还有个方法是只要大于 6 就一直进行,能保证计算结束,不知道怎么证明的。 代码放传统思路。

201.Bitwise AND of Numbers Range*

20170208

二进制从左往右看,当遇到某位不相等的时候,最终结果后面的位都会是0,因为在n~m之间,连续的数字中这些位肯定会出现0。题目巧在如果思路转换为求二进制最长相同前缀,代码就很简单了。

还有一种理解方式也很好,把n的右侧的1一一去掉,当n不大于m的时候,n剩下的就是那个相同前缀。

200.Number of Islands

20170208

我一定是做了道假题。。DFS、BFS随便做,好陈旧。

199.Binary Tree Right Side View

20170208

二叉树层次遍历,加个层数标记。

198.House Robber

20170207

简单的动态规划,两个数一个表示上一个没rob的当前最佳收益,另一个表示上一个rob了的,反复更新。

191.Number of 1 Bits

20170207

做过树状数组应该对n&(n-1)很熟了,n-1让二进制末尾的1变0,这个1后面的0都变1,和n做按位与就相当于去掉了最后一个1,这样每次操作都能去掉一个1,一位一位统计就快多了。

190.Reverse Bits

20170207

首先是最直接的方法,把所有bit放到新数中的对应位置。 题目提到一句“If this function is called many times, how would you optimize it?”是很值得思考的。直接的方法进行了32次操作,每个操作里有若干次位运算,这个数字是否可以优化呢? 一个可能思路是并行的分治。问题二分,并行用位运算实现,这样就log(32)=5次操作了。

直接思路:

并行分治思路:

189.Rotate Array

20170207

空间复杂度不是O(1)的想都不要想。网上方法已经很多了,如: 1、后k个翻转,前面的翻转,再整个翻转。 2、前k个和后k个一一swap,就变成后n-k个做k旋转的子问题了,继续进行到结束。 3、把数组分成若干个以k为间隔的“子数组”,而且这个“子数组”是可以循环回去的,比如1, 2, 3, 4, 5, k=3,“子数组”就是1, 4, 2, 5, 3,对它做step=1的右循环。 这里放 方法3 的代码。

188.Best Time to Buy and Sell Stock IV*

20170207

一开始思路是常规的记忆化搜索,状态记录为[第i天价格][剩下k次][是否在买入状态],是否买入状态是二值的,所以内存主要在于天数和次数的取值,小trick是k取值过大时候,可缩小到天数的1/2。结果还是超内存了,虽然网上看到有类似解法没超内存,不过看最大那组数据,还是不适合开二维数组的。

这题有个特别之处,当考察第i天时,并不关心这是多少天了,而关心的只是当前的盈利情况和剩下多少次交易机会,于是数组缩小为次数k这一维。两个数组分别表示剩下k次的买入状态余额和非买入状态余额,状态方程是buy[k]=max(buy[k], sell[k-1] - price); sell[k]=max(sell[k], buy[k] + price);

187.Repeated DNA Sequences

20170207

没遇到网上说的内存问题,直接unordered_map过掉了。用字典树应该会比较快和稳定吧。 对每个长度为10的串进行统计,大于1次就做记录。

179.Largest Number

一开始用递归写了个复杂逻辑的comp函数,后来发现,主要确定两个字符串 a, b 的 a+b 和 b+a 的大小关系,就能确定 a 和 b 的顺序。

174.Dungeon Game

从左上角开始 DP 的话,无法做到既贪心当前最优,又保证路径最优。

从右下角开始 DP,则可以只考虑路径最优,dp[i][j]表示从(i, j)位置到终点所需最小health值。

这道题也可以用二分答案来直接从左上角贪心,不过速度会慢很多。

173.Binary Search Tree Iterator

变形的非递归中序遍历。

172.Factorial Trailing Zeroes

阶乘的每个数中,每个因子 2 和每个因子 5 可以构成一个0,而 2 远比 5 多,比如 8 就有三个 2,于是统计因子 5 的个数。

让输入 n 迭代除以 5,第一次得到 5 的倍数的个数,第二次是 25 倍数的个数,最后得到所有因子 5 的个数。

171.Excel Sheet Column Number

比用Number算Title容易点,在算每一位时候记得加 1 。

169.Majority Element

很有意思的题目,要求的数占超过一半,那么在O(n)时间里把不同的数抵消掉,“多数数”肯定会被留下来。

168.Excel Sheet Column Title

跳过 0 的 26 进制,处理每一位的时候要减 1 。

166.Fraction to Recurring Decimal

有边界数据,所以直接转成long long做,处理正负号。

对小数部分,每次求余数乘 10 再做下一位,当余数重复出现就是循环了。找重复用unordered_map。

165.Compare Version Numbers

.分开,逐个按数字大小比较。 C++怎么就没个方便的split函数呢。。。

164.Maximum Gap

很久没碰过桶排序了,这道题有个很有意思的推理——把 n 个数放到 n 个桶里,两种情形,1、每个桶一个数。2、存在有多个数的桶,那也一定有其他的空桶。

这两种情况下,最大gap都是某个桶的最小值与它前面最近的有数的桶的最大值之差,所以避免了桶内排序,O(n)

162.Find Peak Element

O(logn)

160.Intersection of Two Linked Lists

先统计两个链表长度,将 长链表 对准 距离末尾 与短链表长度相同 位置,同步遍历返回交叉点。

155.Min Stack

一开始做的是每个元素存两个数的数组,一个表示数值,一个表示“上一个最小值下标”。然后觉得这样的话,不是最小值的那些位置,其实浪费了空间。 还是用两个数组或者两个栈,一个存数,一个存最小值好了。 看Discuss里24ms的答案也没什么特别的,运行时间的浮动吧。

154.Find Minimum in Rotated Sorted Array II

首先如果首尾大量相同元素,那么“先去掉末尾连续相同元素”和“二分的时候nums[mid]==nums[left]时left++”这样的方法,都会退化为O(n)。于是尽可能想二分的方法,有了下面这个分治的方法,然而经不起推敲,其实即便分治,还是会退化成O(n)。贴上两种代码吧。

153.Find Minimum in Rotated Sorted Array

二分

152.Maximum Product Subarray

维护当前位置连续乘积的最大值 tmpp 和最小值 tmpn ,最大值和最小值都可能由三种情况得到:上一个数的 tmppA[i],上一个数的 tmpnA[i],A[i]本身。

不断更新答案,最终输出。

151.Reverse Words in a String

先翻转整个字符串,然后从前往后一个单词一个单词地再翻转一次,同时去除多余空格,等于是扫描两遍,O(n)。

150.Evaluate Reverse Polish Notation

逆波兰表达式计算四则运算。用栈。

149.Max Points on a Line

平面上一条直线最多穿过多少点。乍一看好熟悉的问题,做了这么久计算几何。。。却还真没做过这个小问题。

第一反应当然不能O(n^3)枚举了,枚举圆周好像也不行,毕竟是考察所有点,不是某个点。那么应该就是哈希斜率了吧。

肯定少不了竖直的线,哈希斜率这不像是这类OJ让写的题吧。。忘了map这回事了。

确定思路之后,还是看看别人博客吧,少走点弯路,然后就学习了还有unordered_map这么个东西,还有一个博客 的思路挺好,避免double问题,把斜率转化成化简的x、y组成字符串。

再另外就是重叠的点了,想让题目坑一点,怎能少得了这种数据,单独处理一下。

148.Sort List

又长见识了,原来链表也可以O(nlogn)排序的。没往下想就查了一下,看到人说用归并,于是才开始想能不能实现。。。

O(n)找到中点,把中点的next变成NULL,对两部分递归。递归结束后对两部分归并,先找到newhead,即两部分的头部val较小的那个,然后归并就把小的从newhead往后续。

把最后的next赋值NULL,返回newhead。

又有空数据@_@.

147.Insertion Sort List

指针操作很烦啊。。暴力枚举插入位置,注意细节就能过了。

146.LRU Cache

新建数据类class Val,保存key、val和访问自增标记updatecnt。

用unordered_map更新数据,增加updatecnt,并把更新的数据放入队列,最关键是处理capacity满了的时候,队列依次出队,map中不存在的和updatecnt和最新数据不相等的项目都忽略,直到发现updatecnt和map中存的最新状态相等,则为(最近未使用)数据,出队后在map中erase。思路有点像STL队列实现版本的Dijkstra。

有一个博客 的方法更好,map中存的是链表的节点指针,链表顺序表示访问情况,这样就把map内容和链表的每个节点一一对应了,没有冗余节点,且更新操作也是O(1)的。

145.Binary Tree Postorder Traversal

二叉树的非递归后序遍历,考研的时候非常熟悉了,现在写又要想好久。重点是关于右子树遍历时候需要一个标记,或者标记根节点出栈次数,或者标记右子树是否访问。

144.Binary Tree Preorder Traversal

前序遍历的非递归就容易多了。

143.Reorder List

找到中间位置,把中间之后的链表反转,两个指针一个从头一个从尾开始互插,奇偶和指针绕得有点晕,理清就好了。。

142.Linked List Cycle II

设置两个指针slowfast,从head开始,slow一次一步,fast一次两步,如果fast能再次追上slow则有圈。 设slow走了n步,则fast走了2*n步,设圈长度m,圈起点到head距离为k,相遇位置距离圈起点为t,则有:

n = k + t + pm; (1)

2*n = k + t + qm;(2)

这里p和q是任意整数。(不过fast速度是slow二倍,则肯定在一圈内追上,p就是0了)

2 * (1) - (2)k = lm - t;(l = q - 2 * p)

k 的长度是若干圈少了 t 的长度。 因此这时候,一个指针从head开始,另一个从相遇位置开始,都每次只走一步,当从head开始的指针走到圈开始位置时,两指针刚好相遇。

141.Linked List Cycle

呃,时间逆序做的结果。。。成买一送一了。

140.Word Break II

先递推,dp[i] == true 表示 s 中前 i 个字符的串是符合要求的,枚举位置 i ,对于 i 枚举位置 j < i,如果 dp[j] == truej ~ i的串在字典中,则dp[i] = true

同时对于这样的 j, isite[i].push_back(j),即在 i 位置的可行迭代表中增加位置 j

完成site之后,从尾部倒着DFS过去就得到了所有串。

139.Word Break

参考Word Break II,对于dp标记,当dp[i]为true时候可以停止枚举后面的 j,优化一下常数。

138.Copy List with Random Pointer

第一次遍历,把每个节点复制一份放到对应节点的下一个,即组成二倍长的链表:ori1->copy1->ori2->copy2->...

第二次遍历,利用复制节点总是对应节点的下一个节点特性,将每个ori->next->random指向ori->random->next,中间判断一下空指针。

第三次遍历,把两个链表拆开,恢复原链表。

137.Single Number II

方法一:设置cnt[32]记录 32个比特位的1的个数,出现3次的数的对应位的1总数为3的倍数,则统计之后每个位对3取模,剩下的位为1的则对应个数为1的那个数。

方法二:设置int one, two模拟两位二进制来统计各比特位1次数,每当one和two对应二进制位都为1的时候把one和two都清零,最后剩下的one就是要求的数。

136.Single Number

一路异或过去就可以了。

135.Candy

时间复杂度 O(n)的方法还是容易想了,优化为空间复杂度O(1)的话也不难,只是思考代码的时候会有点绕。

上坡一步步来,下坡走个等差数列,波峰位置比较一下上坡时候记录的最大值和下坡求的的最大值,取较大的,具体看代码:

134.Gas Station

证明题。

一、如果从 i 到 j 的时候理论计算气量刚好为负数,则 i ~ j 的加气站都不可以作为起点。

反证一下,从前往后去掉站,如果去掉的站能增加气,即正数,则结果更糟。如果去掉的站是负数,那么负数如果抵消了之前的正数,则在到 j 之前已经负数了,如果不能抵消之前的正数,那么结果还是更糟。

二、判断是否能成行,一个环的和为非负就可以。

假设环为正, 0 ~ j 刚好为负, j + 1 ~ k 刚好为负数,k + 1 之后为正,则 k + 1 为答案。

也反证一下,k + 1 出发,到gas.size() - 1都为正,则转回来到 j - 1 都会为正。如果到 j 时候为负,则整个环不可能为正,所以到 j 的时候也为正,剩下的一样。这样就能够成功转一圈。

133.Clone Graph

label是唯一的,递归,用unordered_map标记。

132.Palindrome Partitioning II

O(n^2)的动态规划。

cutdp[i] 表示前 i 个字符最小切割几次。

paldp[i][j] == true 表示 i ~ j 是回文。

在枚举 i 和 i 之前的所有 j 的过程中就得到了 paldp[j][i] 的所有回文判断,而对于 i + 1,paldp[j][i + 1]可由 s[j]、s[i + 1]、dp[j + 1][i]在O(1)判断。

cutdp[i]为所有 j (j < i),当paldp[j + 1][i] true的 cutdp[j] + 1的最小值。注意一下边界。

131.Palindrome Partitioning

O(n^2)动态规划,paldp[i][j] == true表示 i ~ j 是回文。这里DP的方法是基本的,不再多说。

得到paldp之后,DFS一下就可以了。因为单字符是回文,所以DFS的终点肯定都是解,所以不必利用其他的结构存储答案信息。

130.Surrounded Regions

周围四条边的O做起点搜索替换为第三种符号,再遍历所有符号把O换成X,第三种符号换回O。

129.Sum Root to Leaf Numbers

遍历一遍加起来。。。

128.Longest Consecutive Sequence

方法一:一开始竟然想了并查集,其实绕弯了,多此一举。哈希+并查集,把每个数哈希,枚举每个数看相邻的数在不在数组里,并查集合并,只是并查集的复杂度要比O(1)大一些。

方法二:哈希+枚举相邻数。相邻的数在数组里的话,每个数至多访问一次;相邻的数不在数组里的话,枚举会中断。所以设哈希复杂度为O(1)的话,这个方法是严格的O(n)。

其实这个题的数据挺善良,如果出了2147483647, -2147483648,那还是用long long 稳妥些。

127.Word Ladder II

用数组类型的队列,BFS过程中记录pre路径,搜完后迭代回去保存路径。

似乎卡了常数,用queue队列,另外存路径的方法超时了。

想更快就双向广搜吧。让我想起了POJ那个八数码。

126.Word Ladder

直接BFS。

125.Valid Palindrome

做过刘汝佳 白书的人想必都知道ctype.h和isdigit(), isalpha(), tolower(), toupper()。

124.Binary Tree Maximum Path Sum

后续遍历,子问题为子树根节点向叶子节点出发的最大路径和。

即 l = DFS(now->left), r = DFS(now->right)。

此时,ans可能是 now->valid,可能是左边一路上来加上now->valid,可能是右边一路上来,也可能是左边上来经过now再右边一路下去,四种情况。

四种情况更新完ans后,now返回上一层只能是 now->valid或左边一路上来或右边一路上来,三种情况。

123.Best Time to Buy and Sell Stock III

前缀pre[i]处理 0 ~ i 买卖一次最优解,后缀suf[i]处理 i ~ prices.size() - 1 买卖一次最优解。

所有位置pre[i] + suf[i]最大值为答案O(n)。

处理最优解的时候是维护前(后)缀prices最小(大)值,与当前prices做差后和前(后)缀最优解比较取最优,O(n)。

总复杂度O(n)。

122.Best Time to Buy and Sell Stock II

可以买卖多次,把所有上坡差累加即可。

121.Best Time to Buy and Sell Stock

维护前(后)缀最小(大)值,和当前prices做差更新答案。

120.Triangle

竟然遇到了ACM递推入门题,想必无数ACMer对这题太熟悉了。

从下往上递推,一维数组滚动更新即可。这里懒省事,直接把原数组改了。

119.Pascal’s Triangle II

滚动数组递推,从后往前以便不破坏上一层递推数据。

118.Pascal’s Triangle

递推。。

117.Populating Next Right Pointers in Each Node II

题目要求空间复杂度O(1),所以递归、队列等传统方法不应该用。

本题可以利用生成的next指针来横向扫描,即得到一层的next指针之后,可以利用这一层的next指针来给下一层的next指针赋值。

116.Populating Next Right Pointers in Each Node

不用考虑连续的空指针,就不用额外实现找下一个子树非空节点,比Populating Next Right Pointers in Each Node II 容易处理。

115.Distinct Subsequences

典型动态规划。dp[i][j] 表示 T 的前 j 个字符在 S 的前 i 个字符中的解。

对于dp[i + 1][j + 1],由两部分组成:

一、 j + 1 对应到 S 前 i 个字符中的解,忽略 S 的第 i + 1 个字符。

二、判断 S 的第 i + 1 个字符是否和 T 的第 j + 1 个字符相同,如果相同,则加上dp[i][j],否则不加。

114.Flatten Binary Tree to Linked List

题意是优先左子树靠前,且排成一列用右子树指针,不管val的大小关系。

后序遍历一遍即可,递归返回子树中尾节点指针,注意各种条件判断。

113.Path Sum II

传统递归,把路径上的数字插入vector,终点判断是否插入答案。

112.Path Sum

遍历树。

111.Minimum Depth of Binary Tree

还是遍历。

110.Balanced Binary Tree

遍历。

109.Convert Sorted List to Binary Search Tree

每次找中点作为根节点,将两边递归,返回根节点指针作为左右节点。

108.Convert Sorted Array to Binary Search Tree

递归做,比链表的容易些。

107.Binary Tree Level Order Traversal II

宽搜和深搜都可以,找对层数就行了。

本以为这题亮点是如何一遍实现从底向上顺序的vector,AC之后上网一查也全是最后把vector翻转的。。。

106.Construct Binary Tree from Inorder and Postorder Traversal

数据结构经典题。后序遍历的结尾是根节点 Proot,在中序遍历中找到这个节点 Iroot,则 Iroot两边即为左右子树。根据左右子树节点个数,在后序遍历中找到左右子树分界(左右子树肯定不交叉),则几个关键分界点都找到了,对左右子树递归。

105.Construct Binary Tree from Preorder and Inorder Traversal

和上一题Construct Binary Tree from Inorder and Postorder Traversal方法一样,前序和后序的信息作用相同。

104.Maximum Depth of Binary Tree

遍历。

103.Binary Tree Zigzag Level Order Traversal

BFS,奇偶层轮流走,一层左到右,一层右到左。

102.Binary Tree Level Order Traversal

懒省事直接在上一题Binary Tree Zigzag Level Order Traversal的代码上改了一下。

只用一个队列的话,增加个层数信息存队列里即可。

101.Symmetric Tree

递归:左指针和右指针,对称递归,即(左的左)和(右的右)对应,(左的右)和(右的左)对应。

非递归:左右子树分别做一个队列,同步遍历。

100.Same Tree

同步遍历,比较判断。

99.Recover Binary Search Tree

中序遍历是二叉查找树的顺序遍历,a, b表示前驱节点和当前节点,因为只有一对数值翻转了,所以肯定会遇到前驱节点val比当前节点val大的情况一次或两次,遇到一次表示翻转的是相邻的两个节点。ans1和ans2指向两个被翻转的节点,当遇到前驱val比当前val大的情况时候,根据第一次还是第二次给ans1和ans2赋值,最终翻转回来。

98.Validate Binary Search Tree

中序遍历,更新前驱节点,与当前节点比较。

97.Interleaving String

动态规划。如果结果是true,则任意 i, js1[i] 之前的字符 和 s2[j]之前的字符,都能够交叉为 s3[i + j] 之前的字符。

由此,当dp[i][j]时,如果s1[i]==s3[i+j],则尝试s1[i]s3[i+j]对应,如果dp[i-1][j]true,则dp[i][j]也为true。如果s2[j]==s3[i+j]则同样处理。

直到最后,判断dp[s1.length()-1][s2.length()-1]是否为true。为方便初始化,坐标后移了一位。

题目不厚道的出了s1.length()+s2.length() != s3.length()的数据,特判一下。

看到网上也都是O(n^2)的解法,我也就放心了。。。

96.Unique Binary Search Trees II

LeetCode目前为止感觉最暴力的。递归遍历所有情况,每次返回子问题(左右子树)的vector的解,两层循环组合这些解。

95.Unique Binary Search Trees

经典问题,卡特兰数,可递推,可用公式(公式用组合数,也要写循环)。

94.Binary Tree Inorder Traversal

数据结构基础

93.Restore IP Addresses

四层递归枚举分割位置,判断数字范围和前导零,处理字符串。

92.Reverse Linked List II

在表头添加一个(哨兵)会好写很多,额外的newhead可以帮助标记翻转之后更换了的头指针。

91.Decode Ways

递推:dp[i]表示前 i 个数字的解码种数。

`dp[i] = if(一)dp[i-1] + if(二)dp[i-2]``

i 位置不为0,可加上 i - 1位置的解。当当前位置和前一位置组成的两位数满足解码且高位不为0,可加上 i - 2 位置的解。

90.Subsets II

统计地存map里,map[i]= j 表示 S 中有 j 个 i。map是有序的,用迭代器递归枚举放入集合的个数。

也可以先排序,用set标记每个数时候被放入过,第一次放入之后才可以继续放同一个数。

代码是用map的方法。

89.Gray Code

格雷码有多种生成方法,可参考维基百科

88.Merge Sorted Array

从后往前,对 A 来说一个萝卜一个坑,肯定不会破坏前面的数据。具体看代码。

87.Scramble String

直接搜索可以过,记忆化搜索可提高效率。

dp[i][j][k]表示从 s1[i] 和 s2[j] 开始长度为 k 的字符串是否是scrambled string。

枚举分割位置,scrambled string要求字符串对应字母的个数是一致的,可以直接排序对比。递归终点是刚好只有一个字母。

86.Partition List

分存大小最后合并。

85.Maximal Rectangle

方法一:linecnt[i][j]统计第 i 行到第 j 位置有多少个连续的 '1',接下来枚举列,每一列相当于一次直方图最大矩形统计,计算每个位置向前和向后最远的不少于当前位置值的位置,每次更新结果,总复杂度O(n^2)

找(最远位置)用迭代指针,理论复杂度略高于O(n)

用单调栈,理论复杂度O(n)。

方法二:每个 1 的点当作一个矩形的底部,left[j]、right[j]、height[j]表示当前行第 j个位置这个点向左、右、上伸展的最大矩形的边界,作为滚动数组,下一行的数据可以由上一行结果得到,总复杂度O(n^2)。

left[j] = max(这一行最左, left[j](上一行最左) );

right[j] = min(这一行最右,right[j](上一行最右) );

height[j] = height[j - 1] + 1;

84.Largest Rectangle in Histogram

参考上一题Maximal Rectangle方法一。

83.Remove Duplicates from Sorted List II

加个表头乱搞吧。

82.Remove Duplicates from Sorted List

直接操作。

81.Search in Rotated Sorted Array II

以mid为界,左右两边至少有一边是有序的。由于不可避免地会有O(n)的可能性,所以确定的时候二分,不确定的时候单位缩减边界。

80.Remove Duplicates from Sorted Array II

记下放了几个,多了不放。

基础DFS。

78.Subsets

基础DFS。

77.Combinations

基础DFS。

76.Minimum Window Substring

先统计 T 中各字符都有多少个,然后两个下标一前(i)一后(j)在 S 上跑, 当 i 跑到把 T 中字符都包含的位置时候,让 j 追到第一个包含 T 的字符的地方,更新结果,去掉 j 这个位置字符的统计,让 i 继续跑,如此反复。

ij 都只遍历一遍 S,复杂度 O(n)

75.Sort Colors

轮流找:

找到哪个放哪个:

74.Search a 2D Matrix

写两个二分查找。或者把整个矩阵看作一维,直接二分,换算坐标。

73.Set Matrix Zeroes

O(m+n)的方法是容易想到的,而空间复杂度O(1),只要利用原矩阵的一行和一列来使用O(m+n)的方法就行了。

72.Edit Distance

动态规划,先初始化 dp[i][0]dp[0][i],即每个字符串对应空串的编辑距离为串长度,之后对每个位置取子问题加上当前位置 改、删、增得解的最小值。

71.Simplify Path

好烦人的题,没什么好说的。

70.Climbing Stairs

递推,就是斐波那契数列。

69.Sqrt(x)

牛顿迭代。 设输入为n,f(x)=x^2-n,解就是f(x)=0时的x。 设猜了一数x[0],那么在f(x)x[0]处的切线与x轴的交点x[1]更接近目标解(可画图看看)。 那么递推下去,x[i]=(x[i-1]+n/x[i-1])/2,用double,越推越精确,直到自己想要的精度。

68.Text Justification

每行限制长度,空格均匀插入,不能完全平均的情况下优先靠前的单词间隔。

最后一行特别处理,单词间只有一个空格,剩下的放在末尾。

67.Plus One

大整数加法。

66.Valid Number

用DFA也不麻烦,题目定义太模糊,为了理解规则错很多次也没办法。

65.Add Binary

翻转,大整数加法,再翻转。无心情优化。

64.Minimum Path Sum

递推

63.Unique Paths II

递推

62.Unique Paths

这是当年学组合数时候的经典题型吧。

61.Rotate List

因为k可能比长度大,需要求长度然后k对长度取模。那么就不要矫情地追求双指针一遍扫描了。

60.Permutation Sequence

一位一位算,每一位优先没使用过的较小的数字,而其后剩下的m个位置有 m! 种排列方法,用 k 减去,直到k不大于这个方法数,则这一位就是枚举到的这个数。

59.Spiral Matrix II

直接算每个位置的数是多少有木有很霸气→_→。 先看当前位置之外有几个嵌套的正方形,再看当前位置在当前正方形四条边的第几条,求出坐标(x,y)位置的数。

58.Length of Last Word

从后往前找。

57.Insert Interval

end 比 newInterval 的 start 小的 intervals 直接插入,从 end 比 newInterval 的 start 大的 intervals 开始,到 start 比 newInterval 的 end 大的 intervals 结束,对这部分区间合并,再把之后的 intervals直接插入,特判 newInterval 最小和最大两种极端情况。

56.Merge Intervals

先按start排个序,然后慢慢合并。。。

55.Jump Game

维护最大可跳距离,每个位置都枚举一次。

54.Spiral Matrix

模拟转一遍吧。写了俩代码,差不多,处理拐弯的方式略有不同。

代码一:

代码二:

53.Maximum Subarray

最大子串和,子串要求至少包含一个数字。

一个变量 sum 表示当前求得的子串和,当 sum 小于0时,对后面的子串没有贡献,则把 sum 置零,中间处理一下要求至少包含一个数字的要求即可。

52.N-Queens II

题目没说 n 的取值范围,就不用 位运算 做标记了。

老老实实开三个 bool 数组,一个标记纵列,另外两个标记两个斜列,一行一行DFS。

51.N-Queens

同上

50.Pow(x, n)

很多人用特判错过了 n=-2147483648 这么优美的 trick,而不特判的话,似乎只能 long long 了。

经典的快速幂,用二进制理解也好,用折半理解也好,网上很多资料。

49.Anagrams

这概念以前没听过诶。。题也没看到样例,不知道以后会不会更新,网上查了才明白啥意思。

调换单词字母顺序能一致的单词集合全放进答案。比如有tea, eat, aet,就都要放进答案,有cat, atc,就都要放进答案,而如果孤零零有个dog,没其他可和他一组的,那么就不放进答案。

手写hash能更快些,但是题目没给数据范围,给hash数组定多大都没合理性,干脆用unordered_map好了。

48.Rotate Image

四个一组,就地旋转。

47.Permutations II

有重复数字,把数字统计起来好了。因为题目没说数字大小,所以统计用了unordered_map。

也可以把数组排序,DFS时跳过重复的数字。

46.Permutations

虽然题目没说有没有重复数字。。既然 Permutations II 说有了,那就当这个没有吧。

传统DFS。

45.Jump Game II

维护一步最远到达的位置,到达这个位置之前的位置需要的步数都是一样的,到达这个位置的时候,下一步的最远位置已经更新完毕。

44.Wildcard Matching

同步扫描两个字符串,每当 p 遇到 * ,记录s和p的当前扫描位置,当 s 与 p 不匹配时,跑扫描指针回到 * 后一个字符, s 扫描指针回到上次遇到 * 之后与 p 开始匹配位置的下一个位置。

43.Multiply Strings

翻转num1和num2,大整数乘法,把结果再翻转。注意 int 和 char 的转换。

42.Trapping Rain Water

对于每个位置,取这个位置左边最高的右边最高的的较低者,如果较低者比这个位置高,则这个位置存水高度为较低者减该位置高度。

41.First Missing Positive

题目要求时间O(n),空间O(1),经分析,不得不破坏原数组 A。

方法一:

剔除非整数,把原数组 A 当作存在标记,存在的数 x 则 A[x-1]取负数。

方法二:把出现的符合范围的数swap到下标和数对应的位置,再次遍历,数和下标不对应则是第一个没出现的数。注意处理有重复数字。

40.Combination Sum

基础DFS

39.Combination Sum II

如果一个数没有被用,那么后面重复的这个数就别用,避免重复解。

38.Count and Say

直接模拟,递推。

37.Sudoku Solver

这道题考察回溯和数独结果的判断。ACM做过,就直接拿dancing links代码了,4ms。

关于dancing links,对于面试题来说变态了些,应该不至于考察。

 class Solution {
 public:
     int rw[10], cl[10], in[10], RW[81], CL[81], IN[81], goal;
     char buf[100];
     void Mark(int i, int num)
     {
         rw[RW[i]] ^= 1 << num;
         cl[CL[i]] ^= 1 << num;
         in[IN[i]] ^= 1 << num;
     }
     void init()
     {
         int i;
         for(i = 0; i < 10; ++ i)
             cl[i] = rw[i] = in[i] = 0;
         for(i = goal = 0; buf[i]; ++ i)
             goal += buf[i] == '.';
         for(i = 0; i < 81; ++ i)
         {
             RW[i] = i / 9, CL[i] = i % 9, IN[i] = i / 3 % 3 + i / 27 * 3;
             if(buf[i] != '.')
                 Mark(i, buf[i] - '1');
         }
     }
     inline int Judge(int i, int num)
     {return ~(rw[RW[i]] | cl[CL[i]] | in[IN[i]]) & (1 << num);}
     int Oper(int sx, int k, int cur)
     {
         Mark(sx, k), buf[sx] = k + '1';
         if(dfs(cur + 1)) return 1;
         Mark(sx, k), buf[sx] = '.';
         return 0;
     }
     int JudgeRWCLIN(int cur)
     {
         int i, j, k, x, cnt, sx;
         for(i = 0; i < 9; ++ i)
             for(k = 0; k < 9; ++ k)
             {
                 if(~rw[i] & (1 << k))
                 {
                     for(j = cnt = 0; j < 9; ++ j)
                     {
                         x = i * 9 + j;
                         if(buf[x] == '.' && Judge(x, k)) ++ cnt, sx = x;
                     }
                     if(cnt == 0) return 0;
                     else if(cnt == 1)
                         return Oper(sx, k, cur);
                 }
                 if(~cl[i] & (1 << k))
                 {
                     for(j = cnt = 0; j < 9; ++ j)
                     {
                         x = j * 9 + i;
                         if(buf[x] == '.' && Judge(x, k)) ++ cnt, sx = x;
                     }
                     if(cnt == 0) return 0;
                     else if(cnt == 1)
                         return Oper(sx, k, cur);
                 }
                 if(~in[i] & (1 << k))
                 {
                     for(j = cnt = 0; j < 9; ++ j)
                     {
                         x = i / 3 * 27 + j / 3 * 9 + i % 3 * 3 + j % 3;
                         if(buf[x] == '.' && Judge(x, k)) ++ cnt, sx = x;
                     }
                     if(cnt == 0) return 0;
                     else if(cnt == 1)
                         return Oper(sx, k, cur);
                 }
             }
         return 2;
     }

     bool dfs(int cur)
     {
         int i, j, num, cnt;
         if(cur == goal) return true;
         for(i = 0; i < 81; ++ i)
             if(buf[i] == '.')
             {
                 for(j = cnt = 0; j < 9; ++ j)
                     if(Judge(i, j)) ++ cnt, num = j;
                 if(cnt == 0) return false;
                 if(cnt == 1)
                         return Oper(i, num, cur);
             }
         if((num = JudgeRWCLIN(cur)) == 0) return false;
         else if(num == 1) return true;
         for(i = 0; i < 81; ++ i)
             if(buf[i] == '.')
             {
                 for(j = 0; j < 9; ++ j)
                     if(Judge(i, j))
                     {
                         Mark(i, j), buf[i] = j + '1';
                         if(dfs(cur + 1)) return true;
                         Mark(i, j), buf[i] = '.';
                     }
             }
         return false;
     }
     void solveSudoku(vector &board) {
         int site = 0;
         for(int i = 0; i < 9; i ++)
             for(int j = 0; j < 9; j ++)
                 buf[site ++] = board[i][j];
         init();
         dfs(0);
         site = 0;
         for(int i = 0; i < 9; i ++)
             for(int j = 0; j < 9; j ++)
                 board[i][j] = buf[site ++];
     }
 };

36.Valid Sudoku

行列九宫格都判断一下。

35.Search Insert Position

二分

34.Search for a Range

二分,容易错。可以用lower_bound和upper_bound。

手工代码:

STL:

33.Search in Rotated Sorted Array

还是二分,但是要判断一下 mid 在哪部分里。

32.Longest Valid Parentheses

这道题时间限制在O(n),用一个 stack 实现括号配对+统计, 为了方便实现,写成数组的形式。

对不同深度的括号配对统计个数,一层配对成功把该层统计结果加给上一层,这一层清空。

31.Next Permutation

从后往前找到第一个非降序的 num[i],再重新从后往前找到第一个比 num[i] 大的,swap(num[i], num[j]),再把 i 之后的排序。

30.Substring with Concatenation of All Words

直观的方法是枚举起点,判断这个起点下的子串是否合法,O(S.length()*L.size())

其实可以把 S 分成 L[0].length() 个序列,每个序列都是元素间相隔 L[0].length() 的(string开头),这些序列互不相干。

如下表,假设 L[0].length()=4,第一行数字为分组组号,第二行数字表示 S 的序号。

(0)|(1)|(2)|(3)|(0)|(1)|(2)|(3)|(0)|(1)|(2)|(3)|(0)|(1)|(2)|(3)|(0)|(1)|(2)|(3)|(0)|
 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16| 17| 18| 19| 20|

对每个序列,用单调队列的思路来处理,一个一个子串入队,当包含了 L 中所有 string 的时候,保存答案。当新元素入队时超出统计允许时————即 L 中有 3 个 “str”, 而这时候遇到第 4 个————则开始出队,一直出到队列里不足 3 个 “str”,然后继续。

这样复杂度为O(L[0].length() * S.length() / L[0].length()) = O(S.length())。目前提交结果是180ms。

29.Divide Two Integers

假设 dividend 与 divisor 正负一致, divisor^(2^n) 为最接近 dividend 的 divisor 的幂,那么令 newdividend = dividend - divisor^(2^n)ans = ans + 2^n,问题就更新为 newdividend 除以 divisor,如此迭代。用 divisor(2n) 是因为 divisor 不停地辗转加自己就可以得到了。

-2147483648 这样的极限数据,因为 int 范围是 -2147483648~+2147483647,发现负数比正数范围(多1),干脆把所有数都转成负数算,这样就避免用 long long 了。最后考察一下flag。

(如果转成正数的话,int 的 -(-2147483648)还是 -2147483648。。)

28.Implement strStr()

KMP。

27.Remove Element

两个游标 i, j 异步挪动,把不等于给定值的数往前挪。

26.Remove Duplicates from Sorted Array

两个游标 i, j 异步挪动,不重复值往前挪。

25.Reverse Nodes in k-Group

用头插法来做的,顺序插入到首节点之后,就反转了。每 k 个节点处理之后,把首节指针点移动到下 k 个的开头。最后面不足 k 个的话,再反转回来。

24.Swap Nodes in Pairs

Reverse Nodes in k-Group的简化版。

23.Merge k Sorted Lists

一个堆(这里用了优先级队列),把所有 list 的首元素放堆里,O(logn)取得最小值插入新队列,异步推进。

22.Generate Parentheses

DFS,保持当前右括号不多于左括号。

21.Merge Two Sorted Lists

归并排序的一次操作,设个哨兵头结点,结束后free。

20.Valid Parentheses

用栈配对。

19.Remove Nth Node From End of List

两个指针相隔 n 距离,前面的指针到了末尾,后面的指针就是删除的位置。

18.4Sum

尝试了O(n^2)的,但是应该常数很大吧,超时了。就是哈希存两两的和,然后通过查哈希表找到 两两+两两,要判断数字重复情况。这题数据量挺大的,O(n^3)如果用不太好的方式实现的话也会超。

O(n^3)方法:先对num排序,然后从两头枚举两个数,O(n^2),后两个数在前两个数之间的两端开始,和小了左边的往右,和大了右边的往左调整,O(n),总共O(n^3)

17.Letter Combinations of a Phone Number

基础DFS。

16.3Sum Closest

O(n^2),先排序,枚举第一个数,后两个数一个在第一个数后边一个开始,一个从 末尾开始,和4Sum类似调整。

15.3Sum

同上。

14.Longest Common Prefix

一个一个扫

13.Roman to Integer

各有各的方法,重点是记录(上一个)数比(这个)数大或小,来确定谁减谁。基本是右结合的,所以从后往前扫好处理些。

12.Integer to Roman

每个十进制位格式是一样的,只是字母替换一下。

11.Container With Most Water

从两端开始枚举,较高的挡板往中间枚举的话一定无法得到更优解,故反复从较低挡板向中间枚举,O(n)。

10.Regular Expression Matching

每遇到一个 * ,问题都会出现分枝,需要用到栈或者递归。

没有 * 的情况好处理,遇到 * 的时候,穷举所有匹配长度。

9.Palindrome Number

首先处理负数的trick。然后主要思路就是通过 while(...) a = a * 10 + x % 10; 来将 x 翻转。

但是注意到 x 很大的时候,翻转的 x 会超出 int 范围,也许会刚好成为另一个和 a 得出的数相等的正数,所以不能完全翻转后判断,而可以在翻转恰好一半的时候判断。

8.String to Integer (atoi)

任何类似多符号、符号数字间有空格的小问题都直接输出 0,这就好办了。处理越界用 long long。

7.Reverse Integer

还是关于越界的讨论,不过这道题本身没有设置处理方式,重点在于面试时的交流。

6.ZigZag Conversion

题意的 “z” 字形指一列nRows个,然后斜着往右上一格一个回到第一行,然后再一列nRows个。比如nRows=5,如下:

1          9          17          25
2       8 10       16 18       24 26
3    7    11    15    19    23    27    …
4 6       12 14       20 22       28 30
5         13          21          29

每行字母在原字符串中的间隔是有规律的,虽然两层for循环,但是s中每个字母只访问了一次,O(n)。

5.Longest Palindromic Substring

网上O(n)的方法是厉害啊。。。简单解释如下:

1、预处理字符串,前后加(哨兵)字符比如 !,每个字母旁边加辅助字符比如#,这样例如字符串 s="ababbcbb" 就变成 tmp="!#a#b#a#b#b#c#b#b#!"。这样的好处是不用讨论回文串长度的奇偶。

2、对转化后的串,维护一个 center 和一个 reach,center 是当前已发现的 reach 最远的回文串中心位置,reach 是这个回文串最右端的位置,center和reach可初始化为 1,即第一个#的位置。

3、维护一个数组vector r(tmp.length())r[i] 表示 i 位置为中心的回文串半径。

4、在考察位置 i 的时候,所有 j < i 的 r[j] 都是已知的子问题。如果 i 在 reach 的左边,则 i 包含在以 center 为中心的回文串中,那么可以想到,如果和 i 关于 center 对称位置的 mirrori 为中心的回文串覆盖范围没有到达 center 为中心的回文串边缘,则 i 为中心的回文串肯定和 mirrori 的一样。而如果 mirrori 的回文串到达了边缘甚至超过,或者 i 本来就在 reach 的右边,那么对 i 为中心的回文串进行一次扩展,则结果 或者刚好不扩展,或者一定更新了reach。无论怎样,这里都得到了 r[i]。知道了所有 r[i],答案就出来了。

核心问题在于第4步“对 i 为中心的回文串进行扩展”的复杂度。每次发生“对 i 扩展”,必然是对 reach 的扩展(也可能刚好不扩展,这个不影响复杂度),而 reach 的扩展范围是 tmp 的长度大约 2n,所以总复杂度为 O(n)。

4.Median of Two Sorted Arrays

如果 A[pa] < B[pb],那么 A[pa] 一定在 A 与 B 合并后的前 pa + pb + 2 个数中。

证明: A 中有 pa + 1 个数 <= A[pa],B 中有小于 pb + 1 个数 <= A[pa],合并后有少于pa + pb + 2 个数 <= A[pa]。

利用这个性质迭代找 A 与 B 合并后的第 k 大数。

3.Longest Substring Without Repeating Characters

维护一个不重复字符的区间。

代码一:

代码二:

2.Add Two Numbers

大整数加法的链表版。

1.Two Sum

哈希存位置,O(n)。