LeetCode 800题突破

上次更新不知道是猴年马月了。

这期间，做了唯一一件事情就是刷题。

说到刷题本来我是没有多大兴趣的。这么多年来尽管心里知道现在互联网公司跳槽基本就是得刷题，心里还是存着十分的抵触。第一是觉得刷题根本就是偏离实际应用，浪费时间。其次觉得要是一个公司面试看中考数据结构算法，那估计也没什么去的必要。

然而那么多年应试教育的教训还是那么深刻，在互联网这个内卷的行业，刷题已经是转职加薪的最简单方法。不需要天赋异才，聪慧过人，只需要静下心来，抽出时间，反复推敲琢磨，甚至死记硬背。自然而然，冲破了那个阈值，新世界的大门也就打开了。

RTO是一个契机

RTO==Return to Office。

对于疫情开始之后长期在宅工作的人来说，回公司上班简直是一个噩耗。当然，这个噩耗来得有些突然。
在今年三月伴随着一系列线上的trouble，公司上层开始把原因归结为在家工作。作为Developer，首当其冲，紧急事态宣言时间一结束，首先出台了DEV部门必须每周五天去公司出勤的规定。

于是在每天确诊人数还在增多的四月中旬，我开始了所谓的RTO。开会还是Zoom。毕竟还有一部分人因为各种原因依旧在家工作。于是一到开会时间，你可以听到耳机里传来你摘下耳机也能听得见的，不远处的同组同学的声音，亦或者是你想集中的时候，周围此起彼伏的开会的声音把你打断。

当然中午的免费的便当还是依旧，菜一点点饭管饱。

想着自己还在领着可怜巴巴的工资，看着同期要么离职要么升职，顿时负面情绪就上来了。

动机和契机都有了，接下来就是刷题了。

刷题，刷题，刷题

其实这次不是第一次想要刷题。以前也陆陆续续刷了将近100题，不过时隔太久，回顾一下刷过的题，又得从0开始了。

为了不半途而废，我给自己定了刷题的原则。

  • 不粘贴复制

  • 不跳过不会的题目

  • 不会做的题目看过题解理解之后自己再做

  • 错过的题目过一阵继续做

刚开始印象比较深刻的题目有利用马拉车算法解回文字符串，KMP模版这些。然而其实这些真正面试时候应该不会考到。
不过按着原则，这些题目以及类似题，都多了好几遍。

一开始在国际版的leetcode上刷，每次都得去google找答案，看得也是一知半解，十分痛苦。等刷到大概250题的时候，
干脆买了国内站的会员，一年折合也就500不到，最关键的是可以看到题解以及讨论。

这个时候，刷题的模式固定成，上班有间隙的时间，刷几题，下班运动一会儿，吃饭，大概7点以后，集中刷题，到了晚上21点半左右，模拟一次3题一小时半的面试。
凌晨一点睡觉。

大概刷到400题左右的时候，平时只能过个两题的模拟，竟然也能三题全过了。大部分中等题也不是那么束手无策了。

大概从500题开始，尝试参加周赛。第一次只做出来两题。不过第三题太难了，也没多少人做出来。500题左右还有一种现象，就是觉得很多题目似曾相识，但是又什么都不会了。
不过我知道大概这是黎明前最后一片黑暗吧。

600题左右的时候，正好有一天猎头联系了我。一开始想给我介绍一些其实和当前工作相比没多大优势的职位，于是统统拒绝了，后来我就提了条件。工资大概得到现在的160%，然后必须是top level的公司。

尽管这些公司不多但是我还是如愿进行了面试。这期间继续坚持刷题。

当然刷题的成果在面试中也反映得淋漓精致。真正我做过原题的题目其实也就1/4，但是思路如泉涌，挡也挡不住。最终包括因为已经拿到了offer终止面试的公司，所有的面试都迎刃而解了。

700题左右的时候第一次38分钟全Pass了周赛，第一次拿到了leetcode的骑士徽章。一切都是那么顺利成章。

今天，交完离职信，提交了第800题。百感交集，感觉得写些什么东西。

当然，新的大门才刚打开，新得旅程，才即将开启。

刷题

[刷题笔记]187 Repeated DNA Sequences

题目

原题地址

思路

很多Discussion里面的解法就是直接10个字符为Key进行Hash了。

很显然，这个题目，出题者的意图是让你找到一种Mapping的方法，既能够保证Key足够短，又能够保证从Key可以还原成原来的字符串。

如果满分是100分，下面介绍的集中方法我都进行相应的打分。

20分解法

直接hash，略过不说了。

50分解法

借用md5 hash，把md5值的前几位作为key。缺点是我也不知道该取前几位，所以得一次次失败提交之后增加位数。

