8.17小红书笔试 2/3

总结：留了70分钟做编程第三题还是做不来

💻题目： 选择题20道（50分），编程题3道（10,15,25）

❓第一题：排序后遍历一个一个删就行，O(nlogn）

t = int(input())
for _ in range(t):
    n, d = map(int, input().split())
    nums = list(map(int, input().split()))
    nums.sort() //排序
    if n == 1:
        print(n)
    else:
        i, j = 0, 1
        del_num = 0
        while i < n and j < n:
            if nums[j] - nums[i] <= d:
                del_num += 1
                j += 1
            else:
                i = j
                j += 1
        if del_num % 2 == 1: //凑整
            del_num += 1
        print(n - del_num)

❓第二题：第一个字符作为最后留下来的参考，后面和第一个字符不一样的都会被删，而且可以删去其后和第一个字符一样的字符，O(n)

n = int(input())
s = input()
del_cnt = 0
ref = s[0]
i = 1
while s[i] == ref:
    i += 1
start = i
ack = 0 // 类似攻击力
for i in range(start, n):
    if s[i] != ref:
        ack += 1 //可以评论后面的（攻击后面的）
        del_cnt += 1 //不一样的会被删（被评论）
    else:
        if ack > 0:
            ack -= 1 // 被攻击就会被删
            del_cnt += 1 
print(del_cnt)

❓第三题：不会，O(n^2)只有9%