华为0920/0923秋招笔试

华为0920/0923秋招笔试

开启这个系列，主要是对大厂的笔试的刷题模式进行熟悉，每次的摘录会选择自己理解并有所思考的题目，也算是一种总结思考。

​

0920.T1 丢失报文的位置

1. 题目说明

某通信系统持续向外发送报文，使用数组nums保存n个最近发送的报文，用于在报文未达到对端的情况下重发。报文使用序号sn表示，序号sn按照报文发送顺序从小到大排序，相邻报文sn不完全连续且有可能相同。报文使用循环覆盖的方式保存，即nums数组填满后，从头开始保存新的报文。假设需要重发序号为sn的报文。请找出序号为sn的报文在数组中的开始位置和结束位置。

解答要求

时间限制:C/C1000ms,其他语言: 2000ms内存限制: C/C256MB其他语言:512MB

输入

第一行输入:数组nums的大小n，取值范围[0,10000]
第二行输入:数组中的所有报文的序号sn，sn取值范围[0,100000]。
第三行输入:需要重发的报文序号sn，取值范围[0,100000]

输出

start end

说明:

start和end代表需要重发的报文序号sn在数组中的起始下标和结束下标

样例1

输入:

7
0 0 1 2 2 5 6
1

输出:

2 2

解释：

nums数组大小为7
保存了7个报文，sn分别是0 0 1 2 2 5 6
sn为1的报文在数组中仅有1个，下标是2，因此输出22

​

2. 分析解答

• 找到特定的元素的下标，返回其在数组中的特定位置，也就是最初出现的位置和最后出现的位置。不难想到是从最小值开始进行遍历，以数组的大小为窗口，不断进行取余的运算(确保最后的元素可以连续不断填充)。

  ​

3.完整代码

import java.util.Scanner;

public class title1 {
    public static void main(String[] arg){
        int n,sn;
        Scanner in=new Scanner(System.in);
        n=in.nextInt();//数组nums的长度
        int[] nums=new int[n];
        for(int i=0;i<n;i++){
            nums[i]=in.nextInt();//输入数组的元素
        }
        sn=in.nextInt();//确定的元素的值

        int minIndex=0,minValue=nums[0];//从最数组最初值开始遍历
        for(int i=0;i<n;i++){
            if(nums[i]<minValue){
                minIndex=i;//最小值下标
                minValue=nums[i];//最小值
            }
        }
        int start=-1,end=-1;//记录开始和结束位置
        for(int i=0;i<n;i++){
            int index=(minIndex+i)%n;//遍历当前的下标
            if(nums[index]==sn) {//找到需要的元素值得下标
                if (start == -1) {//首次
                    start = index;
                    end = index;
                } else {//不是首次的话，只用返回更新end指针即可
                    end = index;
                }
            }
        }
        System.out.println(start+ " " + end);
    }

}

• 现实笔试中是需要完整的代码演示的，所以需要更加谨慎认真，对每个限定条件都进行判定。

  ​

0920.T2 快速传球

1. 题目说明

班级组织传球活动，男女同学随机排成m行n列队伍，第一列中的任意一个男同学都可以作为传球的起点，要求最终将球传到最后一列的任意一个男同学手里，求所有能够完成任务的传球路线中的最优路线(传球次数最少的路线)的传球次数。

传球规则:

1.男同学只能将球传给男同学，不能传给女同学。
2.球只能传给身边前后左右相邻的同学。
3.如果游戏不能完成，返回-1。

说明

1.传球次数最少的路线为最优路线。
2最优路线可能不唯一，不同最优路线都为最少传球次数。

解答要求

时间限制:C/C100ms其他语言: 200ms内存限制: C/C256MB,其他语言: 512MB

输入

班级同学随机排成的m行n列队伍，1代表男同学，0代表女同学。
输入第一行包含两个用空格分开的整数m[1,30]和n [1,30]，表示m行n列的队伍;
接下来是m行每行包含n个用空格分开的整数1或0。

输出

最优路线的传球次数（最少传球次数）

样例1

输入

4 4
1 1 1 0
1 1 1 0
0 0 1 0
0 1 1 1

输出

5

​

2. 分析解答

• 涉及到最优路线和最短的路线，一般都会想到BFS或者DFS。这里就直接最短路BFS。

• 枚举第一列的所有的点，做一次BFS，判断走到最后一列的最短距离即可。关键在于100ms，其他语言一定要注意输入超时。

  ​

3. 具体代码

//班级组织传球活动，男女同学随机排成m行n列队伍，
// 第一列中的任意一个男同学都可以作为传球的起点，要求最终将球传到最后一列的任意一个男同学手里，
// 求所有能够完成任务的传球路线中的最优路线(传球次数最少的路线)的传球次数。

