字节1015秋招笔试

字节1015笔试真题

好久都没更新秋招公司得笔试真题了，搞其他技术栈方面比较多。今天来看看字节大厂的题目，难度适中，没有特别绕的题目，但是发现很多题目，并没有现成的模板可以套，需要自己总结算法的思想加以应用。

​

1015.T1

1. 题目说明

小红有一个长度为n的01字符串，小红想知道最长的美丽连续子串是什么，输出它的长度。如果一个字符串的长度是偶数，且前一半全是0且后一半全是1或者前一半全是1且后一半全是0，那么这个字符串就是美丽串。

如0011，111000都是美丽串。

输入描述：

一行一个长度为n的01字符串。

​

输出描述：

输出一个整数表示答案。

示例1：

// 输入：
000001111011011

// 输出：
8

​

2. 解答分析

• 题目中存在两个比较重要的条件，一个是长度为偶数，一个是五五开含01。

• 对于这类的题目，我们可以找到最大的连续的0或1的个数，取相邻的两个数目的最小值，再在全体字符串中找到ans取最大值即可。

  ​

3. 具体代码

import java.util.Scanner;

public class title1 {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        String s= in.next();
        int n=s.length();
        int ans=0;
        int prev=0;

        for(int i=0;i<n;i++){
            int j=i;
            while(j<n && s.charAt(j)==s.charAt(i)){
                ++j;
            }

            int cur=Math.min(prev,j-i);//找到较小的连续字符串
            ans=Math.max(ans,cur);
            prev=j-i; // 更新前一次出现字符数量
            i=j-1;  // 将 i 赋值为 j-1，跳过上一次出现的连续字符，开始统计下一段连续字符。
        }
        System.out.println(ans*2);//返回最大的连续0或1的长度的两倍，由于cur取的是较小的值，所以较大的那个一定满足条件。
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n^2)$。(最坏的情况，所有的字符都是相等的)

    • 首先，读入输入数据的时间复杂度为 O(1)。
    • 接着，循环遍历输入字符串 s，时间复杂度为 O(n)。在每次循环中，内部使用一个 while 循环寻找当前字符连续出现的最长长度。由于 s 的长度为 n，因此 while 循环的时间复杂度为O(n)。在寻找当前字符连续出现的最长长度之后，还需要更新 ans 和 prev 的值，这两个操作可以在常数时间内完成。因此，单次循环的总时间复杂度为 O(n)。
    • 最后，输出结果的时间复杂度为 O(1)。

  • 空间复杂度：$O(1)$

    ​

1015.T2

1. 题目说明

坐标轴上有n个人,位置分别是a1,a2,... ,an，有n个物资,位置分别是b1,b2,...bn,每个人可以拿走一个物资,每个物资只能被一个人拿走,然后走到终点p,每个人走一步需要花费1的时间,每个人拿走物资的时间为0，问最终每个物资都运送到终点时,每个人所花费时间总和的最小值。

输入描述：

一行两个整数n,p,表示人数和终点位置。一行n个整数a1,a2,..,an,表示每个人的位置。一行n个整数b1,b2,...,bn,表示每个物资的位置。

​ $1\le n \le10^5,1\le p,a_i,b_i \le10^9$

​

输出描述：

输出一个整数，表示最短时间。

示例1：

// 输入：
3 3
1 4 3
2 5 6

// 输出：
11

// 说明
第一个人拿第一个物品花费时间1,走到终点花费时间1。
第二个人拿第三个物品花费时间2,走到终点花费时间3
第三个人拿第二个物品花费时间2,走到终点花费时间2。

​

2. 解答分析

• 对于个人而言，什么时候的移动次数最小？那当然是排序后，搬运最近的物品到最后的终点即可。

• 所以可以利用贪心算法，对人和物品的数组进行排序，从左到右依次增大，以此类推，一一对应地搬运肯定是最优的解。

  ​