80分解法

我们知道

1
2
3
4
A => 65 => 1000001
C => 67 => 1000011
G => 71 => 1000111
T => 84 => 1010100

所以我们可以分别用三个bit代表ACGT这四个字符。

1
2
3
4
A => 001
C => 011
G => 111
T => 100

于是每10个字符可以用30个bit表示。例如

1
2
3
AAACCCCCAA
可以表示为
001001001011011011011011001001

当我们移动到下一个10字长字符串，我们只需要在现在的基础上右移3位(表示移除左边的第一个字符)，然后或上表示下一个字符的3个bit。

由于我们需要30个bit表示key。而int一般长度为32， 所以就可以用一个int来表示key。

为了在左移过程中防止混入我们已经移除的bit。（想象一下，我们第30，29 位在左移之后还存在与我们的32bit int中），所以我们需要一个mask把这最高的两位去掉。

这个mask可以是111111111111111111111111111111(0x3fffffff)，我们把它与上我们的30位bit就是所得到的偶为key的int。

当然为了能用3位bit表示我们的字符，我们需要将其他位省略，我们需要将每个字母与上7（111）。

这样我们逐个在给定的字符串s上移动，每移动一格计算一下key，并在hash[key]中加1。

当hash[key]大于1，我们知道当前字符串重复了，所以将其放入一个结果的set中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def find_repeated_dna_sequences(s)
 str = s[0..9]
 key = 0
 str.split("").each do |c|
     key = key << 3
     key |= (c.ord & 7)
 end
    
 hash = {}
 hash[key] = 1
 set = []
 for i in 10...s.length
     key = key << 3
     key |= (s[i].ord & 7)
     key &= 0x3fffffff
     if(hash[key])
         set << s[i-9..i]
     else
       hash[key] =1   
     end
 end
 return set.uniq 
end

100分的解法

在80分解法的基础上，我们知道我们的key是可以还原成原来的字符的。所以并不需要一个set。我们可以直接在hash中count，然后把左右count大于1的key还原。

怎么还原？我们可以将key不断除以8.通过获得的余数可以知道

1
2
3
4
余1 => A
余3 => C 
余7 => G 
余4 => T

于是最后的解答为

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
def find_repeated_dna_sequences(s)
 str = s[0..9]
 key = 0
 str.split("").each do |c|
     key = key << 3
     key |= (c.ord & 7)
 end
    
 hash = {}
 hash[key] = 1
 for i in 10...s.length
     key = key << 3
     key |= (s[i].ord & 7)
     key &= 0x3fffffff
     if(hash[key])
       hash[key] +=1
     else
       hash[key] =1   
     end
 end
 result = []
 hash.each do |k,v|
     if v > 1
     str = ""
     while k > 0
         left = k % 8
         str = "A" + str if left == 1
         str = "C" + str if left == 3
         str = "G" + str if left == 7
         str = "T" + str if left == 4
         k = k / 8
     end
     result << str
     end
 end
    return result
end

反思

这个题目要求对二进制十分熟悉。当然如果不熟悉就得变得熟悉起来。毕竟不去克服的话就永远安于现状了。

刷题

[刷题笔记] 554 Brick Wall

问题

思路

这个问题解决的关键一下子就看到是累加数组了。

建立一个hash表，记录经过每个缝隙的砖块的count。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def least_bricks(wall)
    hash = {}
    wall.each do |level|
        sum = 0
        if level.length == 1
          next
        end
        level[0..-2].each do |width|
            sum += width
            if hash[sum]
                hash[sum] +=1
            else
                hash[sum] = 1
            end
        end
    end
    max = 0
    hash.each do |k,v|
      max =   max > v ? max : v
    end
    
    return wall.length - max
end

一波三折的解题过程

上面的答案看似很简单，但是一开始，我却第一个想用dp来做。

dp[i][j] 来表示第i行第j个数经过的砖块个数。

后来发现其实dp只和上一行相关。于是把i省去了。不过还是内存溢出。

再仔细一想，那么多dp，其实只有缝隙的地方我们需要记录。于是把不是缝隙的地方又都给排除了。

但是结果还是Timeout。

所以还是回过头来看一下，是不是有些细节可以稍微修改利用。

刷题

[刷题笔记] 139 Copy List with Random Pointer

题目

思路过程

第一次失败

粗略扫了一边题目，准备用三个hashMap分别存储node，next关系，以及random关系。

第一次提交一看，Wrong Anwser，原来，每个Node的val可以相同，所以没办法单独用val来做hashMap的Key。

第二次失败

仔细分析，可以推敲到，如果每个old node能有一个指针指向new node，那么复制random关系的时候就是

