华为OD机考-C卷

攀登者问题

24/03/09 20:50~23:10

攀登者喜欢寻找各种地图，并且尝试攀登到最高的山峰。地图表示为一维数组，数组的索引代表水平位置，数组的元素代表相对海拔高度。其中数组元素0代表地面。一个山脉可能有多座山峰(高度大于相邻位置的高度，或在地图边界且高度大于相邻的高度)。登山者想要知道一张地图中有多少座山峰。

例如[0,1,2,4,3,1,0,0,1,2,3,1,2,1,0], 代表如下图所示的地图，地图中有两个山脉位置分别为 1,2,3,4,5和8,9,10,11,12,13，最高峰高度分别为 4,3。最高峰位置分别为3,10。

一个山脉可能有多座山峰(高度大于相邻位置的高度，或在地图边界且高度大于相邻的高度)。

    /**
     * 返回地图中山峰的数量
     *
     * @param hill_map int整型一维数组 地图数组(长度大于1)
     * @return int整型
     */
    public int count_peaks(int[] hill_map) {
        // write code here 双指针
        int result = 0;
        if (hill_map.length == 0) {
            return result;
        } else if (hill_map.length == 1) {
            return 1;
        }
        for (int i = 0; i < hill_map.length; i++) {
            if (i > 0 && i < hill_map.length - 1) {
                // 处理非边界元素
                if (hill_map[i] > hill_map[i - 1] && hill_map[i] > hill_map[i + 1]) {
                    result++;
                }
            } else if (i == 0 && hill_map[i] > hill_map[i + 1]) {
            	// 处理左边界元素
                result++;
            } else if (i == hill_map.length - 1 && hill_map[i] > hill_map[i - 1]) {
	            // 处理右边界元素
                result++;
            }
        }
        return result;
    }
// 100%
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

停车场

停车场有一横排车位，0代表没有停车，1代表有车。至少停了一辆车在车位上，也至少有一个空位没有停车为了防剐蹭，需为停车人找到一个车位，使得距停车人的车最近的车辆的距离是最大的，返回此时的最大距离。

• 特定大小的停车场，数组cars[]表示，其中1表示有车，0表示没车。
• 车辆大小不一，小车占一个车位（长度1），货车占两个车位（长度2），卡车占三个车位（长度3），统计停车场最少可以停多少辆车，返回具体的数目。
  输入描述
  1.一个用半角逗号分割的停车标识字符串，停车标识为0或1，0为空位，1为已停车。
  2.停车位最多100个。
  输出描述
  最少可以停多少辆车

eg1：

• 输入 1,0,1
• 输出 2
• 说明 1个小车占第1个车位，第二个车位空，1个小车占第3个车位，最少有两辆车

eg2：

• 输入 1,1,0,0,1,1,1,0,1
• 输出 3
• 说明 1个货车占第1、2个车位；第3、4个车位空；1个卡车占第5、6、7个车位；第8个车位空；1个小车占第9个车位；最少3辆车

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String carsLine = in.nextLine();
        int[] cars = new int[0];
        String[] split = carsLine.split(",");
        if (split.length > 0) {
            cars = new int[split.length];
            for (int i = 0; i < split.length; i++) {
                if (Objects.equals(split[i], "0") || Objects.equals(split[i], "1")) {
                    cars[i] = Integer.parseInt(split[i]);
                }
            }
        }
        int i = parkingCount(cars);
        System.out.println(i);
    }
    
    public static int parkingCount(int[] car) {
        int result = 0;
        int count = 0;
        for (int i = 0; i < car.length; i++) {
            if (car[i] == 1) {
            	// 记录停车位大小
                count++;
                if (count == 1) {
                	// 停车位大小为1，就可以停一辆车
                    result++;
                } else if (count == 3) {
                	// 停车位大小为3，到达最大车位，需要重新统计。
                    count = 0;
                }
            } else {
            	// 没有连续车位，停车位大小归0
                count = 0;
            }
        }
        return result;
    }
// 100%
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

最短路径

给定两个字符串，分别为字符串A与字符串B。例如A字符串为ABCABBA，B字符串为CBABAC。可以得到m*n的二维数组，定义原点为(0,0)，终点为(m,n)，水平与垂直的每一条边距离为1,从原点(0,0)到(0,A)为水平边，距离为1，从(0,A)到(A,C)为垂直边，距离为1; 假设两个字符串同一位置的两个字符相同则可以作一个斜边、如(A.C)到.B)最短距离为斜边，距离同样为1。作出所有的斜边，则有(0.0)到(B.B)的距离为 1个水平边+1个垂直边+1个斜边 =3。
根据定义可知，原点到终点的最短距离路径如下图红线标记，最短距离为9;
路径为(0,0)->(A,0)->(A,C)->(B,B)->(C,B)->(A,A)->(B,B)->(B,B)->(A,A)->(A,C)

19% 没做出来