很想一心去走计算机视觉的科研路,但是无奈形式下不得不面临找工作的压力,博主是个很普通的学校,就业压力还是有的,所以博客会新增一些笔试的复盘博客,主要留着给自己备份,有兴趣的欢迎下方留言讨论。本篇复盘的是拼多多20届学霸批算法笔试题,思路也是结合自己当时写的加上已公开的思路,试题是Python来写的,如果有错误和需要改进的欢迎指正。

1.数组升序

题目描述:

给定两个数组A和B。其中数组A是几乎严格升序排列的,几乎的定义是只需改变其中一个数,即可满足完全升序排列。这里严格升序排列指的是不允许相邻两个为相同的数。请找出数组B中满足要求的最大数,并输出最终的有序数组,如果找不到,输出”NO”。

输入描述:

共两行,第一行是数组A,第二行为数组B,输入之间用空格分割,且len(A),len(B)<100。

输出描述:

最终有序数组,不存在则输出NO

示例:

输入:

1 3 5 7 4 10

2 1 5 8 9

输出:

1 3 7 9 10

"""
解题思路:
对B数组升序排序,从后向前找到符合A数组中不满足升序的数并且替换掉,如果没有输出"NO"
注意边界,注意边界,注意边界
"""
if __name__ == "__main__":
    array_A = list(map(int, input().split()))
    array_B = list(map(int, input().split()))
    flag = True
    if len(array_B)==0:
        flag = False
    array_B.sort()
    index_A = 0
    left, right = 0, 0
    if len(array_A) > 1:
        for i in range(1, len(array_A)):
            if array_A[i] <= array_A[i-1]:
                index_A = i
                # 由于A的长度至少为2,所以一定有左边界
                left = array_A[i-1]
                # 如果不是最后一位不满足升序,那么就有右边界,右边界为此时的后一位
                if index_A != len(array_A)-1:
                    right = array_A[i+1]
                break
        for j in range(len(array_B)-1, -1, -1):
            # 当出错不是最后一位,此时一定在left和right之间找
            if index_A != len(array_A)-1 and left < array_B[j] < right:
                array_A[index_A] = array_B[j]
                break
            # 如果最后一位出错,只判断left即可
            elif index_A == len(array_A)-1 and left < array_B[j]:
                array_A[index_A] = array_B[j]
                break
            # 如果遍历完还是找不到合适的,flag置False
            if j == 0:
                flag = False
    if flag:
        print(" ".join(map(str, array_A)))
    else:
        print('NO')

2.字符串成环

题目描述:

给定一个字符串数组(字符串长度和数组的长度均大于1且小于1024),所有字符串均为大写字母,给定的字符串数组能否通过更换数组中元素顺序,从而首尾成环,环上相邻字符串首尾衔接的字符相同。

输入描述:

一行字符串,空格分割

输出描述:

true or false

示例:

输入:

CAT TIGER RPC

输出:

true

"""
解题思路:
所给字符串长度有限直接暴力构造成环输入,满足首尾相同
记得在最后一位上定向到字符串第一位检查是否成环。
"""
if __name__ == "__main__":
    in_string = list(map(str, input().split()))
    len_string = len(in_string)
    flag = True
    for i in range(len_string-1):
        for j in range(i+1, len_string):
            if in_string[i][-1] == in_string[j][0]:
                in_string.insert(i+1, in_string.pop(j))
                break
            if j == len_string-1:
                flag = False
    if in_string[len_string-1][-1] != in_string[0][0]:
        flag = False
    # print(in_string)
    if flag:
        print("true")
    else:
        print("false")

上面的方法在示例ABC CBA CDC下不符合要求,采用dfs方法进行遍历搜索,方法借鉴牛客网讨论区:

"""
作者:酱香小龙虾
链接:https://www.nowcoder.com/discuss/212444
来源:牛客网
经过一些润色和修改
"""