1
2
3
newNode = currentOldNode.getNewNode()
newNode.random = currentOldNode.random.getNewNode()
newNode.next = currentOldNode.next.getNewNode()

那么我们需要重新定义一个class吗？那样还不如把node自身作为HashMap的Key算了。（最不动脑经的做法）

仔细一想，我们可以用old node的next指针指向new node，然后用一个数组按顺序保存old node。这样等我们建立好了new node之间random关系的同时，可以参照数组建立next关系。

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
def copyRandomList(head)
   arr = []
   return nil unless head
   current = head
   while current
       arr.push current
       next_node = current.next
       node = Node.new(current.val)
      # borrow it
       current.next = node
       current = next_node
   end
   head = arr[0].next
   for i in 0...arr.length
       if arr[i].random
         arr[i].next.random = arr[i].random.next
       else
         arr[i].next.random = nil   
       end
       if arr[i+1]
         arr[i].next.next = arr[i+1].next
       else
         arr[i].next.next = nil
       end
   end
    
   return head
end

提交，Wrong anwser。 一看提示，还是没有仔细审题。原来的old node之间的next 关系和 random关系不能改变。

当我们把next借来指向new node的时候，这个关系破坏了。好在我们有数组，可以用来恢复这个关系。

成功代码

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
def copyRandomList(head)
   arr = []
   return nil unless head
   current = head
   while current
       arr.push current
       next_node = current.next
       node = Node.new(current.val)
      # borrow it
       current.next = node
       current = next_node
   end
   head = arr[0].next
   for i in 0...arr.length
       if arr[i].random
         arr[i].next.random = arr[i].random.next
       else
         arr[i].next.random = nil   
       end
       if arr[i+1]
         arr[i].next.next = arr[i+1].next
       else
         arr[i].next.next = nil
       end
   end
    # recover
    for i in 0...arr.length
       if arr[i+1]
         arr[i].next = arr[i+1] 
       else
         arr[i].next = nil
       end
    end
    
   return head
end

反思

参考一下别人的做法，有一种是不需要建立数组。而是把 currentOld 的next 指向 currentNew，然后把currentNew的next指向nextOld。
这个方法不需要额外的数组保存顺序，只需要最后用两个指针把通过next连接在一起的新老list分成两个就好了。

刷题

[刷题笔记] Best Time to Buy and Sell Stock III

题目

思路

主体思想还是动态规划。

如何写出状态矩阵。dp ?

1
2
3
4
5
dp[i][j][k]

i: 当前prices中的第i个元素
j: 还可以出售j次, j in [0,1,2]
k: 0 表示持有股票状态，1 表示不持有股票状态

注意这里的j表示的是可以出售的次数。所以在状态转移的过程中，买入不需要减少j，只有出售时候需要变动。

接下来就是状态转移矩阵

1
2
3
4
5
6
for i in 1...prices.length
    for j in 0..1
        dp[i][j][0] = max(dp[i-1][j+1][1]+prices[i], dp[i-1][j][0])
        dp[i][j][1] = max(dp[i-1][j][0] - prices[i], dp[i-1][j][1])
    end
end

以及初始状态

1
2
3
4
dp[0][0][0] = 0
dp[0][0][1] = - 1 * prices[0]
dp[0][1][0] = 0
dp[0][1][1] = -1 * prices[0]

当然还需要更多初始状态

1
2
3
4
5
for i in 0...prices.length
    dp[i][0][0] = 0
    dp[i][2][0] = 0
    dp[i][2][1] = -1 * min_of(prices)
end

TimeOut的提交

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
def max_profit(prices)
    dp = Array.new(prices.length){Array.new(3){Array.new(2)}}
    # 2 digial can sell count
    dp[0][0][0] = 0
    dp[0][0][1] = - 1 * prices[0]
    dp[0][1][0] = 0
    dp[0][1][1] = -1 * prices[0]
    
    for i in 0...prices.length
       min = prices[i] if  prices[i] < min
        dp[i][0][0] = 0
        dp[i][2][0] = 0
        dp[i][2][1] = -1 * prices[0..i].sort.first
    end
    
    
    for i in 1...prices.length
        for j in 0..1
            dp[i][j][0] = max(dp[i-1][j+1][1]+prices[i], dp[i-1][j][0])
            dp[i][j][1] = max(dp[i-1][j][0] - prices[i], dp[i-1][j][1])   
        end
    end
    
    return dp[prices.length - 1][0][0]
    
    
end

Timeout的原因在于dp[i][2][1] = -1 * prices[0..i].sort.first, 其实我们在遍历的时候可以顺便求最小值。

