数组基本操作-使用python实现
class ArrayTest:
def test(self):
# create an array
a = []
# add an element
# time complexity: O(1)
a.append(1)
a.append(2)
a.append(3)
print(a)
# insert an element
# time complexity: O(n)
a.insert(2, 99)
print(a)
# access element
# time complexity: O(1)
temp = a[2]
print(temp)
# update element
# time complexity: O(1)
a[2] = 88
print(a)
# remove element
# time complexity: O(n)
a.remove(88)
print(a)
a.pop(1)
print(a)
a.pop()
print(a)
# get array size
a = [1,2,3]
size = len(a)
print(size)
# interate arrqy
# time complexity: O(n)
for i in a:
print(i)
for index,element in enumerate(a):
print("index at ", index, "is :", element)
for i in range(0, len(a)):
print("i:", i, 'element:', a[i])
# find an element
# time complexity: O(n)
index = a.index(2)
print(index)
# sort an array
# time complexity: O(nlogn)
# from small to big
a = [3, 1, 2]
a.sort()
print(a)
# from big to small
a.sort(reverse=True)
print(a)
if __name__ == "__main__":
test = ArrayTest()
test.test()
485. 最大连续 1 的个数
输入：[1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
- 方法1：遍历计数
# 方法1
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
result = 0
count = 0
for num in nums:
if num == 1:
count += 1
result = max(count, result)
else:
count = 0
return result
# 方法2
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
if nums is None or len(nums)==0:
return 0
count = 0
result = 0
for num in nums:
if num == 1:
count += 1
else:
result = max(result, count)
count = 0
return max(result,count)
- 方法3：动态规划
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
# 动态数组初始化
dp = [0]*len(nums)
dp[0] = nums[0]
# 动态数组变化
for i in range(1, len(nums)):
if nums[i] == 1:
# 表达式
dp[i] = dp[i-1] + 1
else:
dp[i] = 0
return max(dp)
238. 除自身以外数组的乘积
输入: [1,2,3,4]
输出: [24,12,8,6]
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
result = [1]*len(nums)
left = 1
right = 1
# 先对左侧的数相乘
for i in range(len(nums)):
result[i] *= left
left *= nums[i]
# 然后对右侧的数相乘
for j in range(len(nums)-1, -1, -1):
result[j] *= right
right *= nums[j]
return result
面试题 01.07. 旋转矩阵
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
# 先上下进行 行反转 然后进行 对角线元素反转
row = len(matrix)
col = len(matrix[0]) # 列元素
# 行反转 matrix[0][0], matrix[2][0] = matrix[2][0], matrix[0][0]
for i in range(row//2):
for j in range(col):
matrix[i][j], matrix[row-i-1][j] = matrix[row-i-1][j], matrix[i][j]
# 对角线元素反转
for i in range(row):
for j in range(i): # 注意：只需要反转单侧对角线
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
return matrix
面试题 01.08. 零矩阵
输入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
row = len(matrix)
col = len(matrix[0])
flag_row = False
flag_col = False
# 判断第一行是否存在 0，并进行标记
for i in range(row):
if matrix[i][0] == 0:
flag_col = True
break
# 判断第一列是否存在 0，并进行标记
for j in range(col):
if matrix[0][j] == 0:
flag_row = True
break
# 遍历除了第一行和第一列的元素，使用数组的第一行、第一列对应位置来存储 0 的标记。
for i in range(1, row):
for j in range(1, col):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0
# 遍历除了第一行和第一列的元素，对第一行、第一列对应位置标记为 0 的元素对应的所有行列元素置为 0
for i in range(1, row):
for j in range(1, col):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# 最后检查第一行和第一列
if flag_col:
for i in range(row):
matrix[i][0] = 0
if flag_row:
for j in range(col):
matrix[0][j] = 0
73. 矩阵置零
给定一个 m* x *n 的矩阵，如果一个元素为 **0 **，则将其所在行和列的所有元素都设为 0 。请使用 [原地]算法。
- 相比上一道题目的解题思路，比较简单，便于理解
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
row = len(matrix)
col = len(matrix[0])
# 1 通过遍历查找包括 0 的行和列的位置
locRow = set()
locCol = set()
for i in range(row):
for j in range(col):
if matrix[i][j] == 0:
locRow.add(i)
locCol.add(j)
# 2 将包括0的行和列所有元素置为0
for i in range(row):
for j in range(col):
if i in locRow or j in locCol:
matrix[i][j] = 0
283：移动零元素
输入：[1,2,0,0,3]
输出：[1,2,3,0,0] 保持原先的元素相对位置不变,不使用额外的空间
a = [1,2,0,0,3]
index = 0
for i in a:
if i != 0:
a[index] = i
index += 1
for j in range(index+1, len(a)):
a[j] = 0
print(a)
变位词
输入：'python', 'typhon'
输出：true
方法1：逐字检查
def anagramSolution(s1, s2):
pos1 = 0
stillOk = True
alist = list(s2) # 将s2转变为列表，方便标记
while pos1 < len(s1) and stillOk: # 循环遍历s1
pos2 = 0
found = False
while pos2 < len(s2) and not found: # 循环遍历s2
if s1[pos1] == alist[pos2]:
found = True
else:
pos2 += 1
if found:
alist[pos2] = None
else:
stillOk = False
pos1 += 1
return stillOk
s1 = 'abcde'
s2 = 'abde'
print(anagramSolution(s1, s2))
时间复杂度：两层循环O(n**2)
方法2：排序法
def compareStr(s1, s2):
list1 = list(s1)
list2 = list(s2)
list1.sort()
list2.sort()
pos = 0
match = True
while pos < len(s1) and match:
if list1[pos] == list2[pos]:
pos += 1
else:
match = False
return match
print(compareStr('abc', 'ac'))
时间复杂度：主要是排序算法O(nlogn)
方法3：计数比较
# 总共有26个小写字母
def compareStr(s1, s2):
c1 = [0]*26
c2 = [0]*26
for i in range(len(s1)):
pos = ord(s1[i]) - ord('a') # ASCII
c1[pos] += 1
for j in range(len(s2)):
pos = ord(s1[j]) - ord('a')
c2[pos] += 1
# 计数结果比较
k = 0
match = True
while k < 26 and match:
if c1[k] == c2[k]:
k += 1
else:
match = False
return match
print(compareStr('abc', 'acb'))
时间复杂度：2n+26
网友评论