百度笔试（10.29）

判断s字符串是否可以通过添加某些字符变成t字符串，s是否是t的子序列

s = input()
n = int(input())
st = set()
res = []
for idx in range(n):t = input()if t in st or len(t) < len(s):continuest.add(t)i,j = 0,0while i < len(s) and j < len(t):if s[i] == t[j]:i += 1j += 1if i == len(s):res.append(idx+1)
print(len(res))
print(" ".join(map(str,res)))

修改i层和i+1层数据后，树中的最大最小值之差

from collections import defaultdict
n = int(input())
val = list(map(int,input().split()))
val_mp = defaultdict(int)
for i,v in enumerate(val):val_mp[i+1] = vg = defaultdict(list)
for i in range(n-1):u,v = map(int,input().split())g[u].append(v)
res = []
q = deque()
q.append(1)
val_layer = []
while len(q) > 0:size = len(q)cur_layer = []for _ in range(size):node = q.popleft()cur_layer.append(val_mp[node])for nxt in g[node]:q.append(nxt)val_layer.append(cur_layer)for i in range(len(val_layer)):if i>0 and i!=len(val_layer)-1:temp_val = val_layer.copy()last_layer_vals = [i*2 for i in temp_val[i-1]]cur_layer_vals = [i//2 for i in temp_val[i]]temp_val[i-1] = last_layer_valstemp_val[i] = cur_layer_valsnew_val_list = []for sub_list in temp_val:new_val_list.extend(sub_list)res.append(max(new_val_list)-min(new_val_list))
print(" ".join(map(str,res)))

判断两条线段是否相交

class Point():def __init__(self, x, y):self.x = xself.y = y
def quick_judge(a: Point,b:Point,c:Point,d:Point) -> bool:f1 = max(a.x, b.x) < min(c.x, d.x)f2 = max(a.y, b.y) < min(c.y, d.y)f3 = max(c.x, d.x) < min(a.x, b.x)f4 = max(c.y, d.y) < min(a.y, b.y)if f1 or f2 or f3 or f4:return Falsereturn Truedef xmult(a: Point,b:Point,c:Point,d:Point):vcAx = b.x - a.xvcAy = b.y - a.yvcBx = d.x - c.xvcBy = d.y - c.yreturn vcAx*vcBy-vcAy*vcBxdef judge(a: Point,b:Point,c:Point,d:Point) -> bool:if not quick_judge(a,b,c,d):return Falsexmult1 = xmult(c,d,c,a)xmult2 = xmult(c,d,c,b)xmult3 = xmult(a,b,a,c)xmult4 = xmult(a,b,a,d)if xmult1*xmult2<0 and xmult3*xmult4<0:return Truereturn Falset = int(input())
for _ in range(t):ax1,ay1,ax2,ay2 = map(int, input().split())bx1,by1,bx2,by2 = map(int, input().split())a = Point(ax1, ay1)b = Point(ax2, ay2)c = Point(bx1, by1)d = Point(bx2, by2)if judge(a,b,c,d):print('Yes')else:print('No')