leetcode 数据结构探索数组和字符串

1、集合：由一个或多个确定的元素所构成的整体。集合里的元素类型不一定相同，集合里的元素没有顺序。

2、数组：数组会用一些名为 索引 的数字来标识每项数据在数组中的位置。数组中的元素在内存中是连续存储的，且每个元素占用相同大小的内存。

对于数组，计算机会在内存中申请一段连续的空间，并且会记下索引为 0 处的内存地址。

3、数组的操作：（1）读取元素：通过数组的索引访问数组中的元素。索引其实就是内存地址，值得一提的是，计算机可以跳跃到任意的内存地址上，

这就意味着只要计算出数组中元素的内存地址，则可以一步访问到数组中的元素，时间复杂度为

（3）：合并区间

def merge(intervals):
    intervals.sort(key=lambda x: x[0])

    merge =[]
    for interval in intervals:
        if not merge or merge[-1][1]<interval[0]:
            merge.append(interval)
        else:
            merge[-1][1]=max(merge[-1][1],interval[1])
    return merge


"""
intervals=[[1,4],[4,5],[6,8]]
merge=[]

for 循环：
step 1: merge=[[1,4]]

step 2: merge[-1][1]=interval[0]
        merge[-1][1]=max(merge[-1][1],interval[1])=5
        merge=[[1,5]]

step3:  merge[-1][1]=5<interval[0]=6
        merge = [[1,5],[6,8]]
"""

4、二维数组：二维数组是一种结构较为特殊的数组，只是将数组中的每个元素变成了一维数组。二维数组的本质上仍然是一个一维数组，内部的一维数组仍然从索引 0 开始，我们可以将它看作一个矩阵，并处理矩阵的相关问题。

(4):翻转矩阵

def rotate(matrix):
    n = len(matrix)
    #新建一个N*N的辅助矩阵
    new_matrix= = [[0]*n for _ in range(n)]
    #行row
    for i in range(n):
        #列col
        for j in range(n):
            #矩阵中第i行的第j个元素，在旋转后，它出现在倒数第i列的第j个位置
            new_matrix[j][n-i-1]=matrix[i][j]
    #浅拷贝
    matrix[:] = new_matrix

(5)矩阵清0：若M × N矩阵中某个元素为0，则将其所在的行与列清零。

x = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

row_length = len(x)
col_length = len(x[0])

#存储需要清0行与列
row = [ ]
col = [ ]

#row
for i in range(row_length):
    #col
    for j in range(col_length):
        if x[i][j]==0:
            row.append(i)
            col.append(j)
#对row清0
for i in row:
    for j in range(col_length):
        x[i][j]=0
#对col清0
for j in col:
    for i in range(row_length):
        x[i][j]=0
        
            
print(x)

字符串练习题：（1）字符串最长公共前缀

def f(strs):
    res =""
    for i in zip(*strs):
        if len(set(i))==1:
            res +=i[0]
        else:
             break
    return res

6、双指针使用场景一：从两端向中间迭代数组。使用技巧：一个指针从头部开始，而另一个指针从尾部开始。

（1）翻转数组

def f(s):
    i = 0
    j = len(s)-1
    while i<j:
        s[i],s[j] = s[j],s[i]
        i +=1
        j -=1
    return s
    
s = ['l', 'e', 'e', 't', 'c', 'o', 'd', 'e']
print(f(s))

(2)给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数.函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。且index不从0开始

def f(nums,target):
    n = len(nums)
    i = 0
    j = n-1
    while i<j:
        sum = nums[i]+nums[j]
        if sum==target:
            return [i+1,j+1]
        elif sum<target:
            i +1
        else:
            j -=1

nums = [2, 7, 11, 15]
target =9
print(f(nums,target))

:7、双指针使用场景二：快慢指针。确定两个指针的移动策略，有时可能需要在使用双指针技巧之前对数组进行排序，也可能需要运用贪心法则来决定你的运动策略。

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

#快慢指针移动策略：当快指针指向的值不等与给定值时，满指针移动。
def removeElement(nums,val):
    n=len(nums)
    slow = 0
    for fast in range(n):
        if nums[fast]!=val:
            nums[slow]=nums[fast]
            slow +=1
    return slow

(2)给定一个二进制数组，计算其中最大连续1的个数

def f(nums):
    if 1 not in nums:
        return 0
    else:
        n = len(nums)
        slow = 0
        x = []
        for fast in range(n):
            if nums[fast]==1:
                slow +=1
                x.append(slow)
            else:
                slow = 0
        return max(x)

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

def f(nums,s):
    n = len(nums)
    #初始化左指针
    left = 0
    #初始化最小长度：正无穷。即数组中所有元素累计和小于s
    res = float("inf")
    #初始化数组中元素累和
    temp = 0
    #右指针 r 
    for right in range(n):
        temp +=nums[right]
        #进入循环的条件：元素累和>=s
        while (temp>=s):
            #记录此时最小长度
            res  = min(res, right-left+1)#right-left+1代表左指针到右指针的长度
            temp -=nums[left]#滑动窗口的原则：先进先出。当元素累和超过s时，从左侧吐掉元素。
            left +=1
    if res !=float("inf"):
        return res
    else:
        return 0
            

nums =[2,3,1,2,4,3]
s = 7
print(f(nums,s))

leetcode 数据结构 探索数组和字符串

leetcode 数据结构探索数组和字符串