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