首页 > 笔经面经 > 快手4.12AK笔经详细题解2020校招工程类B卷AC数投票

快手4.12AK笔经详细题解2020校招工程类B卷AC数投票 投票

头像
学!
编辑于 2020-04-13 03:22:59 APP内打开
赞 7 | 收藏 28 | 回复23 | 浏览4817



总体

4个算法题, 比昨天网易难度低两个档次, 前三题10行代码量, 第四题普通dfs
测试用例很少也很水, 也不排除内部会再测一次代码
题目截图可以参考 https://www.nowcoder.com/discuss/406358

第一题

括号匹配问题, 很常见的题目, 时间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



23条回帖

回帖
加载中...
话题 回帖

相关热帖

笔经面经近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