【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【模拟】2023C-攀登者1【欧弟算法】全网注释最详细分类最全的华为OD真题题解

有LeetCode算法/华为OD考试扣扣交流群可加 948025485

可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题

绿色聊天软件戳 od1336了解算法冲刺训练

文章目录

• 题目描述与示例
• • 题目描述
  • • 输入描述
    • 输出描述
    • 示例
    • • 输入
      • 输出
      • 解题思路
      • 代码
      • • Python
        • Java
        • C++
        • 时空复杂度
        • 华为OD算法/大厂面试高频题算法练习冲刺训练

          题目描述与示例

          题目描述

          攀登者喜欢寻找各种地图，并且尝试攀登到最高的山峰。

          地图表示为一维数组，数组的索引代表水平位置，数组的高度代表相对海拔高度。其中数组元素 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。

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

           4
                        +---+
                        |   |
                        |   | 3                       3
                        |   |
                        |   +---+                   +---+
                        |       |                   |   |
                      2 |       |                 2 |   |     2
                        |       |                   |   |
                    +---+       |               +---+   |   +---+
                    |           |               |       |   |   |
                  1 |           | 1           1 |       | 1 |   | 1
                    |           |               |       |   |   |
                +---+           +---+       +---+       +---+   +---+
                |                   |       |                       |
              0 |                   | 0   0 |                       | 0
                |                   |       |                       |
            +---+                   +-------+                       +---+
              0   1   2   3   4   5   6   7   8   9  10  11  12  13  14
          

          登山时会消耗登山者的体力(整数)，上山时，消耗相邻高度差两倍的体力，下坡时消耗相邻高度差一倍的体力，平地不消耗体力，登山者体力消耗到零时会有生命危险。

          例如，上图所示的山峰：从索引 0，走到索引 1，高度差为 1，需要消耗 2*1=2 的体力；从索引 2 高度 2走到高度 4 索引 3 需要消耗 2*2=4 的体力；从索引 3 走到索引 4 则消耗 1*1=1 的体力。

          登山者想知道一张地图中有多少座山峰？

          输入描述

          第一行输入一个长度为N的数组，表示地图。

          输出描述

          输出一个数字，地图中的山峰数量

          示例

          输入

          0,1,4,3,1,0,0,1,2,3,1,2,1,0
          

          输出

          3
          

          解题思路

          本题描述中关于登山者的体力是描述是干扰描述，和题意无关（在【模拟】2023C-攀登者2中才有用）。

          山峰的定义为：高度大于相邻位置的高度，或在地图边界且高度大于相邻的高度。

          所以仅需要一次遍历，检查第i个高度heights[i]是否同时大于heights[i-1]和heights[i+1]即可。

          特别注意边界处应该单独判断heights[0]和heights[1]的关系，以及heights[-1]和heights[-2]的关系

          另外，还需要特别注意数组长度为1的情况。

          代码

          Python

          # 题目：【模拟】2023C-攀登者1
          # 分值：100
          # 作者：许老师-闭着眼睛学数理化
          # 算法：模拟
          # 代码看不懂的地方，请直接在群上提问
          # 输入高度数组
          heights = list(map(int, input().split(",")))
          # 获得数组长度
          n = len(heights)
          # 如果长度为1
          if n == 1:
              # 如果唯一的位置为0，则是平地，没有山峰，输出0
              # 否则唯一的位置为山峰，输出1
              print(1 if heights[0] > 0 else 0)
          # 否则，需要逐位进行判断
          else:
              # 初始化答案变量
              ans = 0
              # 左边界的特殊判断
              ans += 1 if heights[0] > heights[1] else 0
              # 右边界的特殊判断
              ans += 1 if heights[-1] > heights[-2] else 0
              # 遍历从1到n-2的每一个位置
              for i in range(1, n-1):
                  # 如果第i个位置的高度，同时大于前一个位置i-1和后一个位置i+1的高度，则找到一个山峰
                  if heights[i] > heights[i-1] and heights[i] > heights[i+1]:
                      ans += 1
              print(ans)
          

          Java

          import java.util.Scanner;
          public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in);
                  String[] heightsStr = scanner.nextLine().split(",");
                  int[] heights = new int[heightsStr.length];
                  for (int i = 0; i < heightsStr.length; i++) { heights[i] = Integer.parseInt(heightsStr[i]);
                  }
                  int n = heights.length;
                  if (n == 1) { System.out.println(heights[0] > 0 ? 1 : 0);
                  } else { int ans = 0;
                      ans += (heights[0] > heights[1]) ? 1 : 0;
                      ans += (heights[n - 1] > heights[n - 2]) ? 1 : 0;
                      for (int i = 1; i < n - 1; i++) { if (heights[i] > heights[i - 1] && heights[i] > heights[i + 1]) { ans++;
                          }
                      }
                      System.out.println(ans);
                  }
              }
          }
          

          C++

          #include #include #include using namespace std;
          int main() { string heightsInput;
              getline(cin, heightsInput);
              stringstream ss(heightsInput);
              vector heights;
              int height;
              while (getline(ss, heightsInput, ',')) { heights.push_back(stoi(heightsInput));
              }
              int n = heights.size();
              if (n == 1) { cout << (heights[0] > 0 ? 1 : 0) << endl;
              } else { int ans = 0;
                  ans += (heights[0] > heights[1]) ? 1 : 0;
                  ans += (heights[n - 1] > heights[n - 2]) ? 1 : 0;
                  for (int i = 1; i < n - 1; i++) { if (heights[i] > heights[i - 1] && heights[i] > heights[i + 1]) { ans++;
                      }
                  }
                  cout << ans << endl;
              }
              return 0;
          }
          

          时空复杂度

          时间复杂度：O(N)。仅需一次遍历高度数组heights

          空间复杂度：O(1)。仅需若干常数变量

          ---

          华为OD算法/大厂面试高频题算法练习冲刺训练

          • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务300+同学成功上岸！

          • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

          • 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

          • 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

          • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

          • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

          • 绿色聊天软件戳 od1336了解更多