[数据结构与算法]D5-AcWing-800、2816、801、803+复习785-799

我太菜了啊啊 啊啊啊啊啊！昨天上课，居然都没有学习！！！！！！！垃圾
今天赶快补啊啊 ！

800

这是一道双指针，自己写的时候想到用暴力+单调性，但是没领会到如何用单调性，看了y总的视频。
发现单调性就是：i增大，j会减小，j代表使A【i】+B【j】》=x的最左边的数。
这样上面最多走m，下面最多走n，一共是m+n

n,m,x = map(int,input().split())

A = list(map(int,input().split()))
B = list(map(int,input().split()))

j=m-1
for i in range(n):
    while A[i]+B[j]>x:
        j -= 1
    if A[i]+B[j]==x:
        break
print(i,j)    

2816

感觉很简单啊，不知道y总在讲啥。。。

n,m = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

i,j = 0,0
while i!=n and j!=m:
    if A[i]==B[j]:
        i +=1
        j +=1
    else:
        j +=1
if i==n:
    print('Yes')
else:
    print('No')

801

这道题考察的是位运算。
位运算一共有两种：
1、二进制表示中，第k位是多少
n>>k&1
2、lowbit——返回x的最后一位1（从左向右）
这个也可以用来看一共有几个1，就是这题
x&-x
这里的-x是补码+1【反正这么&了就可以返回最后一位负数】

n = int(input())
nums = list(map(int,input().split()))

def lowbit(x):
    return x&-x
for i in range(n):
    res = 0
    while nums[i]:
        nums[i] -= lowbit(nums[i])
        res += 1
    print(res,end=' ')
    i += 1
    

802

参考知乎大佬的区间和（离散化）。
10e9太大了，这里映射到10e5
具体区间化的操作就是：
1、找到所有需要区间化的坐标
2、去重、排序
3、写使两个区间对应起来的find（x）函数，用二分，查找alls【mid】==x的数，也就是，alls里等于x的数的相对位置，就是他在离散化后的相对位置，也是这里的返回值。不过因为要用区间和，所以从1开始。
4、查找坐标，在新的区间上进行操作。

n,m = map(int,input().split())
# x用100000，l和r用200000
a,s = [0]*300010,[0]*300010
# alls里面装所有需要离散化的坐标
alls,add,query=[],[],[]

for _ in range(n):
    x,c =map(int,input().split())
    # 这个是一组一起输入，不然x离散化后找不到对应的c了
    add.append((x,c))
    alls.append(x)
for _ in range(m):
    l,r = map(int,input().split())
    query.append((l,r))
    alls.append(l)
    alls.append(r)
    
# 去重+排序
alls = list(set(alls))
alls.sort()

# 找到离散化后的坐标
def find(x):
    l,r = 0,len(alls)-1
    while l<r:
        mid = l+r>>1
        if alls[mid]>=x:
            r = mid
        else:
            l = mid+1
        # 因为求区间和，所以加1，使坐标从1开始。
    return l+1
# 插入所有数   
for x,c in add:
    index = find(x)
    a[index] += c
    
# 处理前缀和
for i in range(1,300010):
    s[i] = s[i-1]+a[i]

for l,r in query:
    print(s[find(r)]-s[find(l)-1])

803区间合并

这题还是看的知乎大佬的。
区间合并主要的步骤是：
1、排序
在python里用
sorted(x,key=lambda x:(x[0],x[1]))
2、进行合并
主要思路为res为当前维护的列表，如果不为空，
就和待考查列表a中的值进行操作；
如果为空就先加入一个a中待考察的列表（一般就是加入第一个）

n =int(input())
a =[ ]
res = []

for _ in range(n):
    l,r = map(int,input().split())
    a.append([l,r])
# 先根据0，再根据1排序
a = sorted(a,key=lambda x:(x[0],x[1]))

for i in range(n):
    if res:
        if res[-1][1] >= a[i][0]:
            res[-1][1] = max(res[-1][1],a[i][1])
        else:
            res.append([a[i][0],a[i][1]])
    else:
        res.append([a[0][0],a[0][1]])
print(len(res))

785

1、别忘了边界判断
2、快排是从l-1和r+1开始的
3、递归时右边界为j

def quick_sort(q,l,r):
    if l>=r:
        return
    i,j = l-1,r+1
    x = q[l+r>>1]
    while i<j:
        i+=1
        j-=1
        while q[i]<x:
            i += 1
        while q[j]>x:
            j -= 1
        if i<j: q[i],q[j]=q[j],q[i]
        
    quick_sort(q,l,j)
    quick_sort(q,j+1,r)
n = int(input())
nums = list(map(int,input().split()))
quick_sort(nums,0,n-1)
print(' '.join(map(str,nums)))
    

786

j换成i就会有问题。

弄了半天，不知道为什么

def quick_sort(q,l,r,k):
    if l>=r:
        return q[l]
    i,j=l-1,r+1
    x = q[l+r>>1]
    while i<j:
        i +=1
        j -=1
        while q[i]<x:
            i+=1
        while q[j]>x:
            j-=1
        if i<j:
            q[i],q[j]=q[j],q[i]
    sl = j-l+1
    if k<=sl:
        return quick_sort(q,l,j,k)
    else:
        return quick_sort(q,j+1,r,k-sl)
        
n,k = map(int,input().split())
nums = list(map(int,input().split()))
print(quick_sort(nums,0,n-1,k))

787

1、i=l;j=mid+1

2、切片操作赋值！！需要多出来一个：
q[l:r+1]，是r+1才能到r！！！