//班级同学随机排成的m行n列队伍，1代表男同学，0代表女同学。
//输入第一行包含两个用空格分开的整数m[1,30]和n [1,30]，表示m行n列的队伍;
//接下来是m行每行包含n个用空格分开的整数1或0。

//输入：4 4
//1 1 1 0
//1 1 1 0
//0 0 1 0
//0 1 1 1

//输出：5

import java.io.*;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class title2 {
     //定义快速读入的类，这里需要学习记录一下：
    private static  class FastScanner {
        BufferedReader br; //用于按行读取输入数据
        StringTokenizer st; //用于将一行数据分割为多个token。
       
        public FastScanner(InputStream stream){
            br =  new BufferedReader(new InputStreamReader(stream), 32768); //通过InputStreamReader将输入流转换为字符流，并指定缓冲区大小为32768。
            st = null; //初始化为null
        }
        String next() { //用于获取下一个token（字符串）
            while (st == null ||  !st.hasMoreTokens())// 当st为null或者当前行的token已经全部使用完毕时，进入循环
                try {
                    st=new StringTokenizer(br.readLine());//尝试读取下一行数据并将其分割为多个token
                } catch (IOException e) {//异常处理
                    e.printStackTrace();
                }
            return st.nextToken(); //循环结束，返回当前行的下一个token
        }

        int nextInt() {// nextInt()方法，用于获取下一个整数
            return Integer.parseInt(next()); //调用next()方法获取下一个token（字符串），将调用到的token解析为整数并返回
        }
    }


    public static void main(String[] args) {
        new title2().solve();// 创建实例（solve()类看下文）
    }
    int m,n;// 队伍的行和列
    int[][] grid; // 储存队伍中同学的性别信息
    void solve() {
        PrintWriter pwin = new PrintWriter(new OutputStreamWriter(System.out));
        FastScanner fsc = new FastScanner(System.in);// 调用类
        m = fsc.nextInt();;
        n = fsc.nextInt();
        grid = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = fsc.nextInt();
            }
        }
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};// 定义dirs数组，表示四个方向的移动：右、下、左、上
        int res = 10000001; // 初始化变量res为一个较大的数，用于保存最少传球次数
        for (int i = 0; i < m; i++) {// 利用广度优先搜索找到传球到最后一列男同学的最短路径。
            if (grid[i][0] == 1) { // 判断是否为男同学，grid[i][0]表示第i行、第0列的位置，其中1表示男同学，0表示女同学。
                Deque<int[]> dq = new LinkedList<>();// 定义队列，用于广度优先
                dq.add(new int[]{0,i,0}); // 表示起点的传球次数、行号和列号
                boolean[][] used = new boolean[m][n]; // 用于标记已经遍历过的位置
                used[i][0] = true;
                while (!dq.isEmpty()) {
                    int[] a = dq.poll();// 从dq中取出队首元素a，其中d表示传球次数，x表示行号，y表示列号。
                    int d = a[0], x = a[1], y = a[2];
                    if (y == n-1) {
                        res = Math.min(res, d);//如果当前列号等于n-1（最后一列），则更新最小传球次数res为传球次数d的较小值。
                    }
                    for (int[] dir : dirs) {
                        //遍历四个方向的移动，计算新的行号nx和列号ny。
						//判断下一个位置是否合法，如果不合法则跳过继续下一次循环。
						//如果下一个位置合法且未被使用且为男同学，则将该位置标记为已使用，并加入dq，传球次数加1。
                        int nx = x + dir[0],  ny = y + dir[1];
                        if (nx < 0 || ny < 0 || nx >= m || ny >= n || used[nx][ny] || grid[nx][ny] != 1) continue;
                        used[nx][ny] = true;
                        dq.add(new int[]{d+1, nx,ny});// 循环结束，得到从当前起点到最后一列男同学的最短传球次数
                    }
                }
            }
        }
        //如果找到了最短路径，则输出最小传球次数；如果无法找到最短路径，则输出-1。最后，通过刷新打印流pwin，确保结果被立即输出。
        if (res != 10000001) pwin.println(res);//如果不等于10000001，表示找到了从起点到最后一列男同学的最短路径。等于的话就是没有找到
        else pwin.println(-1);
        pwin.flush();
    }
}

​

• 复杂度分析
  • 时间复杂度：$O(m*n)$ 对于每个男同学，最坏情况下需要遍历整个队伍，所以时间复杂度为O(m * n)，其中m为行数，n为列数。
  • 空间复杂度：$O(m*n)$ 需要使用额外的空间保存队列和标记已访问的位置，所以空间复杂度为O(m * n)。

