🗒️LeetCode 刷题记录
type
status
date
slug
summary
tags
category
icon
password
其实我本人不喜欢刷题,但是生活所迫,多少还是得刷点,所以就每天刷点题吧,主要是了解一下算法
题目总表
ID
Preference
URL
Name
Difficulty
Data Type
Tags
Completed Date
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
148
Medium
Sorting
Merge Sort
Fast & Slow Pointers
Apr 28, 2024
75
Medium
Sorting
Counting Sort
Apr 28, 2024
27
Easy
Sorting
Counting Sort
Naive Algorithm
Apr 28, 2024
179
Medium
Sorting
Greedy
Quick Sort
Apr 29, 2024
92
💕 Like
Medium
Linked List
In-place Reversal
May 8, 2024
141
Easy
Linked List
Loop Detection
Fast & Slow Pointers
May 8, 2024
160
Easy
Linked List
Loop Detection
May 8, 2024
215
Medium
Sorting
Quick Select
Counting Sort
May 8, 2024
735
Medium
Stack
Simulation
May 9, 2024
1209
Medium
Stack
Naive Algorithm
Hash Table
May 9, 2024
54
🤔 Thought-provoking
Medium
Queue
Simulation
May 9, 2024
225
Easy
Queue
Design
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
206
Easy
Linked List
In-place Reversal
May 9, 2024
1249
😰 Didn't Expect
Medium
Stack
May 10, 2024
150
Medium
Stack
Math
May 10, 2024
1472
😰 Didn't Expect
Medium
Stack
Simulation
May 11, 2024
20
⚠ Attention to boundaries
Easy
Stack
May 11, 2024
1438
Heap/Priority Queue
Heap / Priority Queue
224
Hard
Stack
232
🤔 Thought-provoking
Easy
Stack
Design
362
💸😭 Poverty Tears
Medium
Queue
Sliding Window
1429
💸😭 Poverty Tears
Medium
Queue
Hash Table
346
💸😭 Poverty Tears
Easy
Queue
Sliding Window
ID
Preference
URL
Name
Difficulty
Data Type
Tags
Completed Date
215
Medium
Sorting
Quick Select
Counting Sort
May 8, 2024
179
Medium
Sorting
Greedy
Quick Sort
Apr 29, 2024
27
Easy
Sorting
Counting Sort
Naive Algorithm
Apr 28, 2024
75
Medium
Sorting
Counting Sort
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
算法拾遗
快排
- 分两个函数:
QuickSort
(主函数)和PartitionSort
(找Pivot)
QuickSort
- 先判断
start
是不是大于等于end
,如果满足的话说明已经结束了 - 通过
PartitionSort
找pivot
,参数就是待排对象
、start
、end
QuickSort
递归处理前半部分和后半部分- 前半部分的参数是
待排对象
、start
、p-1
- 后半部分的参数是
待排对象
、p+1
、end
PartitionSort
- 先规定
pivot
为最后一个对象 - 设置i为索引,默认为小于
pivot
的数,所以初始时,我们假设没有元素小于枢轴,也即i = start -1
for
设定j
,从 start 搜到 end- 如果 j 大于 pivot (或其他标准),则i++,之后把找出来的j和i交换,这样就让所有小于枢轴的都在左边
- 最后把 i+1 和 end 交换,实际上就是把枢轴放到中间
- 返回 i+1 作为 pivot 的位置
快选
快排变种
- 分为两个函数:
QuickSelect
(主函数)和Partition
(找枢轴)。
QuickSelect
:- 先判断
start
是否等于end
,如果满足的话说明已经找到了第 k 大的元素,返回这个元素。 - 通过
Partition
找到枢轴,参数就是待查找的数组、start
、end
。 - 根据 k 和枢轴的位置,决定是在枢轴的左边还是右边继续查找。
- 如果 k 等于枢轴的位置,那么我们就找到了第 k 大的元素,返回这个元素。
- 如果 k 小于枢轴的位置,那么我们在枢轴的左边部分继续查找,参数是待查找的数组、
start
、pivot-1
、k
。 - 如果 k 大于枢轴的位置,那么我们在枢轴的右边部分继续查找,参数是待查找的数组、
pivot+1
、end
、k
。
Partition
:- 先使用
rand.Intn
函数随机选择一个枢轴元素,然后将这个元素交换到数组的末尾,作为枢轴。 - 设置
i
为索引,默认为小于枢轴的数,所以初始时,我们假设没有元素小于枢轴,也即i = start - 1
。 - 设定
j
,从start
遍历到end
。 - 如果
j
所指向的元素小于或等于枢轴,则i++
,之后把j
所指向的元素和i
所指向的元素交换,这样就让所有小于或等于枢轴的元素都在枢轴的左边。 - 最后把
i+1
所指向的元素和end
所指向的元素交换,实际上就是把枢轴放到了正确的位置(所有小于或等于枢轴的元素在枢轴的左边,所有大于枢轴的元素在枢轴的右边)。 - 返回
i+1
,这就是枢轴的位置。