Accepted

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
def max_profit(prices)
    dp = Array.new(prices.length){Array.new(3){Array.new(2)}}
    # 2 digial can sell count
    dp[0][0][0] = 0
    dp[0][0][1] = - 1 * prices[0]
    dp[0][1][0] = 0
    dp[0][1][1] = -1 * prices[0]
    
    min = prices[0]
    for i in 0...prices.length
       min = prices[i] if  prices[i] < min
        dp[i][0][0] = 0
        dp[i][2][0] = 0
        dp[i][2][1] = -1 * min
    end
    
    
    for i in 1...prices.length
        for j in 0..1
            dp[i][j][0] = max(dp[i-1][j+1][1]+prices[i], dp[i-1][j][0])
            dp[i][j][1] = max(dp[i-1][j][0] - prices[i], dp[i-1][j][1])   
        end
    end
    
    return dp[prices.length - 1][0][0]
    
    
end


def max(a,b)
    return a > b ? a : b
end
刷题

[刷题笔记] 115.Distinct Subsequences

题目

解析

第一个如果没想到动态规划就out了。

首先确定dp的定义。

dp[i][j]表示 s[0…i] 与 t[0…j] 之间的Distinct Subsequences的个数。

然后确定初始状态。

dp[0][0] 自然是比较 s[0] t[0] 是否相等。

dp[i][0] 可以通过遍历s，数出有多少s[i] 与 t[0] 相等。

tp[0][j] 相对比较简单，除了 dp[0][0] 之外，都是 0。

接着确定状态转移。

当 s[i] == s[j] 的时候，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]（这个是蒙的，不过也不难蒙）

解法

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
def num_distinct(s, t)
    ls = s.length
    lt = t.length
    dp = Array.new(ls){Array.new(lt)}
    
    count = 0
    for i in 0...ls
        count += 1 if s[i] == t[0]
        dp[i][0] = count
    end
    
    for i in 1...lt
        dp[0][i] = 0
    end
    
    for i in 1...ls
        for j in 1...lt
            if s[i] == t[j]
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
            else
                dp[i][j] = dp[i-1][j]
            end
        end
    end
    return dp[ls-1][lt-1]
end

双百分。

刷题

[刷题笔记] minimum depth of binary tree

题目

https://leetcode.com/problems/minimum-depth-of-binary-tree/submissions/

思路

这个题目标榜的难度是easy，然而通过率只有39%到底是为什么呢？

第一遍的答案

1
2
3
4
5
6
7
8
def min_depth(root)
  if root.left == nil && root.right == nil
    return 1
  end
  left_min = min_depth(root.left)
  right_min = min_depth(root.right)
  return left_min > right_min ? 1+right_min : 1+left_min
end

Exception. 没有处理root是nil的情况。

第二遍，加上处理

1
2
3
4
5
6
7
8
9
def min_depth(root)
  return 0 unless root
  if root.left == nil && root.right == nil
    return 1
  end
  left_min = min_depth(root.left)
  right_min = min_depth(root.right)
  return left_min > right_min ? 1+right_min : 1+left_min
end

Wrong answer. 

1
2
3
4
5
testCase: 
[2,null,3,null,4,null,5,null,6]

actual: 1
expected: 5

如果只有左右中的一个child的情况，一个child深度为0，另一个child深度为计算的值，这个时候不能认为0是正确的深度，因为只有当左右都为nil的时候才是我们获取深度的时候。

最终结果

1
2
3
4
5
6
7
8
9
10
11
12
13
def min_depth(root)
  return 0 unless root
  if root.left == nil && root.right == nil
    return 1
  elsif root.left == nil
    return 1 + min_depth(root.right)
  elsif root.right == nil
    return 1 + min_depth(root.left)
  end
  left_min = min_depth(root.left)
  right_min = min_depth(root.right)
  return left_min > right_min ? 1+right_min : 1+left_min
end
刷题

[刷题笔记] 109. Convert Sorted List to Binary Search Tree

题目

套路

首先找到中间节点mid，接下来，从head到mid之前的节点为left child，从mid节点之后到结尾为right child。

递归生成left child 和 right child 即可。

但是怎么找到中间节点呢？

这里用到了双指针技巧，即两个指针一快一慢，快指针一次前进两格，慢指针一次前进一格，这样快指针遍历到结尾的时候，慢指针就正好指向中间的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def sorted_list_to_bst(head)
    return nil unless head
    if head.next == nil
        return TreeNode.new(head.val)
    end
    head = head
    mid = head
    last = head
    while last
        last = last.next
        break unless last
        first = mid
        mid = mid.next
        last = last.next
    end
    root = TreeNode.new(mid.val)
    root.right = sorted_list_to_bst(first.next.next)
    first.next = nil
    root.left = sorted_list_to_bst(head)
    return root
end
刷题