数据结构与算法-数组

学习计划：3个月内算法小成，完成leetcode hot100

当前进度：之前学了一部分，中断了，然后忘了，而且没有系统学习

学习规划：跟着代码随想录学习，并在此做笔记

刷题语言：Python

时间：2024/09/18-2024/09/20

数据结构与算法内容框架

数据结构

1. 数组
2. 栈和队列（单调栈）
3. 链表
4. 哈希表
5. 树（二叉树）
6. 图（图论）

算法

1. 排序算法
2. 查找算法
3. 回溯算法
4. 贪心算法
5. 动态规划

一、数组

学习链接：代码随想录

1.数组基础理论

数组是存放在连续内存空间上相同数据类型的集合。

2.二分查找

力扣题目链接

给定一个 n 个元素有序的（升序）无重复整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 :

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为4

思路：

题目规定有序数组，无重复元素，此时可以使用二分查找：

双指针法（左右指针法），创建2个指针：left指向数组第一个元素，right指向数组最后一个元素

当left<=right的时候，比较target 与中间的元素大小，由于是升序排序，比较后可以直接对半取，直至target=中间的元素，或者left>right，表示不存在目标值

class Solution:def search(self, nums: List[int], target: int) -> int:print(nums)left,right = 0,len(nums)-1while left<=right:mid = left + (right-left)//2if target>nums[mid]:left = mid+1elif target<nums[mid]:right=mid-1else:return midreturn -1时间复杂度：O（logn） 每次遍历数量减半
空间复杂度：1

其他推荐题目：

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

3.移除元素

力扣题目链接

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

思路：双指针法(快慢指针法)， 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

使用快指针对数组进行遍历，如果遍历的元素不等于 val ，则通过慢指针覆盖保存在原数组左侧。

class Solution:def removeElement(self, nums: List[int], val: int) -> int:fast = 0slow = 0while fast<len(nums):if nums[fast]!=val:nums[slow]=nums[fast]slow+=1fast+=1return slow时间复杂度：O（n）
空间复杂度：O（1）

其他推荐题目：

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

4.有序数组的平方

力扣题目链接

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

• 输入：nums = [-4,-1,0,3,10]
• 输出：[0,1,9,16,100]
• 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

思路：

暴力排序

对数组每个元素进行平方后，对数组进行排序

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:l = [i * i for i in nums]l.sort()return l时间复杂度O（nlogn）

双指针法

数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

双指针法（左右指针法），并定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:left = 0right = len(nums)-1i = len(nums)-1res = [0]*len(nums)while left<=right:if nums[left]**2<nums[right]**2:res[i]=nums[right]**2right-=1else:res[i]=nums[left]**2left+=1i-=1return res时间复杂度O（n）

5.长度最小的子数组

力扣题目链接

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

• 输入：s = 7, nums = [2,3,1,2,4,3]
• 输出：2
• 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

提示：

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

思路：滑动窗口

滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

思路就是 定义nums内部的一个窗口，有一个右边界，有一个左边界。右边界是个“探子”，左边界像是个“保洁员”。
右边界只管往前走，走一步回头看看窗口里这几个数加起来跟 target做比较。
如果没达到target 就继续往前走；
如果≥target，那么就要尝试从左侧缩减窗口的宽度，手段是左边界往右移动一个位置。然后往前看看窗口里这几个数加起来跟 target做比较：
如果还是≥target，那么继续缩减窗口宽度
如果已经<target，那么左边界停止，到此为止。说明这个位置的前一个就是“在当前右边界下最小的窗口”对应的左边界位置

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:left = 0right = 0min_len = 9999sum = 0while right<len(nums):sum+=nums[right]while sum>=target:sum-=nums[left]min_len=min(min_len,right-left+1)left+=1right+=1min_len=0 if min_len==9999 else min_lenreturn min_len时间复杂度：O（n）
空间复杂度：O（1）不要以为for里放一个while就以为是O(n^2)啊， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)

其他推荐题目：

• ​​​​​​​904.水果成篮
• 76.最小覆盖子串

6.螺旋矩阵

力扣题目链接

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

思路：

构建四个方向：

1. 向右（0，1），表示列坐标+1
2. 向下（1，0），表示横坐标+1
3. 向左（0，-1），表示列坐标-1
4. 向上（-1，0），表示横坐标-1

定义循环从0-n*n,每次循环都填充对应的数到指定位置，重点是怎么找的对应的位置。

设置初始起点坐标为（row=0,col=0），此时填充数字1，然后根据判断方向，并使用方向坐标修改当前坐标

class Solution:def generateMatrix(self, n: int) -> List[List[int]]:matrix = [[0]*n for _ in range(n)]row,col= 0 ,0dir = [(0,1),(1,0),(0,-1),(-1,0)]   #分别代表右，下，左，上 四个方向idx=0for i in range(n*n): #循环结束时候，矩阵刚好填充完毕matrix [row][col]=i+1dx,dy = dir[idx]r = row + dxc = col + dyif r>=n or r<0 or c>=n or c<0 or matrix [r][c]>0:#判断什么时候调整方向idx = (idx+1)%4dx,dy = dir[idx]row,col = row+dx,col+dyreturn matrix 
时间复杂度：O（n^2）
空间复杂度：O（1）

7.区间和（ACM）

题目链接

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。

输出描述

输出每个指定区间内元素的总和。

import sys
input = sys.stdin.read  #获取输入,字符串形式def main():data = input().split()# print(data)n = int(data[0])# print(n)list=[]for i in range(n):list.append(int(data[i+1]))# print(list)p=[0]*npresum=0for i in range(n):presum+=list[i]p[i]=presum# print(p)res_list=[]index = n+1while index<=len(data)-2:begin = int(data[index])end = int(data[index+1])# print(begin,end)if begin==0:res=p[end]else:res=p[end]-p[begin-1]# print(res)res_list.append(res)index+=2for result in res_list:print(result)if __name__ =="__main__":main()时间复杂度：O（n）
空间复杂度：O（1）

总结

1.ACM 模式常用代码

import sys
input = sys.stdin.read  #获取输入def main():data = input().split()  #获取输入的内容，字符串格式print(data)n = int(data[0])   #把字符串形式转int类型#输出,直接打印输出即可for str in data:print(int(str))if __name__ =="__main__":main()

2.数组常见解题思路

1. 双指针法（左右指针法）
2. 双指针法(快慢指针法)
3. 原地运算or定义一个新数组result保存结果
4. 滑动窗口