def merge_sort(q,l,r):
    if l>=r:
        return
    mid = l+r>>1
    i,j=l,mid+1
    a=[]

    merge_sort(q,l,mid)
    merge_sort(q,mid+1,r)
    while i<=mid and j<=r:
        if q[i]<=q[j]:
            a.append(q[i])
            i+=1
        else:
            a.append(q[j])
            j+=1
    if i<=mid:
        a += q[i:mid+1]
    if j<=r:
        a += q[j:r+1]
    q[l:r+1] = a[:]
    
n = int(input())
nums=list(map(int,input().split()))
merge_sort(nums,0,n-1)
print(' '.join(map(str,nums)))

788

1、加入tmp后别忘了，给i、j+1
2、函数要return res作为结果。

def merge_sort(q,l,r):
    if l>=r:
        return 0
    mid =l+r>>1
    res = merge_sort(q,l,mid)+merge_sort(q,mid+1,r)
    
    i,j=l,mid+1
    tmp = []
    while i<=mid and j<=r:
        if q[i]<=q[j]:
            tmp.append(q[i])
            i+=1
        else:
            tmp.append(q[j])
            res += mid-i+1
            j+=1
    if i<=mid:
        tmp += q[i:mid+1]
    if j<=r:
        tmp += q[j:r+1]
    
    q[l:r+1]=tmp[:]
    return res
n = int(input())
nums=list(map(int,input().split()))
print(merge_sort(nums,0,n-1))

789

二分后l和r应该是相同的，取哪个都行

def binary_left_search(q,l,r,k):
    while l<r:
        mid = l+r>>1
        if q[mid]>=k:
            r = mid
        else:
            l = mid+1
    if q[l]==k:
        return l
    else:
        return -1
        
def binary_right_search(q,l,r,k):
    while l<r:
        mid = l+r+1>>1
        if q[mid]<=k:
            l=mid
        else:
            r = mid-1
    if q[r]==k:
        return r
    else:
        return -1
n,q = map(int,input().split())
nums = list(map(int,input().split()))
while q!=0:
    q-=1
    k = int(input())
    a1 = binary_left_search(nums,0,n-1,k)
    a2 = binary_right_search(nums,0,n-1,k)
    print(a1,a2)

    
    

790

1、注意print时候的格式：f和.format()
2、是r-l，不是l-r

def binary_search(n):
    l,r=-100.0,100.0
    while r-l>=1e-8:
        mid = (l+r)/2
        if mid**3>=n:
            r = mid
        else:
            l = mid
    print('{:.6f}'.format(l))
n = float(input())
binary_search(n)

795

挺顺利的，前缀和，下标从1开始。

n,m = map(int,input().split())
nums = [0]+list(map(int,input().split()))

s = [0]*100010

for i in range(1,n+1):
    s[i] = s[i-1]+nums[i]

for _ in range(m):
    l,r = map(int,input().split())
    print(s[r]-s[l-1])

796

输入A矩阵的时候，我们需要用A【i】【1：】=

其他的比较顺利

n,m,q = map(int,input().split())

A = [[0]*1010 for _ in range(1010)]
S = [[0]*1010 for _ in range(1010)]

for i in range(1,n+1):
    A[i][1:] = list(map(int,input().split()))

for i in range(1,n+1):
    for j in range(1,m+1):
        S[i][j] = S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[i][j]

for _ in range(q):
    x1,y1,x2,y2 = list(map(int,input().split()))
    print(S[x2][y2]+S[x1-1][y1-1]-S[x1-1][y2]-S[x2][y1-1])

797

有点遗忘了，不过写的很顺滑。查分就是构造一个数组，使其前缀和为原来的数组，这样在一段上的改变可以用O（1）来实现。

n,m=map(int,input().split())
nums =[0]+list(map(int,input().split()))

def insert(l,r,c):
    B[l] += c
    B[r+1] -= c
B = [0]*100010

for i in range(1,n+1):
    insert(i,i,nums[i])

for _ in range(m):
    l,r,c = map(int,input().split())
    insert(l,r,c)

for j in range(1,n+1):
    B[j] += B[j-1]
    print(B[j],end=' ')

798

也是比较顺畅的，开了一个最大的空间，而不是动态的空间。

n,m,q = map(int,input().split())
A = [[0]*1010 for _ in range(1010)]
B = [[0]*1010 for _ in range(1010)]
def insert(x1,y1,x2,y2,c):
    B[x1][y1] += c
    B[x1][y2+1] -= c
    B[x2+1][y1] -= c
    B[x2+1][y2+1] += c

for i in range(1,n+1):
    A[i][1:]=list(map(int,input().split()))

for i in range(1,n+1):
    for j in range(1,m+1):
        insert(i,j,i,j,A[i][j])
        
for _ in range(q):
    x1,y1,x2,y2,c = map(int,input().split())
    insert(x1,y1,x2,y2,c)
    
for i in range(1,n+1):
    for j in range(1,m+1):
        B[i][j] += B[i-1][j]+B[i][j-1]-B[i-1][j-1]
        print(B[i][j],end=' ')
    print()

799

很吃力：
相当于记录以每个i为结尾的不重复的最长子串长度，然后选最长值。
具体方法：
先读到i，一旦有重复的，则缩短j，直到不重复，记录当前长度，把长的放入res中。若读到i没有重复值，则就可直接比较。

n = int(input())
a = list(map(int,input().split()))
#暴力算法：i指向第几位；j用来判断是否有重复；
#双指针单调性：i向右走，j不可能向左走。
i,j,res=0,0,0
index = [0]*100010

while i<n:
    index[a[i]]+=1
    while j<i and index[a[i]]==2:
        index[a[j]]-=1
        j+=1
    res = max(res,i-j+1)
    i+=1
print(res)