算法(3):数组
一鼓作气,再而衰,三而竭,第三篇走起!
- 目录:
算法:附录
算法(1):递归
算法(2):链表
算法(3):数组
算法(4):字符串
算法(5):二叉树
算法(6):二叉查找树
算法(7):队列和堆栈(附赠BFS和DFS)
算法(8):动态规划
算法(9):哈希表
算法(10):排序
算法(11):回溯法
算法(12):位操作
数组(Array)
数组是大家再熟悉不过的东西了,但是这里还是简单说一下,数组是连续存放一系列元素的数据结构,我们可以方便的通过索引访问数组当中的任何一个元素。通常,数组在定义时是固定大小的,但是也有一种动态数组,它在初始化时不需要定义数组大小,也就意味着可以无限装数据,我们称之为动态数组,如C++当中的Vector(曾经是我最喜欢的一个数据结构,当然,在我遇到python当中的List之前)和Java当中的ArrayList 。
安利一波问题4,大家一定要看一看。
问题1:找到一个一维数组的“中枢”元素的索引。如果有很多中枢元素,则只需返回最左侧的即可。中枢在此处意味着该索引左侧元素和等于该索引右侧元素和。
输入: [1, 2, 8, 4, 5, 6]
输出: 3(1+2+8 = 5+6)
代码,那是异常的简单啊。小编不禁想起了有一次面试,面试官让我写一个找数组中最大最小值的算法,啊,那时的时光是多么美好!如下代码的时间复杂度,空间复杂度。
def pivotIndex(nums) -> int:
ts, cs = sum(nums), 0
for idx, num in enumerate(nums):
ls, rs = cs, ts - cs - num
if ls == rs:
return idx
cs += num
return -1
if __name__ == '__main__':
ans = pivotIndex([1, 2, 8, 4, 5, 6])
print(ans)
问题2:加1操作。将输入数组当成一个整数,然后执行加1操作
例子:
输入: [1,2,3] 输出: [1,2,4]
输入: [9,9,9] 输出: [1,0,0,0]
我的方法是直接在数组里面执行操作,当然你也可以换种方法,如把数组里元素按位读出来变成int,然后加一,然后在按位存放到数组中。
def plusOne(digits: list) -> list:
digits = [0] + digits
for i in range(len(digits) - 1, -1, -1):
if digits[i] == 9:
digits[i] = 0
else:
digits[i] += 1
break
return (digits, digits[1:])[0 if digits[0] != 0 else 1]
if __name__ == '__main__':
ans = plusOne([1, 2, 8, 4, 5, 6])
print(ans)
问题3:对角线遍历二维数组(Diagonal Traverse)。
一维数组一般都很简单,但是到了二维数组,难度就会上升一个台阶,毕竟,问题的花样变多了嘛~
输入:[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
输出: [1,2,4,7,5,3,6,8,9]
如果看不懂的话,可以配上下面这张图看,保证一眼就明白~
代码具体思路分为两步:
step1:根据对角线将矩阵分组(可以发现,同一对角线的矩阵row和col坐标相加为定值),如上图,可以分为5组,得到[1] , [2,4],[3,5,7],[6,8],[9]。
step2:按照(row + col)的大小顺序将数据依次添加到结果列表当中。根据代码定义,在(row + col )为偶数时,需要翻转一下该组元素。即[3,5,7](此时row + col = 2)需要变为[7,5,3]再添加到结果中。
import collections
def findDiagonalOrder(matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
result = []
dd = collections.defaultdict(list)
if not matrix: return result
# Step 1: Numbers are grouped by the diagonals.
# Numbers in same diagonal have same value of row+col
for i in range(0, len(matrix)):
for j in range(0, len(matrix[0])):
dd[i + j].append(matrix[i][j]) # starting indices from 1, hence i+j+1.
# Step 2: Place diagonals in the result list.
# But remember to reverse numbers in odd diagonals.
for k in sorted(dd.keys()):
if k % 2 == 0: dd[k].reverse()
result += dd[k]
return result
if __name__ == '__main__':
arr = [[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]
ans = findDiagonalOrder(arr)
print(ans)
问题4:旋转矩阵(Spiral Matrix),即返回一个矩阵顺时针旋转的结果。
输入:
[ [ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ] ]
输出:[1,2,3,6,9,8,7,4,5]
下面这个答案是我在网上找的,看到这个代码之后的好久时间里,我的嘴巴只能发出“wo cao”这两个音。。。看到这段代码,我仿佛恋爱了。
def spiralOrder(matrix: list) -> list:
return matrix and [*matrix.pop(0)] + spiralOrder([*zip(*matrix)][::-1])
if __name__ == '__main__':
arr = [[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]
ans = spiralOrder(arr)
print(ans)
问题5:数组求和。给定一个升序排列的数组,找出两个数,其和等于输入‘target’,结果返回这两个数的索引。
输入: numbers = [2,7,11,15], target = 9
输出: [1,2]
我们如果使用暴力法的话,结果有种,时间复杂度为。那么大家还记不记得 有一招从天而降的掌法... 上一章讲解的双指针技术呢?这里便用到了!两个指针分别从左和右开始向中间走,两个数的和大了,右指针左移,和偏小,左指针右移......
# 四个问题不吉利,小编拍胸脯保证,马上(百年之内)把第五个问题补起来!
def twoSum(numbers: list, target: int) -> list:
i, j = 0, len(numbers) - 1
while i < j:
if numbers[i] + numbers[j] == target:
return [i, j]
elif numbers[i] + numbers[j] > target:
j -= 1
else:
i += 1
return []
if __name__ == '__main__':
numbers = [2, 7, 11, 15]
target = 9
ans = twoSum(numbers,target)
print(ans)
问题6:移除特定值(写五道已经达到我的标准了,奈何又看到一个较为经典的案例,那就......再来个双指针教学吧~),将数组当中等于’target'的值移除掉,空间复杂度限定为,最后结果返回新数组长度。
例子:
输入:[1,2,7,4,4,5],target = 4
输出:4 (新数组为[1,2,7,5],所以长度为4)
快指针遍历数组,慢指针则作为新数组的尾部。只有当快指针所指的值和‘target’不同时,才会执行赋值以及p+=1
操作,相同时直接跳过该数。
def removeElement(numbers: list, target: int) -> int:
p = 0
for i in range(len(numbers)):
if numbers[i] != target:
numbers[p] = numbers[i]
p +=1
return p
if __name__ == '__main__':
numbers = [1,7,3,4,4,5]
target = 4
ans = removeElement(numbers,target)
print(ans)
print(numbers[:ans])
问题7:满足要求的最小子数组(Minimum Size Subarray Sum)。不好意思我忍不住又添了一道......该题给定n只包含正整数的数组,以及一个整数s,要求是找到一个最小长度的连续子数组,该子数组的元素和≥s。 如果不存在,则返回0。
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2(子数组 [4,3] 是满足题目约束的最小数组)
运行下面程序会输出每步变量信息,大家可以自己读读试试,看能否理解~如果不理解可以留言探讨,现在已经晚上11点了,小编扛不住,这道题就不写分析了......
def minSubArrayLen( s: int, nums: list) -> int:
total = left = 0
result = len(nums) + 1
for right, num in enumerate(nums):
total += num
while total >= s:
result = min(result, right - left + 1)
total -= nums[left]
left += 1
print('total:',total,'result:',result,'left:',left,'right:',right)
return result if result <= len(nums) else 0
if __name__ == '__main__':
numbers = [2,3,1,2,4,3]
target = 7
ans = minSubArrayLen(target,numbers)
print(ans)