一、数组题目（简单）
26. 删除排序数组中的重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
解题思路：
运用双指针，快指针进行遍历，慢指针与快指针对比，遇到不一样的，则慢指针加1，快指针的值赋值给慢指针更新后的位置，代码如下：
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
for v in nums:
if nums[i] != v:
i += 1
nums[i] = v
# and中含0，则返回0；都非0，则返回后一个值
return len(nums) and i+1
注意点：
- 注意考虑数组为空的情况
- 原地处理，数组的大小不变，只取前几位不重复的数据，所以需要进行 and 操作。
122. 买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
解题思路：
只需要关注后一天比前一天多就行了。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
profit = 0
for i in range(len(prices)-1):
if prices[i] < prices[i+1]:
profit += (prices[i+1]-prices[i])
i +=1
return profit
注意点：
- 注意考虑数组为空的情况。
旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
- 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
- 要求使用空间复杂度为 O(1) 的 原地 算法。
解题思路：
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
## 1. 时间复杂度较高为O(Kn)，时间超时
# size = len(nums)
# for i in range(k):
# temp = nums[size-1]
# for j in range(size-1):
# nums[size-1-j] = nums[size-2-j]
# nums[0] = temp
### 2. 重新组合
# k=k%len(nums)#保证循环次数在0-len(nums)之间
# nums[:]=nums[len(nums)-k:]+nums[:len(nums)-k]#切割成两块重新组合
### 3. 使用 reversed() 倒序处理
length = len(nums)
k = k%length
nums.reverse()
nums[0:k] = reversed(nums[0:k])
nums[k:] = reversed(nums[k:])
217. 存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
解题思路：
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
## 1. 集合法
# return len((set(nums))) != len(nums)
## 2.排序法
# nums.sort()
# 这里的遍历没有最后一位，因此不需要担心 i+1 会越位
# for i in range(len(nums)-1):
# if nums[i] == nums[i+1]:
# return True
# return False
## 3.hash表法
dic = {}
for num in nums:
if dic.get(num):
return True
dic[num] = 1
return False
136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
解题思路：
class Solution:
def singleNumber(self, nums: List[int]) -> int:
## 1. 排序法
# nums.sort()
# for i in range(0, len(nums)-1, 2):
# if nums[i] != nums[i+1]:
# return nums[i]
# return nums[-1]
## 2. 位运算
# 异或运算，只要两个相同的数进行异或运算，结果为0；
# 结合律（即(a^b)^c == a^(b^c)）
# 交换律 a ^ b = b ^ a
# 对于任何数x，都有x^x=0，x^0=x
# 自反性 A XOR B XOR B = A xor 0 = A
# 那么把这个数组所有数做异或运算，通过交换律和结合律，相同的数抵消，生下来的就是那个不同的数
# 比如：数组为[a, b, c, a, b]
# a^b^c^a^b = a^a^b^b^c = (a^a)^(b^b)^c = 0 ^ 0 ^ c = (0 ^ 0) ^ c = 0 ^ c = c
# sum = 0
# for i in nums:
# sum = sum^i
# return sum
## 3.list的弹出与删除
while len(nums) != 1:
lastCha = nums.pop()
if lastCha in nums:
nums.remove(lastCha)
else:
return lastCha
return nums[0]
350. 两个数组的交集 II
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：
- 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
- 我们可以不考虑输出结果的顺序。
进阶:
- 如果给定的数组已经排好序呢？你将如何优化你的算法？
- 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
- 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
解题思路：
from collections import *
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
# 普通解法1
# result = []
# for i in nums1:
# if i in nums2:
# result.append(i)
# # remove 删除的是第一个与value值相等的数
# nums2.remove(i)
# return result
# 普通解法2
# Counter 是用来进行计数的工具
# return list((Counter(nums1) & Counter(nums2)).elements())
# 进阶解法1：
nums1.sort()
nums2.sort()
i=j=0
result = []
while i<len(nums1) and j<len(nums2):
if nums1[i]==nums2[j]:
result.append(nums1[i])
i += 1
j += 1
elif nums1[i] < nums2[j]:
i += 1
else:
j += 1
return result
注意点：
- Counter 的使用
66. 加一
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
解题思路：
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
# 解法1：先把数组转换成数字+1，然后在转换成数组
# num = 0
# i = 1
# for d in digits[::-1]:
# temp = d * i
# i = i * 10
# num += temp
# num += 1
# return map(int,str(num))
# 解法2：思路一样，只是数组转换成数字的过程使用字符串
return map(int, str(int(''.join('%s' % i for i in digits))+1))
注意点：
- 主要是数组转换成数字，使用字符串更快。
- map 的使用更快。
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
解题思路：
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 双指针法,遇到0就与后面的快指针换
i = 0
for index, num in enumerate(nums):
if num == 0:
continue
if nums[i] == 0:
nums[i], nums[index] = nums[index], nums[i]
i += 1
# 遍历，遇到0删除，再在末尾补0
# for i in nums[:]:
# if i==0:
# nums.append(0)
# nums.remove(0)
注意点：
- 数组内部的互换位置，不需要用temp做中间变量。
1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题思路：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 解法1：双重遍历
# for i, inum in enumerate(nums):
# for j, jnum in enumerate(nums[i+1:]):
# if (inum + jnum) == target:
# return [i,i+j+1]
# 解法2：hash 解法
hashmap={}
for ind,num in enumerate(nums):
hashmap[num] = ind
for i,num in enumerate(nums):
j = hashmap.get(target - num)
if j is not None and i!=j:
return [i,j]
注意点：
- dict 的使用。
36. 有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
解题思路：
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# 思路三： 思路二的另一种实现方式。代码更为简洁（借鉴）
Cell = [[] for i in range(9)] # 没有必要用dict,我们只某个数字关心有没有出现过
Col = [[] for i in range(9)]
Row = [[] for i in range(9)]
for i,row in enumerate(board): # 将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中
for j,num in enumerate(row):
if num != '.':
k = (i//3)*3 + j//3 # 利用地板除，向下取余。巧妙地将矩阵划分为九块
if num in Row[i] + Col[j] + Cell[k]: # list的骚操作,将三个list顺序的拼接
return False
Row[i].append(num)
Col[j].append(num)
Cell[k].append(num)
return True
注意点：
- 二维数组的表示。
- 字典的使用可有效的检查重复。
48. 旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
解题思路：
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
'''矩阵转置'''
for x in range(n):
for y in range(x):
matrix[x][y], matrix[y][x] = matrix[y][x], matrix[x][y]
'''转置后列变换'''
# for i in range(len(matrix)):
# for j in range(len(matrix[i])//2):
# matrix[i][j],matrix[i][len(matrix)-1-j] = matrix[i][len(matrix)-1-j], matrix[i][j]
for i in range(n):
matrix[i] = matrix[i][::-1]
注意点：
- 二维数组的旋转可以用转置和行列变换解决。
二、总结
使用方法总结：
- 双指针法，主要针对删除数组中的重复项。
- reversed() 方法，主要用于旋转数组，还有对于数组的重新组合。
- hash 方法，是否存在重复项。
- 数组转数字，数字转数组，使用字符串更快。
注意点总结：
- 考虑数组为空的情况。
- Counter 的使用。
- map 的使用，数组转数字和数字转数组，用字符串更快。
- 数组内部互换位置，不需要 temp。
网友评论