记录一下找实习过程种各大厂的笔试，水平有限，希望有大佬能指点一二~

笔试题均使用Python编码

1、捕获

小美玩一个游戏，该游戏的目的是尽可能抓获敌人。

敌人的位置将被一个二维坐标（x，y）表示。

小美有一个全屏的技能，该技能一次性能将若干敌人一次性捕获。捕获的敌人之间的横坐标最大差值不能大于A，纵坐标的最大差值不能大于B。现在给出所有敌人的坐标，你的任务是计算小美一次性最多能使用技能捕获多少敌人。

输入描述：

第一行三个正整数N,A,B，表示共有N个敌人，全屏技能的参数A和参数B；

接下来N行，每行两个数字x,y，描述一个敌人所在的坐标。

1≤N≤500，1≤A,B≤1000，1≤x,y≤1000

输出描述：

一行，一个整数表示小美使用技能单次所可以捕获的最多数量

样例输入：

3 1 1

1 1

1 2

1 3

样例输出：

2

样例解释：

最多可以同时捕获两名敌人，可以是(1，1)和(1，2)处的敌人，也可以是(1，2)和(1， 3)处的敌人，

但不可以同时捕获三名敌人，因为三名敌人时，纵坐标的最大差值是2，超过了参数B的值1。

样例输入：

5 1 2

1 1

2 2

3 3

1 3

1 4

样例输出：

3

样例解释：

最多同时捕获三名敌人。其中一种方案如下: 捕获(1，1),(1，3)，(2，2)处的三个敌人。

解法思路：可以使用贪心算法。对所有敌人按照横坐标从小到大排序，然后从前往后依次遍历每个敌人，记录当前捕获数量和最左侧敌人的下标（初始为0）。对于当前敌人，从最左侧敌人依次往后遍历，如果发现有敌人不满足距离条件，则当前捕获数量即为当前下标减去最左侧敌人的下标，同时更新最左侧敌人的下标为当前敌人的下标。遍历完所有敌人后，当前捕获数量即为最终结果。

def max_enemies(enemies, A, B):
    n = len(enemies)
    enemies.sort()
    cnt = 0
    left = 0
    for i in range(n):
        for j in range(left, i):
            if abs(enemies[i][0]-enemies[j][0]) > A or abs(enemies[i][1]-enemies[j][1]) > B:
                cnt = max(cnt, i-left)
                left = j+1
        cnt = max(cnt, i-left+1)
    return cnt

nums = list(map(int,input().split()))
n, A, B = nums[0], nums[1], nums[2]
coord = []
if n != "":
    for i in range(n):
        s = input()
        x = list(map(int,s.split()))
        coord.append(x)
    print(max_enemies(coord, A, B))

2、彩带

小美现在有一串彩带，假定每一厘米的彩带上都是一种色彩。

因为任务的需要，小美希望从彩带上截取一段，使得彩带中的颜色数量不超过K种。

显然，这样的截取方法可能非常多。于是小美决定尽量长的截取一段。你的任务是帮助小美截取尽量长的一段，使得这段彩带上不同的色彩数量不超过K种。

输入描述：

第一行两个整数N,K，以空格分开，分别表示彩带有N厘米长，你截取的一段连续的彩带不能超过K种颜色。

接下来一行N个整数，每个整数表示一种色彩，相同的整数表示相同的色彩。

1≤N,K≤5000，彩带上的颜色数字介于[1, 2000]之间。

输出描述：

一行，一个整数，表示选取的彩带的最大长度。

样例输入：

8 3

1 2 3 2 1 4 5 1

样例输出：

5

样例解释：

最长的一段彩带是[1，2，3，2，1]，共5厘米。

解法思路：采用双指针。首先定义两个指针 left 和 right，分别表示截取的彩带的左右边界，初始值均为0。同时定义一个count，用于记录当前彩带中每种颜色出现的次数。

使用一个while循环，不断向右移动right指针，将每个彩带上的颜色出现次数记录在count列表中。同时，使用另一个while循环，判断当前彩带中不同的颜色数量是否超过K，如果超过了，则需要移动left指针，直到彩带中不同的颜色数量小于等于K。移动left指针的同时，需要将count中对应颜色的出现次数减1。在每次移动left和right指针后，都需要计算当前彩带的长度，并将其与max_k比较并更新max_k。最后返回max_k即可。

def max_length(nums, K, n):
    count = [0]*(max(nums)+1)
    left, right = 0, 0
    max_k = 0
    while right < n:
        count[nums[right]] += 1
        while len(set(nums[left:right+1])) > K:
            count[nums[left]] -= 1
            left += 1
        max_k = max(max_k, right-left+1)
        right += 1
    return max_k

nums = list(map(int,input().split()))
n, K = nums[0], nums[1] 
coord = []

