LeetCode 刷题记录
🗒️LeetCode 刷题记录
type
status
date
slug
summary
tags
category
icon
password
😀
其实我本人不喜欢刷题,但是生活所迫,多少还是得刷点,所以就每天刷点题吧,主要是了解一下算法
序 # 关于 LeetCode 说到 LeetCode,作为一个程序员来说,应该不陌生,近几年参加面试都会提到它。国内外的程序员用它刷题主要是为了面试。据历史记载,这个网站 2011 年就成立了,马上就要到自己 10 周年的生日了。每周举行周赛,双周赛,月赛,在有限时间内编码,确实非常能考验人的算法能力。一些大公司赞助冠名的比赛获得前几名除了有奖品,还能直接拿到内推的机会。 什么是 Cookbook 直译的话就是烹饪书,教你做各种食谱美食的书。经常看 O’Reilly 技术书的同学对这个名词会很熟悉。一般动手操作,实践类的书都会有这个名字。 为什么会写这个开源书 # 笔者刷题刷了一年了,想和大家分享分享一些做题心得,解题方法。想和有相同爱好的人交个朋友,一起交流学习。对于自己来说,写题解也是一种提高。把一道深奥的题目讲给一点都没有头绪的人,并能让他完全听懂,很能锻炼人的表达能力。在讲解中很可能还会遇到听者的一些提问,这些问题可能是自己的知识漏洞,强迫自己去弥补。笔者在公司做过相关的分享,感受很深,双方受益都还不错。 另外,在大学期间,笔者做题的时候最讨厌写题解,感觉是浪费时间,用更多的时间去做更多的题。现在不知道算不算是“出来混的,总是要还的”。 关于书的封面 # 常看 O’Reilly 动物书的同学一看这个封面就知道是向他们致敬。确实是这个目的。O’Reilly 的封面动物都是稀缺动物,并且画风都是黑白素描风。这些动物都有版权了,所以只能在网上找没有版权的黑白素描风的图片。常见的能找到 40 张这种风格的图片。不过用的人太多了,笔者费劲的找了其他几张这种图片,这张孔雀开屏是其中一张。孔雀开屏的意义是希望大家刷完 LeetCode 以后,提高了自身的算法能力,在人生的舞台上开出自己的“屏”。全书配色也都是绿色,因为这是 AC 的颜色。 关于作者 # 笔者是一个刚刚入行一年半的 gopher 新人,还请各位大佬多多指点小弟我。大学参加了 3 年 ACM-ICPC,但是由于资质不高,没有拿到一块金牌。所以在算法方面,我对自己的评价算是新手吧。参加 ACM-ICPC 最大的收获是训练了思维能力,这种能力也会运用到生活中。其次是认识了很多国内很聪明的选手,看到了自己和他们的差距。最后,就是那 200 多页,有些自己都没有完全理解的,打印的密密麻麻的 算法模板。知识学会了,终身都是自己的,没有学会,那些知识都是身外之物。 笔者从 2019 年 3 月 25 号开始刷题,到 2020 年 3 月 25 号,整整一年的时间。原计划是每天一题。实际上每天有时候不止一题,最终完成了 600+: 一个温馨提示:笔者本以为每天做一题,会让这个 submissions 图全绿,但是我发现我错了。如果你也想坚持,让这个图全绿,一定要注意以下的问题:LeetCode 服务器是在 +0 时区的,这个图也是按照这个时区计算的。也就是说,中国每天早上 8 点之前,是算前一天的!也是因为时区的问题,导致我空白了这 22 个格子。比如有一道 Hard 题很难,当天工作也很多,晚上下班回家想出来了就到第二天凌晨了。于是再做一题当做第二天的量。结果会发现这 2 题都算前一天的。有时候笔者早上 6 点起床刷题,提交以后也都是前一天的。
题目总表
ID
Preference
URL
Name
Difficulty
Data Type
Tags
Completed Date
1
😰 Didn't Expect
Easy
Hashmap / Hashset
Hash Table
Feb 19, 2024
2
😊 Normal
Medium
Linked List
Linked List
Math
Recursion
Feb 20, 2024
3
💕 Like
Medium
Two Pointer
Hash Table
Sliding Window
Feb 22, 2024
4
🤔 Thought-provoking
Hard
Sorting
Binary Search
Divide and Conquer
Mar 4, 2024
5
Medium
Two Pointer
Two Pointers
Dynamic Programming
Manacher's Algorithm
Sliding Window
Apr 24, 2024
6
Medium
String
Math
Apr 24, 2024
7
Medium
Math
Apr 24, 2024
8
Medium
String
Math
Apr 24, 2024
9
Easy
Math
Apr 24, 2024
10
Hard
Dynamic Programming
Dynamic Programming
Recursion
DFS
Apr 25, 2024
148
Medium
Sorting
Merge Sort
Fast & Slow Pointers
Apr 28, 2024
27
Easy
Sorting
Counting Sort
Naive Algorithm
Apr 28, 2024
92
💕 Like
Medium
Linked List
In-place Reversal
May 8, 2024
141
Easy
Linked List
Loop Detection
Fast & Slow Pointers
May 8, 2024
54
🤔 Thought-provoking
Medium
Queue
Simulation
May 9, 2024
328
💸😭 Poverty Tears
Medium
Linked List
Two Pointers
May 9, 2024
876
💸😭 Poverty Tears
Easy
Linked List
Fast & Slow Pointers
May 9, 2024
1043
Dynamic Programming
1235
Dynamic Programming
32
Dynamic Programming
44
Dynamic Programming
1048
Dynamic Programming
518
Dynamic Programming
322
Dynamic Programming
1140
Dynamic Programming
87
Dynamic Programming
740
Dynamic Programming
213
Dynamic Programming
198
Dynamic Programming
221
Dynamic Programming
639
Dynamic Programming
91
Dynamic Programming
72
Dynamic Programming
115
Dynamic Programming
174
Dynamic Programming
1062
Dynamic Programming
1143
Dynamic Programming
312
Dynamic Programming
132
Dynamic Programming
45
Dynamic Programming
55
Dynamic Programming
121
Dynamic Programming
256
Dynamic Programming
354
Dynamic Programming
300
Dynamic Programming
368
Dynamic Programming
64
Dynamic Programming
70
Dynamic Programming
62
Dynamic Programming
729
TreeMap
759
Sweep Line
218
Sweep Line
1094
Sweep Line
253
Sweep Line
239
Monotone Stack/Queue
503
Monotone Stack/Queue
901
Monotone Stack/Queue
739
Monotone Stack/Queue
907
Monotone Stack/Queue
84
Monotone Stack/Queue
85
Monotone Stack/Queue
547
Union Find
721
Union Find
53
Prefix Sum
403
DFS
78
DFS
542
BFS
490
BFS
283
Two Pointer
277
Two Pointer
454
Two Pointer
18
Two Pointer
16
Two Pointer
15
Two Pointer
409
Two Pointer
410
Binary Search
1891
Binary Search
528
Binary Search
69
Binary Search
240
Binary Search
74
Binary Search
278
Binary Search
162
Binary Search
1095
Binary Search
895
Heap / Priority Queue
767
Heap / Priority Queue
295
Heap / Priority Queue
692
Heap / Priority Queue
88
Heap / Priority Queue
1086
Heap / Priority Queue
264
Heap / Priority Queue
23
Heap / Priority Queue
347
Heap / Priority Queue
973
Heap / Priority Queue
348
Hashmap / Hashset
299
Hashmap / Hashset
350
Hashmap / Hashset
49
Hashmap / Hashset
380
Hashmap / Hashset
73
Hashmap / Hashset
128
Hashmap / Hashset
146
Hashmap / Hashset
362
💸😭 Poverty Tears
Medium
Queue
Sliding Window
1429
💸😭 Poverty Tears
Medium
Queue
Hash Table
ID
Preference
URL
Name
Difficulty
Data Type
Tags
Completed Date
27
Easy
Sorting
Counting Sort
Naive Algorithm
Apr 28, 2024
148
Medium
Sorting
Merge Sort
Fast & Slow Pointers
Apr 28, 2024
4
🤔 Thought-provoking
Hard
Sorting
Binary Search
Divide and Conquer
Mar 4, 2024
ID
Preference
Name
Difficulty
Data Type
Tags
Completed Date
 