class Solution:
    def __init__(self):
        self.res = False

    def judge(self, s):
        self.dfs(s, '')
        return self.res

    def dfs(self, s, visited):
        if self.res:
            return self.res
        if not s and visited[0] == visited[-1]:
            self.res = True
            return self.res
        for i, e in enumerate(s):
            if not visited:
                self.dfs(s[:i] + s[i + 1:], e[0] + e[-1])
            elif e[0] == visited[-1]:
                self.dfs(s[:i] + s[i + 1:], visited[0] + e[-1])


if __name__ == "__main__":
    in_string = list(map(str, input().split()))
    flag = Solution().judge(in_string)
    if flag:
        print("true")
    else:
        print("false")

3.任务依赖

题目描述:

一共有N个执行的任务,每个任务需要$P_i$的时间完成执行。同时,任务之间可能会有一些依赖关系。比如任务1可能依赖任务2和任务3,那么任务1必须在任务2和任务3都执行完成后才能执行。

同时只能执行一个任务,并且在任务完成之前不能暂停切换去执行其他任务。为了提升平台用户的使用体验,希望最小化任务的平均返回时长。一个任务的返回时长定义为任务执行完成时刻减去平台接收到该任务的时刻。在零时刻,所有N个任务都已经被平台接收。

安排一下任务执行顺序,使得平均返回时长最小。

输入描述:

第一行包含2个正整数N、M,分别表示任务数量以及M个任务依赖关系。

第二行包含N个正整数,第i(1 <= i <= N)个数表示第i个任务的处理时间Pi。

接下来的M行,每行表示一个任务依赖关系。每行包含2个整数Ai(1 <= Ai <= N)、Bi(1 <= Bi <= N)。表示第Bi个任务依赖于第Ai个任务。数据保证不会出现循环依赖的情况。

数据范围:

​ 1 <= N <= 1000

​ 1 <= M <= 50000

​ 1 <= Pi <= 10000

输出描述:

输出一行,包含N个整数(两两之间用一个空格符分隔),其中第i(1 <= i <= N)个整数表示多多鸡执行的第i个任务的编号。若有多种可行方案,则输出字典序最小(优先执行编号较小的任务)的方案。

示例:

输入:

5 6

1 2 1 1 1

1 2

1 3

1 4

2 5

3 5

4 5

输出:

1 3 4 2 5

"""
解题思路:
如果不考虑依赖关系,为了实现最小平均返回时长,需要按照耗时越少任务越早执行的顺序执行,
加上依赖关系后,我们一定要做完依赖任务才能进行依赖后的任务,我们用degree字典保存依赖任务的数量,
只有依赖任务的数量为0(表示依赖任务做完,才能进行本任务的执行),这里的执行顺序还是按照时间排序,
整体的实现利用堆加上优先队列实现。下面是Python实现,强调思想,不强调语言。
"""
def TaskSequence(n, degree, depend, cost):
    """
    :param n: int型, 表示有多少个任务
    :param degree: 字典保存,每个任务对应的等级,依赖越少,等级越小,
                   当value为0时,对应的key可出队,对于示例
                   初始的degree为{1: 0, 2: 1, 3: 1, 4: 1, 5: 3}
    :param depend: 字典保存,表示依赖关系,记录依赖的任务,此字典保持不变
                   对于示例,depend为{1: [2, 3, 4], 2: [5], 3: [5], 4: [5]}
    :param cost: list,表示任务对应的耗时,不考虑依赖时,时长越少越早执行
    :return: res: 符合要求的任务输出序列
    """
    res = []
    queue = []
    for i in range(1, n+1):
        if degree[i] == 0:
            # 先将自由节点(不依赖于别人的节点)入队
            queue.append([i, cost[i-1]])
            degree[i] = -1
    while queue:
        queue.sort(key=lambda x: (x[1], x[0]))  # 按照 执行时间->序号的顺序 排序
        node = queue.pop(0)
        res.append(node[0])
        if node[0] not in depend:
            # 当前节点没有被依赖,继续出队取下一个节点
            continue
        for ref in depend[node[0]]:
            # 所有依赖当前节点的节点 degree - 1(因为把当前节点给执行了)
            degree[ref] -= 1
        for i in range(1, n + 1):
            if degree[i] == 0:
                # 自由节点继续入队
                queue.append([i, cost[i - 1]])
                degree[i] = -1
    return res


