文章目錄
- 160. 相交鏈表（鏈表）
- 232. 用棧實現隊列
- 69. x 的平方根（二分法）
- 215. 數組中的第K個最大元素（快排）
- 347. 前 K 個高頻元素（桶排序）
- 378. 有序矩陣中第K小的元素（排序）
- 1051. 高度檢查器（排序）
- 17. 電話號碼的字母組合（遞歸）
- 241. 為運算表達式設計優先級（分治）
- 455. 分發餅干（貪心）
160. 相交鏈表（鏈表）
把兩個鏈表連起來，不斷遍歷，相等停下！
class
Solution
(
object
)
:
def
getIntersectionNode
(
self
,
headA
,
headB
)
:
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
p
=
headA
q
=
headB
while
(
q
!=
p
)
:
if
p
==
None
:
p
=
headB
else
:
p
=
p
.
next
if
q
==
None
:
q
=
headA
else
:
q
=
q
.
next
return
p
232. 用棧實現隊列
-
使用棧實現隊列的下列操作：
push(x) – 將一個元素放入隊列的尾部。
pop() – 從隊列首部移除元素。
peek() – 返回隊列首部的元素。
empty() – 返回隊列是否為空。 -
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false -
說明:
你只能使用標準的棧操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標準的棧操作即可。
假設所有操作都是有效的 （例如，一個空的隊列不會調用 pop 或者 peek 操作）。
思路，用兩個棧，一個負責輸入（push），一個負責輸出（pop）
class
MyQueue
(
object
)
:
def
__init__
(
self
)
:
"""
Initialize your data structure here.
"""
self
.
s1
=
[
]
# 負責輸入
self
.
s2
=
[
]
# 負責輸出
def
push
(
self
,
x
)
:
"""
Push element x to the back of queue.
:type x: int
:rtype: None
"""
self
.
s1
.
append
(
x
)
def
pop
(
self
)
:
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
if
not
self
.
s2
:
# 為空的話，把s1的元素逆序傳進去s2
while
self
.
s1
:
self
.
s2
.
append
(
self
.
s1
.
pop
(
)
)
return
self
.
s2
.
pop
(
)
#返回 s2的棧頂元素，也就是 s1的棧底，也就是隊頭
def
peek
(
self
)
:
"""
Get the front element.
:rtype: int
"""
if
not
self
.
s2
:
# 思路和 pop 一樣
while
self
.
s1
:
self
.
s2
.
append
(
self
.
s1
.
pop
(
)
)
return
self
.
s2
[
-
1
]
# 返回 s2的棧頂元素，也就是 s1的棧底，也就是隊頭
def
empty
(
self
)
:
"""
Returns whether the queue is empty.
:rtype: bool
"""
return
self
.
s1
==
[
]
and
self
.
s2
==
[
]
# 當兩個棧都為空的時候，隊列為空！
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
69. x 的平方根（二分法）
實現 int sqrt(int x) 函數。
計算并返回 x 的平方根，其中 x 是非負整數。
由于返回類型是整數，結果只保留整數的部分，小數部分將被舍去。
-
示例 1:
輸入: 4
輸出: 2 -
示例 2:
輸入: 8
輸出: 2 -
說明: 8 的平方根是 2.82842…,
由于返回類型是整數，小數部分將被舍去。
1）暴力法
會超時
class
Solution
(
object
)
:
def
mySqrt
(
self
,
x
)
:
"""
:type x: int
:rtype: int
"""
for
i
in
range
(
x
//
2
,
-
1
,
-
1
)
:
if
i
**
2
==
x
:
return
i
elif
i
**
2
>
x
>=
(
i
-
1
)
**
2
:
return
i
-
1
2）二分法
這里比較別扭的是取整，和二分查找還不一樣，x 的平方根大概率會落在兩個數字之間，所以要對二分法做一些小改進
middle**2 <= x < (middle+1)**2
class
Solution
(
object
)
:
def
mySqrt
(
self
,
x
)
:
"""
:type x: int
:rtype: int
"""
if
(
x
==
0
)
:
# 這一句也是相當重要的！
return
x
start
=
1
end
=
x
while
(
start
<=
end
)
:
middle
=
(
start
+
end
)
//
2
# 注意二分法的計算中間值的時候要放在 while 里面
if
middle
**
2
<=
x
<
(
middle
+
1
)
**
2
:
return
middle
if
middle
**
2
<
x
:
start
=
middle
if
middle
**
2
>
x
:
end
=
middle
二分法的核心就是
while(start <= end)
，然后不斷調整 start 和 end 來縮小搜索空間！！！
215. 數組中的第K個最大元素（快排）
在未排序的數組中找到第 k 個最大的元素。請注意，你需要找的是數組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。
-
示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5 -
示例 2:
輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4 -
說明:
你可以假設 k 總是有效的，且 1 ≤ k ≤ 數組的長度。
1）調用 sorted
class
Solution
(
object
)
:
def
findKthLargest
(
self
,
nums
,
k
)
:
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
nums
=
sorted
(
nums
)
return
nums
[
-
k
]
2）快排
快排是對冒泡排序的一種改進，它的基本思想（分治）是，通過一趟排序，將待排記錄分割成獨立的兩個部分，其中一個部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序！
先用快排排序，再挑選第 k 大的值
class
Solution
(
object
)
:
def
findKthLargest
(
self
,
nums
,
k
)
:
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
def
partion
(
nums
,
left
,
right
)
:
key
=
nums
[
left
]
# 注意這里基元素的選取，第一個元素，別寫成了 nums[0]
low
=
left
high
=
right
while
low
<
high
:
while
(
low
<
high
)
and
(
nums
[
high
]
>=
key
)
:
#右指針遇到小于基準元素的停下
high
-=
1
nums
[
low
]
=
nums
[
high
]
#右指針指向的值覆蓋左指針
while
(
low
<
high
)
and
(
nums
[
low
]
<=
key
)
:
# 左指針遇到大于基準元素的停下
low
+=
1
nums
[
high
]
=
nums
[
low
]
# 左指針指向的值覆蓋右指針
nums
[
low
]
=
key
# 用基值覆蓋左右指針相逢的地方
return
low
# 返回左右指針相逢的地方
def
quicksort
(
nums
,
left
,
right
)
:
if
left
<
right
:
#這句話超級關鍵
p
=
partion
(
nums
,
left
,
right
)
quicksort
(
nums
,
left
,
p
-
1
)
quicksort
(
nums
,
p
+
1
,
right
)
return
nums
return
quicksort
(
nums
,
0
,
len
(
nums
)
-
1
)
[
-
k
]
注意
def quicksort
中的遞歸終止條件！
def partion
中，掃描指針的兩個
while
改變下符號，就可以從大到小排序
nums[high] <= key
和
nums[low] >= key
注意，while 的順序
以 [5,7,3,8,1,9,2,0,6] 為例，可以看看 partion 的例子
3）堆排
……（bryant）
347. 前 K 個高頻元素（桶排序）
給定一個非空的整數數組，返回其中出現頻率前 k 高的元素。
-
示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2] -
示例 2:
輸入: nums = [1], k = 1
輸出: [1] -
說明：
你可以假設給定的 k 總是合理的，且 1 ≤ k ≤ 數組中不相同的元素的個數。
你的算法的時間復雜度必須優于 O(n log n) , n 是數組的大小。
先回顧下最簡單的 Bucket sort
res
=
[
]
nums
=
[
2
,
8
,
3
,
2
,
3
,
8
,
3
,
4
]
buckets
=
[
0
]
*
(
max
(
nums
)
-
min
(
nums
)
+
1
)
#最大數和最小數之間，一個桶里放一個數
# 遍歷數組，下標對應數字，數組內容對應頻數
for
i
in
nums
:
buckets
[
i
-
min
(
nums
)
]
+=
1
print
(
buckets
)
#遍歷桶，根據頻數輸出數字（根據數組內容輸出下標的次數）
for
i
in
range
(
len
(
buckets
)
)
:
if
buckets
[
i
]
:
res
.
extend
(
[
i
+
min
(
nums
)
]
*
buckets
[
i
]
)
res
output
[
2
,
3
,
1
,
0
,
0
,
0
,
2
]
[
2
,
2
,
3
,
3
,
3
,
4
,
8
,
8
]
關鍵點是
min(nums)
扮演的作用和地位，以及合并列表用的是
extend
不是
append
顯然，當數字跨度較大，用下標表示數字，數組內容表示對應數字頻數的時候并不合適，因此，我們換一下，用下標表示頻數，數組內容表示該頻數的數字，此時同一頻數的數字可能有多種，所以要 構建二維數組，行表示頻數，列表示該頻數的數字！
class
Solution
(
object
)
:
def
topKFrequent
(
self
,
nums
,
k
)
:
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
dict1
=
{
}
# keys 數字，values 頻數
res
=
[
]
for
i
in
nums
:
if
i
in
dict1
:
dict1
[
i
]
+=
1
else
:
dict1
[
i
]
=
1
buckets
=
[
[
]
for
i
in
range
(
len
(
nums
)
+
1
)
]
# [[],[],...[]],加一多了個頻數0
for
key
in
dict1
:
# 這里表示遍歷字典 key，也即數字
buckets
[
dict1
[
key
]
]
.
append
(
key
)
#將數字存放在對應的頻數下標中
for
i
in
range
(
len
(
nums
)
,
-
1
,
-
1
)
:
#從后往前掃描，第一個-1是為了兼顧0下標，第二個-1表示倒序，len(nums)因為 buckets長度是 len（nums）+1
if
buckets
[
i
]
:
# 如果對應頻數有數字
for
j
in
buckets
[
i
]
:
# 遍歷該頻數的所有數字
if
len
(
res
)
==
k
:
# 按題目要求輸出頻數最高的K個
break
else
:
res
.
append
(
j
)
#搜集符合條件的數字
return
res
eg：
nums = [2,8,3,2,3,8,3,4]
k = 2
- dict1 為 {2: 2, 8: 2, 3: 3, 4: 1} 表示 2 出現 2 次，8 出現 2 次，3 出現 3 次，4 出現 1 次
- 初始化的 buckets 為 [[], [], [], [], [], [], [], [], []]
- 裝入信息的 buckets [[], [4], [2, 8], [3], [], [], [], [], []] 表示 4 出現 1 次，2，8 出現 2 次，3 出現 3 次
- 輸出結果 [3, 2]
378. 有序矩陣中第K小的元素（排序）
給定一個 n x n 矩陣，其中每行和每列元素均按升序排序，找到矩陣中第k小的元素。
請注意，它是排序后的第k小元素，而不是第k個元素。
-
示例:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。 -
說明:
你可以假設 k 的值永遠是有效的, 1 ≤ k ≤ n2 。
思路，將二維 matrix 拉成一維的，用 list 的 extend 功能，然后排序（這個可以自由發揮，我用的 sorted），返回 list[k-1]
class
Solution
(
object
)
:
def
kthSmallest
(
self
,
matrix
,
k
)
:
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
sort_list
=
[
]
for
i
in
range
(
len
(
matrix
)
)
:
sort_list
.
extend
(
matrix
[
i
]
)
sort_list
=
sorted
(
sort_list
)
return
sort_list
[
k
-
1
]
不過這樣沒有充分利用數組的有序信息，還可以用二分查找來算……（bryant）
1051. 高度檢查器（排序）
學校在拍年度紀念照時，一般要求學生按照 非遞減 的高度順序排列。
請你返回至少有多少個學生沒有站在正確位置數量。該人數指的是：能讓所有學生以 非遞減 高度排列的必要移動人數。
-
示例：
輸入：[1,1,4,2,1,3]
輸出：3
解釋：
高度為 4、3 和最后一個 1 的學生，沒有站在正確的位置。 -
提示：
1 <= heights.length <= 100
1 <= heights[i] <= 100
一開始比比劃劃，束手無策，找不到很好的泛化方式，升序排序后，比較排序后和排序前的差異就可以得出結果了！這里我用的是快排！
class
Solution
(
object
)
:
def
heightChecker
(
self
,
heights
)
:
"""
:type heights: List[int]
:rtype: int
"""
original_heights
=
[
]
# 不先定義會報錯
original_heights
[
:
]
=
heights
[
:
]
#deep copy，因為快排會改變list
# 快排
def
quick_sort
(
num
,
start
,
end
)
:
if
start
<
end
:
base
=
split
(
num
,
start
,
end
)
quick_sort
(
num
,
start
,
base
-
1
)
quick_sort
(
num
,
base
+
1
,
end
)
return
num
def
split
(
nums
,
start
,
end
)
:
l
=
start
r
=
end
base
=
nums
[
l
]
while
(
l
<
r
)
:
while
l
<
r
and
nums
[
r
]
>=
base
:
r
-=
1
nums
[
l
]
=
nums
[
r
]
while
l
<
r
and
nums
[
l
]
<=
base
:
l
+=
1
nums
[
r
]
=
nums
[
l
]
nums
[
l
]
=
base
return
l
sorted_heights
=
quick_sort
(
heights
,
0
,
len
(
heights
)
-
1
)
num
=
0
# 記錄不一樣的數字
for
i
in
range
(
len
(
heights
)
)
:
if
original_heights
[
i
]
!=
sorted_heights
[
i
]
:
num
+=
1
return
num
17. 電話號碼的字母組合（遞歸）
給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。
給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。
-
示例:
輸入：“23”
輸出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
思路：字符串長度為 n n n ，便利第一個字符串和 1 ：n 的字符串結合，遞歸下去，如果字符串長度為1，返回數字對應的字母！
class
Solution
(
object
)
:
def
letterCombinations
(
self
,
digits
)
:
"""
:type digits: str
:rtype: List[str]
"""
dict_nums
=
{
2
:
[
'a'
,
'b'
,
'c'
]
,
3
:
[
'd'
,
'e'
,
'f'
]
,
4
:
[
'g'
,
'h'
,
'i'
]
,
5
:
[
'j'
,
'k'
,
'l'
]
,
6
:
[
'm'
,
'n'
,
'o'
]
,
7
:
[
'p'
,
'q'
,
'r'
,
's'
]
,
8
:
[
't'
,
'u'
,
'v'
]
,
9
:
[
'w'
,
'x'
,
'y'
,
'z'
]
}
if
digits
==
""
:
return
[
]
if
len
(
digits
)
==
1
:
return
dict_nums
[
int
(
digits
)
]
dict_nums_next
=
self
.
letterCombinations
(
digits
[
1
:
]
)
result
=
[
]
for
i
in
dict_nums
[
int
(
digits
[
0
]
)
]
:
for
j
in
dict_nums_next
:
result
.
append
(
i
+
j
)
return
result
241. 為運算表達式設計優先級（分治）
給定一個含有數字和運算符的字符串，為表達式添加括號，改變其運算優先級以求出不同的結果。你需要給出所有可能的組合的結果。有效的運算符號包含 +, - 以及 * 。
-
示例 1:
輸入: “2-1-1”
輸出: [0, 2] -
解釋:
( ( 2 ? 1 ) ? 1 ) = 0 ((2-1)-1) = 0 ( ( 2 ? 1 ) ? 1 ) = 0
( 2 ? ( 1 ? 1 ) ) = 2 (2-(1-1)) = 2 ( 2 ? ( 1 ? 1 ) ) = 2 -
示例 2:
輸入: " 2 ? 3 ? 4 ? 5 " "2*3-4*5" " 2 ? 3 ? 4 ? 5 "
輸出: [ ? 34 , ? 14 , ? 10 , ? 10 , 10 ] [-34, -14, -10, -10, 10] [ ? 3 4 , ? 1 4 , ? 1 0 , ? 1 0 , 1 0 ] -
解釋:
( 2 ? ( 3 ? ( 4 ? 5 ) ) ) = ? 34 (2*(3-(4*5))) = -34 ( 2 ? ( 3 ? ( 4 ? 5 ) ) ) = ? 3 4
( ( 2 ? 3 ) ? ( 4 ? 5 ) ) = ? 14 ((2*3)-(4*5)) = -14 ( ( 2 ? 3 ) ? ( 4 ? 5 ) ) = ? 1 4
( ( 2 ? ( 3 ? 4 ) ) ? 5 ) = ? 10 ((2*(3-4))*5) = -10 ( ( 2 ? ( 3 ? 4 ) ) ? 5 ) = ? 1 0
( 2 ? ( ( 3 ? 4 ) ? 5 ) ) = ? 10 (2*((3-4)*5)) = -10 ( 2 ? ( ( 3 ? 4 ) ? 5 ) ) = ? 1 0
( ( ( 2 ? 3 ) ? 4 ) ? 5 ) = 10 (((2*3)-4)*5) = 10 ( ( ( 2 ? 3 ) ? 4 ) ? 5 ) = 1 0
這個題目也有點分治的意思，但是主體還是遞歸，思路如下（參考 LeetCode - 241. Different Ways to Add Parentheses(分治、dp) ）：
-
遞歸函數，遍歷當前字符串，只要有符號是
+、-、*的就將整個字符串分開成兩半； - 然后左邊一半的字符串去遞歸求出那個解的集合，右邊的也求出解的集合；
-
最后關鍵的是當前的字符串的解是左和右的
笛卡爾積（這個操作尤為重要）；
圖片來源 https://blog.csdn.net/zxzxzx0119/article/details/83748086
class
Solution
(
object
)
:
def
diffWaysToCompute
(
self
,
input
)
:
"""
:type input: str
:rtype: List[int]
"""
# 遞歸終止條件，全部是數字
if
input
.
isdigit
(
)
:
return
[
int
(
input
)
]
res
=
[
]
for
i
in
range
(
len
(
input
)
)
:
if
input
[
i
]
in
"+-*"
:
L
=
self
.
diffWaysToCompute
(
input
[
:
i
]
)
# 記得 self
R
=
self
.
diffWaysToCompute
(
input
[
i
+
1
:
]
)
# 遍歷左右 str，計算笛卡爾積
for
l
in
L
:
for
r
in
R
:
if
input
[
i
]
==
"+"
:
res
.
append
(
l
+
r
)
elif
input
[
i
]
==
"-"
:
res
.
append
(
l
-
r
)
else
:
res
.
append
(
l
*
r
)
return
res
# 記得返回，不然 return None 會報錯 TypeError: 'NoneType' object is not iterable"
455. 分發餅干（貪心）
假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。對每個孩子 i ，都有一個胃口值 gi ，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j ，都有一個尺寸 sj 。如果 sj >= gi ，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數量的孩子，并輸出這個最大數值。
-
注意：
你可以假設胃口值為正。
一個小朋友最多只能擁有一塊餅干。 -
示例 1:
輸入: [1,2,3], [1,1]
輸出: 1 -
解釋:
你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應該輸出1。 -
示例 2:
輸入: [1,2], [1,2,3]
輸出: 2 -
解釋:
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。
你擁有的餅干數量和尺寸都足以讓所有孩子滿足。
所以你應該輸出2.
參考 LeetCode-Python-455. 分發餅干
孩子需求從小到大排序，餅干從小到大發放
滿足孩子需求的話，有請下一位小朋友和下一個餅干，結果統計加1
不然就換個更大的餅干來滿足當前的小朋友
直到餅干發完或者小朋友都被滿足
class
Solution
(
object
)
:
def
findContentChildren
(
self
,
g
,
s
)
:
"""
:type g: List[int]
:type s: List[int]
:rtype: int
"""
g
=
sorted
(
g
)
s
=
sorted
(
s
)
child
=
0
cake
=
0
while
(
child
<
len
(
g
)
and
cake
<
len
(
s
)
)
:
if
g
[
child
]
<=
s
[
cake
]
:
child
+=
1
# 得到了滿足就有請下一位
cake
+=
1
# 從小到大發餅干
return
child
# 返回被滿足的孩子數量
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
