文章目录
- 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
(
)
