class check_united:
def __init__(self, n):
self.parent = [i for i in range(n)]
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def united(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
self.parent[root_x] = root_y
def is_connected(self, x, y):
return self.find(x) == self.find(y)
n, m = map(int, input().split())
ip2id = {}
id2ip = {}
#IP, id
for i in range(n):
ip, idx = input().split()
idx = int(idx)
ip2id[ip] = idx
id2ip[idx] = ip
#guanxi
fun = check_united(n)
for i in range(m):
a, b = map(int, input().split())
fun.united(a - 1, b - 1)
q = int(input())
for i in range(q):
ip1, ip2 = input().split()
if fun.is_connected(ip2id[ip1] - 1, ip2id[ip2] - 1):
print("Yes")
else:
print("No")
分析：动态规划
def fun(times, scores, t):
N = len(times)
dp = [[0]*(t+1) for _ in range(N+1)]
for i in range(1, N+1):
for j in range(1, t + 1):
dp[i][j] = dp[i - 1][j]
if j >= times[i - 1]:
dp[i][j] = max(dp[i][j], dp[i - 1][j - times[i - 1]] + scores[i - 1])
return dp[N][t]
times_input = list(map(int, input().split(',')))
scores_input = list(map(int, input().split(',')))
t_input = int(input())
print(fun(times_input, scores_input, t_input))
给定存在N个元组的集合，每个元组里面的值为(等级，价格)，等级和价格都是非负整数。【在集合中选取数量大于0小于等于N的元组，要求这些元组的等级差不能超过X，并且它们的价格之和最大。】最后输出最大的价格
输入描述：第一行包含两个整数N和x，分别是给定的元组集合的数量和等级差。接下来的 N 行是元组的具体数值，每一行为一个元组的两个值，等级和价格，数字之间用空格隔开
输出描述：输出选取的元组最大的价格之和。
示例输入：
4 2
0 14
3 16
8 9
10 18
示例输出：27
说明：总共有4个元组，限制选取的元组等级差为2，那么只能选第三和第四个，或者只选一个。对比这几种选组，价格之和最高的是选第三和第四个元组，结果为27。
分析：选取尽量大的元组，等级差不超过x，但价格之和要最大。这是一个动态规划问题，我们可以使用一个二维数组dp来存储状态。dp[i][j]表示在前i个元组中选择等级差不超过j的元组能得到的最大价格。
N, x = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(N)]
data.sort()
left, right = 0, 0
max_sum = 0
current_sum = 0
while right < N:
if data[right][0] - data[left][0] <= x:
current_sum += data[right][1]
right += 1
else:
current_sum -= data[left][1]
left += 1
max_sum = max(max_sum, current_sum)
print(max_sum)
给定一个字符串A和一个字符串B，找到B在A中的最小子串，他将包含B中的所有字符。当A中没有符合条件的B字符串时，返回空字符串
输入示例：‘DKAFWADCBEILBCEA’
输出示例：‘BCA’
说明：因为“ADCB"和”BCEA"都符合且长度最小，但“ADCB"是最先匹配的
分析：双指针，滑动窗口法。先扩大窗口，到大某一条件后，缩小窗口，寻求最短or最小
from collections import Counter
a = eval(input())
b = eval(input())
counter_a = Counter()
counter_b = Counter(b) #计数器工具
'''
collections.Counter("abracadabra") => Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
'''
fast = slow = 0
min_len = float("inf") #先奠定什么都没有时的输出
min_str = ''
while fast < len(a):
counter_a[a[fast]] += 1
while all(map(lambda x: counter_a[x] >= counter_b[x], counter_b.keys())):#只要 counter_a 中每个与 counter_b
# 中相应键的值都大于或等于 counter_b 中的值，就会继续执行代码块中的操作。
if fast - slow + 1 < min_len:
min_len = fast - slow + 1
min_str = a[slow:fast+1]
#收缩窗口
counter_a[a[slow]] -= 1
slow += 1
fast += 1
min_str = min_str if min_len != float('inf') else ''
print(min_str)
示例1
输入[1,null,2,3]
输出[1,2,3]
以下代码是错的，oj模式，先层序遍历构建二叉树，再递归前序遍历
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 2，则返回 0
示例1：输入[3, 6, 9, 1]
输出：3
小明用计算机随机生成了N个正整数，他希望从这N个数中选取若干个数，使得它们的和等于M。这些随机生成的数字可能会相同，但是每个数字最多只允许使用一次。当然这样的选取方案可能不存在，也可能有多个。现在希望你编写一个程序，能够找出数字个数最少的选取方案，输出对应的最少数字的个数，如果无解输出“Nosolution”。
输入描述
单组输入，每组输入2行。第1行包含两个正整数N和M，分别表示初始输入的正整数个数和目标数字和(N<=1e3,M<=1e5).第2行为N个正整数，两两之间用空格隔开(每一个正整数均小于等于1e5)。
输出描述
输出数字个数最少的选取方案中所包含的最少数字个数，如果无解输出“Nosolution"
样例输入
55
13211
样例输出：2
def min_number(N, M, nums):
dp = [float('inf')] * (M + 1)
dp[0] = 0
for i in range(N):
for j in range(M, nums[i] - 1, -1):
dp[j] = min(dp[j], dp[j - nums[i]] + 1)
return dp[M] if dp[M] != float('inf') else "Nosolution"
N, M = map(int, input().split())
nums = list(map(int, input().split()))
print(min_number(N, M, nums))
有n个人排成一条直线，从左到右编号分别为1到n。报数由头报到尾，再由尾巴报到头。现在从第1个人开始报数，在报数过程中，如果有人报到m则出列，下一个人将继续从1开始报数。第n个人报数完之后再接着往回报数，即倒数第2个人继续报下一个数; 当报到第1个人后，第2个人再接着报数。如此循环，直到只留下一个人为止。
例如当n=2，m=3时，第1个人报1，第2个人报2，接下来第1个人报3，出列，留下第2个人。
当输入n和m时，请问通过 (n-1) 轮报数后，最后留下的那个人的编号是多少?
输入描述：单组输入。输入两个正整数n和m
输出描述：输出最后留下的那个人的编号
样例输入：5 3
样例输出：1
说明：1, 2，3, 4，5
先从头报，报到数字3的是编号3它出局，剩1， 2， 4， 5
再从刚刚出局的编号3的下一个即编号4开始报1，编号4（1） -> 编号5（2） -> 编号4（3），所以编号4出局，剩1， 2， 5
下一轮从编号4出局的下一个即编号2开始报，编号2（1）-> 编号1（2） -> 编号5（3），所以编号5出局，剩1,2
再往回报，编号2（1）-> 编号1（2）->编号2（3），编号2出局，剩下编号1，所以输出1
class Node:
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
class DoubleLinkList:
def __init__(self):
self.first = None
self.last = None
def insert_last(self, value):
new_node = Node(value)
if self.first is None:
self.first = new_node
else:
self.last.next = new_node
new_node.prev = self.last
self.last = new_node
def delete_first(self):
if self.first is None:
raise Exception("链表数据不存在")
temp = self.first
if self.first.next is None:
self.last = None
else:
self.first.next.prev = None
self.first = temp.next
return temp
def delete_last(self):
if self.first is None:
raise Exception("链表数据不存在")
temp = self.last
if self.first.next is None:
self.last = None
self.first = None
else:
self.last.prev.next = None
self.last = temp.prev
return temp
def display(self):
current = self.first
while current is not None:
print(current.value, end=' ')
current = current.next
def main():
link_list = DoubleLinkList()
n, m = map(int, input().split())
for i in range(1, n+1):
link_list.insert_last(i)
temp = link_list.first
index, num, flag = 0, 0, True
while True:
index += 1
if temp == link_list.last:
flag = False
elif temp == link_list.first:
flag = True
if index % m == 0:
print(f"删除的值: {temp.value}")
if temp == link_list.last:
link_list.delete_last()
flag = False
elif temp == link_list.first:
link_list.delete_first()
flag = True
else:
temp.prev.next = temp.next
temp.next.prev = temp.prev
num += 1
if flag:
temp = temp.next
else:
temp = temp.prev
if num == n - 1:
break
if __name__ == "__main__":
main()