算法刷题总结 (一) 数组

算法总结1 数组

一、算法刷题数组数组
- 1.1、总结二分查找
- - 1.1.1、算法刷题数组原题
  - 1.1.2、总结方法
  - 1.1.3、算法刷题数组相似题型
- 1.2、总结双指针法
- - 1.2.1、算法刷题数组原题
  - 1.2.2、总结方法
  - 1.2.3、算法刷题数组相似题型
- 1.3、总结滑动窗口
- - 1.3.1、算法刷题数组原题
  - 1.3.2、总结方法
  - 1.3.3、算法刷题数组相似题型
- 1.4、总结过程模拟
- - 1.4.1、算法刷题数组原题
  - 1.4.2、方法
  - 1.4.3、相似题型
参考

一、数组

本文章为数组的基础算法部分，相似题型汇总: 数组经典题型

1.1、二分查找

1.1.1、原题

力扣题目链接

二分查找的条件：

有序
无重复元素

1.1.2、方法

根据区间的定义做边界处理。

想象有一个区间，该区间会随着二分而缩小范围，同时改变其左右闭边界([left, right])。不断二分该区间，比较mid与target的大小而选择二分区间其一。

def search(li, target):	# 定义左右闭区间	left, right = 0, len(li)-1	# 二分迭代，比较中值和target，不断调整边界缩小范围。	# 当left>target左右交错时遍历完成退出循环。	while left<=right:		# 中值		mid = (left+right)//2		# 有下面这种写法，这里 m>>n 为 m//(2**n), 即 mid = left + (right-left)//2		# mid = left + (right-left)>>1		# 若中值大于目标值		if li[mid]>target:			# 将查找区间右半部分去掉，即right替换成中值左边一位			right = mid-1		elif li[mid]right 退出循环，说明列表整个遍历后找不到目标值，则返回 -1	return -1

注意这里每次划分都不包括mid的值。
在这里插入图片描述

1.1.3、相似题型

35.搜索插入位置
34.在排序数组中查找元素的第一个和最后一个位置
69.x的平方根
367.有效的完全平方数

1.2、双指针法

1.2.1、原题

力扣题目链接
元素的删除：
注意这里为原地操作，也就是原址操作。也就是在原列表的上进行的所有操作。
这里就要注意某些函数方法会产生新的地址，一般无返回值的函数为原址操作，有返回值的为新址操作：
比如：
list.remove()无返回值，原址操作，改变原list，而不会产生新的list。
sorted(list)有返回值，新址操作，不改变原list，会产生新的list。

1.2.2、方法

1.一般解法，遍历一次列表：
思路：使用nums[:]创建一个新的list，遍历这个新的list，每次遇到val就删除原list等于val的值，这样就不会造成删除过程中index位移而错过连续的重复元素。

class Solution:    def removeElement(self, nums: List[int], val: int) ->int:        for i in nums[:]:            if i == val:                nums.remove(i)        return len(nums)

2.高级解法，快慢指针：
设定两个指针，快指针每次都往前移动一个索引，慢指针只有当快指针的值不等于val时，将它的值赋予给慢指针此刻的索引，再往后移动一格

class Solution:    def removeElement(self, nums: List[int], val: int) ->int:        fastIndex = 0        slowIndex = 0        while fastIndex

`1.2.3、相似题型`

26.删除排序数组中的重复项 283.移动零 844.比较含退格的字符串 977.有序数组的平方



1.3、滑动窗口
1.3.1、原题
力扣题目链接

1.3.2、方法
1.一般解法，暴力破解：
思路：因为是该子序列是连续的，所以定义起始点和结束点，以区间内的和和长度进行比较。因为是暴力求解，会遍历list，所以该解法遇到较长的list会超时。
class Solution:    def minSubArrayLen(self, target: int, nums: List[int]) ->int:    	# 先定义一个无限大长度，后续更新变小，因为要找到最小连续子序列        lengt_h = float(inf)        # 先定义起始位置        for i in range(len(nums)):        	# 每个起始位置定义一个和，保存起始和结尾区间的值，用于比较target            su_m = 0            # 结尾的位置            for j in range(i, len(nums)):            	# 区间求和                su_m = sum(nums[i:j+1])                # 满足和大于等于target的条件就比较长度                # 这里主要比较的是不同起始位置产生的区间长度                # 因为同一起始位置，往后遍历长度只会越长，第一次满足条件则直接break                # 后续的满足条件的区间必然会越来越大                if su_m>=target:                    length = j-i+1                    # 比较原长度与目前长度的大小，小则替换，大则保留原始                    lengt_h = lengt_h if lengt_h
2.滑动窗口：
暴力破解定义了两个循环，分别代表了起始和结尾位置。
所以滑动窗口更加简化，只使用一个循环，动态维持一个起点到结尾的动态窗口，而这个循环表示结尾索引。
class Solution:    def minSubArrayLen(self, target: int, nums: List[int]) ->int:        lengt_h = float(inf)        su_m = 0        # 滑动窗口的起始索引        ind = 0        # 滑动窗口的结尾        for i in range(len(nums)):        	# 结尾索引，从0开始不断遍历，不断求和        	# 后续只改变起始位置，来动态改变区间长度和求和的值            su_m+=nums[i]            # 小于target时，起始点不变，不断扩展结尾点，增加和的值和长度            # 一旦大于等于target，试图缩小窗口，窗口缩小，则要减去相应索引位置的值            while su_m>=target:            	# 保留最小的长度到lengt_h                lengt_h = min(lengt_h, i-ind+1)                # 减去起始位置的索引的值，去缩小长度                su_m -= nums[ind]                # 起始索引后移                ind += 1        # 找不到即长度为无限大，则输出0        return 0 if lengt_h == float(inf) else lengt_h
滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。
1.3.3、相似题型
904.水果成篮
76.最小覆盖子串


1.4、过程模拟
1.4.1、原题
力扣题目链接

1.4.2、方法
找规律，每一圈为一层，不断向内缩减
class Solution:    def generateMatrix(self, n: int) ->List[List[int]]:        nums = [[0]*n for _ in range(n)]        # 起始点        startx, starty = 0, 0        # loop循环次数，循环几圈        # mid中间点的坐标，一般为奇数才使用到，因为中间的点不算一个圈        loop, mid = n//2, n//2        # 计数点 1-n        count = 1                # 每循环一层，偏移量加一        for offset in range(1, loop+1):            # 从左至右，左闭右开            for i in range(starty, n-offset):                nums[startx][i] = count                count += 1            # 从上至下，上闭下开            for i in range(startx, n-offset):                nums[i][n-offset] = count                count += 1            # 从右至左，右闭左开            for i in range(n-offset, startx,-1):                nums[n-offset][i] = count                count += 1            # 从下至上，下闭上开            for i in range(n-offset, starty, -1):                nums[i][starty] = count                count += 1            startx += 1            starty += 1                    if n%2!=0:            nums[mid][mid] = count        return nums
1.4.3、相似题型
54.螺旋矩阵
剑指Offer 29.顺时针打印矩阵


参考
数组经典题型