VIVO笔试编程题三题

Posted on

2020年应届生Vivo初试笔试编程题三道（附思路及解法）。

问题1（难度：** ）

  • 给定一个非负整数数组，你最初位于数组的第一个位置。

  • 数组中的每个元素代表你在该位置可以跳跃的最大长度。

  • 判断你到达最后一个位置所花费的最小步数。

  • 一开始就在最后一个位置返回0。

  • 不能到达最后一个位置返回-1。

思路：

  • 初始步数为0。

  • 从前往后遍历，直到能找到一个位置i，在该位置能够跳转到末尾。步数+1。

  • 从前往后遍历，直到能找到一个位置j，在该位置能够跳转i。步数+1。

  • 重复上述步骤，直到从初始位置开始跳转。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q1 {
    public static void main(String[] args) throws IOException {
         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        while (in.ready()) {
            String[] strings = in.readLine().split(" ");
            int len = strings.length;
            int[] nums = new int[len];
            for (int i = 0; i < len; i++) {
                nums[i] = Integer.parseInt(strings[i]);
            }

            System.out.println(start(nums, len - 1));
            /* got nums */
            // if (in.ready()) result.append("\n");
        }
        in.close();
    }

    //从后往前遍历，得到能跳转当前索引的最前面的点
    public static int start(int[] nums, int index) {
        if (index == 0) {
            return 0;
        }
        for (int i = 0; i < index; i++) {
            if (nums[i] + i >= index) {
                return 1 + start(nums, i);
            }
        }
        return -1;
    }

}

改进算法

上述代码时间复杂度为O(n*n)，每次遍历出现了大量的冗余工作，每个位置被重复遍历多次，下面做出修改，改进后的算法时间复杂度为O(n)。

改进思路

  • 用列表list维护不同步数能够跳转到能够到达末尾的索引。

  • 首先将末尾索引加入到list中。list下标代表步数，内容代表当前索引。涵义：末尾索引位置的点经过0步到达末尾。

  • 数组从后往前遍历（遍历一次）。列表从前往后遍历，当数组索引处能跳转到列表中存储的索引，在列表后面设置索引。

  • 返回0所在的索引即为从初始位置跳转的最少步数。

  • 异常情况分析：

    1、一开始就在末尾：不用遍历，直接返回索引0；

    2、不存在路径，list中不含0，list返回不存在元素的索引为-1。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Q1 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        while (in.ready()) {
            String[] strings = in.readLine().split(" ");
            int len = strings.length;
            int[] nums = new int[len];
            for (int i = 0; i < len; i++) {
                nums[i] = Integer.parseInt(strings[i]);
            }

            // 从后往前遍历截断数组
            List<Integer> list = new ArrayList<>();
            list.add(len - 1);
            for (int index = len - 2; index >= 0; index--) {
                for (int i = 0; i < list.size(); i++) {
                    if (index + nums[index] >= list.get(i)) {
                        if (i < list.size() - 1) {
                            list.set(i + 1, index);
                        } else {
                            list.add(index);
                        }
                        break;
                    }
                }
            }
            System.out.println(list.indexOf(0));
        }
        in.close();
    }
}

问题2（难度：** ）

m个人，每次数n个数排除，排除的人按次序排列输出。

思路

典型的约瑟夫环问题。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Q2 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        while (in.ready()) {
            String[] strings = in.readLine().split(" ");
            int count = strings.length;
            int[] nums = new int[count];
            for (int i = 0; i < count; i++) {
                nums[i] = Integer.parseInt(strings[i]);
            }
            int m = nums[0];
            int n = nums[1];
            yuesefu(m, n);
        }
        in.close();
    }

    public static void yuesefu(int totalNum, int countNum) {
        // 初始化人数
        List<Integer> start = new ArrayList<Integer>();
        for (int i = 1; i <= totalNum; i++) {
            start.add(i);
        }
        // 从第K个开始计数
        int k = 0;
        while (start.size() > 0) {
            k = k + countNum;
            // 第m人的索引位置
            k = k % (start.size()) - 1;
            // 判断是否到队尾
            if (k < 0) {
                System.out.println(start.get(start.size() - 1));
                start.remove(start.size() - 1);
                k = 0;
            } else {
                System.out.println(start.get(k));
                start.remove(k);
            }
        }
    }
}