3. 具体代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class title2 {
    
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int p=in.nextInt();
        int[] a=new int[n];
        int[] b=new int[n];	//下面将人和物品的数组填满
        for(int i=0;i<n;i++){
            a[i]=in.nextInt();
        }
        for(int i=0;i<n;i++){
            b[i]=in.nextInt();
        }
        //排序
        Arrays.sort(a);
        Arrays.sort(b);

        //贪心计算答案
        long ans=0;
        for(int i=0;i<n;i++){
            ans+=Math.abs(a[i]-b[i])+Math.abs(b[i]-p);//人和货物的距离+货物到终点的距离
        }
        System.out.println(ans);
        in.close();
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n)$

  • 空间复杂度：$O(1)$

    ​

1015.T3

1. 题目说明

小红是一名科学家,她正在研究一种植物的叶子。这种植物的叶子有两个特征:颜色和形状。小红一共有n片叶子需要研究,她按照顺序依次摘取。然而,小红的研究假设是,研究一片叶子时,如果发现曾经已经研究过相同颜色和形状的叶子,那么本次研究的知识减半**(向下取整)**。现在问题是,小红可以自由排序,选择研究的顺序,最多可以获得多少知识。

输入描述：

第一行一个正整数n,表示叶子的数量。

第二行n个正整数a1, a2,...,an,表示每片叶子的颜色。

第三行n个正整数b1,b2,...,bn,表示每片叶子的形状。

第四行n个正整数c1,c2…,cn,表示第一次研究可以获得知识,如果之前见过相同颜色和形状的叶子,则获得的知识是ci/2(向下取整)。

​ $1\le n \le10^5;1\le a_i,b_i \le10^9;1 \le c_i \le 10^4$

​

输出描述：

一个整数,表示最多能获得的知识。

示例1：

// 输入：
4
1 2 2 2
1 2 3 2
2 3 4 5

// 输出：
12

// 说明：
按照1，4，3，2的研究顺序，获得知识2 + 5 + 4 +（3/2）= 12

​

2. 解答分析

• 读题，本题需要记录最基础的两组数据：颜色和形状，再根据颜色和形状是否相同进行知识研究判断。

• 所以我们应该采用一种可以唯一确定两者关系的映射，自然而然想到HashMap。直接根据ai和bi建立哈希，对每一个key生成一个数组，存放ci，然后直接按照题目要求累加即可。

  ​

3. 具体代码

import java.util.*;

public class title3 {
    
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);

        //首先读入输入的数据
        int n=in.nextInt();
        int[] color=new int[n];
        int[] shape=new int[n];
        int[] a=new int[n];

        for(int i=0;i<n;i++){
            color[i]=in.nextInt();
        }
        for(int i=0;i<n;i++){
            shape[i]=in.nextInt();
        }
        for (int i=0;i<n;i++){
            a[i]=in.nextInt();
        }

        //计算答案
        long ans=0;
        HashMap<Long, List<Integer>>mp=new HashMap<>();
        for(int i=0;i<n;i++){
            long key=((long)color[i]*(long)(1e9+1))+shape[i];
            mp.computeIfAbsent(key,k->new ArrayList<>()).add(a[i]);//使用将研究知识添加到对应的列表中。
        }
        for(Map.Entry<Long,List<Integer>> entry:mp.entrySet()){//转化为集合
            List<Integer> v = entry.getValue();//获取列表的值
            v.sort(Collections.reverseOrder());//列表中的降序排列
            long cur = v.get(0);
            for (int i = 1; i < v.size(); i++) {
                cur += v.get(i) / 2;//遍历列表的其他元素，将其除以2并累加到 cur 中
            }
            ans += cur;//变量 ans 存储了小红能获得的累计的最大知识
        }

        // 输出答案
        System.out.println(ans);

        in.close();
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n*(m*logm+m))$

    1. 读入输入数据：需要遍历n个叶子，时间复杂度为O(n)。
    2. 构建哈希表：遍历n个叶子，在哈希表中插入或更新n个元素，每次插入/更新的时间复杂度为O(1)，因此总的时间复杂度为O(n)。
    3. 遍历哈希表条目：最坏情况下，哈希表中有n个不同的键，对于每个键，需要对其对应的列表进行排序和累积计算，假设列表的平均长度为m，则对每个键的操作的时间复杂度为O(m*logm+m)，因此遍历所有的键的时间复杂度为O(n*(m*logm+m))。
    4. 输出答案：时间复杂度为O(1)。

  • 空间复杂度：$O(n^2)$

    1. 输入数据的存储：需要用到三个整型数组 color[]、shape[] 和 a[]，它们的长度均为n，因此空间复杂度为O(n)。
    2. 哈希表和列表的存储：哈希表 mp 存储了每种颜色和形状组合对应的研究知识列表。最坏情况下，哈希表有n个不同的键，每个键对应的列表长度为n，因此哈希表和列表的总体空间复杂度为O(n^2)。

    ​

