笔试与面试算法

编程题（100，100，100），a 了前两道

1. 股票交易，N 天，M 只股票，初始资金 K，交易次数不限制，股票数额可不为整数

   贪心，当天与次天比较，计算利润，排序后取利润最大的一只股票，买入卖出，不存在则空仓

2. 实现 2048 游戏

   模拟，上下左右移动，合并相同的数字

3. ax + by + cz + dw == k, 0 <= x, y, z, w, k <= 10 ** 9, 0 <= a, b, c, d <= 2500, 求系数的最小字典序组合

   哈希，预处理 a，b，再枚举 c，d，查找 k - c * z - d * w 是否存在，直接比较字典序

选择题 30 分，编程题 70 分（20, 20, 30） 编程题前两题 a 了，最后一道 60%

1. 镜像大写字母的回文串

   双指针，判断是否为镜像大写字母，判断是否为回文串

2. 中位数位于奇数长度数组正中间的数组为好数组，求好数组的个数

   枚举中位数，左右两边的数的个数相等

3. 青蛙从 k 开始按指令跳跃，'L’向左跳，'R’向右跳，'?'随机跳，求终点的可能位置，跃出边界时保持不变

   贪心，先执行’L’和’R’指令，并计算’?'的个数，枚举每个位置，条件判断是否能够到达

编程题（100，100，100，100），除了第二道暴力拿了 40%，其他都 a 了

1. 走迷宫，按照指令走，求最终位置是否为（0，0）

   模拟

2. 给定左右边界，判断是否一个数的子串是 3 的倍数，求这种数的个数

   数论，鸽巢原理，长度超过 3 的子串必有 3 的倍数，子串前缀和可以解释，小于 1000 直接特判

3. 给定一个数组，求每个位置能够观察到的元素个数之和

   单调栈，加入哨兵，从右往左

4. 给定两个字符串，A 和 B，还有一个下标数组 idx，A[idx[i]] = B[i]，B 和 idx 中顺序随意调换，求字典序最小的 A

   贪心，保留 idx 中不同的元素，idx 和 B 排序，再次遍历 idx，将 B 中对应的元素放入 A 中

选择题 40 分，多选题 15 分，编程题 45 分（20，25） 第一道 80%，第二道 a 了

1. 给定数组，划分成 k 个子序列，求最大的子序列的最大差值的和

   双指针，贪心，排序后，每次取最大值和最小值

2. 分水果 m 个，相邻元素差值不超过 1，每个元素大于 0，求下标 k 的最大值

   二分查找，数列求和判断是否大于 m

选择题 40 分，多选题 20 分，编程题 40 分（20，20） 第一道 a 了 90%吧，第二道不会

1. 给定区间和权值，合理安排区间，求最大权值和

   贪心，排序后，贪心选择

2. 给定诸多点，求包围所有点的最小路径

   先求出所有点的凸包，再求路径

编程题 100 分（20，25，25，30），前两道 a 了，第三道 39%，我是用贪心做的，骗了点分

1. 见图片

   枚举，注意单独成队

2. 见图片

   bfs，注意从入度为 0 的点开始

3. 见图片

   dp

4. 见图片

   大模拟

单选题（10 分），多选题（30 分），编程题（60 分）

过于简单，ak 了

单选题（60 分），多选题（30分），编程题（10分） 分值这样安排很难受啊，结果就是没过，编程题只通过了50%

给定一个仅包含 'a'、'b'、'c' 的字符串 s，你只能对前缀做翻转操作（即 s[0:i+1] = reversed(s[0:i+1])），求最少操作次数使字符串变为 按字典序升序排列（即所有的 a 在前，b 在中，c 在后）

• 0 < n <= 13
• 0 < q <= 10 ** 6

from collections import deque

n, q = map(int, input().split())

def is_sorted(t):
	return all(t[i] <= t[i + 1] for i in range(len(t) - 1))

for _ in range(q):
	s = input()
	visited = set()
	queue = deque([(s, 0)])
	visited.add(s)
	
	while queue:
		cur, step = queue.popleft()
		if is_sorted(cur):
			break
		for i in range(1, len(cur) + 1):
			new_s = cur[:i][::-1] + cur[i:]
			if new_s not in visited:
				visited.add(new_s)
				queue.append((new_s, step + 1))
	print(step)

杂 ​

def reverseStack(st):
    if not st:
        return
    top = st.pop()
    reverseStack(st)
    insertAtBottom(st, top)

def insertAtBottom(st, item):
    if not st:
        st.append(item)
        return
    top = st.pop()
    insertAtBottom(st, item)
    st.append(top)