第三题太复杂了，还没弄懂，9.23号的后续接着更新…

​

0923.T1 分销粮食

1. 题目说明

粮食公司从农场收购了n吨粮食，现在要要平均分配给分销商进行销售(除不尽向下取整)。分销商数量若干，请计算分销商获得的粮食数量有几种可能。

解答要求

时间限制: C/C++ 2000ms,其他语言: 4000m内存限制:C/C++256MB,其他语言:512MB

输入

n:粮食总量，0<n<=4294967295

输出

m:分销商获得的粮食数有几种可能

样例1

输入:5
输出:3

​

2. 分析解答

• 简单的模拟题，对所求的结果进行遍历即可。比如说粮食数量为5，那么我们假设有m个商家，如果要求商家都要均分到粮食，那么可以对m的数量进行遍历。

  • m=1,n/m=5/1=5； 1个经销商分得5份粮食

  • m=2,n/m=2；2个经销商各分得2份粮食

  • m=3,n/m=1; 3个经销商各分得1份粮食（这种情况的时候，后续随着商家的数量变多后，分得的粮食数肯定比1小，但是由于取整，可能还是为1，直到最后的均分数为0舍去）。

    ​

3. 具体代码

import java.util.Hashset;
import java.util.Scanner;
import java.util.set;

public class title1{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        Set<Integer> res=new HashSet<>();
        
        int i=1;//初始化商家的个数,其实也是保证后续的除数不为0
        
        while(true){
            res.add(n/i);
            if(n/i==1){
                break;//保证当前的每个商家均分的粮食数目为1的时候即可停止，由于均分的数目不能为0
            }
            i++;//开始遍历
        }
        System.out.println(res.size());// 返回hshSet的长度
    }
}

• 复杂度分析

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

    因为在while循环中，变量i从1遍历到n/i，所以总的迭代次数为n/1 + n/2 + n/3 + … + n/n，这个等价于n * (1/1 + 1/2 + 1/3 + … + 1/n)。 根据调和级数的性质，1/1 + 1/2 + 1/3 + … + 1/n 的和约为ln(n)，所以总的迭代次数约为 n * ln(n)。 因此，该代码的时间复杂度为O(n)。

  • 空间复杂度：$O(\sqrt{n})$

    在while循环中，将n/i的结果存储在一个HashSet集合res中。在最坏的情况下，当i取到sqrt(n)时，HashSet res 中的元素数量达到最大，即sqrt(n)，所以空间复杂度为O(sqrt(n))。

​

0923.T2 糖果迷宫

1. 题目说明

小华和小为在一个两个m列的糖果迷宫里，迷宫的每一个位置上都有对应得糖果数目a[i][j],他们只能向右或者向下移动。

小华和小为都将从左上方a[0[[0]位置出发，向右下角a[1，m-1]走去，每到一个位置都将吃掉这个位置上的糖果。

假设小华先走，他走完后会吃掉路过的糖果，然后小为才开始走，被小华吃掉的糖果，小为就能再吃了。

小华希望小为吃掉最少的糖果总数，然后小为也希望在小华走完后自己能吃掉更多的糖果总数。

请你帮忙计算小为最多可以吃掉多少糖果。

解答要求

时间限制:C/C++ 1000ms 其他语言2000ms，内存限制: C/C++ 256MB,其他语言:512MB

输入

第一行包含一个整数m(1<=m<=100000),标识迷宫的宽度。

接下来包含两行，每行包含m个整数，每一个整数a[i]j代表该位置的糖果数目。

输出

输出小为最多可以吃到多少糖果。

样例1

输入：3
     1 3 7
     3 5 1
输出：7
解释：1 3 7
     3 5 1
     小为吃掉小华选择吃掉粗体部分的糖果1、3、5、1，小为吃掉7

​

2. 解答分析

• 由于只有两行，可以进行前缀的模拟操作，就是记录下小华需要在第一行的那个位置转弯，这个点记录为i,然后小为可以获得的总价值就是第二行的前i个或者是第一行的后n-i个。

• 具体说明是定义小华的轨迹路线，注意其可走的位置有m+1个，需要注意第2行中的前i个的操作，同第1行中的后n-i个的操作.

  ​

3. 具体代码

import java.util.Scanner;

public class title2 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();//m为列的个数
        int[][] grid = new int[2][m];
        int[][] qzs = new int[2][m+1];//前缀数组，长度为m+1

        for (int j = 0; j < m; j++) {//第一行
            grid[0][j] = sc.nextInt();
            qzs[0][j+1] = qzs[0][j] + grid[0][j];
        }

        for (int j = 0; j < m; j++) {//第二行
            grid[1][j] = sc.nextInt();
            qzs[1][j+1] = qzs[1][j] + grid[1][j];
        }

        long ans = Integer.MAX_VALUE;//确定最后的答案
        for (int i = 0; i < m; i++) {
            int tmp = Math.max(qzs[1][i], qzs[0][m]-qzs[0][i+1]);//第2行的前i个和第1行的后n-i个
            ans = Math.min(ans, tmp);//返回最小值，保证小华的最大值
        }

        System.out.println(ans);

    }

}