1015.T4

1. 题目说明

小红准备卖n个西瓜,已知每个西瓜的品质为ai。小红可以设置一个品质标准品质x，不小于x的西瓜为优质品。小红希望设置完品质标准x后,当顾客从左到右依次买瓜时，每个人买到优质品的概率都不小于P(顾客不知道哪个瓜是优质品,只知道剩下的瓜数量以及剩下的优质品数量)。小红想知道,x的最大值是多少?

​

输入描述：

第一行输入一个正整数n和一个正实数p,含义如题意所述。

第二行输入n个正整数ai,分别代表每个瓜的品质。

​ $1\le n \le2000001\le a_i\le10^9; 0\le q\le 1$

​

输出描述：

一个正整数,代表x的最大值。

示例1：

// 输入
4 0.5
5 3 9 6

// 输出：
6

// 说明：
当优质品标准设置为6时,第三个和第四个瓜是优质品：
第一个顾客买瓜时,买到优质品的概率是0.5。
第二个顾客买瓜时,买到优质品的概率是0.6666666。
第三个顾客买瓜时,买到优质品的概率是1。
第四个顾客买瓜时,买到优质品的概率是1。
可以证明,6为品质标准设置的最大值。

​

2. 解答分析

• 其实只看题目并没有清楚具体含义，通过示例可以看出，顾客从左往右买瓜时，是按照次序买的，即第一个人只能买第一个瓜，那么就比较直观了；

• 可以使用二分，枚举品质标准的设置值mid，再计算当品质标准为x时，是否满足买到优质品的概率不低于p。

• 这时候需要设定哨兵ok用于不断计算剩余的，取到优质瓜的概率cur。

  • 一旦此时的概率cur比设定的p小的时候，说明此时的good值小了，需要降低阈值，增加good的数量。更新此时的mid值，将右边界左移（mid=r-1;）

  • 一旦此时的概率cur比设定的p大的时候，说明此时的good值大了，需要增大阈值，减少good的数量。需要更新此时的mid值，将左边界右移（mid=l+1;）

    ​

3. 具体代码

import java.util.Scanner;

public class title4 {
    
    public static void main(String[]args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        double p=in.nextDouble();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=in.nextInt();
        }
        int l=1,r=1000000000;
        while(l<=r){	//显然不可能取到相等
            int mid=l+(r-l)/2;	//下面开始二分查找
            boolean ok=true;	//设置哨兵,判断顾客买到优质瓜的概率不小于给定的p。
            int good=0;
            for(int i=n-1;i>=0&&ok;i--){
                if(a[i]>=mid){
                    good++;
                }
                double cur=good*1.0/(n-i);
                if(cur<p){
                    ok=false;	//此时的概率比最小设定的概率还小，说明不满足要求，此时的哨兵为错误，说明此时的good数量要增大，也就是mid的值需要向左小一些
                }
            }
            if(ok){	//符合条件，直接指向mid的下一个
                l=mid+1;
            }else{	// 不符合要求，右边界左移
                r=mid-1;
            }
        }
        System.out.println(l);	//返回符合条件的时候的左边界，l和r相等
        in.close();
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n*logn)$，其中$n$为瓜的个数。

    1. 输入部分：读取n和p的时间复杂度为O(1)，读取数组a的时间复杂度为O(n)，总计O(n)。
    2. 二分查找部分：由于二分查找的次数最多为O(logN)，其中N为品质值的范围（这里为10^9），每次查找需要O(n)的遍历数组a的时间复杂度，所以总计时间复杂度为O(n*logN)。
    3. 输出部分：打印结果的时间复杂度为O(1)。

  • 空间复杂度：$O(n)$

    ​ 整型数组a占用了O(n)的空间，用于存储每个瓜的品质。

    ​

---

END~