if __name__ == "__main__":
    n, m = map(int, input().split())
    cost = list(map(int, input().split()))
    degree = {}  # 存储节点依赖于多少个别的节点
    for i in range(1, n+1):
        degree[i] = 0
    depend = {}   # 存储节点的依赖关系。val 是 list,这些节点依赖于 key 节点
    for _ in range(m):
        ref = list(map(int, input().split()))
        depend.setdefault(ref[0], []).append(ref[1])
        degree[ref[1]] += 1  # 该节点依赖于别人,degree + 1
    res = TaskSequence(n, degree, depend, cost)
    print(" ".join(map(str, res)))

4.最高金字塔

题目描述:

有N个长方体积木,每个积木的高都是1,长宽都为Li,重量为Wi。

现在要用这些积木搭一个高高的金字塔。他打算金字塔的每一层是由且仅由一块积木组成。同时每一层的积木边长都严格比在其下方的积木小。

每块积木只能承受自身重量的7倍重量,若超过7倍自重,搭建的金字塔会因此变得不稳定。具体来说即:对于每一块积木,在其上方的积木重量之和必须小于等于其自重的7倍。

计算一下最高可以搭一个多高的金字塔?

数据范围:

​ 1 <= N <= 100

​ 1 <= Li <= 1000

​ 1 <= Wi <= 1000

输入描述:

第一行包含1个正整数N,表示积木的数量。

第二行包含N个正整数,第i个数表示第i个积木的长度Li。

第三行包含N个正整数,第i个数表示第i个积木的重量Wi。

输出描述:

输出占一行,仅包含一个整数,表示可以搭出的金字塔的最高高度。

示例:

输入:

10

1 2 3 4 5 6 7 8 9 10

1 1 1 1 1 1 1 1 1 10

输出:

9

"""
解题思路:
最重要的就是选择哪一块作为积木的底,这个问题可以采用dp思想
提前对积木按照由小到大的排序排序
状态: dp[i][j]表示第i个积木为底时,构造高度为j时所用的积木的最小重量
状态转移方差:dp[i][j] = min(dp[i][j], dp[k][j-1]+wi)
(前提dp[k][j-1]状态合法,且第k个积木尺寸小于第i个积木
"""
if __name__ == "__main__":
    N = int(input())
    L = list(map(int, input().split()))
    W = list(map(int, input().split()))
    Pair = []
    for i in range(N):
        Pair.append([L[i], W[i]])
    Pair.sort(key=lambda x:x[0])
    Pair.insert(0, [0, 0])
    # dp[i][j]表示第i个积木为底时,构造高度为j时所用的积木的最小重量
    dp = [[float("inf") for _ in range(N + 1)] for _ in range(N + 1)]
    dp[0][0] = 0
    ans = 0
    for i in range(1, N + 1):
        # 以第i块积木为底时
        for k in range(i):
            if Pair[k][0] < Pair[i][0]:  # 长度满足条件
                for j in range(k+1):
                    # 重量满足条件
                    if dp[k][j] != float("inf") and dp[k][j] <= Pair[i][1]*7:
                        dp[i][j+1] = min(dp[i][j+1], dp[k][j]+Pair[i][1])
                        ans = max(ans, j+1)
    print(ans)

总结

所有程序并不能保证通过所有用例,主要强调思路,算法题是刷不完的,在正式笔试的时候也有可能卡顿,所以尽量形成一套比较好的解题流程,定期的笔试训练还是可以增进一下思维。本博客还是以计算机视觉和深度学习知识为主,欢迎多交流。