训前编码训练
共21题，已完成14题
1、出栈顺序可能性
题目描述：已知某一个字母序列，把序列中的字母按出现顺序压入一个栈，在入栈的任意过程中，允许栈中的字母出栈，求所有可能的出栈顺序
题解：每一个时刻都有两种的可能性，出栈和入栈。所以我们只要保存每一个时刻产生的栈和结果，依次进行下一步，等所有的栈的为空的时候，我们要的所有的可能性就收集完整了。
import sys
## 获取输入数据
strings = sys.stdin.readline().strip()
## 手动反转字符串
new_strings = ''
for s in strings:
new_strings = s+new_strings
## 初始化长度和结果
length = len(new_strings)
res = []
## 递归函数
def process(data, stack, result, length):
## 记录结果
if len(result) >= length:
res.append(result)
return
## 入栈
if len(data)>0:
d = data[-1]
new_data = data[:-1]
new_stack = stack + d
new_result = result
process(new_data, new_stack, new_result, length)
## 出栈
if len(stack)>0:
new_result = result+ stack[-1]
new_stack = stack[:-1]
new_data = data
process(new_data, new_stack, new_result, length)
process(new_strings, '', '', length)
for r in res[-1::-1]:
print(r)2、最优二叉树
题目描述：有一个节点数组，需要创建一棵最优二叉树，即每个节点的权值乘以节点在树中的长度，然后相加得到的值最小。以下图一为例，节点数组的[A,B,C,D,E]的权值分别为[15,7,6,6,5]，构建好的最优二叉树见图二。
题解：最优二叉树也为哈夫曼树，构造哈夫曼树的步骤如下：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
import sys
## 树节点
class node:
def __init__(self, val):
self.left = None
self.right = None
self.parent = -1
self.val = val
## 构建树函数
def build_tree(arr, cnt):
while True:
## 定义两个最小的树
min1 = -1
min2 = -1
root_node = 0
## 找到这两个最小的树
for i in range(0, cnt):
if arr[i].parent >= 0: continue
root_node += 1
if min1 < 0:
min1 = i
elif arr[i].val < arr[min1].val:
min2 = min1
min1 = i
elif min2 < 0:
min2 = i
elif arr[i].val < arr[min2].val:
min2 = i
## 若剩余无父节点树小于两个，退出
if root_node < 2: break
## 合并这两个最小的树
arr[cnt].left = min2
arr[cnt].right = min1
arr[cnt].val = arr[min1].val + arr[min2].val
arr[cnt].parent = -1
arr[min1].parent = cnt
arr[min2].parent = cnt
cnt += 1
## 返回最后一个合并完的节点位置
return cnt
## 定义100个节点集合
node_arr = []
for n in range(100):
node_arr.append(node(-1))
## 初始化获取的节点数据进入集合中
number = int(sys.stdin.readline().strip())
value = sys.stdin.readline().strip().split(' ')
for n in range(number):
node_arr[n].val = int(value[n])
## 构建哈夫曼树
cnt = build_tree(node_arr, number)
## 根据要求打印数据
print('```mermaid')
print('graph TD')
for n in range(cnt):
if n < number:
print('\tn{}[n{}:{}]'.format(n, n, node_arr[n].val))
else:
print('\tn{}(({}))'.format(n, node_arr[n].val))
if n < cnt-1:
print('\tn{} --> n{}'.format(n, node_arr[n].parent))
print('```')3、字符串匹配
题目描述：函数match检查字符串str是否匹配模板pattern，匹配则返回0，否则返回-1。模板支持普通字符(a-z0-9A-Z)及通配符?和。普通字符匹配该字符本身，?匹配任意一个字符，匹配任意多个任意字符。比如字符串abc对下述模板的匹配结果为：
模板 结果 模板 结果
abc 0 ab -1
a 0 ab? 0
ac 0 a? -1
*题解*：分别对？和进行特别的解析，加上是否完成判断即可
import sys
string = sys.stdin.readline().strip()
pattern = sys.stdin.readline().strip()
## 定义字符串和模板长度，各自匹配起始位置
s_length = len(string)-1
p_length = len(pattern)-1
s_match = 0
p_match = 0
## 定义结果
res = 0
## 遍历模板
for p in pattern:
## 解析字符？
if p == '?':
s_match += 1
p_match += 1
## 解析字符*
elif p == '*':
## 是否已经为模板最后一个字符
if p_match == p_length:
res = 0
break
status = 0
## 找到模板下一个字符在字符串中相等的位置
for i in range(s_match+1, s_length+1):
if pattern[p_match+1] == '*': break
elif pattern[p_match+1] == '?': break
## 如果不相等，判断是否已经匹配到字符串末尾
if pattern[p_match+1] != string[i]:
if i == s_length:
status = 1
break
## 相等则退出
else:
break
## 判断是否匹配完成，否则继续向下匹配
if status == 1:
res = -1
break
else:
s_match =i
p_match += 1
## 判断模板字符和字符串字符是否相等，相等则继续往下匹配，否则匹配失败
elif p == string[s_match]:
p_match += 1
s_match += 1
else:
res = -1
break
## 当前模板是否没有匹配完而字符串已经用完了
if p_match<p_length and s_match > s_length:
res = -1
break
## 当前模板已匹配完而字符串还有剩余
if p_match >p_length and s_match<=s_length:
res = -1
## 按格式要求输出结果
if res == 0: print('match')
else: print('unmatch')
4、字符串解析
题目描述：以下函数解析字符串str是否合法的C语言字符串字面值定义(不考虑八进制和十六进制字符编码)，如果是，则将解码后的内容保存到buf中，并返回0，否则返回-1。比如，"hello "sangfor""解码后结果为hello "sangfor"，请完成该函数代码：
题解：对于转义的字符分别进行处理即可。
special_chr = {'a':'\a', 'b':'\b', 'f':'\f',
'n':'\n', 'r':'\r', 't':'\t',
'v':'\v', '0':'\0'}
import sys
string = sys.stdin.readline().strip()
res = 0
if string and string[0] == '\"': string = string[1:]
else: res = -1
if string and string[-1] == '\"':string = string[:-1]
else: res = -1
length = len(string)-1
skip_index = -1
buf = ''
for index, s in enumerate(string):
if index == skip_index: continue
if s == '\'':
res = -1
break
elif s == '\"':
res = -1
break
elif s == '\\':
if index == length:
res = -1
break
next_s = string[index+1]
if next_s == '\'' or next_s == '\"' or next_s == '\\':
buf += next_s
skip_index = index +1
elif special_chr.get(next_s, False):
buf += special_chr.get(next_s)
skip_index = index +1
else:
res = -1
break
else:
buf += s
if res != -1: print(buf)
else: print('error')5、二进制位反序
题目描述：编写函数reverse，将val(32位无符号整数)的二进制位反序。比如，如果val的二进制表示为1011000011111111，反序后val的二进制表示为1111111100001101。
题解：先把十六进制转换二进制反转再转换十六进制就可
import sys
string = sys.stdin.readline().strip()
n = len(string[2:])
d = str(bin(int(string, 16))[2:])
for i in range(len(d),4*n):
d = '0' + d
d = d[::-1]
new_s = ''
for i in range(0, len(d), 4):
new_s += str(hex(int(d[i:i+4],2))[2:])
for i in range(len(new_s),8):
new_s += '0'
print(new_s)
6、集合遍历
题目描述：有K种颜色的小球(K<=10)，每种小球有若干个，总数小于100个。
现在有一个小盒子，能放N个小球(N<=8)，现在要从这些小球里挑出N个小球，放满盒子。
想知道有哪些挑选方式。注：每种颜色的小球之间没有差别。
请按数字递增顺序输出挑选小球的所有方式。
如有3种颜色，每种颜色小球的个数分别为a:1,b:2,c:3，挑出3个小球的挑法有：
003,012,021,102,111,120
题解：暴力破解时间过长，还是看了别人大佬的代码才解出来，还是太菜了。用递归的方法，每一位扣去使用的数量，最后满足条件的记录即可。
import sys
K, N = list(map(int, sys.stdin.readline().split()))
def backtrace(i, my_dic, cnt, res, s):
if i == K and cnt == N:
res.append(''.join(s))
elif i < K:
for use in range(my_dic[i] + 1):
if use <= N - cnt:
s.append(str(use))
backtrace(i + 1, my_dic, cnt + use, res, s)
s.pop()
else:
break
my_dic = {}
for i in range(K):
my_dic[i] = int(sys.stdin.readline().strip())
res = []
backtrace(0, my_dic, 0, res, [])
for r in res:
print(r)7、连接跟踪
题目描述：现在某Sangfor安全设备检测到网络上的多个数据包，并且知道这些数据包的源IP、源端口、目的IP、目的端口 这四个信息，请你判断这些数据包分别属于哪一条TCP连接。如果这个数据包属于以前出现过的某条连接，则请你输出这条TCP连接的编号；如果这个数据包属于新的TCP连接，则请你给这个TCP连接分配并输出一个新的TCP连接编号。新的TCP连接编号从1开始分配，每次加一。
题解：这个题用Python的dict来做的话非常简单，只要匹配是否相等即可
import sys
n = int(sys.stdin.readline().strip())
new_d = {}
start = 1
res = []
for i in range(n):
ip = sys.stdin.readline().strip()
if new_d.get(ip,False):
res.append(new_d.get(ip))
else:
new_d[ip] = start
res.append(start)
start += 1
for r in res:
print(r)
8、下棋
题目描述：8x8的棋盘上，布有黑白两色棋子，白子先下，当白子下N手后，棋盘上最多有可能留下多少颗白子？
下法规则：
1.每次落子后，以该棋子为中心的8个方向(米字形的8条直线)，如果有同色棋子，
且两个同色棋子之间连续排列着若干个异色棋子，无空白及同色棋子。则，这次落子可以把这些夹在中间的异色棋子全部翻色（即黑变白，白变黑）。
2. 黑白子交错落子。
3. 如果一个位置上有棋子，不能继续在该位置上落子；
4. 如果一个位置上落子后，不能翻对手的棋子，则该位置不能落子；
题解：这道题卡了很久，实在没有什么思路，后来看了些大佬的写法，思路如下：
1.全遍历整个棋盘，找到可以转变颜色的位置，记录下来
2.计算转变颜色后白色棋子的总数，把数量最多的白棋颜色记录下来
但是一次次去全部算，会陷入时间长的问题，所以这种解法只过了80%
import sys
import copy
def find(board, i, j, di, dj, clr, rev):
i += di
j += dj
cnt = 1
while i >= 0 and i <8 and j>=0 and j <8:
if board[i][j] == clr: return cnt
elif board[i][j] != rev: return 0
i += di
j += dj
cnt += 1
return 0;
def set(board, i, j, di, dj, cnt, clr):
for x in range(cnt):
board[i][j] = clr
i += di
j += dj
def dfs(cnt_step, board):
global ans, n
if cnt_step == n:
cur = 0
for i in range(8):
for j in range(8):
if board[i][j] == 2:
cur += 1
ans = max(ans, cur)
else:
clr = 2 - (cnt_step%2)
rev = 3 - clr
next_board = [[0]*8 for i in range(8)]
for i in range(8):
for j in range(8):
if board[i][j] == 0:
flag = False
for di in range(-1, 2):
for dj in range(-1, 2):
if di==0 and dj==0: continue
cnt = find(board, i, j, di, dj, clr, rev)
if cnt > 1:
if not flag:
next_board = copy.deepcopy(board)
flag = True
set(next_board, i, j, di, dj, cnt, clr)
if flag: dfs(cnt_step+1, next_board)
n = int(sys.stdin.readline().strip())
n = 2*n -1
board = []
for i in range(8):
board.append(list(map(int,sys.stdin.readline().strip().split(' '))))
ans = 0
if n <= 0:
print(0)
else:
dfs(0, board)
print(ans)9、长方体的摆放
题目描述：一个长方体，长宽高分别为x,y,z，都为自然数。
现在要把若干个相同的立方体摆成高为N的一根柱形体。
每层摆1个，如果两种摆法的高度是一样的，则认为这两种摆法等价，所以每层只有三种摆法。
求一共有多少种摆法。
题解：因为每一层都有三种的可能，有一种解法就是暴力解，利用递归每一层3种可能去计算，当然也会有时间过长无法通过的部分。所以换一个思路，就是从类似动态规划，当前的高度是由下面的几种可能的高度的数量构成的，总的层数肯定比最短的一面堆起来所用的层数低。
n = int(input())
a, b, c = list(map(int, input().split()))
max_layer = int(n // min(a, b, c))
dp = [[0] * (n + 1) for i in range(max_layer + 1)]
dp[0][0] = 1
for i in range(1,len(dp)):
for j in range(len(dp[0])):
if j - a >=0:
dp[i][j] += dp[i-1][j-a]
if j - b >=0:
dp[i][j] += dp[i-1][j-b]
if j - c >=0:
dp[i][j] += dp[i-1][j-c]
result = 0
for line in dp:
result += line[n]
print(result)
10、IP段合并
题目描述：一个数字段由首尾两个数字标识，表示一个自然数集合，
比如数字段[beg, end)表示从beg到end之间的所有自然数，
包含beg，但不包含end。
有若干个数字段，这些数字段之间可能有重叠，
怎么把这些数字段合并去重，用最少个数的数字段来表示。
合并前后，整个集合包含的数字不发生变化。
题解：这个题目可以先按照每个数字段的beg排序，排序完后两两对比时候可以合并就可
import sys
n = int(sys.stdin.readline().strip())
data = []
res = []
for i in range(n):
data.append(list(map(int, sys.stdin.readline().strip().split(' '))))
data.sort(key= lambda x:x[0])
res.append(data[0])
for r in data[1:]:
if r[0] <= res[-1][1]:
res[-1][1] = max(r[1], res[-1][1])
else:
res.append(r)
for r in res:
print(r[0], r[1])11、组词
题目描述：判断所给的字符串是否由所给的词典中的若干个词组成。
如已知词典["code", "sangfor", "org"]
则字符串"codesangfororg" 由上述词典组成，
字符串"codesangforsangfororg" 也由上述词典组成，
但字符串"sangforcom" 则不由上述词典组成。
题解：1、记录已知词典
2、查找字符串开头是否还有词典中的词，找到后就裁剪，继续找，最后全部裁剪完即为是组成字符串
import sys
number = int(sys.stdin.readline().strip())
word = []
for i in range(number):
word.append(sys.stdin.readline().strip())
sentence = sys.stdin.readline().strip()
while sentence:
find = False
for w in word:
if sentence[:len(w)] == w:
find = True
sentence = sentence[len(w):]
break
if not find:
break
if not find: print('no')
else: print('yes')12、最佳路线
题目描述：有A、B、C、D、E、F 6个城市，假如某人驾车，A到B需要12个小时，C到D需要3个小时，B到C需要10个小时，D到E需要4个小时，C到F需要6个小时，F到A需要16个小时，E到F需要2个小时，B到F需要7个小时，C到E需要5个小时，求任意给定的两地之间的最佳驾驶路线。
题解：把路线记录成dict形式，然后递归去查找路线，记录以往的经过点，如果再次经过就结束，找到能够到达的路线，计算路途长度，返回即可。
data = {'A':{'B':12, 'F':16},
'B':{'C':10, 'F':7},
'C':{'D':3, 'F':6, 'E':5, 'B':10},
'D':{'E':4, 'C':3},
'E':{'F':2, 'C':5, 'D':4},
'F':{'A':16, 'B':7, 'C':6, 'E':2}}
import sys
start, end = sys.stdin.readline().strip().split()
def findpath(start, road, cur, end, res, path):
if cur == end:
res.append(list(road+[path]))
elif cur in road[:-1]:
return
else:
for key in data[cur].keys():
road.append(key)
path += data[cur][key]
findpath(start, road, key, end, res, path)
path -= data[cur][key]
road.pop()
res = []
if start == end:
print(0)
print(start, end)
else:
findpath(start, [start], start, end, res, 0)
res.sort(key=lambda x: x[-1])
print(res[0][-1])
print(' '.join(res[0][:-1]))13、二叉树序列化
题目描述：二叉树序列化可以基于先序/中序/后序/按层等遍历方式进行。
现输入二叉树层次遍历序列，请输出其前序遍历序列。
如有二叉树如下：
0
/
1 2
/
3 4
\ /
5 6
其层次遍历序列为：0, 1, 2, 3, #, #, 4, #, 5, 6, #
其先序遍历序列为：0, 1, 3, #, 5, #, #, #, 2, #, 4, 6, #, #, #
（其中空用"#"代替）
题解：首先是反序列化，把树构建出来，然后再先序遍历即可，要留意的是补充‘#’
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
def deserialize(data):
i = 1
root = Node(data[0])
queue = [root]
while queue:
node = queue.pop(0)
if i == len(data):
break
new_node = Node(data[i])
if data[i] != '#':
queue.append(new_node)
node.left = new_node
i += 1
if i == len(data):
new_node = Node('#')
node.right = new_node
break
new_node = Node(data[i])
if data[i] != '#':
queue.append(new_node)
node.right = new_node
i += 1
return root
def front(data):
res = []
queue = [data]
node = data
while queue:
while node:
queue.append(node)
res.append(node.val)
if not node.left and not node.right and node.val != '#':
res.append('#')
res.append('#')
node = node.left
node = queue.pop().right
return res
import sys
number = int(sys.stdin.readline().strip())
data = []
for n in range(number):
data.append(sys.stdin.readline().strip())
if data:
root = deserialize(data)
res = front(root)
for r in res:
print(r)
else:
print('#')
14、LRU
题目描述：设计实现一个LRU（Least Recently Used）缓存器
LRU有如下两个方法：
int get(int key) - 从缓存中取值，返回key对应的value（值总是一个正数）， 如不存在返回 -1。
void set(int key, int value) - 往缓存中存键值对。 当缓存达到容量限制时，令“最近最少使用” 的键值对失效。
根据输入内容操作该LRU缓存器，输出LRU缓存器每个get的结果。
题解：非常经典的题目，主要思路还是理解LRU的实现结果，就是哈希表加链表，理解它的作用和过程就可以完成本题。
class DLinkedNode:
def __init__(self):
self.val = 0
self.pre = None
self.next = None
self.key = 0
class LRUCache:
def __init__(self, limit):
self.cache = {}
self.size = 0
self.limit = limit
self.head, self.tail = DLinkedNode(), DLinkedNode()
self.head.next = self.tail
self.tail.pre = self.head
def add_node(self, node):
node.pre = self.head
node.next = self.head.next
self.head.next.pre = node
self.head.next = node
def remove_node(self, node):
node.pre.next = node.next
node.next.pre = node.pre
def move_to_head(self, node):
self.remove_node(node)
self.add_node(node)
def pop_tail(self):
node = self.tail.pre
self.remove_node(node)
return node
def get(self, key):
node = self.cache.get(key, None)
if node:
self.move_to_head(node)
else:
return -1
return node.val
def put(self,key, value):
node = self.cache.get(key, None)
if not node:
node = DLinkedNode()
node.key = key
node.val = value
self.cache[key] = node
self.add_node(node)
self.size += 1
if self.size > self.limit:
del_node = self.pop_tail()
del self.cache[del_node.key]
self.size -= 1
else:
node.val = value
self.move_to_head(node)
import sys
N, L = sys.stdin.readline().strip().split( )
N = int(N)
L = int(L)
cache = LRUCache(N)
for i in range(L):
operation = sys.stdin.readline().strip().split(' ')
if operation[0] == 's':
cache.put(operation[1], int(operation[2]))
elif operation[0] == 'g':
d = cache.get(operation[1])
print(d)
泰隆银行HR面5人在聊
查看13道真题和解析