• 复杂度分析：

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

    1. 输入阶段：读取m个整数值，时间复杂度为O(m)。
    2. 创建二维数组grid和前缀数组qzs：创建二维数组的时间复杂度为O(2m)。创建前缀数组的时间复杂度为O(m)。
    3. 遍历循环：遍历m次，时间复杂度为O(m)。
    4. 内部计算：常数时间操作，时间复杂度为O(1)。

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

    1. 二维数组grid和前缀数组qzs：空间复杂度为O(2m+2m) = O(4m) = O(m)。
    2. 整型变量m和tmp：空间复杂度为O(1)

​

0923.T3 对战比赛

1. 题目说明

小明参加一个在线比赛。需要与n个对手对战。当小明的等级大于等于对手的等级，他就能赢。如果小明赢了，等级提升1级，否则会减少1级。对手的等级固定不变。小明的初始等级是x，小明想把他的等级提高到y（y>x）。

该比赛有一条规则：每局此赛小明只能选择和对战次数最少的对手进行对战。

小明想用尽可能少的对站题升到等级y，计算小明为提升到等级y所需的最小可能的对战数。

注意，对手的等级不会改变，而小明的等级会改变。

解答要求

时间限制: C/C++ 2000ms,其他语言：4000ms 内存限制: C/C++ 256MB，其他语言：512MB

输入

第一行包含三个整数n、x和y($1\le n\le2* 10^5$,$1\le x<y\le 10^{12}$)表示对手个数，小明的初始等级和期望等级。

第二行包含n个整数a1,a2,a3,…,an(1<=ai<=10^12)表示对手的等级。

输出

打印小明为提升到等级y所需的最少对战数，如果不可能，则打印-1.

样例1

输入：7 2 10
     3 1 9 2 5 20 8
输出：20

2. 解答分析

• 贪心 + 模拟。
  1. 每一次优先击败小等级的对手
  2. 每一轮可以打败的人数记为cnt，那么每一轮增长的总次数为2*cnt - n。
  3. 每一次可以击败的人的位置记为i，那么从i+1开始就开始打不过了，那么等级增长到i+1对应的等级的时候， 就应该更换策略了，通过这个差值可以算出需要轮询的次数了。

3. 具体代码

import java.util.*;

public class title3 {

    public static void main(String[] args) {
        int n, cnt = 0;
        long x,y;

        long[] nums ;

        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        x = in.nextLong();
        y = in.nextLong();
        nums = new long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextLong();
        }

        Arrays.sort(nums);

        long[] diff = new long[n];

        for (int i = 0; i < n; i++) {
            diff[i] = Math.max(0, nums[i] - i);
            if (diff[i] <= x) cnt++;
        }

        if (x+cnt >= y) {
            System.out.println(y-x);
            return;
        }
        if (n-cnt >= cnt) {
            System.out.println(-1);
            return;
        }
        long ans = 0;
        while (x < y) {
            int l = 0, r = n-1;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (diff[mid] <= x) l = mid;
                else r = mid - 1;
            }
            if (r == n-1) {
                System.out.println(ans + y - x);
                return;
            }
            r++;
            int cur = 2*r - n;
            long next = Math.min(diff[r], y);
            long d = next - x;
            if (next == y && d <= r) {
                System.out.println(ans + d);
                return;
            }
            if (cur < 0) {
                System.out.println( -1);
                return;
            }
            long time = d / cur;
            ans += time * n;
            x += cur * time;

        }
        System.out.println(ans);
    }

}

• 时间复杂度：

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

    1. 输入阶段：读取n、x、y和n个长整型数值，时间复杂度为O(n)。
    2. 数组排序：使用Arrays.sort进行排序，时间复杂度为O(nlogn)。
    3. 创建并初始化diff数组：循环n次，时间复杂度为O(n)。
    4. 计算cnt：循环n次，时间复杂度为O(n)。
    5. 判断条件和计算ans：while循环的次数不超过n次，每次循环的时间复杂度为O(logn)。

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

    1. 整型变量n、cnt。
    2. 长整型变量x、y。
    3. 长整型数组nums和diff。

---

End~ 继续努力！😊