前言
笔试一共五道编程题，满分是100分，时间是两个小时，可以跳题，使用的平台是牛客网，允许跳出界面使用本地IDE。
题目一：构建数字
给定n个长度均为m的数字字符串，从上往下构建成m个新的数，去掉前置0后按照从小到大的顺序输出。
输入：
第一行包括一个整数n。
接下来n行每行包括一个长度为m的数字字符串。
输出：
第一行包括新构建的数按从小到大排列。
输入示例：
3
0121
1502
2138
输出示例：
12 128 151 203
思路
该题比较简单，可以直接暴力求解，需要注意的是前置0的处理。
n = int(input())
nums = []
for i in range(n):num = input()nums.append(num)ans = []
for i in range(len(nums[0])):a = ""for j in range(n):a += nums[j][i]# int()函数会直接去掉前置0ans.append(int(a))ans.sort()
for i in range(len(ans)):print(ans[i], end=" ")
题目二：淘汰数字
给定一个数组，下标从1~n，每次淘汰下标为非质数的数字，剩下的数形成新的数组，重复上述过程，直到数组内只剩下一个数字。
本题为核心代码模式，只需要补充解法类的实现代码即可。
输入：
第一行包括一个长度为n的数组。
输出：
第一行包括一个整数。
输入示例1：
[1, 2, 3, 4]
输出示例1：
3
输入示例2：
[3, 1 , 1 , 4 , 5, 6]
输出示例2：
5
思路
本题也是直接暴力求解，重点是求出n内的所有质数。
from math import sqrt, ceil
class Solution:def isP(self, x):m = ceil(sqrt(x))+1for j in range(2, m):if x%j == 0:return Falsereturn Truedef getNumber(self , a):# write code heren = len(a)pnums = [2]for i in range(3, n):if self.isP(i):pnums.append(i)while n != 1:k = 0for i in range(len(pnums)):if pnums[i] > n:breaka[k] = a[pnums[i]-1]k += 1n = kreturn a[0]a = [1,2,3,4] # [3,1,1,4,5,6]
print(Solution().getNumber(a))
题目三：士兵分配
给定一定数量的士兵，编号为1n，用长度为n的0/1串s表示，其中0代表该士兵只会进攻，1代表该士兵只会防御，且其攻击力或防御力等于其编号。将士兵分组，编号为1pos的士兵为进攻组，该组的攻击力之和用w表示，编号为pos+1~n的士兵为防御组，该组的防御力之和用v表示，求|w-v|的最小值。注意：pos可以取0，当pos取0时，表示将所有士兵分到防御组，而进攻组没有士兵。
输入：
第一行包括一个整数n，表示士兵的数量。
第二行包括一个0/1字符串s，表示士兵的状态。
输出：
第一行包括一个整数，表示|w-v|的最小值。
输入示例1：
4
0011
输出示例1：
1
输入示例2：
7
1000101
输出示例2：
2
思路
思路一：暴力求解。遍历整个字符串，在每一个位置对其进行分割，得到左右两个子串，然后分别统计左右两边的攻击力或防御力，与此同时不断刷新差值绝对值的最小值。这种方法的算法复杂度较高，无法AC。
思路二：逐个分配。可以先假设所有的士兵都在右边，左边没有士兵，即pos为0的情况，此时w和v均可知。然后遍历整个字符串，将士兵逐个从右边分配到左边，如果分配的士兵为0，那么w加上该士兵的编号，v不变；如果分配的士兵为1，那么v减去该士兵的编号，w不变，与此同时不断刷新差值绝对值的最小值即可。
以下为思路二的代码：
n = int(input())
s = input()
# 因为编号为1~n，且pos的取值范围为0~n
# 所以添加两个占位符可以简化问题的求解过程
s = "-" + s + "-"
w = 0
v = 0
for i in range(n+2):if s[i] == "1":v += i
res = v
for i in range(n+2):if s[i] == "0":w += iif s[i] == "1":v -= ires = min(res, abs(w-v))
print(res)
题目四：合并链表
给出一个链表数组，该链表数组均是某一个环状链表的一部分，请将这些链表组合并成环状链表，然后需要找到一个位置，使得从这个位置将环切开后，按照顺序或逆序遍历这个环，形成的链字典序尽量小，并返回这条链。
-
链表字典序的定义：对于两个链表a、b，从头节点到尾节点遍历，找到第一个不相同的节点值并比较大小，如果a[i].val < b[i].val，则认为a的字典序小于b的字典序。例如：链表{1,2,3} < 链表{1,2,4}, 链表{3,4,5} < 链表{6,7}。
-
环状链表不存在相同的节点值。
-
该题环状链表节点个数最小为2
-
每个链表都是在环状链表上的顺时针的一部分。
-
给定的链表数组一定能组成一个环状链表。
输入示例1：
[{1, 2, 3}, {2, 3, 4}, {4, 1}]
输出示例1：
{1, 2, 3, 4}
输入示例2：
[{3, 7, 4}, {7, 4, 5, 1, 10, 3}]
输出示例2：
{1, 5, 4, 7, 3, 10}
思路
用字典存每个下标的前驱和后继，即可还原环状链表。接下来考虑切口位置，可将其转化为确定头节点和遍历方向的问题。要使字典序最小，那么头节点必须是链表里面的最小值（确定头节点），而下一节点为头节点的前驱节点和后继节点中较小的一个（确定遍历方向）。
本题的解法并不难，难的是如何处理输入，将其合并成一个环状链表。系统中采用的核心代码模式，只需补充解法类的实现代码即可，这里给出的是完整代码。
from re import compile
from xmlrpc.client import MAXINT
inp = input()
lss = compile('\d+').findall(inp)
ring = dict()
head = MAXINT
for i in range(len(lss)-1):ring[int(lss[i])] = int(lss[i+1])head = min(head, int(lss[i]))rering = {v : k for k, v in ring.items()}
pre = rering[head]
nex = ring[head]
res = '{' + str(head) + ','
if pre < nex:for i in range(len(rering)-1):res += str(rering[head]) + ','head = rering[head]
if pre > nex:for i in range(len(ring)-1):res += str(ring[head]) + ','head = ring[head]
print(res[:-1] + '}')
题目五：买卖股票
现在有一个长度为n的价格数组a，表示某只股票每天的价格。每天最多可以买入或卖出该只股票的一股，买入或者卖出没有手续费，且卖出股票前必须手里已经有股票才能卖出，但是持有的股票数目不受限制，并且初始资金为m元，在任何时刻都不能进行透支，即资金必须始终大于等于0。请问在n天结束之后，拥有的最大总资产是多少？其中总资产 = 股票数目 * 股票价格 + 现金。
输入：
第一行包括两个整数n和m，分别表示天数和初始资金。
第二行包括n个整数，分别表示该只股票每天的价格。
输入示例：
6 2
2 3 1 1 1 2
输出示例：
6
思路
动态规划，01背包的变种。定义dp[i][j]代表前i天，手上当前持有j只股票的最大现金数，那么可以根据每天选择买入还是卖出达成转移。
n, m = map(int, input().split())
prices = list(map(int, input().split()))
prices.insert(0, -1e16)
dp = [[-1e16 for i in range(n+2)] for j in range(n+2)]
dp[0][0] = m
for i in range(1, n+1):for j in range(n+1):# 今天不买不卖的情况nodo = dp[i-1][j]# 今天买入一股的情况buy = -1e16if j > 0 and dp[i-1][j-1] >= prices[i]:buy = dp[i-1][j-1]-prices[i]# 昨天卖出一股的情况sell = dp[i-1][j+1]+prices[i]# 取资金数目最大的一种dp[i][j] = max(nodo, buy, sell)res = -1e16
for i in range(n+1):res = max(res, dp[n][i] + i*prices[n])print(res)
凉梦空间
欢迎你进入我的个人博客网站参观交流：https://www.liangmeng.xyz
