推荐：只出现一次的数字，旋转数组，两个数组的交集 II 和 两数之和。
1. 删除排序数组中的重复项
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
# 删除排序数组中的重复项
# 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
# 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
class Solution:
def removeDuplicates(self, nums) -> int:
# 第一个游标用于更改值
i = 0
# 第二个游标用于遍历
for j in range(1, len(nums)):
# 判断与之前记录的值不同
if nums[i] != nums[j]:
# 赋值，且游标加一
nums[i + 1] = nums[j]
i += 1
return i + 1
2. 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
# 买卖股票的最佳时机
# 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
# 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
class Solution:
def max_profit(self, prices) -> int:
# 用于计算利润
z = 0
# 遍历数据
for i in range(len(prices) - 1):
# 如果第二天的值大于当天的值，买入
if prices[i] < prices[i + 1]:
print(z, prices[i], prices[i + 1])
z = z + prices[i + 1] - prices[i]
return z
3. 旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
# 旋转数组
# 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
class Solution:
def rotate(self, nums, k: int) -> None:
# 计算数组长度
l = len(nums)
# 第一种解法
nums[:] = nums[l - k:] + nums[:l - k]
# 第二种解法
# nums[:l - k] = reversed(nums[:l - k])
# nums[l - k:] = reversed(nums[l - k:])
# nums[:] = reversed(nums)
4. 存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
# 存在重复元素
# 给定一个整数数组，判断是否存在重复元素。
# 如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
import collections
class Solution:
def containsDuplicate(self, nums) -> bool:
# Counter模块统计数组中各元素出现的次数，返回一个字典
count = collections.Counter(nums)
# 遍历结果
for value in count.values():
print(value)
if value >= 2:
return True
return False
5. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
# 只出现一次的数字
# 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
class Solution:
def singleNumber(self, nums) -> int:
res = 0
for v in nums:
# 使用异或
# 0异或任何数都是0，a^b^a = b, 异或满足加法结合律和交换律
res ^= v
return res
6. 两个数组的交集 II
给定两个数组，编写一个函数来计算它们的交集。
# 两个数组的交集 II
# 给定两个数组，编写一个函数来计算它们的交集。
class Solution:
def intersect(self, nums1, nums2):
# 第一种解法，速度偏慢
# res = []
# 判断两个数组的长度，遍历较短的数组
# if len(nums1) <= len(nums2):
# for i in nums1:
# # 如果存在在另一个数组中，则添加到结果中，并且在另一个数组删除该元素
# if i in nums2:
# res.append(i)
# nums2.remove(i)
# else:
# for i in nums2:
# if i in nums1:
# res.append(i)
# nums1.remove(i)
# return res
# 第二种解法
# 先对两个数组进行排序
nums1.sort()
nums2.sort()
# 使用两个游标记录
i, j = 0, 0
res = []
# 在游标不超过数组长度情况下
while i < len(nums1) and j < len(nums2):
# 如果结果相同，添加到结果列表，并同时移动游标
if nums1[i] == nums2[j]:
res.append(nums1[i])
i += 1
j += 1
# 如果第一个数组的值小于第二个数组的值，移动第一个游标
elif nums1[i] < nums2[j]:
i += 1
# 如果第一个数组的值大于第二个数组的值，移动第二个游标
else:
j += 1
return res
7. 加一
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
# 加一
# 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
# 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
# 你可以假设除了整数 0 之外，这个整数不会以零开头。
class Solution:
def plusOne(self, digits):
# 将列表转为字符串，再转为数字后加一
tmp = int(''.join([str(i) for i in digits])) + 1
# 将数字转为字符串，再转为列表
return [int(i) for i in str(tmp)]
8. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
# 移动零
# 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
class Solution:
def moveZeroes(self, nums) -> None:
# 游标，用于记录零所在的位置
i = 0
# for循环用于交换零和非零元素
for j in range(len(nums)):
# 不为零，就交换，然后游标加一
if nums[j] != 0:
nums[j], nums[i] = nums[i], nums[j]
i += 1
9. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
# 两数之和
# 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
# 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
class Solution:
def twoSum(self, nums, target):
# 遍历整个数组
for i in range(len(nums)):
# 判断两者之差，是否在数组中
if target - nums[i] in nums:
# 获取第二个数字的索引
num2_index = nums.index(target - nums[i])
# 索引不同返回结果
if i != num2_index:
return [i, num2_index]
10. 有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次
# 有效的数独
# 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
# 数字 1-9 在每一行只能出现一次。
# 数字 1-9 在每一列只能出现一次。
# 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次
class Solution:
def isValidSudoku(self, board) -> bool:
cell_list = [[] for i in range(9)]
col_list = [[] for i in range(9)]
row_list = [[] for i in range(9)]
# 遍历一遍数组
for i, row in enumerate(board):
for j, num in enumerate(row):
if num != '.':
# 计算属于第几个3x3 的宫
k = (i//3)*3 + j//3
# 将三个列表拼接起来，判断是否存在该数字，存在返回False，不存在则添加该数字
if num in cell_list[i] + col_list[j] + row_list[k]:
return False
cell_list[i].append(num)
col_list[j].append(num)
row_list[k].append(num)
return True
11. 旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
# 旋转图像
# 给定一个 n × n 的二维矩阵表示一个图像。
# 将图像顺时针旋转 90 度。
class Solution:
def rotate(self, matrix) -> None:
length = len(matrix)
# 第一个for循环，对矩阵进行转置
for i in range(length):
for j in range(i + 1, length):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# 第二个循环，对转置后的矩阵中的每个列表进行反转
for i in range(length):
matrix[i] = matrix[i][::-1]
网友评论