Note for LeetCode in Java (401~800)
刷题。祝我好运。
402. remove-k-digits
- 给一个纯数字组成的字符串,给一个整数k,要求删除k个数字后得到的数尽可能地小。例如
112
删除2个后需要得到1
。 - 找到规律,使用stack的思路+贪心法,每次将数字入栈,若当前数字比栈顶小,说明前面的数字应当删除,一直删除到栈顶数字不再比当前数字大,再入栈。最后保留下来的数字不一定删够了k个,需要twick索引只保留一部分栈里剩下的数字。
1 | class Solution { |
403. frog-jump
- 给一个数组表示石头所处的x坐标,青蛙每次只能跳上一次跳跃长度的-1,0,1三种可能,判断能否跳到最后一个石头。例如
[0,1,3,5,6,8,12,17]
是可以的,而[0,1,2,3,4,8,9,11]
就不行。 - 相当于BFS,每个石头处维护一个set存放他可以跳的长度,然后每次都往后跳看看能否有新的石头,有就更新那个石头的可跳长度。
1 | // BFS,从开头出发,不断更新后续可达石头的新步数,若中途更新到了最后一个石头,就可达 |
404. sum-of-left-leaves
- 给一个数,求所有左叶子的和。
- 递归求,只有是左孩子且是叶子才返回node.val。
1 | class Solution { |
405. convert-a-number-to-hexadecimal
- 将数字转换为十六进制字符串。
- 方法一:利用mask每次只取最后四个bit,然后直接map到字符拼接到hexStr的最前面,然后unsigned shift四位。
1 | final private char[] map = {'0', '1', '2', '3','4','5','6','7','8','9','a','b','c','d','e','f'}; |
- 方法二:更general的做法,可以推广到十进制转任意进制字符串。不过首先需要转成long并且过滤掉long前面填充的一堆符号位,然后取模得到的就是当前位的数值,直接map到字符;然后继续除。
1 | final private char[] map = {'0', '1', '2', '3','4','5','6','7','8','9','a','b','c','d','e','f'}; |
409. valid-word-abbreviation
- 给两个字符串word和abbr,word只含有小写字母,abbr除小写字母外含有数字表示可以替换成多少个字母,判断abbr是否是word的简写。例如
word
可以简写成w2d
。 - 注意corner case,例如
w4
就不是word
的简写了,01
也不是a
的简写。
1 | public boolean validWordAbbreviation(String word, String abbr) { |
410. split-array-largest-sum
- 给一个只含有非负整数的int数组和一个subArray数目m,将这个数组分成m个连续subarray,求他们的最大值最小是多少。
- 方法一:在学c++时老师讲过,最大值最小化,经典二分查找问题。一波流求最大值和sum分别作为下界和上界,然后进行二分查找,mid作为targetSum,即如果每个subarray都不超过这个targetSum需要划分成多少个子数组,如果多了说明targetSum太小,需要往前收缩;注意需要尽量biase到尽可能小的targetSum,联想到求first occurance的二分查找。
1 | class Solution { |
- 方法二:DP。。。
412. FizzBuzz
- 根据是否为3、5的倍数输出指定的字符串。skip。
413. arithmetic-slices
- 给一个int数组,求其中有多少段是等差数列。等差数列要求长度为3+。
- DP。当前的长度只取决于以之前一个元素结尾的等差数列长度,如果不等差了则长度归零。
1 | class Solution { |
414. third-maximum-number
- 给一个数组,求其中第三大的数字。
[2, 2, 3, 1] -> 1
.若第三大不存在(例如就两个数字)则返回最大的数字。[1, 2] -> 2
. 用pq搞定,pass。
1 | class Solution { |
416. partition-equal-subset-sum
- 给一个只含有正数的int数组,判断是否可以划分成两个和相等的数组。
- 和698类似的暴力做法,直接遍历找所有可能的组合。
1 | class Solution { |
- 其实这题想考察的是DP。
dp[i][j]
表示i
个数组成的和为j
,期中这i
个数不是全部都取。对于dp[i][j]
来说如果不取第i个数(对应索引为i - 1
),则直接来自dp[i - 1][j]
;如果取了第i个数,则是从dp[i - 1][j - nums[i - 1]]
转移过来。
1 | class Solution { |
417. pacific-atlantic-water-flow
- 给一个int二维数组,左边和上边连接pacific,右边和下边连接atlantic。若当前元素大于相邻元素,则可达。求所有可以同时到达两个海洋的坐标。
- 从四条边进行DFS。与平时的区别在于visited数组,这里需要维护两种visited信息,一种是从pacific来,一种是从atlantic来,因此考虑用bit小技巧。注意DFS的visited可以放到进入后进行,而BFS需要在进入之前进行,防止重复放入queue。
1 | class Solution { |
419. battleships-in-a-board
- 给一个二维char数组,其中含有
.
和X
字符,X
表示船,船只会横或者竖着放,船之间至少有一个.
。求船的个数。 - 直接算「第一个」出现的
X
,即左边和上面都不是X
的。
424. longest-repeating-character-replacement
- 给一个仅包含大写字母的字符串,再给一个k,表示假设可以有k次机会将其中的某些字母任意变成另一个字母,返回最长的相同字母的substring的长度。例如
ABAB
变2次,最长长度为4(AAAA
);AAABAABB
变1次,为6. - 这个替换是一一对应的吗?(不是,可以任意换成需要的字符。也就是可以多对一)
- 双指针 + producer/consumer的方法,快指针先往后求各个字母的计数,同时更新一个出现最多的字母的频数maxCount。当前后两指针所夹字母数大于了maxCount + k,说明已经超过了可以替换的数目,此时就需要挪慢指针来consume计数。至于为什么不需要每次都保持最精确的maxCount,因为我们只关心最大的,当前最大的挪出窗口后,计数肯定是减掉的,那么后续再出现的时候,不会错误地产生更大的计数,最大值再大也大不过历史峰值。解释来自这里.
1 | class Solution { |
425. word-squares
- 给一个wordList,将List中的String放入matrix中使得行、列的单词都来自于这个List。
- Trie + DFS,对于每个Trie节点,除了正常的nexts数组、isWord布尔值,额外维护一个List
保存以「到达当前TrieNode路径」为prefix的所有word。固定一个word之后,下一个词的prefix可以通过纵向append得到,具体规律见这个discussion.
1 | class Solution { |
426. convert-binary-search-tree-to-sorted-doubly-linked-list
- 给一个BST,将它转换成排好序的循环双向链表(头尾相接),返回头部。可以把左右孩子就看作是当前节点的前后链表节点,不需要额外搞ListNode类。
- BST要维持顺序,那就是用中序遍历。利用全局变量prev来记录每一个子树的结尾节点,先build左子树,然后把当前节点拼到prev的后面,再去继续build右子树即可。
1 | private Node prev = null; |
- 方法二:分治法。先把左右子树的循环双向链表build好,再把当前节点塞到中间,同时把新的前后循环连接一下。注意在分别build的时候,需要把root本身设一个自循环,这样就可以重复使用connect方法了。
1 | public Node treeToDoublyList(Node root) { |
428. serialize-and-deserialize-n-ary-tree
- 对N叉树实现与string的互相转换。实现方式只有一个限制,就是必须是stateless,即不能用函数外面的全局变量。
- 对于这个话题很多讨论比较有意思。首先是如何将字符串拼接起来,事实上直接
+
从performance的角度来说是最快的,但消耗的内粗很大,因为需要复制很多次。若已经有一个list of strings,直接用join最快。如果是on-the-fly,那就用StringBuilder. - 实现本身不难,因为实现很自由。例如直接存节点值和孩子节点数量,pre-order的方式递归拼入数组,用
,
连接。如果可以假设数字值域为[0, 65535]
,则连,
都不用,直接将数值转成unicode character即可,(char) (value + '0')
.
1 | class Codec { |
430. flatten-a-multilevel-doubly-linked-list
- 给一个nested的双向链表,将所有child节点都插入到父节点的后面。
- 方法一:递归,利用一个全局变量存放上一次flatten之后的最后一个节点,对于每一个节点都连到prev后面,然后flatten当前节点的子节点,然后再继续往后。
1 | Node prev = null; |
- 方法二:简单的遍历,当前节点有child时就到它的child那一层找到尾巴节点接到后面,然后继续遍历即可。但无法保证每个节点只遍历到一次。
1 | public Node flatten(Node head) { |
- 方法三:用stack记录next节点和child节点(注意push的顺序,保证先处理child节点),每次从stack中取节点连接。
1 | public Node flatten(Node head) { |
432. encode-n-ary-tree-to-binary-tree
- 实现一个类,能够将N-ary树转换为二叉树、也能把二叉树转回N-ary。
- 对于N-ary的孩子放到左子树,对于同一级的节点则一直放到右子树。
1 | class Codec { |
435. non-overlapping-intervals
- 给一个interval数组,求至少需要删除多少个interval才能让剩余的不重叠。相关的问题见56、252、253、452.
- 方法一:首先按照interval的起点从小到大排序,对于前后两个求overlap的部分,若有重叠,则无论如何至少得删掉一个,但是只保留重叠部分与后续比较。时间
O(NlogN)
.
1 | class Solution { |
- 转换思路,这题和求最多的non-overlapping interval个数一摸一样。统计最多的独立interval个数,首先根据interval的右界进行排序,然后取左界与当前的右界进行比较,如果左界大,说明是新的独立interval,直接计数++。最后返回总interval数减去独立interval数即可。时间
O(NlogN)
.
1 | class Solution { |
437. path-sum-iii
- 给一个二叉树,给一个目标值sum,求有几条从上往下累加的路径之和等于sum。
- 递归DFS,每次深入之前都先减掉当前节点的值。
1 | class Solution { |
- 优化:显然上面最原始的方式会有许多重复性计算,所以考虑使用memo存放从各个可能的根到当前节点的各种sum出现的次数,这样看看”当前sum减去目标和”出现过多少次即可。
1 | class Solution { |
438. find-all-anagrams-in-a-string
- 给一个字符串s和一个字符串p,求s中所有p的anagram子串的起始位置的List。
- 双指针 + producer/consumer的方法,map中存放p中每个字符及其对应出现的次数,快指针负责consume直到没有可用的字符(只需要管map中有的字符),这时看看快慢指针所夹字符的个数是否等于p;之后就挪动慢指针provide补回字符。
1 | class Solution { |
439. ternary-expression-parser
- 给一个三元运算的
? :
字符串,布尔表达式直接就是T或者F,其余的都是0-9的一位数字,求最终结果。例如F?1:T?4:5
最后就是4. - 方法一:Stack。想到了要用Stack,但是没有想出确切的方法。其实就是需要从后往前遍历,确定最终需要保留的是什么数字就好了,在stack中存放两个值以及问号,这样当下一个字符(准确说是前一个)出现时只需要判断栈顶是否是问号就知道当前字符是作为bool还是值。
1 | class Solution { |
- 方法二:递归DFS。对于每一个问号都进行计数++,每个冒号进行计数–,这样当计数归0的时候就找到了与问号对应的冒号,然后根据T/F递归找前后其中一部分的结果就好。
1 | public class Solution { |
442. find-all-duplicates-in-an-array
- 给一个
size = n
的int数组,其中每个int都在[1, n]
范围内。其中部分元素恰好出现了两次,剩余元素出现一次。求所有出现两次的元素,顺序无所谓。 - 暴力就是用Set,但如果要求不用额外空间且O(N)时间复杂度,就不行了。
- 充分利用
[1, n]
这个条件,每个int都可以作为index,那么就在index上面做文章,出现过的index就将元素标记一下,例如变为负数。这样在遍历数组过程中如果发现对应index已经是负数了,说明之前出现过。
1 | class Solution { |
443. string-compression
- 给一个字符数组,统计字符出现的个数实现压缩。例如
a,a,a,a,a,b,c,c,c,c,c,c,c,c,c,c,c,c,c,c,c,c,c
就是a,5,b,c,1,7
。要求in-place。 - 每次从头开始,以第一个为基准往后判断,直到不想等,再根据个数往里塞。
1 | class Solution { |
444. sequence-reconstruction
- 给一个int数组org,再给一个List of list,这些list是某个original sequence的子序列,问根据这些子序列是否可以唯一地还原成一个完整的序列且正是org.
- 经典的拓扑排序。用
Map<Integer, Set<Integer>>
维护邻接关系,用Map<Integer>
维护inDegrees关系
1 | class Solution { |
445. add-two-numbers-ii
- 给两个链表的头节点,每个节点表示一个数位,将两个数字相加得到的链表.
- 方法一:stack,将节点统统存入之后,逐个pop相加。
- 方法二:先求得长度,然后根据长度差来加。
1 | public ListNode addTwoNumbers(ListNode l1, ListNode l2) { |
448. find-all-numbers-disappeared-in-an-array
- 给一个长度为N的int数组,其中的值都在
1~N
之间,每个值可能出现1或2次,求中落下的数字。例如[4,3,2,7,8,2,3,1]
中,落下的数字是[5, 6]
. - 有点类似于swap求missing number,于是就想到用索引和value的关系来swap,最后和索引对应关系错误的就是missing的。但事实上不需要真的swap,而是可以在第一次遍历的时候,直接根据当前值跳到对应索引,然后将该处的值变为负数,这样就知道这个索引的值出现过了,第二次遍历直接将正值索引对应的数加入列表即可。
1 | class Solution { |
449. serialize-and-deserialize-bst
- 给一个BST,实现序列化和反序列化,即和String互相转换。
- 如果只是一个普通的二叉树,直接暴力写preorder和StringBuilder拼接没问题。但对于BST这个条件要怎么用呢?root一定比所有左边节点大、比所有右边节点小,那么在反序列化的时候直接通过val找到属于左边那半部分subtree去build即可。
1 | public class Codec { |
450. delete-node-in-a-bst
- 给一个BST和一个key,如果存在这个key就删除这个值,返回root(可能会更新)。
- 经典。首先是搜索这个key,然后就是删除节点。如果这个节点是叶子,直接返回null;如果是单边,返回非空child;如果是双边children,则需要取中序遍历的下一个节点来替换掉当前节点。一种做法是去右子树的最左节点的值放到当前节点,再把该最左节点删除。另一种是真正的替换
1 | class Solution { |
452. minimum-number-of-arrows-to-burst-balloons
- 给一个二维int数组,每一项表示一个气球的跨度,求最少用几根针可以扎破所有气球,注意气球的边界也算有效扎破范围。例如
[[10,16], [2,8], [1,6], [7,12]]
就至少需要两根针。 - 贪心做法,既然针蹭到也算扎破,那就按照气球的右边界从小到大排序,然后从头开始遍历,一旦发现当前区间的左边界大于了之前的右边界,就说明前面需要用新的针来继续扎后面的了。
1 | public int findMinArrowShots(int[][] points) { |
453. minimum-moves-to-equal-array-elements
- 给一个int数组,返回move几次能够让每个元素相等。move指的是对某位置以外的所有元素加1.
- 这题其实是个math problem,推导在此,假设所有数之和为sum,最小值为minNum,加了m次达到x,则有
sum + m * (n - 1) = x * n
以及minNum + m = x
,代入抵消一下就得到sum + mn - m = minNum * n + mn
,所求的m为sum - minNum * n = SUM(num_i - minNum)
。直接根据公式来,先求一波最小值,然后累加即可。
1 | class Solution { |
454. 4sum-ii
- 给四个数组,求其中有多少个组合使得
A[i] + B[j] + C[k] + D[l] = 0
. - Map统计A和B的所有和出现的次数,然后遍历C+D的组合,到map中找对应项。skip。
456. 132-pattern
- 给一个int数组,判断其中是否有满足
i < k < j
且A[i] < A[j] < A[k]
的形式,类似于1, 3, 2
. - 暴力的想法就是固定i和j,在中间找k。但事实上在中间找k这个操作可以利用stack优化。首先走一波存放minBefore,表示当前索引及之前的元素中的最小值。然后从后往前遍历原数组,如果出现了
minBefore < num
,相当于固定A[i]
和A[k]
,从stack中找有没有落在范围内的值。如果持续弹出栈顶,直到比minBefore大,这时再看看是否小于num。
1 | class Solution { |
457. circular-array-loop
- 给一个int数组,从任意一点出发,跳动步数就是数组的值,判断是否存在一个单一方向的、含有多于一个element的loop。数组中不含0.尝试不实用额外空间。
- 如果可以使用extra space,可以直接用Set记录到过的index以及某个path的index。如果不用额外空间呢?联想LinkedList找loop用快慢指针,这里也是一样。slow每次往后一步、fast每次两步,若全程能保持同一个方向移动且slow和fast相遇,则有loop.注意这里需要filter掉self-loop的元素。为了标记是否访问过而不使用Set,可以利用条件「原数组不含有0元素」,将访问过的元素改成0。保证一个方向的loop则是通过每一步经过的元素是否符号相同来判定的,也就是相乘大于0.
1 | class Solution { |
459. repeated-substring-pattern
- 给一个字符串,判断它是否能够通过子字符串自行重复拼接而成。
- 方法一:
O(N^2)
, 从小到达遍历各种子字符串长度,逐个判断是否能拼接成整个字符串。 - 方法二:
O(N)
使用KMP找字符串的common prefix和suffix的长度l
,n - l
表示非prefix或非suffix的部分,如果这个部分能够被总长度整除,就说明这个部分重复之后就能得到这个那个字符串。关于KMP,可以看1392. longest-happy-prefix加深理解。
1 | class Solution { |
460. Least Frequently Used Cache
- 实现最近最频繁使用的有限容量缓存,到达容量上限时evict最不频繁使用的key,若频繁情况相同则evict掉最早插入的。
- 首先考虑如何实现根据频数来evict,这就需要一个
(freq -> 元素)
的map来维护,由于频数持平时需要evict掉更久远的元素,因此这个map中就需要维护一个List,根据LRU使用doublelinkedlist可以在O(1)
删除。当缓存满了,需要丢掉最小的freq中最早插入的元素,这个“最小的freq”只需要一个变量维护即可,而不需要保持整个freq都是有序的。
1 | class LFUCache { |
461. hamming-distance
- 给两个int,求hamming distance. hamming distance指的是两个数不同的bit的个数,例如1001和0011就有两位不同。
- 异或之后看多少个bit。
1 | class Solution { |
463. island-perimeter
- 给一个0/1二维矩阵,求其中为1的island的周长。
- 方法一:BFS,每个1都先算它有四条边,然后根据邻接情况减掉不是边的即可��
1 | class Solution { |
- 方法二:找规律。对于每一个1的cell,看它的下方和右方neighbor是不是1,记录neighbor数,最后周长就是islands * 4 - neighbours * 2。
1 | public int islandPerimeter(int[][] grid) { |
464. can-i-win
- 给定一个最大可取的int,再给个目标值target,两个人轮流从
[1, int]
之间取值,用过的值就不能再用了,两个人取的值不断累加,恰好达到或超过target的人就赢了。问是否能稳赢。 - 经典的DFS递归。有两个状态需要维护,一个是可选的数字需要用map或者数组bucket存起来,一个是剩余的target。同样为了避免DFS重复计算,需要用一个map将中间结果存起来。如果不加memorize的话时间复杂度
O(N!)
,相当于从1到N每一步都有N, N-1, N-2…个选择。如果加了memorize,则提升到O(2^N)
,相当于1到N每个数字都有取或不取两种状态,可以保证访问过的状态不会重复heo访问,那么就是2^N
。
1 | class Solution { |
468. validate-ip-address
- 给一个字符串,返回他属于的IP地址类型,若不属于IPv4或IPv6,返回Neither. IPv4的规定是有四个数字组成,用
.
分开。 - 很没意思的一题,就是split之后各种判断,需要考虑各种edge case,例如
-0
,192.0.0.1.
。
1 | class Solution { |
470. implement-rand10-using-rand7
- 利用rand7实现rand10,返回随机数1-10.
- 把它想像成掷骰子,用7面骰子模拟10面骰子,最直接的想法是投多次。例如投两次的话,总共有
7*7
种可能性,为了映射到1~10
,最直接的办法就是取模。但是149直接取模并不是均匀分布的,因此可以直接将尾巴去掉,即只取到`140`,之所以可以这样是因为每个数字取到的概率都是一样的,我筛掉不取也一样。具体证明见这里。 - 由此可以推广,大模拟小的情况下可以直接忽略较大值或取较小值的模,例如用6面骰子模拟2面骰子,可以只取1、2,或者取
(x % 2) + 1
. 小模拟大则需要找到超过大值的最小幂,例如用3面骰子模拟11面骰子,则可以掷3面骰子3次(3*3*3 = 27
),取1~22
,最后取x % 11 + 1
。
1 | /** |
471. encode-string-with-shortest-length
- 给一个字符串,将它压缩成
k[part]
的形式,要求压缩后的长度比原来短(答案不唯一)。 - DFS + memo,尝试将字符串拆分成一半、1/3、1/4以此类推的子串,如果发现了重复出现的pattern就可以压缩,同时也尝试将字符串劈成左右两部分分别压缩,最后最小长度的那个。时间复杂度应该是O(N^4)。其中查找最短的重复出现pattern可以用KMP算法,KMP求的是“最长共同prefix和suffix”,也就对应“最短的重复pattern”。
1 | class Solution { |
- DP也是类似的思路,
dp[i][j]
表示以i为起点、j为长度的子字符串的压缩结果,因此后面的结果需要依赖于前面所有更短的字符串的压缩结果,所以dp最外层循环根据的就是长度,然后内层循环尝试将字符串本身压缩、或者divide and conquer左右两部分的压缩结果。这里用到了KMP。
1 | class Solution { |
472. concatenated-words
- 给一个字符串数组,求所有能通过其他字符串拼接而成的字符串。例如
[a, b, abb, bbab, c]
返回[abb, bbab]
. - 近似于暴力的做法:首先将数组按照长度进行排序,然后逐个判断是否能够通过更短的部分组成。这个判断的过程可以用到双指针+DP,利用双指针来取子字符串看看是否在先前出现过,如果出现过且子字符串往前部分也可以由别的部分组成,则到当前索引为止也是可以由其他组成的。假设字符串们平均长度为
L
,则判断部分O(L*L)
;主函数对字符串进行排序为O(NlogN)
,对每个字符串遍历调用判断,整体时间复杂度为O(N*L*L)
。
1 | class Solution { |
475. heaters
- 给两个数组,一个表示房屋的水平坐标(非负int)、另一个表示暖气的位置。求最小的暖气半径使得每个房子都能被覆盖。
- greedy其实就需要找到每个房子距离最近的暖气的距离,取最大值即可保证当暖气为该距离时所有的房子都会被覆盖到。因此对两个数组分别排序后,固定房子坐标,然后取「与当前暖气的距离」跟「与后续暖气的距离」比较,若与当前暖气的距离更近就不需要用到后续暖气来覆盖了,否则就继续往后找暖气。
1 | class Solution { |
476. number-complement
- 给一个正整数,求它的所有bit flip之后的正整数。例如
5 = 101
,就对应2 = 010
。 - 可以构造一个全是1的数字,直接异或/减去原数即可。
111 ^ 101 = 010
1 | class Solution { |
477. total-hamming-distance
- 给一个int数组,求这些数两两之间的hamming distance之和。hamming distance指的是两个数不同的bit的个数,例如1001和0011就有两位不同。
- 直接用mask每一个bit地看有多少个数x该位为1,然后x乘一下(N - x)就得到该位不同的数的个数了。
1 | class Solution { |
480. sliding-window-median
- 给一个数组,给一个窗口size = k,从前往后滑动窗口,求每一个范围的median。
- 用两个PriorityQueue分别维护大根堆(存的是较小的值)和小根堆(存的是较大的值),在往里存元素的时候先尝试往minHeap中存比堆顶大的值,不行就直接存入maxHeap。两个堆加起来存够k个元素之后,还需要根据两个堆的size进行调整,因为不一定刚好一半一半。匀完了之后,每次从两个堆中取最大、最小值,再根据size = k决定中位数是直接取中间还是求平均。当窗口往后挪了之后,需要从两个堆的其中一个中删除,PriorityQueue的
offer, poll, remove
是O(logN)
的,contains
是O(N)
的,retreive peek
是O(1)
的。
1 | class Solution { |
482. license-key-formatting
- 给一个字符串,只含有数字和字母,再给一个K,将字符以K个为一组组成licenseKey。skip.
484. find-permutation
- 给一个只有D和I的字符串,表示相邻两个数的大小关系下降和上升。求lexicographical最小的、符合这个升降关系的
1~n+1
的数组。 - 贪心做法,先一波升序填进去,然后再对应遍历字符串,对于D就一直往后找连续的D,将这一段reverse即可。
1 | public int[] findPermutation(String s) { |
485. max-consecutive-ones
- 给一个只含有0和1的数组,求最多连续出现1的个数。
- 用一个lastIndex记录上一个出现的1的位置,然后不断往后遍历数组,如果是1就更新count、否则就把lastIndex更新过来。
1 | class Solution { |
486. predict-the-winner
- 给一个int数组,两个玩家每次可以从两端任取一个数,轮流取完后比较取出数字之和,谁大谁赢(相等则player 1赢)。判断先选数字的player 1是否稳赢(两个玩家都会走最优)
- DP。是否赢需要依赖之前选数字的状态,最终胜负并不在意具体的sum是多少,而是比较两个玩家的sum,因此
dp[i][j]
存储nums[i...j]
中此时选择的玩家会比另一个玩家多多少分。相比上一步,当前玩家可以在两端分别选nums[i]或者nums[j],每次会选让自己分更多的,即Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]
(注意上一步存的是另一个玩家比自己多多少分,因此需要取负).注意到dp每次只会用到左侧和下侧相邻的cell,可以优化成只用一维数组的dp。
1 | class Solution { |
487. max-consecutive-ones-ii
- 给一个只含有0和1的数组,至多可以将一个0 flip成1,求最长连续出现1的个数。
- 利用双指针维护一个至多含有一个0的window,当0过多就移动左指针直到恢复。
1 | class Solution { |
- follow-up: 如果输入的数组无法全部存入内存?输入将以stream的形式传入,这样的话就不能直接存放整个数组,可以将零出现的index存入queue,当queue的size超过k的时候就说明window中零的个数过多,此时就将left移到
q.poll() + 1
即可。
489. robot-room-cleaner
- 给一个Robot机器人类,这个机器人初始化在一个房间内面朝上,0表示障碍、1表示空地。这个机器人可以左转、右转、前进(若遇到障碍/边界则返回false)、清扫。要求将这个房间完全清扫。
- 本质上就是考图的遍历,区别是只能用一个机器人通过DFS做。每次机器人进入一个cell的时候需要转到四个方向尝试前进,可以固定只向右转。四个方向都DFS完后会回到进入当前cell的方向,此时就需要回退到上一个cell,此时就需要实现一个掉头、前进、再掉头的步骤。时间复杂度为
O(1cells - 0cells)
,因为每个cell只会进入一次。
1 | class Solution { |
490. the-maze
- 给一个grid,0表示空地1表示障碍物,一颗球在里面滚动,只有碰到障碍物或者边缘才会停下,给起点和终点坐标判断能否到达。BFS. skip.
494. target-sum
- 给一个只含有非负数的int数组和一个target,给这些int加正号或负号进行求和,求共有多少中加符号的方式使得sum等于target。其中所有数的sum不会超过1000,且数组长度不超过20.
- 注意到了限制“所有数的sum不会超过1000”,就联想到了木桶法。每个bucket[index]表示和为index有多少种方式,那么读入新的数x时将当前index的数加到[index+x]和[index-x]处即可。注意不可对原数组直接操作。
1 | class Solution { |
495. teemo-attacking
- pass。
496. next-greater-element-i
- 给两个int数组,都不含重复元素,求nums1中元素在nums2中的next greater.不存在则设为-1.
- 首先处理一波nums2,从前往后入栈,每次入栈之前需要判断是否小于栈顶,如果大于了栈顶,说明栈中元素的next greater就是当前元素,用一个map存起来(不含重复元素就可以这样搞),最后遍历nums1的时候直接从map中取就可以了。
1 | class Solution { |
498. diagonal-traverse
- 给一个matrix,求蛇形遍历后得到的一维数组。
- 分情况讨论,向右上遍历的时候可能从上、右侧出去,向左下遍历的时候可能从左、下侧出去,对应调整index即可。pass。
499. the-maze-iii
- 给一个grid,0表示空地1表示障碍物,一颗球在里面滚动,只有碰到障碍物或者边缘才会停下,给起点和终点(和另两题的区别是这是一个洞,球滚到这里就会掉进去)坐标,求最短滚过的格子的路径(用u, d, l, r代替走过的上下左右),若有多个最短路径则取lexicographical更小的那个路径,若无法到达则返回
impossible
. - 和前面第二题相比又需要存多一个path的信息,同时PriorityQueue的比较函数也需要更新当滚过的路程一样长时需要比较String。
1 | class Solution { |
503. next-greater-element-ii
- 给一个circular数组,求每一个元素的下一个更大的元素的索引,如果不存在则设为-1。例如
[1,2,1]
返回[2,-1,2]
。 - 这种circular性质的,容易想到直接拼接一段重复的元素到后方,转换成普通数组找后续更大值,时间O(N^2)。此外还能利用stack存放索引,首先从后往前把所有元素都丢进去,然后i还是从后往前遍历原数组并与栈顶索引对应的元素比较,直到小于栈顶时才将栈顶存入结果数组。此时还需要将当前索引push到栈中,因为循环的下一步是往前一个,所以需要将当前的元素存入stack作为最接近的next candidate.
1 | class Solution { |
505. the-maze-ii
- 给一个grid,0表示空地1表示障碍物,一颗球在里面滚动,只有碰到障碍物或者边缘才会停下,给起点和终点坐标,求最短滚过的格子数,若无法到达则返回-1.
- 仍然是BFS,只不过此时需要利用PriorityQueue代替传统BFS的Queue,这个PQ的比较函数是将从起点滚过距离最短的放在前面,这样率先到达终点的就一定是最短路径。
508. most-frequent-subtree-sum
- 给一个二叉树,求所有subtree sum中出现最频繁的,tie则全都输出。
- 递归求sum过程中直接用map统计出现次数,最后导出来存入数组返回即可。skip。
509. fibonacci-number
- 实现斐波那契数列。
- 递归/memo递归/双变量都可以。还有两个没有见过的方法,一是用矩阵Matrix Exponentiation,这样只需要
O(logN)
时间&空间复杂度就可以了。二是用纯数学,用黄金比例可以O(1)
实现。具体见这里
510. inorder-successor-in-bst-ii
- 给一个BST中的节点(除了left, right, val还有parent),求在in-order遍历中它的下一个节点,即比他大的最小节点。
- 根据BST的定义,节点左子树全部比它小、右子树全部比它大。给定节点,如果它有右子树,则取右子树的最左节点即可。如果它没有右子树,说明在它上方某处,一直向上回溯,直到找到一个节点是parent的左子树,那么这个parent就是恰好比所有这堆左子树大的了。时间复杂度为
O(树高度)
,平均为O(logN)
,最坏O(N)
.
1 | /* |
513. find-bottom-left-tree-value
- 给一个二叉树,求最下面一层最左边的节点。
- 方法一:Iterative,从右往左进行层级遍历,最后一个遍历到的节点就是最下层的最左节点。
1 | class Solution { |
- 方法二:Recursive, 正常地从左到右前序遍历,但是会track深度,第一个达到新的深度的节点就一定是最左边的。
1 | class Solution { |
515. find-largest-value-in-each-tree-row
- 给一个树,返回它每一个level节点的最大值。
- 层级遍历嘛。DFS和BFS。
1 | class Solution { |
516. longest-palindromic-subsequence
- 给一个字符串,求其中最长的自对称的subsequence(顺序与原字符串一样但不一定是连续的)的长度。例如
bbbab
最长为4(bbbb
)。 - DP。和647一样也是从后往前更新DP数组,
dp[i][j]
表示从i到j(inclusive)的最长长度。
1 | class Solution { |
518. coin-change-2
- 给一个数组表示有哪些面额的硬币,每个面额的硬币有无限多个可以任取。给定一个目标值,求总共有多少种组合方式。
- DP。和前面的那个硬币题类似,这里dp[i]表示达到i这个值有多少组合方式。如果当前硬币的面额是x,则dp[i] = dp[i] + dp[i - x].
1 | class Solution { |
523. continuous-subarray-sum
- 给一个非负int数组和一个非负整数k,判断是否含有长度大于等于2的连续subarray whose sum是k的multiple。可以保证将原数组所有数加起来不会爆int。
- 方法一:暴力法,求膜的方式O(N^2)两重循环求sum。
- 方法二:求是否含有一部分使得sum是n*k,那么如果利用Map记录sum对应的索引,一路往后加x%k,当出现前面已经存在的sum的时候,说明这一路加的x刚好膜k得到0,即为k的倍数。注意需要特殊处理0,不可以膜0.
1 | class Solution { |
524. longest-word-in-dictionary-through-deleting
- 给一个字符串s,给一个单词List,求将s中部分字母删除后能得到的最长的在List中的单词,若长度相等则取lexicographical更短的。
- 遍历List中的单词,与s比较看是否是subsequence。基本是暴力做法,只不过prune掉了一些情况,只有当candidate比之前的结果更长或者lexicographical order更前才会计算。还有一种做法是先对List进行排序,长度长的在前、字典序小的在前,然后再直接遍历List,第一个subsequence即为所求。
525. contiguous-array
- 给一个只含0,1的int数组,求最长subarray的长度使得其中的0,1个数相等。
- 方法一:暴力破解,固定start和end依次看当前窗口的0,1个数。O(N^2)超时。
- 方法二:既然需要的是0,1相等的个数而不关心具体位置/顺序,也就是如果经过一波操作之后0和1的个数差回到原点,说明一波操作没有造成什么后果,也就是0,1个数相等。或者更近一步,将0先一波流替换成-1,这样只要sum为0就意味着相等,而且如果当前的sum在之前出现过,说明经过一波操作又回到原点,那么-1,1的个数也是相等的。因此想到用map记录sum出现的各个位置,只记录最早出现的位置,这样一旦后面出现了这个sum就可以求得最长长度了。
1 | class Solution { |
526. beautiful-arrangement
- 美丽安排指的是在数组中元素和下标之间有整除关系(谁除谁都行)。
- DFS即可,每次尝试不同元素。时间复杂度
O(n!)
.
1 | class Solution { |
528. random-pick-with-weight
- 给一个只含有正整数的数组,表示该index所占的权重,实现一个随机生成器按照这个权重来取对应的索引。
- 利用一个累加数组,将所有权重累加起来。然后根据总和生成随机数,再利用二分查找看看这个数应该落在哪个权重和的区间内,就可以取对应的索引了。
1 | class Solution { |
529. minesweeper
- 点击一个位置,根据是否有雷更新棋盘。如果是雷,直接改成叉叉并返回;如果没有点开并且周围八个相邻格子有雷,则改成雷的数目并返回;如果周围都没有雷,就扩散到相邻格子继续更新。
- 方法一:根据描述本身就蕴含了递归,所以自然想到DFS。
1 | class Solution { |
- 方法二:BFS,Queue中存放点击之后扩散的点(如果有的话),一直扩散直到Queue为空。但是和DFS需要区别的是,由于BFS会将相邻的所有E的格子都入队,很可能会出现重复,所以就直接在更新时就赋值为B,防止重复入队。
1 | class Solution { |
530. minimum-absolute-difference-in-bst
- 给一个BST,求任意两个节点之差的绝对值的最小值。
- BST的重要特性就是中序遍历能得到有序序列,而最小的差一定是相邻的两个节点。因此可以中序遍历的时候利用prev减一减。
1 | class Solution { |
532. k-diff-pairs-in-an-array
- 给一个int数组,找其中unique对儿使得两个数的差的绝对值等于k,求对儿数。
- 方法一:用map来count每个数字出现的次数,如果是新出现的数字且map中有对应的另一半就累加。注意用map是因为要处理
k = 0
的情况。 - 方法二:排序后双指针,如果发现gap较大说明需要挪动左指针、gap过小则需要挪动右指针。需要注意处理左指针连续相同值的情况,这就需要连续挪动直到前后值不相等。
1 | class Solution { |
535. encode-and-decode-tinyurl
- 实现一个含有encode和decode方法的类,能够转码和解码tinyURL。
- 这种映射关系必定需要Map,关键是如何建立这种从长到短的映射?利用随机数随机从一长串字符串中取字符,取够6个即形成了短码。如果这个短码已经存在,就需要再来一次生成新的短码,直到出现新的。
1 | public class Codec { |
536. construct-binary-tree-from-string
- 给一个由数字、
-
、括号组成的字符串,将它还原成一个二叉树,注意空树由""
表示而不是()
。一开始完全无法理解-
是干啥的,原来只是用来表示负数,囧。 - 方法一:看到这种括号嵌套就想到利用stack,到
(
直接忽略,碰到数字或者-
则将这个value提取出来后,再看看栈顶节点是否已经有left/right,对应添加上去后再入栈,这样就可以保证后续的孩子节点能够继续连到当前节点,碰到)
则说明栈顶节点已经处理完毕,直接弹出即可。
1 | public TreeNode str2tree(String s) { |
- 方法二:更自然的是想到递归,但是这样就不是one-pass的,因为每次需要根据括号的情况找到后续节点对应的字符串,需要不断地count括号,比如这个。
1 | public TreeNode str2tree(String s) { |
538. convert-bst-to-greater-tree
- 给一个BST,将每个节点的值加上BST中所有比他大的节点值,返回修改之后的greater树。
- 既然是BST,那么在中序遍历的时候就可以得到从小到大的序列了,因此使用一个全局的running sum从右往左求和即可滚雪球似的得到比当前节点大的所有值之和了。
1 | class Solution { |
- 如果不能用全局变量,就考虑传入一个参数作为running sum。对于每一个节点,比他大的节点可以出现在右孩子,或者他的祖先(如果他本身是左孩子的话)。由于没有prev链接,因此在递归时需要直接传入他的祖先中比他大的值之和。
1 | class Solution { |
539. minimum-time-difference
- 给一个表示时间的字符串数组,包含的字符串都是合法的
00:00 ~ 23:59
时间,求最小的两个时间之分钟差。注意23:59 + 1 = 00:00
,因此之差一分钟。 - 将全部都转为分钟,排个序之后相邻两个做对比.
540. single-element-in-a-sorted-array
- 给一个排好序的数组,每个数字都出现了两次except其中一个,求这个毒瘤。要求时间复杂度O(logN),空间(1).
- 二分查找,利用pair的特性,以偶数index与下一个元素为判断依据,若元素相等说明毒瘤出现在后半部分,若不想等说明出现在前面。edge case需要考虑单独元素出现在数组首位和末尾的情况。
1 | class Solution { |
543. diameter-of-binary-tree
- Zillow面试题刻骨铭心。给一个二叉树,求其中任意两个节点的path距离中最长长度。例如下面的树就有
4-2-1-3
和5-2-1-3
两个最长路径,都是3. - 对于当前节点有取和不取两种情况(但),取根则等于左深度加右深度,不取则在往下求深度的时候就可以顺便用一个全局变量去更新,时间复杂度就为O(N)了。
1 | class Solution { |
544. output-contest-matches
- 给一个整数n表示有多少支队伍,返回这些队伍的对决情况。例如n = 4时,返回
((1,4),(2,3))
. - 有点类似动态规划,n个格子存放当前的对阵情况,队伍减半后再继续套。
1 | class Solution { |
545. boundary-of-binary-tree
- 给一个二叉树,求它从左到下方到右的所有boundary的元素。
- 方法一:根据定义来写,则是老老实实先把所有左边界找出来、再把叶子节点找出来、再把右边界节点找出来。需要注意的是在遍历左边界时遵循preorder,当所有的左侧叶子节点都遍历完了再重新潜入一次找所有最下方节点(叶子节点),找完所有叶子结点之后再开始遍历右边界节点,遵循postorder.
1 | class Solution { |
- 方法二:如何one-pass只遍历一次呢?在潜入的时候其实就已经知道节点的身份了:若当前节点是左边界,潜入左child时肯定还是左边界;右边界亦然。若当前节点是左边界,潜入右child时,若左child是null,则当前继续是左边界,也就是一个AND的关系。若当前节点是右边界,潜入左child时,若右child为null,则继续时右边界。
1 | class Solution { |
547. friend-circles
- 给一个只含有0/1的二维矩阵,1表示row和col互为好友,求总共有多少个独立的朋友圈子。
- 经典的并查集。需要讨论的是时间复杂度。root数组相当于保存了N-ary的树,利用size可以保证每次union的时候都尽量保持树balance(size小的往大的merge),所以每次union相当于从最深处走到根,最大深度也就是log(N),所以时间复杂度是
log(N)
.TODO【并查集的复杂度分析】
1 | class Solution { |
548. split-array-with-equal-sum
- 给一个int数组,判断是否存在三个分割点i, j, k使得被这三个点分割出来的四个部分(不包含分割点)的sum相等。
- 方法一:类似于4sum,利用Set存储在之前出现过的相等的sum,然后固定中间点j,遍历可能的i,将前面两部分相等的sum存入set,然后遍历后半部分k,若也存在两部分相等的和且set中存在,则说明确实可以分成四个相等的部分。
1 | class Solution { |
- DFS也可破。枚举所有可能的part sum,然后dfs到后续部分判断是否可以根据这个part sum恰好得到四个部分。注意为了避免无效DFS,需要ignore连续出现的0。
1 | class Solution { |
549. binary-tree-longest-consecutive-sequence-ii
- 给一个二叉树,求其中路径最长的连续increasing或decreasing的长度,这个路径不一定是parent-child的,怎么上下左右都行,只要是连续即可。
- 不论怎么弯折,对于每一个节点来说其实就是看和孩子能否形成increase和decrease,可以则加一下就是一个弯折的路径了。
1 | class Solution { |
551. student-attendance-record-i
- 给一个字符串,若连续出现2次以上
L
、总共出现1次以上A
则返回false。pass.
554. brick-wall
- 给一个二维List表示每一行每一块砖各自的长度。求纵向切下来最少穿过的墙的个数。
- 最少的穿过的个数也就是求穿过最多缝隙的个数,也就事给定一个结束长度,最多的那个即为所求。用Map记录每一行的累加的结尾长度,不断更新最多的那个长度,最后wall的行数减去count即可。
1 | class Solution { |
556. next-greater-element-iii
- 给一个32bit的正整数,求十进制中相同数字组成的下一个更大值。例如
12
的下一个就是21
,1342
则是1423
。 - 若已经是最大的可能值?(返回-1)
- 对输入的数字从后往前遍历,找到连续的两个数字使得前面的(
i - 1
)小于后面的(i
),然后再从i + 1
开始往后找最小的大于i - 1
的数字,互换他俩,最后从i开始往后从小到大排个序即可。
1 | class Solution { |
559. maximum-depth-of-n-ary-tree
- 给一个多叉树,求最深的深度。DFS/BSF均可,pass。
560. subarray-sum-equals-k
- 给一个int数组和一个k,问有多少连续的subarray之和等于k。这些int都在
[-1000, 1000]
,数组长度最多20000。 - 一开始想用双指针,但有正有负,更新条件不好搞。正解是使用Map,在计算sum的时候顺便看看之前是否出现过sum - k。这其实和path sum III 很像,都是利用prefix sum.
1 | class Solution { |
562. longest-line-of-consecutive-one-in-matrix
- 给一个只含有0和1的二维数组,求横、竖、两个斜对角的连续出现1的最长长度。
- 方法一:O(N^2)从每个点出发往四个方向分别遍历,求最长长度。
1 | class Solution { |
1 | class Solution { |
563. binary-tree-tilt
- 给一个二叉树,求每一个节点的左右子树和的差的绝对值之和。
- 直接后序遍历求sum搞定。pass。
565. array-nesting
- 给一个长度为N的int数组,其中元素为
0 ~ N-1
。从nums[i]
开始往后跳,nums[nums[i]]
持续跳直到回到原处。求所有这些自循环链接中的最长长度。 - 方法一:利用visited数组,模拟跳动。
- 方法二:不需要额外数组,利用
0 ~ N-1
这个条件直接用一些trick来重复使用input array. 常见手段包括:- Negating: 既然都是正数,不妨用负数表示visited。
- Modulo: 加上n来表示visited,最后
% N
即可得到原值。 - Sorting: 将
nums[i]
放到i
处,但这里就不适用了。
566. reshape-the-matrix
- 给一个二维数组,返回reshape之后的。pass.
567. permutation-in-string
- 给两个字符串,判断s1的permutation是否包含在s2中,例如
s1 = "ab" s2 = "eidbaooo"
返回true,因为s2包含了ba
。 - 其实这个s1的permutation并不用真的一个个求出来,在意的只是s1的每个字符及其出现次数,因此用一个map O(N)扫一波就好了。然后就对s2进行双指针 + producer/consumer操作,如果消耗完map中所有字符的时候恰好前后指针间距等于s1的长度,说明就是permutation的一种了,返回true。
1 | class Solution { |
572. subtree-of-another-tree
- 给两棵树,判断后者是不是前者的子树。子树指的是还有一个任意节点为根的子树,结构、数值完全一样。
- 递归搞定。先判断两个树是否相同,若相同直接就是子树了。若不同则需要到左右子树进行递归,判断t是否是左/右的子树。
1 | class Solution { |
575. distribute-candies
- 给一个数组表示糖果的id,其中可能有重复,且糖果数量一定是偶数。要求将其分成两部分,问如果想尝最多的不同的糖果,有多少种。例如
[3,2,2,1,3,1]
就有三种,[7,3,1,4,3,7,4,3,7]
就有四种。要求时间复杂度最差O(N*lgN)
,空间复杂度O(N)。 - 先排序,然后双指针一个从前往后,一个从后往前。left指针负责将糖果存入set,right则是调取后方的糖果往前替换,当left发现当前糖果吃过了,就从right那里swap过来继续判断,直到出现新的糖果或者穷尽。
1 | private static int maxCandy(int[] candies) { |
581. shortest-unsorted-continuous-subarray
- 给一个部分部分有序的数组,求将其中哪一部分排序之后整个数组就都有序了,求最短的区间的长度。
- 首先从左往右逆序对,然后从右往左找逆序对。这样就有了一个大致区间,但是还需要找区间内的min和max,分别往前和往后遍历看看是否真的完全符合,否则还需要扩展区间。例如
[1,3,6,4,8,2,7,10]
在前两步之后找到得失[6,4]
和[8,2]
实际上前面的3和后面的1都需要加入进来。
1 | class Solution { |
582. kill-process
- 给两个pid的int list,分别表示进程id和parent进程id。给一个id,从它出发找出所有后续pid,返回所有被杀掉的进程id。
- 直接map表示
pid -> list of child id
,然后递归/迭代找后续pid即可。pass.
594. longest-harmonious-subsequence
- 给一个int数组,求其中最大和最小值恰好为1的非连续子序列。
- 用Map存每个值出现的次数,然后遍历Map取key相差1都存在的进行更新。
1 | class Solution { |
598. range-addition-ii
- 给一个二维数组的规模m和n,初始值为0,再给一个ops二维数组,每个op表示前x行和前y列都加1.求最终最大值的个数。例如
m = 3, n = 3, operations = [[2,2],[3,3]]
,那么就是先给左上方2*2
加1,再给3*3
加1,最后就有4个最大值(2)。 - 直接找行和列的最小值,相乘即可。m和n甚至都没啥用。
1 | class Solution { |
600. non-negative-integers-without-consecutive-ones
- 给一个正数num,求[0, num]之间的bitString不含连续1的数字的个数。
- 方法一:DP。对于bitString有两种可能,以1结尾或以0结尾。为了不出现连续的1,对于0结尾的数字可以拼上0或1,而对于1结尾的数字就只能拼上0.Geeks4Geeks上面给的是bitString的长度,这里也可以用类似的方法。不过由于这里num的存在可能需要砍掉一部分结果,因此在最后需要多一步判断。如果num中出现了连续的
xx00xxx
(注意是从右往左遍历),而如果没有这个限制xx10xxx, xx01xxx
等都可能算进去,因此需要减去前一个0到最前面的数字位数所保存的endWithOne的值。
1 | class Solution { |
- 方法二:constant space的DP。
604. design-compressed-string-iterator
- 给一个字符加数字组成的字符串,实现next、hasNext函数遍历这个字符串。例如
L20J3B8
这样。 - 一开始直接根据频数全部存入queue,后来发现如果某个数频数特别大,而实际用不到那么多项就很不划算。因此就自定义类来搞了。写出来是这样.
605. can-place-flowers
- 给一个只含有0和1的数组,1表示该处被种了花,0表示可以种,同时相邻的位置不能同时种花。给一个花数n,判断能否种到所给的花池中。
- 方法一:想到了greedy的方法,每次判断0前后是否都为0,可以就直接设为1.
1 | class Solution { |
- 方法二:计算0的个数,碰到1就计算前面最多可以放多少0,同时重置计数。注意初始化count = 1,比如
0 0 1
在碰到1的时候需要保证slot为1,如果count初始化为0就无法得到了。
1 | class Solution { |
606. construct-string-from-binary-tree
- 给一个二叉树,encode成括号分割的字符串。
- 递归拼接。注意左子树和右子树为空时加不加括号需要加判断。
1 | class Solution { |
609. find-duplicate-file-in-system
- 给一个字符串数组,每个字符串中表示某路径下的所有文件以及内容,求相同文件内容的文件路径并存入List。比较有意思的是follow-up,解答参考这里:在真实的文件系统中你会选择BFS还是DFS?(BFS。虽然会消耗更多空间,但是可以利用locality提速)如果每个文件内容非常巨大怎么办?(不直接hash文件内容,而是首先根据文件大小判断是否是同一个文件,然后再取文件其中一部分进行hash)
- 直接以内容为key、路径&文件名为value存入map。最坏时间复杂度是O(N^2 * k),N是文件个数,k是文件大小。
1 | class Solution { |
611. valid-triangle-number
- 给一个int数组表示边长,问这些边可以组成多少个三角形。(这些边可能重复,但是算作不同的边)
- 三角形任意两边之和大于第三边,这个任意其实指的是起码较小的两边之和大于最大边。
1 | class Solution { |
616. add-bold-tag-in-string
- 给一个字符串s和一个字符串数组dict,若dict中的词在s中出现则需要加粗,例如
abc
加粗成<b>abc</b>
。 - 方法一:近似于暴力的做法,s逐位往后挪,对于每一个dict中的词都取出来用startsWith判断,用一个boolean数组标记是否加粗。
1 | class Solution { |
- 方法二:直接使用indexOf将所有词出现的位置标出来,同样用一个boolean数组标记。
1 | class Solution { |
- 方法二:首先将所有dict中出现的位置找出来,用Interval表示,然后就转化成了merge intervals的问题。
621. task-scheduler
- 给一个char数组,每个char表示一个task的名字;然后给一个interval表示相同的task必须经过这么多时间之后才能再次执行。求执行完所有任务所需要的时间。
- greedy可解,即以所给的interval作为周期,每次按频数从多到少地放task,如果周期没有用完而后续还有任务则需要把idle的时间也加进去。
1 | class Solution { |
[622. design-circular-queue] (https://leetcode.com/problems/design-circular-queue/)
- 设计并实现一个循环队列,给定初始长度为k,根据操作(enqueue/dequeue)成功与否返回boolean.
- 其实不难,只是需要想清楚逻辑。将数组想像成无限长的,利用头尾两个index和len,每次enqueueu挪动尾指针(初始为-1)、dequeue挪动头指针。
623. add-one-row-to-tree
- 给一个二叉树,root深度为1,给一个value和深度d,在d处插入值为value的节点,继承原先的左、右子树。返回插入完成后的root。
- 有三种方法。一是直接BFS层级遍历,在
d - 1
层停下来插入。二是DFS并利用currDepth来跟踪当前节点的深度从而决定是否插入。三是无需额外递归函数的DFS,通过直接修改传入的d
值来决定是否到达了需要插入的层数,并巧妙利用d = 1或0来决定插入左边还是右边。
1 | class Solution { |
624. design-search-autocomplete-system
- 实现一个搜索框按照历史搜索频数排序的自动推荐搜索词条系统。初始化时会提供一串历史搜索词条和对应频数,每次用户输入一个字符就需要看历史中是否出现过以此为开头的,按照出现频数返回前三个词条。当用户输入
#
时表示输入结束,将当前的输入词条补充到频数统计中。输入的只有小写字母和空格。 - 方法一:传统的bucket + Map方法。根据第一个字母划分成26个buckets,首先将最开始给出的词条存入对应bucket的map中。用户没输入一个字符就到对应的bucket中取map,看看是否有key是以当前输入的字符串开头的,将所有符合的词条排序返回。初始化时间复杂度为
O(k*l + 26)
,其中k为词条平均长度、总共有l个不同的词条,这里主要是消耗在对各个词条字符串计算哈希值。input时间复杂度为O(s + mlogm)
,其中s为bucket中取出map的规模、m符合以当前输入开头的key的个数,需要排序。
1 | class AutocompleteSystem { |
- 方法二:既然都是小写字母+空格,完全可以用Trie来实现搜索。对于每个Trie节点存放后续节点数组,共27个(a-z加上空格)。与一般Trie搜索不同的是,只要在traverse过程中碰到节点的count不为0,那么经过路径所拼接成的string就是一个合法的词条了,需要加到返回的list中。假设l个词条、平均长度为k,初始化时间复杂度为
O(k*l)
;input时假设当前已输入的长度为p、trie有效后续节点为q,时间复杂度为O(p + q + mlogm)
.
1 | class AutocompleteSystem { |
628. maximum-product-of-three-numbers
- 给一个int数组,求其中任意三个数的最大乘积(不用考虑越界问题)。
- naive的想法是排序后取三个max,但实际上只需要用到三个max以及两个可能为负数的min。
1 | class Solution { |
631. design-excel-sum-formula
- 实现一个excel类,能够set、get、sum,单元格如果修改了对应的sum也要更新。
- 根据需求确定实现方式。假如是read heavy,那就需要让get最快,牺牲set和sum的时间。将单元格之间的关系想像成subscribe的关系,单元格永远保持在最新状态,set时更新所有包含它的sum所处的单元格,同时取消旧的sum subscription;sum的时候就是subscribe到对应的单元格中。subscribe关系通过两个map实现。
1 | class Excel { |
- 假如是set heavy,那么可以set的时候直接保存值,sum的时候保存需要sum的单元格,get的时候再从各个单元格中取值相加。
632. smallest-range
- 给一个
List<List<Integer>>
,每行List内部是排好序的,求一个区间使其包括每一行的某个元素。例如[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
,返回[20,24]
. - 类似于merge k sorted list,自定义一个Node类存放值、所属的行数、所处的列数信息,每次从每个List中取值存入PriorityQueue,然后每次从pq中poll掉元素的下一个作为新的元素存入pq。
1 | class Solution { |
633. sum-of-square-numbers
- 给一个非负数,判断它是否是两个整数的平方和。
- 方法一:类似two sum,把每个整数的平方和存入set,判断set中是否有target - curr即可。
1 | class Solution { |
- 方法二:双指针,同时从0和sqrt(num)出发往中间逼近,若平方和大了则左移右指针、若小了则右移左指针。但
1 | public boolean judgeSquareSum(int c) { |
636. exclusive-time-of-functions
- 给一个log数组,每个log包含
function_id:start_or_end:timestamp
形式的字符串,求每个function执行时间长度。注意这些function的执行可能嵌套、也可能递归调用。 - 经典的Stack题,需要用Stack记录function_id,这样在后续log来的时候,如果是start,说明栈顶函数暂停执行了,需要先把它的时间存起来(当前时间戳减去之前的时间戳);如果是end,说明栈顶函数彻底执行完了,此时的时间计算需要加上end的这个时间戳。
1 | class Solution { |
637. average-of-levels-in-binary-tree
- 给一个二叉树,求每一层的平均数。
- 还是层级遍历的变形,主要是防止求平均值的时候越界,用了double,这样求平均值的时候也方便很多。写出来是这样。
638. shopping-offers
- 给一个list表示商品单价,然后给一些购买组合,最后给一个target,求组成target所需的最小开销。
- DFS+memo。对于每一个优惠组合都进行尝试,如果有商品数小于target,则可以取当前开销后继续DFS,否则说明当前组合超过需要的了,直接break。在暴力尝试所有购买组合的过程中,target可能会被反复访问到,所以用一个map表示target对应的最小开销即可。
1 | class Solution { |
646. maximum-length-of-pair-chain
- 给一个pair的数组,每个pair可以作为chain的节点。节点
[c, d]
能够连到[a, b]
后面的条件是b < c
。求最长的链长度。 - DP。
len[i]
表示以pair[i]结尾的链的长度,那么在双重循环时,就需要找到pairs[j]使得pairs[j][1] < pairs[i][0]
。
1 | class Solution { |
647. palindromic-substrings
- 给一个字符串,求其中自对称的子串的个数。例如
aaa
就有6个,aba
就有4个。 - DP。
dp[i][j]
表示从第i个字符到第j个字符是否对称,当判断第i
和第j
个字符的时候,如果相等则需要用到i + 1
到j - 1
之间的结果(若也对称则当前这个也是对称的),因此需要从后往前递推更新DP数组才行。
1 | class Solution { |
648. replace-words
- 给一个List的dict表示词根,然后给一个sentence String,将其中以词根开头的单词替换成词根,返回修改后的String。
- 方法一:直接用Set存放这些词根,然后split之后暴力取每一个单词,再逐一取字符append判断是否在Set中,有就替换过去。
1 | class Solution { |
- 方法二:使用Trie,将dict中的所有词根都存入Trie,然后还是取出来判断这些word是否有前缀出现在Trie中。
1 | class Solution { |
650. 2-keys-keyboard
- 假设有一个2键键盘,分别为全选屏幕上的字符复制、粘贴。开始时屏幕上有一个字符A,求输出n个A最少需要按几次键盘。
- 朴素DP:最后按下的键一定是粘贴,不知道的是在前方何时按下复制,因此需要暴力遍历。
dp[n]
表示产生n个A所需的最小按键次数,最开始屏幕上就有一个A,因此dp[1] = 0
. 对于dp[k]
,假设在dp[i]
处按下了复制键复制了屏幕上的i
个A,之后粘贴(k - i)/i
次,加上按下的一次复制,总共为k / i
次。
1 | class Solution { |
- 方法二:较为specific的方法。假设分为
[cpp][cpppp][cp]
组,每组的按键次数为l1, l2, l3,则最后得到的总数N = l1 * l2 * l3
,因此问题转换为求N的所有素数factors,而且这个按键次数一定是最少的,因为pq >= p + q
.
1 | class Solution { |
651. 4-keys-keyboard
- 假设有一个4键键盘,分别为输入A、全选、复制、粘贴。求一共按N次的情况下最多能够输出多少A。
- DP。
652. find-duplicate-subtrees
- 给一个二叉树,返回一个包含所有duplicate的子树根节点的List。例如下面的树就有2-4和4两个duplicate的子树。
1 | 1 |
- 利用encoding tree的思路,对于每一个节点为root的树都进行一波类似前序遍历点操作,将遍历结果encode成字符串作为key、计数作为value存入map。一旦出现了两次就加入结果List。
1 | class Solution { |
653. two-sum-iv-input-is-a-bst
- 给一个二叉搜索树和一个sum值,判断树中是否存在两个node之和等于sum。
- 朴素想法,对于每个可能的值进行O(logN)的搜索,因此总的时间复杂度就是O(NlogN),而空间复杂度如果考虑递归栈的话就是O(TreeHeight)。
1 | class Solution { |
- 方法二:用BST中序遍历转换成有序数组,再用双指针分别从头和尾往中间找。时间O(N),空间O(N).
1 | class Solution { |
654. maximum-binary-tree
- 给一个不重复的int数组表示的二叉树节点value,最大值作为root,左侧子数组对应root左子树,右侧子数组对应root右子树,重新建树并返回root节点。
- 方法一:直接递归解决,但是时间复杂度最坏情况是O(N^2)。
1 | public TreeNode constructMaximumBinaryTree(int[] nums) { |
- 方法二:利用Stack可以达到O(N)时间复杂度,关键是发现规律,即「当前节点的左孩子一定是在左侧大于它的最远节点右侧的小于当前val的最左节点,同理右孩子一定是在右边较大节点左侧的小于当前节点值的最右节点」。在Stack中需要栈底到栈顶是从大到小的,一旦新的节点更大,就要不断pop,同时将此时pop出来的节点作为新节点的左节点,这样就能实现第一个要求。第二个要求则是在插入的时候,将栈顶的右孩子暂时指向新节点,同时将新节点入栈,之后如果有比新节点更大但没有前一个节点大的节点加入,则又回指向该节点了。
1 | public TreeNode constructMaximumBinaryTree(int[] nums) { |
655. print-binary-tree
- 给一个二叉树,将每一层每个节点的值打印成字符串List,若为null则打印成空字符串。
- 方法一:递归。首先需要知道树的高度H才能确定每一层需要打印多少字符串。将List全部初始化为
""
后,对每一层List的终点进行赋值,然后递归到下一层对左右子节点继续赋值。
1 | class Solution { |
- 方法二:在populate中不递归调用,二是使用Queue进行BFS,对于每一层也是取中点进行赋值,然后将当前节点的左右孩子入队。
657. judge-route-circle
- 给一个字符串表示一个移动的seq,判断最终是否回到远点。skip.
658. find-k-closest-elements
- 在一个排好序的数组中��找距离x最近的k个元素,若有tie则尽量取更小的值。
- 二分查找找到x所在位置/若x存在则应该处在的index,然后取它左边的元素作为left、本身作为right,双指针前后取即可。为了提高insert效率,使用linkedlist的addfirst。
1 | class Solution { |
662. maximum-width-of-binary-tree
- 给一个二叉树,求最大宽度,即最左节点和最右节点之间的间隔。
- 在dfs过程中记录最左节点的id(类似于数组存储二叉树的形式),然后在遍历过程中根据level和当前id求间隔。
1 | class Solution { |
663. equal-tree-partition
- 给一个二叉树,判断是否可能通过移除一个edge使得两个拆分出来的树的节点sum相等。
- 方法一:使用Set存放所有可能的sum,然后在根部直接
/ 2
看看在Set中是否存在。时间、空间都是O(N)
. - 方法二:首先一波流求总的sum,然后在递归逐个节点求sum,看看总sum减去当前sum是否就是当前sum。需要注意edge case
[0, -1, 1]
,只要当前节点不是root即可。这样时间也是O(N)
,空间为O(Height)
。
1 | class Solution { |
- 方法三:直接修改节点值,存放每个子树的sum。逐层判断即可,也需要排除root。
665. non-decreasing-array
- 给一个int数组,问能否只修改其中一个元素使得整个数组non-decending.
- greedy。对于当前元素与之前一位的比较,如果之前一位更大,就需要考虑是将当前元素拔高还是将之前元素降低。如果要保证后续尽量少操作,应当尽量把之前元素降低,但是还需要考虑再之前一个元素:如果再之前一个元素比当前元素大,即形成
3,4,2
的局面,则为了保证操作数最少,只能将当前元素拔高;否则就是类似与3,6,4
的局面,将6
降低即可。
1 | class Solution { |
666. path-sum-iv
- 给一个int数组,每个数字都有三个digit,表示一个二叉树中的
深度、从左到右第几个、值
。求这个树的所有root到leaf的path sum. - 不用构造树,可以直接根据层数、索引来确定后续的节点是什么,和普通的遍历一样进行DFS就可以了。
1 | class Solution { |
669. trim-a-binary-search-tree
- 给一个BST和一个值域[L, R],只保留BST中属于该值域的节点。递归搞定,skip。
670. maximum-swap
- 给一个非负数,求至多将其中两个digit互换位置之后所能得到的最大数。例如
9987
就是本身,9978
是9987
,958469
是998465
. - 暗中观察规律就是找其中一个小的数字并找在它右侧的最大数,交换。因此首先需要记录每个数字最后出现的位置,然后从原数字第一位开始遍历,从最大的数字开始比较,一旦找到比自己大且排在自己后面的数字就可以直接交换位置了。
1 | class Solution { |
671. second-minimum-node-in-a-binary-tree
- 给一个特殊的二叉树,每一个节点只有0或2个children,且值是两个子节点的较小值。求树中第二小的值,若没有,返回-1.
- 既然找的是比最小值大的最小的值,就用递归的方法在左右两边分别找比最小值的大的最小值,然后比较一下即可。
1 | class Solution { |
673. number-of-longest-increasing-subsequence
- 给一个数组,求其中最长递增的subsequence的个数。如
[1,3,5,4,7]
中有两个长度为4的subsequence。 - DP。用一个len[k]数组记录以k结尾的字符处的最长长度,
count[k]
记录对应的计数。双重循环时,当nums[i] > nums[j]
,若len[j] + 1 > len[i]
则需要更新i处的长度,同时count也直接更新;若len[j] + 1 == len[i]
,则说明刚好从j过来可以形成递增sequence,直接累加就行了(一开始以为是lc300求长度,就用stack做了,然而stack这个greedy做法也是错误的,还是需要上DP。。
1 | class Solution { |
674. longest-continuous-increasing-subsequence
- 给一个数组,求其中最长递增的连续subarray的长度。如
[1,2,3,4,5,6,5,4,3,4,5]
就是6,[2,2,2,2,2]
就是1. - 贪心法,只有大于前面元素才更新,一旦小于就更新到总的里面。注意最后返回之前还要取一次max。
1 | class Solution { |
676. implement-magic-dictionary
- 实现
buildDict
和search
方法,search时判断能否通过「替换一个字符」的方式使得修改后的字符串包含在dict中,返回boolean。例如给["hello", "leetcode"]
,搜索hhllo
就返回true、搜索hello
返回false。 - 方法一:dict就想到选择map,在build时对于每个字符串,将其中每个字符替换成特殊字符如
*
,将替换后的字符串作为key、被替换的字符作为value存入map。如果出现相同的key,则说明这个位置可以放任何字符(例如hello, hallo
的第二位);在搜索时也是对每个字符替换,然后看map中有没有,判断一下当前字符是否是value的字符(防止indentical)。
1 | class MagicDictionary { |
- 方法二:使用Trie。build的时候就正常地创建Trie,然后在search的时候逐个位置替换26个字符,每换一次就在Trie中搜索。Trie的效率感觉不高啊,感觉有square级别。
1 | class MagicDictionary { |
678. valid-parenthesis-string
- 给一个只含有
(
,*
,)
的字符串,其中*
可以是任何一种括号,或者为空,判断字符串是否合法。 - 方法一:与传统的valid parenthesis相比就是多了一个
*
,那就把它分别带入左右和空三种情况递归判断即可。
1 | public boolean checkValidString(String s) { |
- 方法二:延续stack的做法,左括号和星号的index入栈,每次遇到右括号先把左括号的stack弹出。最后比较左括号的星号栈的索引大小即可。
1 | public boolean checkValidString(String s) { |
- 方法三:从左到右扫一遍,分别统计左括号和星号,优先匹配左括号,当左括号不够时再调用右括号;但是这样一波无法判断
(*()
这样的情况,因为星号始终是当成左的。因此需要再从右往左走一波,把星号当成有括号。
1 | public boolean checkValidString(String s) { |
680. valid-palindrome-ii
- 给一个字符串,判断能否通过“最多删掉一个字符”形成自对称字符串。例如
aba
本身就是,abca
可以通过删掉b或c变成自对称。 - 直接前后指针往中间并拢,一旦发现不同的字符就把不同的两个字符分别遮住继续判断,如果还不行那就一定不能自对称了。
1 | class Solution { |
681. next-closest-time
- 给一个字符串表示时间,求由这些数组组成的、下一个最近的时间(数字可无限使用)。
- greedy方法,从末尾开始替换,如果有恰好比他大的数字,替换之后直接就返回了。否则就替换成这些数字中最小的数字。注意每一个位置的限制都不同,例如第二位就需要根据第一位是否为2来决定最大值是3还是9.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49class Solution {
public String nextClosestTime(String time) {
if (time == null || time.length() == 0) {
return null;
}
char[] digits = getDigits(time.split(":"));
char[] digitsOrigin = Arrays.copyOf(digits, digits.length);
char[] ans = new char[5];
ans[0] = digitsOrigin[0];
ans[1] = digitsOrigin[1];
ans[2] = ':';
ans[3] = digitsOrigin[2];
ans[4] = digitsOrigin[3];
Arrays.sort(digits);
ans[4] = getNextGreater(digitsOrigin[3], '9', digits);
if (ans[4] > digitsOrigin[3]) {
return String.valueOf(ans);
}
ans[3] = getNextGreater(digitsOrigin[2], '5', digits);
if (ans[3] > digitsOrigin[2]) {
return String.valueOf(ans);
}
ans[1] = getNextGreater(digitsOrigin[1], digitsOrigin[0] == '2' ? '3' : '9', digits);
if (ans[1] > digitsOrigin[1]) {
return String.valueOf(ans);
}
ans[0] = getNextGreater(digitsOrigin[0], '2', digits);
return String.valueOf(ans);
}
private char[] getDigits(String[] timeSplitted) {
char[] digits = new char[4];
digits[0] = (char)('0' + Integer.parseInt(timeSplitted[0]) / 10);
digits[1] = (char)('0' + Integer.parseInt(timeSplitted[0]) % 10);
digits[2] = (char)('0' + Integer.parseInt(timeSplitted[1]) / 10);
digits[3] = (char)('0' + Integer.parseInt(timeSplitted[1]) % 10);
return digits;
}
private char getNextGreater(char curr, char limit, char[] digits) {
int pos = Arrays.binarySearch(digits, curr) + 1;
while (pos < 4 && digits[pos] <= limit && digits[pos] == curr) {
pos++;
}
return pos < 4 && digits[pos] <= limit ? digits[pos] : digits[0];
}
}
682. baseball-game
- 定义一个积分规则,没有什么好说的,用List即可。
683. k-empty-slots
- 给一个flowers数组表示第
i + 1
天,开花的索引是flowers[i]
。再给一个k,问是否存在某一天使得存在连续k个花未开且左右两边都已经开放,返回这个天数,若不存在则返回-1。 - 方法一:维护一个days数组表示该index的花在第
days[index]
天开。需要求得一个子序列left, left+1, left+2, ..., left+k, right
使得days[left]和days[right]开放时间比中间任何一个都要早。从左往右遍历days数组,一旦发现中间某天开花时间早于left或者right就说明这个子序列中断了,更新left为i即可。时间空间都是O(N).1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public int kEmptySlots(int[] flowers, int k) {
if (flowers == null || flowers.length <= k) {
return -1;
}
int[] days = new int[flowers.length];
for (int i = 0; i < flowers.length; i++) {
days[flowers[i] - 1] = i + 1;
}
int left = 0, right = k + 1, ans = Integer.MAX_VALUE; // 从左开始往右遍历
for (int i = 0; right < days.length; i++) {
if (days[i] < days[left] || days[i] <= days[right]) { // 若其中某个i开花时刻早于左或者右侧window,就以该处为新的起点
if (i == right) { // 若遍历到right都没有问题,就是一个新的ans
ans = Math.min(ans, Math.max(days[left], days[right]));
}
left = i;
right = i + k + 1;
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
} - 方法二:利用TreeSet存储flowers,随着天数增加,利用TreeSet的lower找小于该索引处的最大值、利用higher找大于该索引的最小值,这样求出来就能碰到完美等于k的子序列了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public int kEmptySlots(int[] flowers, int k) {
if (flowers == null || flowers.length <= k) {
return -1;
}
TreeSet<Integer> bloomIndex = new TreeSet<>();
for (int day = 0; day < flowers.length; day++) {
bloomIndex.add(flowers[day]);
Integer left = bloomIndex.lower(flowers[day]);
Integer right = bloomIndex.higher(flowers[day]);
if ((left != null && flowers[day] - left == k + 1)
|| (right != null && right - flowers[day] == k + 1)) {
return day + 1;
}
}
return -1;
}
}
684. redundant-connection
- 给一系列边组成无向图,其中恰好多了一个边使图无法形成树,求多出来的这个边即最后出现的这个边。例如
[[1,2], [2,3], [3,4], [1,4], [1,5]]
,返回[1,4]
。 - 并查集,维护每个节点的祖先,首次出现时默认以自己为祖先,然后就判断edge中的两个节点祖先是否一样,一样就说明成环了,否则就把前者的祖先指向后者的祖先。
1 | class Solution { |
685. redundant-connection-ii
- 给一系列边组成有向图,其中恰好多了一个边使图无法形成rooted tree,求多出来的这个边即最后出现的这个边。例如
[[2,1],[3,1],[4,2],[1,4]]
,返回[2,1]
。 - 与684相比这里的边都是有向的了,有两种情况来判别边invalid:形成了环,或者一个节点同时有两个parent节点。做法分为两步:首先check看是否有节点有两个parent,有的话就设为candidate A和B,并把B设置为invalid(设一个节点为0即可);然后进行union-find,如果此时树已经是valid的了,就直接返回candidate B(因为是后出现的)。
1 | class Solution { |
686. repeated-string-match
- 给两个字符串A和B,求A需要重复几次才能让B成为它的substring.
- 狗家实习的OA,自己想的方法。先看看起始字符都出现在哪些索引,统统入queue;然后先拼一波使得A的长度不小于B;然后从queue中取起始索引,比较看B是否包含其中;如果queue还没用完则还需要拼多一次。
1 | class Solution { |
- 或者直接用拼接的方式,一直拼接A直到超过B的长度,然后看是否包含。如果不包含还需要额外的一次拼接再看。
1 | public int repeatedStringMatch(String A, String B) { |
687. longest-univalue-path
- 给一个二叉树,求其中最长的连续边数使得经过的节点值都一样。不一定是完全笔直的路径。
- 对于左子树和右子树递归调用求最长路径(不取当前节点的情况),然后根据当前节点的值进行DFS(也就是取当前节点的情况)。最后取最大。
1 | class Solution { |
- 但是上面的这个方法存在大量重复访问节点,时间复杂度O(N^2)。因此考虑和之前diameter题一样,使用全局变量求最大path,同时在dfs每步直接将两侧中较大深度返回给上一层。
1 | class Solution { |
688. knight-probability-in-chessboard
- 给一个整数N表示是
N*N
的棋盘,其中一个knight/马在坐标(r, c),问走K步后它还在棋盘有效范围内的概率是多少。 - 概率就是走到棋盘上的情况数/总的情况数即
8^K
种走法。当前位置取决于上一步的位置,但是我们并不知道上一步有多少种走法,因此想到bottom-up的DP方法,即假设当前是走完K步之后的位置,可以从之前的哪些位置走过来呢,倒推上一步的走法,然后再继续倒推。注意只有上一步是在有效棋盘内才能update。
1 | class Solution { |
689. maximum-sum-of-3-non-overlapping-subarrays
- 给一个正整数数组,找出三个互不重叠的、size为k的子数组,使得总和最大。返回的形式是每个subarray的起始索引。例如
[1,2,1,2,6,7,5,1], k=2
则返回[0, 3, 5]
。 - 有唯一解吗?(可能有多个,只需返回最先出现索引)k本身会不会很大?(不会,不大于len/3)
- 首先是如何快速求某个区间内的和?如果数值都不大的话,可以通过累加把sum都给缓存下来,用的时候直接减一下就行了。然后是如何求subarray的结果?可以用二位dp数组,行表示划分成row个subarray,列表示从0到col处为止能得到的最大的总sum。此外还需要一个二维index数组记录第row个subarray对应的起始位置。从第一个subarray开始循环,固定求size为k的subarray使之和最大,其实就是贪心的思想,只要过程中求的每个subarray的和都最大那么最终的总和就是最大的。在循环过程中就可以不断求总和,为了防止重叠求和时必须求往前k个元素为end的dp结果。
1 | class Solution { |
690. employee-importance
- 给一个List of Employee,包含id、importance、下属List等属性。给定id,求这个id对应员工及其所有下属(不一定是直接下属)的imp之和。
- DFS。用一个Map先存储id-Employee的键值对,然后可以给定一个id快速访问到该Employee的信息,然后DFS递归搞定。
1 | /* |
692. top-k-frequent-words
- 给一个String数组,求出现频率top k的字符串。
- 跟347类似。先用Map存每个单词出现的频数,再自定义根据频数minHeap存这些Map.Entry,然后每次都check堆的规模,一旦大于k就直接把最小的poll出来,这样就保证在minHeap中的一定是top k.最后就直接逆序插入结果List。
1 | class Solution { |
- follow-up:如果给定的输入不是一个完整的数组,而是一个stream,即每次都只能取得一个单词,然后立即返回top k,如何改进?
- 关键在于无法在最开始就获得完整的频数统计Map,在插入minHeap的时候就无法知道后续的Entry需不需要覆盖PQ中的值。因此需要一个额外的Map记录具体哪些Entry目前被存放在minHeap中;当新的单词出现,就先更新map中的项,然后再看看它是否在PQ中,在则需要更新(我只能想到把k个元素全抖出来再加进去),不在则跟minHeap的peek比较决定是否需要替换。这样时间是O(N)的统计频数、O(logN)的插入minHeap、O(KlogK)的更新(?)和最后O(K)的倒入List。
694. number-of-distinct-islands
- 给一个grid,其中含有0和1,求所有distinct的连续1的团簇的个数,distinct指的是通过位移无法完全匹配的连续的1的区域。
- 与统计number of island的区别在于这里的island需要通过某种方式辨别该形状是否出现过,联想到encode方法,利用上下左右标记走过的路程。对于DFS,需要额外标出回溯的字母。对于BFS,也需要在结束当前节点的邻接点enqueue后加上标记符。
1 | class Solution { |
695. max-area-of-island
- 给一个grid,表示水和小岛,求最大的岛的面积。DFS搞定,skip。
696. count-binary-substrings
- 给一个只含有0和1的字符串,求其中有多少个子字符串使得0和1分别连续出现且个数相等,例如
01
,1100
就满足要求。 - 从头到尾遍历,然后双指针扩散判断。
1 | class Solution { |
697. degree-of-an-array
- 给一个int数组,degree为其中元素出现的最大频数。求和原数组degree相同的最小subarray长度。
- 对每个元素计数,同时记录第一个出现的index,出现新degree直接就是当前索引到第一个出现索引的距离。pass。
698. partition-to-k-equal-sum-subsets
- 给一个只含有(0, 10000)的int数组和一个k,判断是否可以将该数组划分为k个相等sum的partition。
- 似乎是个NP-hard的问题。只能用暴力办法,DFS+标记数组,每次累加过后进入下一层看看是否达到了targetSum,达到了就清空继续往后找新的一组subset.最后如果只剩下一组了,直接返回true,因为此时其他k - 1个组都已经达到targetSum了,当前的
sum = k * targetSum - (k - 1) * targetSum = targetSum
.
1 | class Solution { |
- 方法二:更快的做法是先对数组排序,然后存k个bucket,每个bucket从后往前取元素不断累加.
1 | class Solution { |
- follow-up: 如果去掉正数的限制,允许出现负数和0?
- 上面的方法只考虑了直接累积叠加,无法解决负数问题。因此需要引入一个elementCount来统计当前这一波存入了多少element,当达到targetSum的时候需要判断当前这一波是否真的存入了元素。
1 | class Solution { |
699. falling-squares
- 给一个二维数组,每一行表示一个方块的起始坐标和边长。方块按照数组的顺序下落,方块底部可以粘在下面的方块上,无限堆叠,求一个List表示当前已下落的所有方块中的最大高度。
- 方法一:naive的O(N^2)暴力遍历法。对于每个方块都往前遍历所有的方块求当前方块的高度,然后和List的前一个元素比较,获取最大高度。
1 | class Solution { |
- 方法二:TreeMap
- 方法三:Segment Tree
700. search-in-a-binary-search-tree
- 给一个BST和val,返回对应节点。pass.
701. insert-into-a-binary-search-tree
- 给一个BST和一个val,将val插入BST,返回插入后的BST。
- 方法一:递归。val与当前节点比较,小就深入左子树、大就深入右子树。
1 | class Solution { |
- 方法二:迭代。思路类似,根据大小决定潜入左还是右子树。
1 | class Solution { |
703. kth-largest-element-in-a-stream
- 实现一个能handle stream of int的类,调用add时能返回第k大的数。
- 和求top k element一个道理,PriorityQueue搞定。skip.
704. binary-search
- 实现二分查找,直接套了模版。
706. design-hashmap
- 实现一个HashMap。
- 基本上就是考察CS基础了。最直接的想法就是用bucket,输入的key范围是多少就用多少空间。如果没有那么多空间,那就要考虑缩小空间并处理collision. 这里可以使用
ListNode chaining
解决。
1 | class MyHashMap { |
708. insert-into-a-cyclic-sorted-list
- 给一个环状链表的任意一个节点,这个链表是从小到大有序的,插入一个新节点,返回原本给的那个节点。若一开始为null,则返回新插入的节点。
- 方法一:各种条件判断,边缘情况讨论,各种if,没有成功。
- 方法二:先走一波找到最大的节点,即给的节点开始往后走,一旦当前节点比后续节点大了就说明拐点到了。暂时将最大节点与后续节点断开,后续节点就是最小节点,在它之前插入一个dummy节点,以方便插入,然后从dummy开始往后一个个看,一旦当前节点不比要插入的节点小了,就是插入位置了,或者一直到最后都没找到插入点,就插在末尾。最后再把最大节点接回最小节点即可,注意需要判断最大节点有没有变化,即看看之前的那个「最大节点」后面是否为null。
1 | class Solution { |
709. to-lower-case
- 实现转化成小写的函数。pass。
711. number-of-distinct-islands-ii
- 给一个二维grid表示小岛,求其中形状distinct的小岛数量。这些形状可以任意平移、轴对称、翻转。
- 暴力方法,遍历完一个小岛的时候就将所有的轴对称、翻转形式统统列出来,然后根据某个统一标准取一个root form来代表所有这些形状,这里就直接使用encode之后字典序最小的作为key。
1 | class Solution { |
712. minimum-ascii-delete-sum-for-two-strings
- 给两个字符串,需要删除适当的字符使得他们相等,求最小的所有被删除字符的ascii之和。
- 每个字符是否保留都是独立的决策,因此考虑DP。
dp[i][j]
表示s1[i]
到末尾、s2[j]
到末尾的需要被删字符的最小ascii之和。如果其中一个字符串为空,显然ascii之和就是非空字符串各个字符从后往前累加,最后dp[0][0]
即为所求。
1 | class Solution { |
713. subarray-product-less-than-k
- 给一个正整数数组,和一个k,求有多少个子数组的积小于k。
- 滑动窗口,一旦发现当前积大于k就挪动左指针,直到小于。此时左右指针中间的即为valid的子数组。
1 | class Solution { |
714. best-time-to-buy-and-sell-stock-with-transaction-fee
- 给一个数组表示股票价格,每次交易(买卖完成算一次)都会收取手续费。求最大收益。
- (思路来自覃超说算法)DP。
profit[i][0]
表示第i天不持有股票手头的资金,profit[i][1]
表示第i天持有股票手头的资金.初始化时第一天如果不持有股票则手头为0,若持有股票则需要消耗资金,因此是-price[0]
。之后的状态转换为profit[i][0] = profit[i - 1][0](前一天也没有买入)和profit[i - 1][1] + prices[i](前一天是持有的,今天卖出)的较大者
。类似地,profit[i][1] = profit[i - 1][1](前一天也持有)和profit[i - 1][0] - prices[i](前一天没有,今天买入)的较大者
。最后返回最后一天不持有股票的profit即可。
1 | class Solution { |
716. max-stack
- 实现一个maxStack类,支持普通栈的pop, top,还有peekMax, popMax操作。
- 方法一:maxStack经典做法就是双栈,一个作为普通stack,一个记录以对应元素为栈顶时的最大元素。tricky的时popMax时需要暂时将普通栈的元素转存到另一个栈中,直到找到当前max元素,pop掉之后,再push回去,这样时间复杂度为
O(N)
,其中N为操作数。
1 | class MaxStack { |
- 方法二:如果希望提升peekMax的速度到logN(其他O(1)的操作可以降速),就需要思考如何提升删除元素的速度了。在LRU中我们学习过double linked list可以在给定node时O(1)删除元素,因此可以用来作为stack本体。至于max,就可以考虑tree结构来维护最大堆value -> node,由于stack中可以重复出现元素,对于每一个value需要维护一个node的list,在list后面的就是后插入的,也就是需要先行挪出的。这样所有操作的时间复杂度都是
O(logN)
(因为涉及treeMap的查询)
1 | class MaxStack { |
717. 1-bit-and-2-bit-characters
- 给一个只含有0、1的int数组,读取时只可以读成
0
或11
或10
。判断最后一个数字是否必须是1-bit. - 贪心即可。每次向后挪动,碰到0挪动1位、碰到1挪动2位,最后看看停留的索引即可。pass。
718. maximum-length-of-repeated-subarray
- 给两个int数组,求其中相同的subarray的最大长度。
- DP,
dp[i][j]
表示A[0, i)
和B[0, j)
的相同subarray的最大长度。如果两个元素相同,则以当前元素结尾的子数组长度取决于以前一个元素结尾的长度。
1 | class Solution { |
719. find-k-th-smallest-pair-distance
- 给一个int数组,求每两个数之差中第k小的值。例如
[1,3,8,4,5,45]
,当k = 1,返回1,当k = 3,返回2. - 先对所有元素从小到大排序,那么间距最小值为0、最大值为最右减最左。用二分查找的思想,假设mid为第k小的值,然后O(N^2)遍历求有多少对儿数之差小于mid;若对儿数小于k,说明猜的值太小了排太前了;大于k则说明猜太大了。
1 | class Solution { |
720. longest-word-in-dictionary
- 给一个string数组,只含有小写字母,这些word可能形成链式如
a, ap, app, appl, apple
,求能形成链式的最长的单词,若有多个则取lexicographical最小的。 - 用sort + Set的方式比较trivial。还有一种Trie + DFS/BFS的更考察基本功,构建trie之后从root节点开始尝试从后往前遍历邻接点并更新最长word,这样就可以保证是lexicograpchical最小的了。
721. accounts-merge
- 给一堆字符串List,每个List中首先是名字,然后是这个人的各种邮箱。最后放回经过merge的姓名、邮箱List,并且要求将邮箱从小到大排序。
- 这种多对一的关系查找,特别适合用并查集。首先将每个邮箱的parent设为自己,然后将每个List靠后面的邮箱统一把parent设成第一个邮箱。然后利用TreeSet实现邮箱的排序,最后导出到List返回。
1 | class Solution { |
- 其实更直白的看,这题就是个图论题,整理出图的联通部分。首先是构建graph,每个邮箱都是节点,用Set存每一行所给邮箱组成的subgraph,每个邮箱都用Set存放可达邻居(需要双向添加)。然后开始DFS或BFS搜索图,将每一行的第一个邮箱作为起点,把所有可达的邮箱都加进来,在这个过程中需要标记visited。之后如果再遇到visited的邮箱就说明已经在之前“可达”掉了。
1 | class Solution { |
722. remove-comments
- 给一个string数组,每一个string代表一行C++代码,要求将其中的comment清除。可以保证这些comment不会存在于字符串中。
- 没什么意思。用一个inComment布尔值存放当前是否在注释块中。遍历每行代码的时候若仍在注释块中则关注
*/
;正常状态下则先关注是否是//
,这样后续就不用继续append了,否则关注/*
。
723. candy-crush
- 模拟candy crush小游戏,给一个初始的board。若水平或者垂直方向连续三个相同的int,则需要消掉并将上面的数字往下填充,最顶上如果掉下了则补充0表示空。
- 其实主要就是模拟这个过程。如果监测到水平/垂直连续三个相同绝对值的int,则将这三个标记为负。最终再从下往上将负的值用更上面的正值覆盖。
1 | class Solution { |
724. find-pivot-index
- 给一个int数组,求其中一个index使得左侧数字之和与右侧数字之和相等。zillow面试原题,维护leftSum和rightSum即可。
726. number-of-atoms
- 给一个字符串表示化学物质,统计其中的元素及出现次数,按字典序输出。例如
H2(O(Mn)2)3
输出H2Mn6O3
. - 只有1个元素是输出1还是不输出?(不输出数字,只输出元素)
- 由于含有括号,联想运算符算式就知道要用Stack进行吞吐来处理括号嵌套的情况。如果是字母,就一直找到小写的为止作为元素名字,之后跟着的数字就是count,存入map。若出现左括号,则当前的这个map(保存了括号之前的元素及count)直接入栈,然后用新的map继续统计,一旦遇到右括号,说明当前部分结束(注意需要检查右括号之后还有没有数字),则与栈顶弹出的map合并一下就好了。
1 | class Solution { |
727. minimum-window-subsequence
- 给一个source字符串和一个target字符串,求在source的最短子串使得包含target的所有字符(个数和出现顺序都必须一致)。
- DP(感觉是野路子,不太好想)。。。纵向行为target,横向列为source,第一行全部初始化为
0,1,2....sLen
表示从第几位开始取,之后所有值初始化为-1表示无解。然后O(M*N)逐个字符遍历两个字符串,若匹配上了则从左上方取起始位置(看前一个字符的情况),若匹配不上则默认继续取source(直接取左侧的值)。
1 | class Solution { |
729. my-calendar-i
- 给若干开始时间+结束时间pair,实现book函数判断能否成功添加事件,不能有时间重叠。
- 方法一:暴力法,从头到尾遍历链表,无冲突就插入。效率O(N)。
1 | class MyCalendar { |
- 方法二:利用TreeMap,对于每个[start, end]对,从TreeMap中找start的floor,取出它对应的end。一旦这个end大于start,就说明有重叠了。同理,也要从TreeMap中找start的ceiling,如果这个ceiling小于end,说明与后面有重叠。
1 | class MyCalendar { |
731. my-calendar-ii
- 与729相比变成了不能出现triple的重叠就算是可以book。
- 注意不能简单地理解为一个interval同时与两个interval重叠,因为
[2,6]
和[1,3]&[5,7]
同时重叠,但没有形成triplet. - 同样是维护TreeMap,对于每个新加入的interval,遍历已有的interval并把重叠的部分插入treemap。如果插入时发现有重叠,说明“重叠部分之间也有重叠”,这样就是triple了。
1 | class MyCalendarTwo { |
733. flood-fill
- 给一个二维int数组,其中包含0-65535的值。给定坐标i,j,和一个newColor,将该cell周围和它值相等的cell都赋值为newColor.
- DFS,直接赋值。需要注意如果原色和newColor相等就直接返回了,否则会stack overflow。
1 | class Solution { |
734. sentence-similarity
- 给一堆同义词
[("restaurant", "cafe"), ("ratings", "reviews"), ...]
,再给一些queries[("restaurant ratings", "cafe reviews"), ...]
,要求返回每个query里的对应词是否都是synonym。同义词没有传递性。 - 直接把字符串作为key、对应的所有同义词的set作为value存入map,正反都放一次,比如
map.get("restaurant").add("cafe")), map.get("restaurant").add("cafe")
,这样在query的时候就可以直接调用了。
1 | // 维护一个总的map,每个单词作为key,对等的单词塞入它维护的Set中 |
735. asteroid-collision
- 给一个int数组,表示原子。正数向右移动,负数向左移动,可能会发生碰撞,如果绝对值相等则会抵消,否则绝对值更大的会把小的给干掉。求碰撞完后的数组。
- 直接用一个List,正数直接存,负数就需要与list中末尾的元素比较,如果是负就直接push,是正就需要比较看看谁更大。
1 | class Solution { |
- 更巧妙的做法是直接用一个数组模拟stack,然后用加法判断是否抵消。每次都强行取栈顶元素出来,如果没有被干掉就再放回去。
1 | class Solution { |
737. sentence-similarity-ii
- 给一堆同义词
[("restaurant", "cafe"), ("ratings", "reviews"), ...]
,再给一些queries[("restaurant ratings", "cafe reviews"), ...]
,要求返回每个query里的对应词是否都是synonym。注意这些同义词具有传递性,a=b, b=c -> a=c
。 - 方法一:图论题,每个词都是一个节点,对于每个节点维护一个Set,通过DFS遍历所有可达的节点。
1 | // 和前一个版本的区别是这个可以无限传递a=b=c=d... |
- 方法二:并查集,初始化时每个单词都是自己的root;然后根据同义词关系将前者的老大设为后者。判断句子是否同义时就找两个单词的老大是否相等即可。
1 | // 并查集。初始化时每个单词都是自己的root;然后根据同义词关系将前者的老大设为后者。 |
739. daily-temperatures
- 给一个int数组表示气温,返回一个数组表示该日最短需要多少天才会有更温暖的日子。例如
[73, 74, 75, 71, 69, 72, 76, 73]
输出[1, 1, 4, 2, 1, 1, 0, 0]
。 - 解法:维护一个Stack存放索引,每次读入新的温度时就和栈顶对应的温度比较,如果更高,就弹出并设置该索引处的天数。
1 | class Solution { |
740. delete-and-earn
- 给一个int数组,每次从中取出一个数字
num
作为score,同时将所有num + 1
和num - 1
抹去。求能得到的最多的score。 - DP。对于每个数字只有两种情况,要么选中成为score,要么忽略等着选中其他的num被抹去,因此维护一个take、一个skip,take的前一位一定是skip(相邻的不可能同时pick)、skip的前一位取不取都可以,选更大者即可。
1 | class Solution { |
741. cherry-pickup
- 给一个只含有
-1, 0, 1
的NxN
棋盘,从左上角出发只能往右/往下挪到右下角后,再往左/往上挪回起点。-1表示障碍物,1为cherry,求往返之后能收集到的最多的cherry数目。 - 既然只能往右、往下,那么第一趟所能走过的步数是固定的,就是2N,往回走也是一样。为了简化问题,可以想像成有两个人同时从起点往终点向右、向下挪,收集cherry时如果在同一个格子就只计算一次。采用dfs即可遍历所有可能的row1, col1, row2, col2组合。时间复杂度为
O(N^4)
. 相比之下如果不加memo就是纯暴力对于每个可能都要来一次递归,就是O(4^(N*N))
.
1 | class Solution { |
- 一个优化是,这里row1 + col1 == row2 + col2,因此其实只需要3个变量,三维的memo即可。
742. closest-leaf-in-a-binary-tree
- 给一个二叉树和一个其中必定存在的值k,求这个节点到最近的leaf节点的距离。注意不是BST。
- 纯粹用Tree来思考有点困难,需要抽象成graph来思考:给定一个target点,怎么找最近的满足一定条件的neighbor?BFS。因此先dfs一波找到target节点,同时记录target节点怎么往parent走。然后从target节点开始BFS找最近的leaf节点即可。
1 | class Solution { |
743. network-delay-time
- 总共有1、2、3、…、N个节点,给一个times数组表示从node A到node B需要传播的时间,给定起始点K,求最长需要消耗的时间。类似于求最短路,BFS搞定。注意需要更新到达节点所需要的时间。
744. find-smallest-letter-greater-than-target
- 给一个排好序的a-z的char数组,给一个target,求比他大的字符,若是最后一个则wrap到前面如比z大的就是最前面的字符。
- 二分查找,找last occurence,直接返回「下一个」字符。
1 | class Solution { |
745. prefix-and-suffix-search
- 给一个字符串数组,之后给一些query,这些query含有前缀和后缀(0~10个字符),求符合前缀的单词的索引。
- 有多个答案怎么办?返回最后一个出现的。
- 方法一:encode的方式将每个单词所有可能的前缀后缀组合作为key存入map,索引作为value,这样在query的时候直接再encode一下就可以直接get了。初始化时间复杂度O(N * wordLen^2),query时间复杂度O(1),空间占用O(N * wordLen^2).
1 | class WordFilter { |
- 方法二:拆分成两个map,一个专门维护前缀、一个专门维护后缀,value都是索引的List。在query的时候需要把两个List取出来,然后O(N)扫描看看有没有交点。初始化时间复杂度O(N * wordLen),query时间复杂度O(N),空间占用O(N * wordLen).
1 | class WordFilter { |
- 方法三:直接使用内建函数startsWith和endsWith。初始化时间复杂度O(1),query时间复杂度O(N * wordLen),空间占用O(1).
1 | class WordFilter { |
747. largest-number-at-least-twice-of-others
- 给一个只包含
[1, 50]
范围内的数组,求其中最大的、且至少是次大的数两倍的数的index。若不存在则返回-1. 第一次提交遗漏了更新次大数的条件。
1 | class Solution { |
748. shortest-completing-word
- 给一个licensePlate,再给一个words数组,求其中最短的字符串使得licensePlate出现过的字母都有。例如
licensePlate = "1s3 PSt"中只用关注S P S T, words = ["step", "steps", "stripe", "stepple"]
,输出steps
。 - licensePlate有哪些字符、确定只关注字母?(-是的)字母大小写?(-忽略大小写)
- 解法:先统计licensePlate中字母出现次数,然后
O(N)
遍历字符串数组,对于每一个单词判断是否包含licensePlate的所有字母(O(26)
),再找最短的返回。
1 | class Solution { |
749. contain-virus
- 给一个只含有0和1的二维数组,1表示带病毒的细胞、0是健康细胞,每分钟病毒会传染给上下左右直接相邻的健康细胞。假设从最开始可以选择一团带病毒的细胞在他们和健康细胞之间建隔离带,
0|1
这样会消耗一个隔离带。每次选择相邻健康细胞最多的一团进行隔离,然后经过一分钟剩下部分完成感染后在继续建隔离带。求这样的策略下最终需要多少隔离带(结果可能是完成了隔离、抑或全部都被感染)。 - 本质上就是DFS。先找出所有团簇,然后相邻健康细胞取最多的进行隔离,然后模拟感染扩散,然后再循环找团簇隔离。。。
1 | class Solution { |
750. number-of-corner-rectangles
- 给一个只含有0和1的二维数组,求其中四个1所能组成矩形的个数。矩形的边必须横、竖两个方向。
- 扫描线的思路,取两个行,同时扫竖线,统计同时出现1的pair数作为竖线,然后把这些竖线组合一下即可。
1 | class Solution { |
752. open-the-lock
- 假如有一个锁头从
0000
开始转,每次只能只能转四位中的一位,给一个String数组表示这些数字不可以转到,给一个target表示最终开锁的密码。求最短需要多少次才能开锁,不可能打开则返回-1。 - 这种最短路径问题就想到了BFS,不过需要小心的是target本身不可达以及起始点就不可达的情况。
1 | class Solution { |
- 以上是basic的BFS,如果要提速,可以进行双向的BFS,也就是维护两个Set,一个begin作为开始、一个end作为结束,每次switch角色,搞完begin就将end补过来、将当前begin的邻居点作为新的end。
759. employee-free-time
- 给一个List of List,每一个子List存放每个employee的工作时间,求所有employee的共同空闲时间。没有则返回空List。
- 直接将List flatten,然后按照工作开始时间从小到大排序,再往后依次取工作时间,若当前开始时间比之前的结束时间长,说明出现了空闲时间;否则需要更新prev的end,保证prev的结束时间cover到所有结束时间,即取max。
1 | public List<Interval> employeeFreeTime(List<List<Interval>> schedule) { |
760. find-anagram-mappings
- 给两个数组,求对应出现的位置。skip.
763. partition-labels
- 给一个字符串,尝试将它进行partition使得每个字符至多只出现在一个partition,划分处尽量多的partition,求每个partition的长度。
- 方法一:LinkedHashMap搞定。统计每个字符出现的初始位置和最后一次出现的位置,然后遍历,当前后无法相连则说明这是一个新的partition。
- 方法二:不需要对每一个字母同时存放start和end,而是对于一个partition维护start和end。遍历字符串时若当前索引正是当前字符的最后一次出现的索引,且到达了当前partition的end,说明partition结束;否则需要适当更新end。
1 | class Solution { |
764. largest-plus-sign
- 给定N表示棋盘的长和宽,默认棋盘中每个cell都是1,再给一些坐标表示该处是0。求棋盘中最大的加号的长度。
- 可以利用grid本身记录上下左右四个方向最长延伸出去多长。最原始的想法是每个方向都维护一个二维数组专门记录到该cell的最长长度是多少,不过经过改进可以将所有的计算都合并到一个grid中完成。开始时初始化每个cell的长度都为N,然后直接从前、后、上、下同时更新,不过每一步循环中更新的其实是四个不同的cell,最后循环结束时每个cell都会被更新四次。时间复杂度O(N^2)。
1 | class Solution { |
765. couples-holding-hands
- 给一个int数组表示每个位置坐的人,假设0-1, 2-3, 4-5…是一对,问最少通过几次交换座位可以让没对情侣都相邻而坐��
- 可以用greedy的办法,每发现一个坐错位置的人,就让他和应该在这个位置的人swap一次。
1 | class Solution { |
767. reorganize-string
- 给一个只含有小写字母的字符串,将这些字符重新排列使得相邻字母不同,若不存在则返回””;
- greedy,先统计每一个字符出现的次数,存入priorityqueue使得次数多的先取,取后若仍有剩余则需要更新次数并重新放回pq。注意若当前取出的次数最多的字母是上一次append的,则需要取第二多的字符,若没有后续字符说明没法这么存,返回””即可。
768. max-chunks-to-make-sorted-ii
- 给一个int数组,将这个数组分成若干个chunk后在每个chunk内部排序之后拼接能得到sorted的数组,求最多划分成多少个这样的chunk。
- 形成chunk的条件是「chunk中最大值小于等于右侧所有数的最小值」。因此维护两个数组存放当前位置的左侧最大值和右侧最小值即可。
1 | class Solution { |
769. max-chunks-to-make-sorted
- 给一个int数组,其中含有元素
[0, 1, ..., arr.length - 1]
(顺序不一定是这样的,是一个permutation),将这个数组分成若干个chunk后在每个chunk内部排序之后拼接能得到sorted的数组,求最多划分成多少个这样的chunk。如[4,3,2,1,0]
必须整个作为一个chunk排序,[1,0,2,3,4]
则分成[1, 0], [2], [3], [4]
来排序。 - 既然元素和index是能对应填充的,考虑他们之间的关系。要想形成chunk,必须chunk的最大值在最右侧index的左侧,维护一个max即可。
1 | class Solution { |
771. jewels-and-stones
- 简单的bucket计数,pass。
773. sliding-puzzle
- 给一个2x3的board,只含有数字0-5。只有0可以与相邻的元素swap,问最少经过多少swap能得到
[[1, 2, 3], [5, 6, 0]]
. - 转换为BFS问题,每个状态就是一个可达的节点,最关键的其实就是看
0
能否和周围数字swap。从当前节点到下一个节点,就是找出所有0
与邻居swap之后的状态。这里还有一个trick就是将二维数组转化成一维的string,直接通过字符串比较高效很多。时间复杂度为O(row * col * (row * col)!)
.
1 | class Solution { |
775. global-and-local-inversions
- 给一个长度为N、元素值为
0 ~ N-1
的int数组,判断它的global inversion数量和local inversion数量是否相等。global表示任意一对儿数字逆序了、local表示相邻前后数字逆序了。 - 本质上就是判断是否有「非相邻前后数字」逆序的情况。直接loop判断
A[i] - i
的绝对值即可,只要他们差值大于1就说明有跨度超过1的逆序对了。
1 | class Solution { |
776. split-bst
- 给一个BST和一个value,这个value不一定存在于BST中,要求以这个value为临界点将BST分成小于等于&大于两部分。
- 在split的时候比较节点与value,若value更大则split点会出现在右子树且split后会得到两个split之后的子树,需要将小于等于的那个子树拼接到当前节点的右侧。若value不大于当前节点,则需要到左子树去搜索split点,同样需要将split之后较大的那个子树拼接到当前子树的左侧。
1 | public TreeNode[] splitBST(TreeNode root, int V) { |
777. swap-adjacent-in-lr-string
- 给两个字符串
start
和end
,其中类似RX
的可以转化成XR
,XL
的可以转化成LX
,但是RL
就无法挪动了。判断是否可以成功转化。 - 首先需要判断两个字符串中L和R的相对位置是否一致,如果可以match上,再逐步判断
start
中的R
是否都再end
中R
的前面、start
中的L
是否都再end
中L
的后面。
1 | class Solution { |
778. swim-in-rising-water
- 给一个
NxN
的grid,其中的值为[1,…, N*N]。如果当前时间t > val则可以瞬间到达该坐标,求最小的t使得从左上角能移动到右下角。 - 方法一:最朴素的想法,二分查找来“猜”最终答案,每次对猜的答案进行DFS/BFS验证是否可以从左上到右下,若可以到达,则缩小上界以尽可能找最小值,若不能到达说明t不够,提升下界。时间复杂度为
log(N*N)*N*N
.
1 | class Solution { |
- 方法二:贪心算法,使用priorityqueue取代queue进行BFS,每次push的时候存入当前坐标已经到达当前坐标所需的时间,每次从pq中取坐标都可以找到当前可达范围内的最小的时间。时间复杂度和上面其实一样,毕竟需要在pq中维护顺序
O(NlogN)
,也就是这里的N*N*log(N*N)
。
1 | class Solution { |
785. is-graph-bipartite
- 给一个数组,每个index对应着该node的所有邻接点。问这个graph能否只用两个颜色给node上色使得相邻两个点的颜色都不一样。
- 方法一:DFS。对于每一个点都一波直接深度搜索上色,用一个数组存储上色状态,0表示未访问过,-1和1分别表示两个颜色,在dfs时对于当前的点若已经访问过就判断是否符合当前给定的颜色,若未访问则直接上色并DFS到它所有邻接点。需要注意可能有若干独立的cluster,因此不能一次DFS搜索就结束了,而是需要一个循环保证对所有未访问过的点都进行一次DFS。
1 | class Solution { |
- 方法二:BFS,还是用queue存放所有邻接点然后逐一上色。
1 | class Solution { |
787. cheapest-flights-within-k-stops
- 给一组city和航班信息,在最多stop k次的情况下求从src到dst最便宜的航班价格。
- 经典grpah最短路问题,首先用Map记录每一个city的邻居city航班,然后从src出发BFS,维护一个minPrice数组,发现更低价格时就更新对应city的到达所需价格。在BFS过程中,每扩散一轮就算作stop一次,利用一个flightCount保证最多停k次。
1 | class Solution { |
788. rotated-digits
- 给一个数字N,求1~N范围内将各位数字上下反转180度后能得到与它本身不同数字的个数。
- 当前数字需要依赖之前几位数字的情况,因此考虑简单的DP。第一想法是维护一个map存反转信息,这样确实更直接明白,但速度会慢很多。其实可以直接用if判断。
1 | class Solution { |
791. custom-sort-string
- 给两个String,S只含有不重复的小写字母表示custom定义的顺序,需要将T按照这个给定顺序进行排序,对于没有出现过的字母随便放哪里都可以。
- 方法一:遍历S,在循环内层遍历T,遇到当前字符就往前swap,时间复杂度O(N^2).
- 方法二:木桶排序,既然只会出现小写字母,就用26个木桶统计出现个数,然后遍历S取处相应的append即可,最后再把S中没有的字母拼接到最后即可。时间O(N).
792. number-of-matching-subsequences
- 给一个源字符串S和一个字符串数组,求数组中有多少个是S的子序列。
- 方法一:朴素的逐个判断。缓存入seq和nonSeq两个集合,遍历数组中每个字符串,判断是seq,对应存入两个set即可。这两个set并不是必须的,而是提速的,作为缓存来应付重复call的情况。
1 | class Solution { |
- 方法二:为了加速在源字符串中的查找,将每个字母在S中出现的索引存入TreeSet中,每次查找时直接从TreeSet中拿大于等于当前SIndex的索引,如果找不到就直接false。
1 | class Solution { |
794. valid-tic-tac-toe-state
- 给一个3x3的棋盘,判断是否是一个合法的OOXX状态。默认X先走,三连就退出。
- 和之前design-tic-tac-toe类似,X持续加,O持续减。最后来几个if判断即可。没啥意思。
1 | class Solution { |
795. number-of-subarrays-with-bounded-maximum
- 给一个数组和一个范围[L, R],求该数组有多少个子数组,使得子数组的最大值落在[L, R]中。
- 首先想到DP,
dp[i][j]
表示从i到j的子数组的最大值,O(N^2)遍历的时候就可以顺便判断。
1 | class Solution { |
- follow-up:进一步优化,不使用额外的空间,同时时间复杂度降到O(N).
- 子数组的总量是一定的,既然求的是range,那首先求所有数都不超过max的子数组数量,然后求所有数都不超过(min - 1)的子数组的数量,两个一减就得到了在[min, max]之间的子数组的数量。
1 | class Solution { |
796. rotate-string
- 给两个String,判断A能否通过shift变成B。
- 经典。观察可以得出A拼接上自身之后必须包含B才能保证shift得到B。时间复杂度
O(N^2)
.
1 | public boolean rotateString(String A, String B) { |
- 既然涉及在一个str中找另一个str,那么KMP也可以应用。首先对B做一个KMP存放common prefix/suffix,然后在
S = A+A
中对B进行查找,注意S的索引只会一路向前移动,B的索引会在没匹配上时就能回退到”上一个同样前缀最后出现的位置”。
1 | class Solution { |