快手4.12AK笔经详细题解2020校招工程类B卷AC数投票
总体
4个算法题, 比昨天网易难度低两个档次, 前三题10行代码量, 第四题普通dfs
测试用例很少也很水, 也不排除内部会再测一次代码
第一题
括号匹配问题, 很常见的题目, 时间O(n) 空间O(n)
代码
s=input()
p=r=0
stack=[]
for c in s:
if c=='(':
stack.append(c)
elif c==')':
if stack:
p+=1
stack.pop()
else:
r+=1
print(p,len(stack),r) 第二题
描述
给一个整数N, 0<N<=1000
再给一个整数R, 0<R<=1000000
题目很难理解, 理解后就是问R能否表示成N进制数并且每个位上都是1或者0
是则输出R都在哪些位上是1(返回一个数组arr, arr[i]表示R从右往左第i位是1), 不是则输出 `[]`
算法
把R当作一个N进制数来处理, 判断R表示成N进制数是否每个位都是1或0
最优的算法时间复杂度
空间
通过的代码
这个代码写的不是很好, 时间import math
import bisect # 二分
class Solution:
def GetPowerFactor(self , R , N ):
upbound = math.ceil(math.log(R,N))
kth = [N**i for i in range(1+upbound)]
res = set()
varR = R
while varR != 0:
upbound = bisect.bisect_right(kth, varR) #相当于c++里面的upper_bound, kth中找第一个>varR的元素的索引
varR -= kth[upbound-1]
if upbound-1 not in res:
res.add(upbound-1)
else:
return []
return list(res) 改进的代码(未提交)
时间  "图片标题")
import math class Solution: def GetPowerFactor(self , R , N ): ans = [] for i in range(math.floor(math.log(R,N))+1): if R%N>1: return [] elif R%N==1: # R%N 表示 R在从右往左第i+1位上的数值 ans.append(i) R//=N return ans
第三题
描述
给两个长为n的整型数组a,b
给一个包含1,2,3,4...,n的n个数字的序列S, 数字i带有两种属性a[i-1]和b[i-1]
序列Sf是对S的排列(Permutation),
假设我们把序列Sf用数组表示
定义`cost := sum(i*a[e-1]+(n-i-1)*b[e-1] for i,e in enumerate(Sf))`题目要求找出Sf使得cost最小, 返回Sf
算法
交换两个元素不会改变其他元素贡献的cost, 因此此题可转化为一个基于比较的排序算法
我这种思路最优的算法时间其实能达到, 空间O(n)
因为`sum(i*a[e-1]+(n-i-1)*b[e-1] for i,e in enumerate(Sf))= sum( i*(a[e-1]-b[e-1]) + (n-1)*b[e-1] for i,e in enumerate(Sf) ) = (n-1)*sum(b) + sum(i*(a[e-1]-b[e-1]) for i,e in enumerate(Sf))`
因此只需要把数组按 a[e-1]-b[e-1] 的值从小到大排
通过的代码
时间 )
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
using namespace std;
class Solution {
public:
vector<int> WaitInLine(vector<int>& a, vector<int>& b) {
ios::sync_with_stdio(false); cin.tie(NULL);
int n = a.size();
vector<int> ans(n);
iota(all(ans),1);
sort(all(ans), [&](int l, int r){ // 这里lambda参数名搞错了, 其实l是在r的右边, return 1 就交换lr
auto il = find(all(ans), l) - begin(ans);
auto ir = find(all(ans), r) - begin(ans);
auto prv = il*a[l-1] + (n-il-1)*b[l-1]+ ir*a[r-1] + (n-ir-1)*b[r-1];
auto cur = ir*a[l-1] + (n-ir-1)*b[l-1]+ il*a[r-1] + (n-il-1)*b[r-1];
return cur<prv;
});
return ans;
}
}; 改进的代码(未提交)
时间 )
class Solution: def WaitInLine(self, a,b): ans = list(range(1,len(a)+1)) ans.sort(key=lambda e:a[e-1]-b[e-1]) return ans
第四题
描述
给一个例如下方所示的竖长为n, 横宽为m的长方形地图,
该地图用来表示工作位置,"*"表示该位置不能使用, "."表示该位置可以使用,
而且使用的工位不能上下左右相邻, 问最多能同时使用多少工位
*.**. *.*** *.**.
算法
标准dfs回溯, 具体怎么运作可以看代码
代码
时间 )
C表示地图中"."的数量; 辅助空间O(C)
class Solution: def GetMaxStaffs(self , pos ): n = len(pos) m = len(pos[0]) can=[] for i in range(n): for j in range(m): if pos[i][j]=='.': can.append((i,j)) l = len(can) ma=0 # who: 现在开始研究第i个工位(i从0开始), i之前的工位都已经安排好了 # cnt: 目前已经使用了的工位数量 # 无返回值 def dfs(who, cnt): nonlocal ma if who==l: ma=max(ma, cnt) return i,j = can[who] # 是否有相邻的工位被使用 flag = 0 for d in [-1,0],[1,0],[0,1],[0,-1]: ni = i+d[0] nj = j+d[1] if 0<=ni<n and 0<=nj<m and pos[ni][nj]=='$': flag=1 if not flag: pos[i][j]='$' # 使用这个工位 dfs(who+1, cnt+1) # 先判断dfs(who+1, cnt+1) pos[i][j]='.' # 撤回这个工位 dfs(who+1, cnt) # 再判断dfs(who+1, cnt) dfs(0,0) return ma
