面试之前的一些问题总结

牛客网线上笔试

数据的读入:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#数据输入格式为:
# 5
# 1 2
# 5 3
# 4 6
# 7 5
# 9 0

import sys

num = sys.stdin.readline().strip()
num = int(num)
data = []
for i in range(num):
line = sys.stdin.readline().strip()
if line == '':
break
line = [int(val) for val in line.split(' ')]
data.append(line)
## 成功读到data

最终答案需要print输出

1
print(result)

collections库的用法

counter

1
2
3
4
5
6
7
8
9
10
from collections import Counter
count = Counter(['a','b','b','c','d','b','a'])
print(count)
# Counter({'b': 3, 'a': 2, 'c': 1, 'd': 1})
count.items()
# Out[6]: dict_items([('a', 2), ('b', 3), ('c', 1), ('d', 1)])
list(count.elements())
# Out[10]: ['a', 'a', 'b', 'b', 'b', 'c', 'd']
count.most_common()
# [('b', 3),('a', 2), ('c', 1), ('d', 1)]

defaultdict

1
2
3
4
5
from collections import defaultdict
dicto = defaultdict(list) # 不需要判断元素是否已经存在key中,存入参数为values对应的类型
dicto['lei']
# dicto:{'lei':[]}
dicto.pop('lei')

python的map函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def double(x):
return x ** 2

nums = [1,2,3,4]
res = list(map(double,nums)) # res = [1,4,9,16]
map # 传参数只能传入一个参数,或者选择将参数组合起来,作为整体输入

def bigger(x):
if x[0] > x[1]:
return x[0]
bb = [1,2,3,4,5]
val = [3,3,3,3,3]
cc = list(zip(bb,val))
result = list(map(bigger,cc))
print(result)# [None,None,None,4,5]

lambda表达式

1
2
3
4
5
6
7
8
9
g = lambda x:x+1 # 输入的参数为x,输出x+1的结果
f = lambda a,b:a*b # 传入多个参数
# lambda配合其他函数使用
filter(lambda x:x>3,alist)
sorted(alist,key = lambda x:(x[1],x[0])) # 按照不同的列进行排序
sorted(alist,key= lambda x:abs(x-5)) # 按照和5的距离排序
map(lambda x:x**2,alist) # 对数组元素都做lambda运算
reduce(lambda a,b:a+b,alist) # reduce两个元素算完放回list
# 如[1,2,3,4,5]计算如 ((((1+2)+3)+4)+5)

bisect库

使得有序列表插入仍保持有序,函数返回值是插入的位置:

1
2
3
4
5
6
7
8
9
10
import bisect

bisect.bisect_left(alist,target,lo=0,hi=len(alist))
# 其中alist是有序数组,target是插入的目标,如果target存在,就返回target的左边
bisect.bisect_right(alist,target,lo=0,hi=len(alist))
bisect.bisect(alist,target,lo=0,hi=len(alist))
# 均返回插入点的右侧的
bisect.insort_left(alist,target,lo=0,hi=len(alist))# 找到插入点,并插入元素,左插
bisect.insort(alist,target,lo=0,hi=len(alist))
bisect.insort_right(alist,target,lo=0,hi=len(alist))# 找到插入点,并插入元素,右插

random

生成一个0-1之间的随机数。

1
2
import random
random.random()

CPP的基本语法

vector(python中对应list)

1
2
3
4
5
6
7
vector<int> arr;
int len = arr.size();
arr.push_back(1); // 末尾加入元素
arr.pop_back(); // 删除最后一个变量
arr.empty(); // 判断是否为空
arr.erase(arr.begin() + 3);//删除指针指向的元素
arr.insert(arr.begin() + 1,4);// [1,2,3] -> [1,4,2,3]

Map(python中对应map)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<utility>
#include<string>
#include<iostream>
using namespace std;
pair<int,string> p(1,'lala');
cout << p.first << p.second;
#include<map>
map<char,string> m;
m['a'] = 'abc';
cout<<m['a'];
for(auto& x:m){
cout<<m.first << m.second;
}
m.erase(key);
m.erase(m.begin());
auto it = m.find(key); // 若存在则返回迭代器,否则返回指向末尾的迭代器m.end();
if(it == m.end()){
cout <<'none';
}
else{
cout<<it->first<<it->second;
}
m.size();

set (对应python中的set)

1
2
3
set<int> s;
s.insert(1); // set中的元素都是唯一的
// erase,find那些方法都和map差不多

面试题

输入两个整数 n 和 m,从数列1,2,3,…….,n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = 10
m = 8

def getList(n,m,lists,ans):
if m == 0:
ans.append(lists[::])
return
if m < 0 or n <=0:
return
getList(n-1,m,lists,ans)

lists.append(n)
getList(n-1,m-n,lists,ans)
lists.pop()
ans = []
getList(n,m,[],ans)
print(ans)

查找两个字符串a,b中的最长公共子串。若有多个,输出在较短串中最先出现的那个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
s1 = 'abcdefgeeeeeeeeee'
s2 = 'abcdefgaeeeeeeee'

def get_longest_str(s1,s2):
if len(s1) < len(s2):
s1,s2 = s2,s1
# s1 > s2
max_len = 0
max_start = 0
dp = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]
for i in range(1,len(s1)+1):
for j in range(1,len(s2)+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
if dp[i][j] > max_len:
max_len = dp[i][j]
max_start = j - max_len
return s2[max_start:max_start + max_len]

print(get_longest_str(s1,s2))