ID
Preference
URL
Name
Difficulty
Data Type
Tags
Completed Date
503
Monotone Stack/Queue
907
Monotone Stack/Queue
84
Monotone Stack/Queue
85
Monotone Stack/Queue
901
Monotone Stack/Queue
239
Monotone Stack/Queue
739
Monotone Stack/Queue

算法拾遗

快排

  1. 分两个函数:QuickSort(主函数)和 PartitionSort (找Pivot)
  1. QuickSort
    1. 先判断start是不是大于等于end,如果满足的话说明已经结束了
    2. 通过 PartitionSortpivot,参数就是 待排对象startend
    3. QuickSort 递归处理前半部分和后半部分
      1. 前半部分的参数是 待排对象startp-1
      2. 后半部分的参数是 待排对象p+1end
  1. PartitionSort
    1. 先规定pivot为最后一个对象
    2. 设置i为索引,默认为小于pivot的数,所以初始时,我们假设没有元素小于枢轴,也即i = start -1
    3. for设定j,从 start 搜到 end
    4. 如果 j 大于 pivot (或其他标准),则i++,之后把找出来的j和i交换,这样就让所有小于枢轴的都在左边
    5. 最后把 i+1 和 end 交换,实际上就是把枢轴放到中间
    6. 返回 i+1 作为 pivot 的位置

快选

快排变种
 
  1. 分为两个函数:QuickSelect(主函数)和 Partition (找枢轴)。
  1. QuickSelect
    1. 先判断 start 是否等于 end,如果满足的话说明已经找到了第 k 大的元素,返回这个元素。
    2. 通过 Partition 找到枢轴,参数就是待查找的数组、startend
    3. 根据 k 和枢轴的位置,决定是在枢轴的左边还是右边继续查找。
      1. 如果 k 等于枢轴的位置,那么我们就找到了第 k 大的元素,返回这个元素。
      2. 如果 k 小于枢轴的位置,那么我们在枢轴的左边部分继续查找,参数是待查找的数组、startpivot-1k
      3. 如果 k 大于枢轴的位置,那么我们在枢轴的右边部分继续查找,参数是待查找的数组、pivot+1endk
  1. Partition
    1. 先使用 rand.Intn 函数随机选择一个枢轴元素,然后将这个元素交换到数组的末尾,作为枢轴。
    2. 设置 i 为索引,默认为小于枢轴的数,所以初始时,我们假设没有元素小于枢轴,也即 i = start - 1
    3. 设定 j,从 start 遍历到 end
    4. 如果 j 所指向的元素小于或等于枢轴,则 i++,之后把 j 所指向的元素和 i 所指向的元素交换,这样就让所有小于或等于枢轴的元素都在枢轴的左边。
    5. 最后把 i+1 所指向的元素和 end 所指向的元素交换,实际上就是把枢轴放到了正确的位置(所有小于或等于枢轴的元素在枢轴的左边,所有大于枢轴的元素在枢轴的右边)。
    6. 返回 i+1,这就是枢轴的位置。
    7.  
某视频分析软件快速暴力破解思路后端开发人员面试问题