讨论/求职面试/面试题|请教各位大佬一道字节笔试题目/
面试题|请教各位大佬一道字节笔试题目

本渣渣不久前参加了字节的校招笔试,有一道题想了很久依旧没有思路,想要请教一下各位

题目描述

某某作家有n本小说,评委会要对该作家的写作进行打分。需要从中挑选两本小说进行计分,计分规则如下:

  • 每本小说有5个方面的评价指标
  • 两本小说进行合并计分,每个方面的分数选两本小说高分作为这个方面的得分
  • 两本小说可以从n本中任意挑选,然后选取合并计分后的五个方面的最低分作为该作家的得分。

要求求出小说家得分最高的两本小说的索引


测试样例与说明

数据的第一行两个数字代表小说家的数目m和每位小说家的小说数量n,
接下来的m*n行为每本小说五个维度的得分

2 3
1 2 3 4 5
2 3 4 5 6
5 4 3 2 1

1 1 1 1 1
2 2 2 2 2
3 3 3 3 3

预期答案:

2 3
2 3

解释:

第一位小说家第2和第3本小说的综合得分为5 4 4 5 6,最低分为4分,因此选第2和第3本小说小说家得分为4分,是最高得分组合。
第二位小说家同理。


我的做法

我简单的用暴力法进行搜索,结果一个测试样例都过不了,说明此题要求不能用暴力法,实在想不到思路,求各位大神解答。

6
共 46 个回复

二分答案,将问题转化为检测是否存在得分不低于ans的方案,这样每本小说的每个方面评分就变成了满足(1)和不满足(0)。你只需要找出是否存在两个小说满足互补,此时即便暴力枚举也只需要32*32次检测。

17

按最高赞的思路写的, 感觉还不错

def solve(n=3, A=[[1,2,3,4,5],[2,3,4,5,6],[5,4,3,2,1]]):
    # O(31*( 5*n + 4**5 ))
    # all index from 0
    assert n>=2
    ans = ()
    def judge(finalScore):
        nonlocal ans
        seen = {}
        for i,scores in enumerate(A):
            sta = 0
            for e in scores:
                sta=sta*2+(e>=finalScore)
            # example [1,2,3,4,1], finalScore=3
            # sta = 0b00110
            seen[sta]=i
        
        for i in range(32):
            for j in range(32):
                if (i|j==31) and i in seen and j in seen:
                    # 保证不会选到相同的书
                    if i==j: # if i==j==31:
                        if seen[i]+1<len(A):
                            ans = (seen[i]+1, seen[j])
                        else:
                            ans = (seen[i]-1, seen[j])
                    else:
                        ans = (seen[i], seen[j])
                    return True

        return False
    
    l=0
    r=2**31-1
    while l<r:
        m=l+(r-l)//2
        if not judge(m):
            r=m
        else:
            l=m+1
    # Highest score is l-1
    return ans[0]+1,ans[1]+1 # answer index start from 1
4

这什么阴间题目啊,读都读不懂。

2
2

从前两本书(即前两行)往下遍历,用两个int或一个int[2]保存当前最高得分对应的两行所在的索引,用一个int[n]数组保存当前得分最高的两本书对应的各项临时得分结果。

从第三行起,计算每一列的元素-当前临时结果中元素的差值,累加每列的差值,完成一行遍历后,如果总差值大于0,说明当前这行对“靠近最高得分”的贡献为正:因为临时结果已经是历史遍历过程中的最高得分,所以如果总差值为正,表示这一行可以替代历史结果中的某一行。此时去遍历已记录的历史最高得分对应那两行,看哪一行跟当前行能组成更高总得分。然后更新索引。

没写代码,只想了思路,不知道对不对,对的话总复杂度应该是O(m*n),m对应书的数量,n代表指标数量,这里n应该固定为5。

2

确实有点问题,貌似还得枚举一维度的,再算剩下四维度的。。这样应该没什么问题了

2

大概率正确, 而且代码改一下有些情况下是比二分(官方标答)时间复杂度更优的, 我已经在CF上测过了
O(mnlog(mn)+4m)O(mnlog(mn)+4^m)


