文章目錄
- python力扣刷題
- 探索初級算法
- 數(shù)組
- 從數(shù)組中刪除重復(fù)項(xiàng)
- 買賣股票的最佳時(shí)機(jī) II
- 向右旋轉(zhuǎn)數(shù)組幾次
- 存在重復(fù)
- 找出只出現(xiàn)一次的數(shù)字的元素
- 兩個(gè)數(shù)組的交集 II
- 元素末尾加一
- 移動(dòng)0的位置到數(shù)組末尾
- 求數(shù)組中兩數(shù)之和等于指定值的兩個(gè)數(shù)，并求索引
- 有效的數(shù)獨(dú)
- 旋轉(zhuǎn)圖像(zip函數(shù)，map函數(shù))
python力扣刷題
探索初級算法
數(shù)組
從數(shù)組中刪除重復(fù)項(xiàng)
class
Solution
:
def
removeDuplicates
(
self
,
nums
)
:
"""
刪除重復(fù)項(xiàng)后的數(shù)組
"""
if
(
len
(
nums
)
==
0
)
:
return
0
for
i
in
range
(
len
(
nums
)
)
:
for
j
in
range
(
i
+
1
,
len
(
nums
)
)
:
if
(
nums
[
j
]
==
nums
[
i
]
)
:
nums
[
j
]
=
[
]
# 把為[]的數(shù)刪掉
while
[
]
in
nums
:
nums
.
remove
(
[
]
)
remo_lists_len
=
len
(
nums
)
return
remo_lists_len
,
nums
def
main
(
)
:
"""
主函數(shù)
"""
print
(
'請輸入任意數(shù)組(每個(gè)元素用空格隔開，如：1 1 2'
)
nums_str
=
input
(
'請輸入：'
)
str_list
=
nums_str
.
split
(
' '
)
# 字符串列表轉(zhuǎn)數(shù)值字符串
nums
=
[
]
for
i
in
range
(
len
(
str_list
)
)
:
nums
.
append
(
float
(
str_list
[
i
]
)
)
# 調(diào)用類
sol
=
Solution
(
)
# 執(zhí)行類的初始化
remo_lists_len
,
remo_lists
=
sol
.
removeDuplicates
(
nums
)
# 刪除重復(fù)項(xiàng)后的數(shù)組
print
(
'刪除重復(fù)項(xiàng)后的數(shù)組為：{},長度為：{}'
.
format
(
remo_lists
,
remo_lists_len
)
)
if
__name__
==
'__main__'
:
main
(
)
買賣股票的最佳時(shí)機(jī) II
"""
給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。
"""
class
Solution
:
def
maxProfit
(
self
,
nums
)
:
"""
求最大收益
"""
profit
=
0
i
=
0
while
(
i
<
len
(
nums
)
-
1
)
:
j
=
i
+
1
# 如果第j個(gè)值比第i個(gè)值小，不售出，i=i+1
if
nums
[
j
]
<
nums
[
i
]
:
i
+=
1
# 如果第j個(gè)值比第i個(gè)值大 and 第j個(gè)值比第j+1個(gè)值大，售出，i=i+2
elif
nums
[
j
]
>
nums
[
i
]
and
nums
[
j
]
>
nums
[
j
+
1
]
:
buy_in
=
nums
[
i
]
buy_out
=
nums
[
j
]
profit
+=
buy_out
-
buy_in
i
+=
2
# 如果第j個(gè)值比第i個(gè)值大 and 第j個(gè)值比第j+1個(gè)值小，找出j最大的位置，售出，i=i+j
elif
nums
[
j
]
>
nums
[
i
]
and
nums
[
j
]
<
nums
[
j
+
1
]
:
while
(
nums
[
j
]
<
nums
[
j
+
1
]
)
:
j
+=
1
if
j
==
len
(
nums
)
-
1
:
break
buy_in
=
nums
[
i
]
buy_out
=
nums
[
j
]
i
+=
j
profit
+=
buy_out
-
buy_in
return
profit
def
main
(
)
:
"""
主函數(shù)
"""
nums
=
[
7
,
6
,
4
,
3
,
1
]
# 調(diào)用類
sol
=
Solution
(
)
# 執(zhí)行類的初始化
profit
=
sol
.
maxProfit
(
nums
)
print
(
'最大收益為：{}'
.
format
(
profit
)
)
if
__name__
==
'__main__'
:
main
(
)
向右旋轉(zhuǎn)數(shù)組幾次
"""
給定一個(gè)數(shù)組，將數(shù)組中的元素向右移動(dòng) k 個(gè)位置，其中 k 是非負(fù)數(shù)
eg:
輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]
執(zhí)行用時(shí)：24ms
"""
class
Solution
:
def
rotate
(
self
,
nums
,
k
)
:
"""
nums 輸入的數(shù)組
k 向右移動(dòng)幾位
"""
while
(
k
>
0
)
:
nums
.
insert
(
0
,
nums
[
-
1
]
)
nums
.
pop
(
)
k
-=
1
return
nums
def
main
(
)
:
"""
主函數(shù)
"""
nums
=
[
1
,
2
,
3
,
4
,
5
,
6
,
7
]
k
=
3
# 調(diào)用類
sol
=
Solution
(
)
# 執(zhí)行類的初始化
rotate_list
=
sol
.
rotate
(
nums
,
k
)
print
(
'旋轉(zhuǎn){}次后數(shù)組為：{}'
.
format
(
k
,
rotate_list
)
)
if
__name__
==
'__main__'
:
main
(
)
存在重復(fù)
"""
功能：給定一個(gè)整數(shù)數(shù)組，判斷是否存在重復(fù)元素。
如果任何值在數(shù)組中出現(xiàn)至少兩次，函數(shù)返回 true。如果數(shù)組中每個(gè)元素都不相同，則返回 false。
執(zhí)行用時(shí)：24ms
"""
class
Solution
(
object
)
:
def
containsDuplicate
(
self
,
nums
)
:
"""
nums 輸入的數(shù)組
"""
for
i
in
range
(
len
(
nums
)
)
:
result
=
False
if
nums
.
count
(
nums
[
i
]
)
>=
2
:
result
=
True
return
result
def
main
(
)
:
"""
主函數(shù)
"""
nums
=
[
1
,
1
,
1
,
3
,
3
,
4
,
3
,
2
,
4
,
2
]
# 調(diào)用類
sol
=
Solution
(
)
# 執(zhí)行類的初始化
result
=
sol
.
containsDuplicate
(
nums
)
print
(
'函數(shù)返回: {}'
.
format
(
result
)
)
if
__name__
==
'__main__'
:
main
(
)
找出只出現(xiàn)一次的數(shù)字的元素
"""
功能：給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素
eg:
輸入: [4,1,2,1,2]
輸出: 4
執(zhí)行用時(shí)：24ms
"""
class
Solution
(
object
)
:
def
singleNumber
(
self
,
nums
)
:
"""
找出那個(gè)只出現(xiàn)了一次的元素
"""
for
i
in
range
(
len
(
nums
)
)
:
if
nums
.
count
(
nums
[
i
]
)
==
1
:
return
nums
[
i
]
def
main
(
)
:
"""
主函數(shù)
"""
nums
=
[
4
,
1
,
2
,
1
,
2
]
# 調(diào)用類
sol
=
Solution
(
)
# 執(zhí)行類的初始化
result
=
sol
.
singleNumber
(
nums
)
print
(
'輸出: {}'
.
format
(
result
)
)
if
__name__
==
'__main__'
:
main
(
)
兩個(gè)數(shù)組的交集 II
"""
功能：給定兩個(gè)數(shù)組，編寫一個(gè)函數(shù)來計(jì)算它們的交集, 補(bǔ)集，并集
eg:
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
"""
class
Solution
(
object
)
:
def
intersection
(
self
,
nums1
,
nums2
)
:
# 計(jì)算交集
result_intersection_
=
[
]
for
i
in
nums1
:
if
i
in
nums2
:
result_intersection_
.
append
(
i
)
return
result_intersection_
def
intersect
(
self
,
nums1
,
nums2
)
:
"""
計(jì)算它們的交集, 補(bǔ)集，并集
"""
result_diff
=
set
(
nums1
)
-
set
(
nums2
)
result_unin
=
set
(
nums1
)
|
set
(
nums2
)
result_intersection
=
set
(
nums1
)
&
set
(
nums2
)
result_diff
=
list
(
result_diff
)
result_unin
=
list
(
result_unin
)
result_intersection
=
list
(
result_intersection
)
return
result_diff
,
result_unin
,
result_intersection
,
self
.
intersection
(
nums1
,
nums2
)
def
main
(
)
:
"""
主函數(shù)
"""
nums1
=
[
1
,
2
,
2
,
1
]
nums2
=
[
2
,
2
]
# 調(diào)用類
sol
=
Solution
(
)
# 執(zhí)行類的初始化
result_diff
,
result_unin
,
result_intersection
,
result_intersection_
=
sol
.
intersect
(
nums1
,
nums2
)
print
(
'nums1 = [1,2,2,1] nums2 = [2,2]'
)
print
(
'差集: {}'
.
format
(
result_diff
)
)
print
(
'并集: {}'
.
format
(
result_unin
)
)
print
(
'集合中符號(hào)求得交集: {}'
.
format
(
result_intersection
)
)
print
(
'要求的交集: {}'
.
format
(
result_intersection_
)
)
if
__name__
==
'__main__'
:
main
(
)
元素末尾加一
"""
功能：給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。
最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個(gè)元素只存儲(chǔ)一個(gè)數(shù)字。
你可以假設(shè)除了整數(shù) 0 之外，這個(gè)整數(shù)不會(huì)以零開頭。
eg: 輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入數(shù)組表示數(shù)字 123。
"""
class
Solution
(
object
)
:
def
plusOne
(
self
,
digits
)
:
digits
[
-
1
]
=
digits
[
-
1
]
+
1
return
digits
def
main
(
)
:
"""
主函數(shù)
"""
digits
=
[
1
,
2
,
3
]
# 調(diào)用類
sol
=
Solution
(
)
# 執(zhí)行類的初始化
result
=
sol
.
plusOne
(
digits
)
print
(
'加1后的數(shù)組為: {}'
.
format
(
result
)
)
if
__name__
==
'__main__'
:
main
(
)
移動(dòng)0的位置到數(shù)組末尾
"""
功能：給定一個(gè)數(shù)組 nums，編寫一個(gè)函數(shù)將所有 0 移動(dòng)到數(shù)組的末尾，同時(shí)保持非零元素的相對順序。
必須在原數(shù)組上操作，不能拷貝額外的數(shù)組。
盡量減少操作次數(shù)。
eg:
[0,1,0,3,12]
輸出: [1,3,12,0,0]
"""
class
Solution
(
object
)
:
def
moveZeroes
(
self
,
nums
)
:
for
i
in
range
(
len
(
nums
)
-
1
)
:
# 如果前一個(gè)為0，后一個(gè)不為0，交換位置
if
nums
[
i
]
==
0
and
nums
[
i
+
1
]
!=
0
:
t
=
nums
[
i
]
nums
[
i
]
=
nums
[
i
+
1
]
nums
[
i
+
1
]
=
t
# 如果前一個(gè)為0，后一個(gè)為0，找到不為0的元素，交換位置
elif
(
nums
[
i
]
==
0
)
and
(
nums
[
i
+
1
]
==
0
)
:
step
=
0
while
nums
[
i
]
==
0
:
i
+=
1
step
+=
1
if
i
>
len
(
nums
)
-
1
:
i
-=
1
step
-=
1
break
t
=
nums
[
i
]
nums
[
i
]
=
nums
[
i
-
step
]
nums
[
i
-
step
]
=
t
return
nums
def
main
(
)
:
"""
主函數(shù)
"""
nums
=
[
0
,
1
,
0
,
3
,
12
]
# 調(diào)用類
sol
=
Solution
(
)
# 執(zhí)行類的初始化
result
=
sol
.
moveZeroes
(
nums
)
print
(
'數(shù)組為: {}'
.
format
(
result
)
)
if
__name__
==
'__main__'
:
main
(
)
求數(shù)組中兩數(shù)之和等于指定值的兩個(gè)數(shù)，并求索引
"""
功能：給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。
eg:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
用時(shí)：20ms
"""
class
Solution
(
object
)
:
def
twoSum
(
self
,
nums
,
target
)
:
for
i
in
range
(
len
(
nums
)
-
1
)
:
for
j
in
range
(
i
+
1
,
len
(
nums
)
)
:
if
nums
[
i
]
+
nums
[
j
]
==
target
:
return
i
,
j
def
main
(
)
:
"""
主函數(shù)
"""
nums
=
[
15
,
2
,
7
]
target
=
9
# 調(diào)用類
sol
=
Solution
(
)
# 執(zhí)行類的初始化
i
,
j
=
sol
.
twoSum
(
nums
,
target
)
print
(
'兩個(gè)數(shù)字分別為：{}，{}\n索引分別為：{}，{}'
.
format
(
nums
[
i
]
,
nums
[
j
]
,
i
,
j
)
)
if
__name__
==
'__main__'
:
main
(
)
有效的數(shù)獨(dú)
"""
功能：判斷一個(gè) 9x9 的數(shù)獨(dú)是否有效。只需要根據(jù)以下規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。
數(shù)字 1-9 在每一行只能出現(xiàn)一次。
數(shù)字 1-9 在每一列只能出現(xiàn)一次。
數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。
說明:
一個(gè)有效的數(shù)獨(dú)（部分已被填充）不一定是可解的。
只需要根據(jù)以上規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。
給定數(shù)獨(dú)序列只包含數(shù)字 1-9 和字符 '.' 。
給定數(shù)獨(dú)永遠(yuǎn)是 9x9 形式的。
"""
class
Solution
(
object
)
:
def
__init__
(
self
,
board
)
:
self
.
board
=
board
def
row
(
self
)
:
"""
數(shù)字 1-9 在每一行只能出現(xiàn)一次
"""
# 列循環(huán)，數(shù)組循環(huán)
for
colum
in
range
(
0
,
9
)
:
# 行循環(huán)，i 操作
for
i
in
range
(
0
,
9
)
:
# 行循環(huán)，j操作
for
j
in
range
(
i
+
1
,
9
)
:
if
(
self
.
board
[
colum
]
[
i
]
==
self
.
board
[
colum
]
[
j
]
)
and
type
(
self
.
board
[
colum
]
[
i
]
)
==
int
:
return
False
return
True
def
colum
(
self
)
:
"""
數(shù)字 1-9 在每一列只能出現(xiàn)一次
"""
# 行循環(huán)，數(shù)組循環(huán)
for
colum
in
range
(
0
,
9
)
:
# 列循環(huán)，i 操作
for
i
in
range
(
0
,
9
)
:
# 列循環(huán)，j操作
for
j
in
range
(
i
+
1
,
9
)
:
if
(
self
.
board
[
i
]
[
colum
]
==
self
.
board
[
j
]
[
colum
]
)
and
type
(
self
.
board
[
colum
]
[
i
]
)
==
int
:
return
False
return
True
def
box
(
self
,
colum_start
,
colum_end
,
i_start
,
i_end
,
)
:
"""
colum_start: eg:第一行的三個(gè)3*3的box, 要循環(huán)大數(shù)組的前三行，第一行start為0
colum_end: eg: 第一行的三個(gè)3*3的box, 要循環(huán)大數(shù)組的前三行，第三行end為3，range里面3取不到
i_start: 要比較的元素索引開始值
i_end: 要比較的元素索引終點(diǎn)值
return:判斷在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次,true,否則返回false
"""
# 9個(gè)單元格的列循環(huán)
for
colum
in
range
(
colum_start
,
colum_end
)
:
# 行循環(huán)，i 操作
for
i
in
range
(
i_start
,
i_end
)
:
# 行循環(huán)，j操作，每次按列尋找
for
j
in
range
(
i_start
,
i_end
)
:
if
(
(
self
.
board
[
colum
]
[
i
]
==
self
.
board
[
colum_start
]
[
j
]
if
i
!=
j
else
False
)
\
or
(
self
.
board
[
colum
]
[
i
]
==
self
.
board
[
colum_start
+
1
]
[
j
]
if
(
(
i
!=
j
)
and
(
colum
!=
colum_start
+
1
)
)
else
False
)
\
or
(
self
.
board
[
colum
]
[
i
]
==
self
.
board
[
colum_start
+
2
]
[
j
]
if
(
(
i
!=
j
)
and
(
colum
!=
colum_start
+
2
)
)
else
False
)
)
\
and
ord
(
self
.
board
[
colum
]
[
i
]
)
!=
46
:
# ord(), 返回元素的數(shù)值，用它來排除符號(hào)相等的問題
return
False
return
True
def
nine
(
self
)
:
"""
在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次
"""
# 三個(gè)box, 第1行
result_1
=
self
.
box
(
0
,
3
,
0
,
3
)
result_2
=
self
.
box
(
0
,
3
,
3
,
6
)
result_3
=
self
.
box
(
0
,
3
,
6
,
9
)
# 三個(gè)box, 第2行
result_4
=
self
.
box
(
3
,
6
,
0
,
3
)
result_5
=
self
.
box
(
3
,
6
,
3
,
6
)
result_6
=
self
.
box
(
3
,
6
,
6
,
9
)
# 三個(gè)box, 第3行
result_7
=
self
.
box
(
6
,
9
,
0
,
3
)
result_8
=
self
.
box
(
6
,
9
,
3
,
6
)
result_9
=
self
.
box
(
6
,
9
,
6
,
9
)
if
result_1
==
result_2
==
result_3 \
==
result_4
==
result_5
==
result_6 \
==
result_7
==
result_8
==
result_9 \
==
True
:
return
True
else
:
return
False
def
isValidSudoku
(
self
)
:
result_row
=
self
.
row
(
)
result_colum
=
self
.
colum
(
)
result_nine
=
self
.
nine
(
)
if
result_row
==
result_colum
==
result_nine
==
True
:
return
True
else
:
return
False
def
main
(
)
:
"""
主函數(shù)
"""
board
=
[
[
"5"
,
"3"
,
"."
,
"."
,
"7"
,
"."
,
"."
,
"."
,
"."
]
,
[
"6"
,
"."
,
"."
,
"1"
,
"9"
,
"5"
,
"."
,
"."
,
"."
]
,
[
"."
,
"9"
,
"8"
,
"."
,
"."
,
"."
,
"."
,
"6"
,
"."
]
,
[
"8"
,
"."
,
"."
,
"."
,
"6"
,
"."
,
"."
,
"."
,
"3"
]
,
[
"4"
,
"."
,
"."
,
"8"
,
"."
,
"3"
,
"."
,
"."
,
"1"
]
,
[
"7"
,
"."
,
"."
,
"."
,
"2"
,
"."
,
"."
,
"."
,
"6"
]
,
[
"."
,
"6"
,
"."
,
"."
,
"."
,
"."
,
"2"
,
"8"
,
"."
]
,
[
"."
,
"."
,
"."
,
"4"
,
"1"
,
"9"
,
"."
,
"."
,
"5"
]
,
[
"."
,
"."
,
"."
,
"."
,
"8"
,
"."
,
"."
,
"7"
,
"9"
]
]
sol
=
Solution
(
board
)
result
=
sol
.
isValidSudoku
(
)
print
(
result
)
if
__name__
==
'__main__'
:
main
(
)
旋轉(zhuǎn)圖像(zip函數(shù)，map函數(shù))
"""
功能：給定一個(gè) n × n 的二維矩陣表示一個(gè)圖像。
將圖像順時(shí)針旋轉(zhuǎn) 90 度。
你必須在原地旋轉(zhuǎn)圖像，這意味著你需要直接修改輸入的二維矩陣。請不要使用另一個(gè)矩陣來旋轉(zhuǎn)圖像。
eg:
給定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
變?yōu)?
[
[7,4,1],
[8,5,2],
[9,6,3]
]
zip 函數(shù)的用法：
>>> a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> list(zip(*a))
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]
>>> map(list,zip(*a))
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]
而我們想要的結(jié)果是[[7, 4, 1], [8, 5, 2], [9, 6, 3]]，只需要將每行reverse即可
總結(jié)：對于二維數(shù)組，zip(*a) 將縱向壓縮數(shù)組，打包為元組的列表
map( func, seq1[, seq2...] )
Python函數(shù)式編程中的map()函數(shù)是將func作用于seq中的每一個(gè)元素，并用一個(gè)列表給出返回值
"""
import
numpy
as
np
class
Solution
(
object
)
:
def
rotate
(
self
,
matrix
)
:
mat_map
=
list
(
map
(
list
,
zip
(
*
matrix
)
)
)
mat
=
np
.
array
(
matrix
)
row_n
=
mat
.
shape
[
0
]
for
i
in
range
(
row_n
)
:
mat_map
[
i
]
.
reverse
(
)
return
mat_map
def
main
(
)
:
"""
主函數(shù)
"""
matrix
=
[
[
1
,
2
,
3
]
,
[
4
,
5
,
6
]
,
[
7
,
8
,
9
]
]
sol
=
Solution
(
)
result
=
sol
.
rotate
(
matrix
)
print
(
result
)
if
__name__
==
'__main__'
:
main
(
)
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