if n != "":
    s = input()
    x = list(map(int,s.split()))
    print(max_length(x, K, n))

3、回文串

现在小美获得了一个字符串。小美想要使得这个字符串是回文串。

小美找到了你。你可以将字符串中至多两个位置改为任意小写英文字符 'a'-'z'。

你的任务是帮助小美在当前制约下，获得字典序最小的回文字符串。

数据保证能在题目限制下形成回文字符串。

注：回文字符串：即一个字符串从前向后和从后向前是完全一致的字符串。

例如字符串abcba,aaaa,acca都是回文字符串。字符串abcd,acea都不是回文字符串。

输入描述：

一行，一个字符串。字符串中仅由小写英文字符构成

保证字符串不会是空字符串。

字符串长度介于[1,100000] 之间。

输出描述：

一行，一个在题目条件限制下所可以获得的字典序最小的回文字符串。

样例输入：

acca

样例输出：

aaaa

样例解释：

原来的字符串已经是回文字符串了。但它不是题目条件下可以取得的字典序最小的回文字符串。将第二个字符和第三个字符都改为a可以获得字典序最小的回文字符串。

样例输入：

abcde

样例输出：

abcba

解法思路：

采用双指针+贪心算法。

1. 用双指针法判断当前字符串是否为回文字符串，记录不同字符的下标位置；
2. 根据不同字符的下标位置，分情况进行操作：

• 如果没有不同字符，则将左右两端的字符改为 'a' 即可；
• 如果有两个不同字符，则将它们改为 'a' 即可；
• 如果有四个不同字符，则将前两个和后两个中字典序较小的字符改为 'a'。

最后输出修改后的字符串即可。

s = input()
low, high, diff = 0, len(s)-1, 0
it = []

while low < high:
    if s[low] != s[high]:
        diff += 1
        it.append(low)
        it.append(high)
    low += 1
    high -= 1

low, high = 0, len(s)-1
if len(it) == 0:
    while s[low] == 'a':
        low += 1
        high -= 1
    s = s[:low] + 'a' + s[low+1:high] + 'a' + s[high+1:]
elif len(it) == 2:
    if len(s) % 2 and (s[it[0]] == 'a' or s[it[1]] == 'a'):
        s = s[:len(s)//2] + 'a' + s[len(s)//2+1:]
    s = s[:it[0]] + 'a' + s[it[0]+1:it[1]] + 'a' + s[it[1]+1:]
else:
    ss=list(s)
    ss[it[0]] = min(s[it[0]], s[it[1]])
    ss[it[1]] = min(s[it[0]], s[it[1]])
    ss[it[2]] = min(s[it[2]], s[it[3]])
    ss[it[3]] = min(s[it[2]], s[it[3]])
print(''.join(ss))

4、商店

现在商店里有N个物品，每个物品有原价和折扣价。

小美想要购买商品。小美拥有X元，一共Y张折扣券。

小美需要最大化购买商品的数量，并在所购商品数量尽量多的前提下，尽量减少花费。你的任务是帮助小美求出最优情况下的商品购买数量和花费的钱数。

输入描述：

第一行三个整数，以空格分开，分别表示N,X,Y。

接下来N行，每行两个整数，以空格分开，表示一个的原价和折扣价。

1≤N≤100,1≤X≤5000,1≤Y≤50，每个商品原价和折扣价均介于[1,50]之间。

输出描述：

一行，两个整数，以空格分开。第一个数字表示最多买几个商品，

第二个数字表示在满足商品尽量多的前提下所花费的最少的钱数。

样例输入：

3 5 1

4 3

3 1

6 1

样例输出：

2 4

样例解释：

可以发现有很多种买两个商品的方法。最省钱的方案是第二个商品原价购入，第三个商品折扣价购入。此时花费4元。

样例输入：

10 30 3

2 1

3 2

2 1

10 8

6 5

4 3

2 1

10 9

5 4

4 2

样例输出：

8 24

解法思路：这应该是个背包问题，没写出来。。。

def buy_goods(n, X, Y ,goods):
    goods.sort(key=lambda x: (x[1],-x[0]))
    count = 0
    cost = 0
    for i in range(n):
        price, discount = goods[i]
        if Y > 0 and discount > 0:
            Y -= 1
            cost += discount
            X -= discount
            count += 1
        elif X >= price:
            X -= price
            cost += price
            count += 1
    return count, cost

nums = list(map(int,input().split()))
n, x, y = nums[0], nums[1], nums[2]
coord = []
if n != "":
    for i in range(n):
        s = input()
        temp = list(map(int,s.split()))
        coord.append(temp)
    num_buy, total_cost = buy_goods(n, x, y, coord)
    print(num_buy,total_cost)