def solve(V):
	n, m = len(V), len(V[0])
	entrys = []
	for i,v in enumerate(V):
		for di,entry in enumerate(v):
			entrys.append((i,di,entry))
	entrys.sort(key=lambda t:-t[2])
	nsta = 2**m
	masks = [0]*n 
	seen = {}
	ans = () # index of vi,vj and Y
	for i,di,entry in entrys:
		masks[i]|=2**di
		if masks[i] not in seen:
			seen[masks[i]] = (i,entry)
		if masks[i] = nsta-1:
			ans = (i,i,entry)
			break
	for i in range(nsta):
		for j in range(nsta):
			if ((i|j)==nsta-1) and i in seen and j in seen:
				curY = min(seen[i][1],seen[j][1])
				if ans[2] < curY:
					ans = (seen[i][0], seen[j][0], curY)
	return ans
1
public static void main(String[] args) {
    //m:小说家人数,
    //n:每位小说家有n本书
    int m = 2, n = 3;
    int[][] a = {
            {1, 2, 3, 4, 5},
            {2, 3, 4, 5, 6},
            {5, 4, 3, 2, 1},

            {1, 1, 1, 1, 1},
            {2, 2, 2, 2, 2},
            {3, 3, 3, 3, 3},
    };
    f(m, n, a);
}

https://www.cnblogs.com/yanchuanbin/p/14765020.html

请各位指点下,有没有问题

2

不一定正确

#include<bits/stdc++.h>
using namespace std;

struct node{
    //第几本书
    int id;
    //本书的第几个评价
    int p;
    //分值
    int val;
};

int main(){
    int t;
    scanf("%d",&t);
    //样例数目
    while(t--){
        int n;
        scanf("%d",&n);
        vector<node> arr(5*n);
        int cnt = 0;
        for(int i =0;i<n;i++){
            for(int j =0;j<5;j++){
                //第i本书
                arr[cnt].id = i;
                //第j个评价
                arr[cnt].p = j;
                //分值
                scanf("%d",&arr[cnt].val);
                cnt++;
            }
        }
        sort(arr.begin(),arr.end(),[](node& n1,node& n2){
            if(n1.val!=n2.val){
                return n1.val>n2.val;
            }
            return n1.id<n2.id;
        });
        //记录最大值
        int mx = -1;
        vector<int> ans(2,INT_MAX);
        vector<int> tmp(2,INT_MAX);
        //his[i]记录掩码为i的最小的两个id
        vector<vector<int>> his(1<<5,vector<int>(2,INT_MAX));
        //记录每本书已经访问的掩码
        vector<int> mask(n,0);
        int target = (1<<5)-1;
        for(int i =0;i<arr.size();i++){
            if(arr[i].val<mx){
                break;
            }
            int id = arr[i].id;
            mask[id]|=(1<<arr[i].p);
            if(mask[id]==target){
                ans[0] = id;
                ans[1] = id==0?1:0;
                if(ans[0]>ans[1]){
                    swap(ans[0],ans[1]);
                }
                mx = arr[i].val;
                break;
            }
            for(int j =0;j<32;j++){
                if((j|mask[id])==target){
                    tmp[0] = id;
                    tmp[1] = his[j][0];
                    if(his[j][0]==id){
                        tmp[1] = his[j][1];
                    }
                    if(tmp[1]==INT_MAX){
                        continue;
                    }
                    if(tmp[0]>tmp[1]){
                        swap(tmp[0],tmp[1]);
                    }
                    if(tmp<ans){
                        ans = tmp;
                    }
                    mx = arr[i].val;
                }
            }
            if(his[mask[id]][0]>id){
                his[mask[id]][1] = his[mask[id]][0];
                his[mask[id]][0] = id;
            }else if(his[mask[id]][1]>id){
                his[mask[id]][1] = id;
            }
           
        }
        ans[0]++;
        ans[1]++;
        cout<<mx<<" "<<ans[0]<<" "<<ans[1]<<endl;
    }
    return 0;
}
1

贴主大佬没描述清楚状态压缩步骤
m个数的状态是有限的,5种评分下一本书满足条件的boolean值压缩成int后其上限为32
设判断是否存在两本小说能组合出target这个得分的方法为check()

boolean check(int target){
    //用于在32种场景之一上标记书的index
    int[] masks=new int[32];

    Arrays.fill(masks,-1);
    for(int i=0;i<books.length;i++){
        int[] b=books[i];
        int m=0;
        for(int j=0,mod=1;j<5;j++,mod<<=1){
            if(b[j]>=target) m|=mod;
        }
        masks[m]=i; //将书的index映射给场景
    }

    //遍历场景而非遍历书
    for(int i=0;i<32;i++){
        for(int j=0;j<32;j++){
            //...
        }
    }
}
1