写在前面：本笔记是leetcode-master/数组理论基础.md at master · youngyangyang04/leetcode-master (github.com)该github项目的跟学笔记。看我的没什么意义直接看原版吧。（当然如果有偶然看到的朋友想一起也可以）
这个系列暂时放到数据结构与算法专题分类中，严格按照随想录顺序跟学。过程中如果有发现其他很好的课程或者题单也许也会加进来:)
除此之外还在学李宏毅的机器学习和唐宇迪的nlp，另外还有两个项目，所以进度并不快。
以上。
数组
基础知识
1.数组存储方式
| 内存地址 | 100 | 101 | 102 | 103 | 104 | 105 |
|---|---|---|---|---|---|---|
| 字符数组 | H | O | T | A | R | U |
| 数组下标 | 0 | 1 | 2 | 3 | 4 | 5 |
-
数组下标从零开始
-
数组内存空间地址连续
2.数组的增加和删除
-
数组的内存地址是连续的，在增加和删除时需要移动其他元素的地址
-
数组的元素不能删，只能覆盖
3.二维数组
-
索引顺序：行、列
-
在内存的空间地址： 不同编程语言的内存管理不同。C++中二维数组是连续分布的
第一题 二分查找
leetcode-master/0704.二分查找.md at master · youngyangyang04/leetcode-master (github.com)
关键词：顺序数组、不重复、返回下标
思路：left right更改窗口位置二分，动态计算mid，更新left和right
py代码
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)-1
while left<=right:
mid = int((right+left)/2)
if nums[mid]==target:
return mid
if nums[mid] > target:
right = mid-1
if nums[mid] < target:
left = mid+1
return -1
二分查找
第二题 移除元素
leetcode-master/0027.移除元素.md at master · youngyangyang04/leetcode-master (github.com)
关键词：原地算法
思路：动态修改循环窗口，遇到val冒泡（暴力）
py代码（时间复杂度O(n^2) 空间复杂度O(1)）
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
length = len(nums) #养成好习惯提前计算
count = 0
i=0
while i < len(nums)-count: #动态减少需要循环的数组位置
if nums[i]==val:
count+=1
for j in range(i,length-1): #类似冒泡
temp = nums[j]
nums[j] = nums[j+1]
nums[j+1] = temp
if nums[i]==val and length-i+2!=count : #是防止有连续的val
i-=1
i+=1
return length-count #虽然不知道为什么这题可以这么返回但是总之就返回这个
移除元素-暴力
虽说力扣只要求了空间o1吧，还是学习一下好的解法
思路：双指针（快慢指针）通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。 随想录给的方法解释：
定义快慢指针
-
快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
-
慢指针：指向更新 新数组下标的位置
这是我看了之后写的：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
fast = 0
slow = 0
length = len(nums)
while fast < length:
nums[fast],nums[slow]=nums[slow],nums[fast]
if nums[slow]==val:
slow-=1
slow+=1
fast+=1
return slow
移除元素-快慢指针
但是好像速度并没有多大区别 但是想法很好 虽然多半记不住 但是努力记一下
第三题 有序数组的平方
leetcode-master/0977.有序数组的平方.md at master · youngyangyang04/leetcode-master (github.com)
我是个笨蛋。
python代码
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
length = len(nums)
left = 0 #原数组左指针
right = length-1 #原数组右指针
ans = [0]*length #答案数组
sub = right #答案数组下标
while sub!=-1:
# 徐丽莹自信一点 确实是一个在左一个在右的
# 只不过不能原地改而已 呵呵呵
if abs(nums[right])>=abs(nums[left]):
ans[sub] = nums[right]*nums[right]
right-=1
sub-=1
if abs(nums[right])<abs(nums[left]):
ans[sub]=nums[left]*nums[left]
left+=1
sub-=1
return ans
有序数组平方
第四题 长度最小的子数组
leetcode-master/0209.长度最小的子数组.md at master · youngyangyang04/leetcode-master (github.com)
思路：还是滑动窗口
注意读题：是大于等于不是等于 是最短不是最长
一直想错的一个点：对于right已经顶到头了如果temp<target怎么移 我都不知道我在想些什么……那就break啊（扶额
py代码
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
# 是不是还是双指针啊
length = len(nums)
left = 0
right = left
minans = 100001 #这里数字一开始设置小了
temp = 0
while left<length and left<=right:
if left==0 and right==length:
return 0
if temp<target:
if right<length:
temp+=nums[right]
right+=1
else:
break #服了 你竟然二十分钟都没发现 哎
if temp>=target:
print(temp)
print(left,right-1)
minans = right-left if (right-left)<minans else minans
temp-=nums[left]
left+=1
return minans
长度最小子数组
第五题 螺旋矩阵Ⅱ
leetcode-master/0059.螺旋矩阵II.md at master · youngyangyang04/leetcode-master (github.com)
经典模拟 没啥算法
直觉上就直接写，按照右下左上的顺序去循环（我感觉我的比随想录的代码要直观一点 没有求中心点和更新起始点） py代码
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
nums = [[0]*n for i in range(n)] #第一次用py写二维数组 大概初始化就这样吧
count=0
x=0 #数组横坐标
y=0 #数组纵坐标
i=1
if n==1:
nums = [[1]]
return nums #emm 犯懒单独判断
while i<n*n: #很直观
nums[x][y]=i
while y+1<n and nums[x][y+1]==0: #右
y+=1
i+=1
nums[x][y]=i
while x+1<n and nums[x+1][y]==0: #下
x+=1
i+=1
nums[x][y]=i
while y-1>=0 and nums[x][y-1]==0: #左
y-=1
i+=1
nums[x][y]=i
while x-1>=0 and nums[x-1][y]==0: #上
x-=1
i+=1
nums[x][y]=i
return nums
螺旋矩阵Ⅱ
一些总结
leetcode-master/数组总结篇.md at master · youngyangyang04/leetcode-master (github.com)
数组经典题目和方法
二分法
-
暴力解法时间复杂度：O(n)
-
二分法时间复杂度：O(logn)
关键点：循环条件、left和right的变化
双指针&快慢指针
快慢指针可以在一个for循环下完成两个for循环的工作。 例题是数组元素的移除，理解起来并不容易。
数组中元素不能移除的原因：
-
数组在内存中是连续的地址空间，不能释放单一元素，如果要释放，就是全释放（程序运行结束，回收内存栈空间）。
-
C++中vector和array的区别一定要弄清楚，vector的底层实现是array，封装后使用更友好。
滑动窗口
滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。
标签：right,nums,int,随想录,master,数组,菜鸡,跟学,left From： https://www.cnblogs.com/hotaru-klxx/p/16854244.html