攀登者2 - 华为OD统一考试

news/2024/7/20 19:31:12 标签: 华为od, 算法, java, python, c++, 面试, 动态规划

OD统一考试

分值： 200分

题解： Java / Python / C++

alt

题目描述

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

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

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

image-20240104103125507

登山时会消耗登山者的体力(整数)，

  • 上山时，消耗相邻高度差两倍的体力
  • 下山时，消耗相邻高度差一倍的体力
  • 平地不消耗体力

登山者体力消耗到零时会有生命危险。

例如，上图所示的山峰：

  • 从索引0，走到索引1，高度差为1，需要消耗 2 * 1 = 2 的体力，
  • 从索引2，走到索引3，高度差为2，需要消耗 2 * 2 = 4 的体力。
  • 从索引3，走到索引4，高度差为1，需要消耗 1 * 1 = 1 的体力。

攀登者想要评估一张地图内有多少座山峰可以进行攀登，且可以安全返回到地面，且无生命危险。

例如：上图中的数组，有3个不同的山峰，登上位置在3的山可以从位置0或者位置6开始，从位置0登到山顶需要消耗体力 1 * 2 + 1 * 2 + 2 * 2 = 8，从山顶返回到地面0需要消耗体力 2 * 1 + 1 * 1 + 1 * 1 = 4 的体力，按照登山路线 0 → 3 → 0 需要消耗体力12。攀登者至少需要12以上的体力（大于12）才能安全返回。

输入描述

第一行输入为地图一维数组

第二行输入为攀登者的体力

输出描述

确保可以安全返回地面，且无生命危险的情况下，地图中有多少山峰可以攀登。

示例1

输入：
0,1,2,4,3,1,0,0,1,2,3,1,2,1,0
13

输出：
3

说明：
3，10，12 都可安全到达。

示例2

输入：
1,4,3
999

输出：
0

说明：
没有合适的起点和终点

题解

这是一个通过动态规划求解的问题，主要思路如下：

  1. 首先，遍历一次数组，计算每个位置到左侧最近的地面的向上和向下的总高度差，分别存储在 left_up 和 left_down 数组中。
  2. 然后，从右向左遍历数组，计算每个峰值的上山和下山的最小体力消耗，并判断是否满足攀登者的体力条件。
  3. 最后，统计满足条件的峰值个数。

这个算法的时间复杂度为 O(n)，其中 n 是数组的长度

Java

java">import java.util.Arrays;
import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {

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

        // 读取地图高度数组
        int[] heights = Arrays.stream(scanner.nextLine().split(","))
                .mapToInt(Integer::parseInt)
                .toArray();
        int n = heights.length;
        int power = scanner.nextInt();

        // 初始化数组用于记录从左侧最近的地面到当前位置的向上和向下的总高度差
        int[] leftUp = new int[n + 1];
        int[] leftDown = new int[n + 1];
        Arrays.fill(leftUp, Integer.MAX_VALUE);
        Arrays.fill(leftDown, Integer.MAX_VALUE);

        int prevHeight = -1;
        // 从左向右遍历地图，计算左侧最近的地面到当前位置的向上和向下的总高度差
        for (int i = 1; i <= n; i++) {
            int curHeight = heights[i - 1];
            if (curHeight == 0) {
                leftUp[i] = 0;
                leftDown[i] = 0;
            } else if (leftUp[i - 1] != Integer.MAX_VALUE) {
                int d = Math.abs(curHeight - prevHeight);
                if (curHeight >= prevHeight) {
                    leftUp[i] = leftUp[i - 1] + d;
                    leftDown[i] = leftDown[i - 1];
                } else {
                    leftUp[i] = leftUp[i - 1];
                    leftDown[i] = leftDown[i - 1] + d;
                }
            }
            prevHeight = curHeight;
        }

        int peakCount = 0;

        // 初始化变量用于记录从右侧最近的地面到当前位置的向上和向下的总高度差
        int rightUp = Integer.MAX_VALUE;
        int rightDown = Integer.MAX_VALUE;
        // 从右向左遍历地图
        for (int r = n - 1; r >= 0; r--) {
            if (heights[r] == 0) {
                rightUp = 0;
                rightDown = 0;
            } else if (rightUp != Integer.MAX_VALUE) {
                int d = Math.abs(heights[r] - heights[r + 1]);
                if (heights[r] > heights[r + 1]) {
                    rightUp += d;
                } else {
                    rightDown += d;
                }
            }

            // 当前位置为峰值时，计算上山和下山的最小体力消耗，并判断是否满足攀登者的体力条件
            if ((r == 0 || heights[r - 1] < heights[r]) && (r + 1 == n || heights[r] > heights[r + 1])) {
                int minUpCost = Integer.MAX_VALUE;
                int minDownCost = Integer.MAX_VALUE;
                if (leftUp[r + 1] != Integer.MAX_VALUE) {
                    minUpCost = Math.min(leftUp[r + 1] * 2 + leftDown[r + 1], minUpCost);
                    minDownCost = Math.min(leftUp[r + 1] + leftDown[r + 1] * 2, minDownCost);
                }
                if (rightUp != Integer.MAX_VALUE) {
                    minUpCost = Math.min(minUpCost, rightUp * 2 + rightDown);
                    minDownCost = Math.min(minDownCost, rightUp + rightDown * 2);
                }

                if (minUpCost != Integer.MAX_VALUE && minUpCost + minDownCost < power) {
                    // System.out.println(r + "可安全到达");
                    peakCount++;
                }
            }
        }

        // 输出满足条件的峰值个数
        System.out.println(peakCount);
    }
}

Python

python">from math import inf


heights = list(map(int, input().split(",")))
power = int(input())

n = len(heights)

# left_up[i] 表示从左侧最近的地面出发到达当前位置需要向上走的总高度差
# left_down[i] 表示从左侧最近的地面出发到达当前位置需要向下走的总高度差
left_up, left_down = [inf] * (n + 1), [inf] * (n + 1)
prev_hegiht = -1
for i, cur_height in enumerate(heights, start=1):
    if cur_height == 0:  # 可以作为起点
        left_up[i], left_down[i] = 0, 0
    elif left_up[i-1] != inf:  # 可达非起点
        d = abs(cur_height - prev_hegiht)
        if cur_height >= prev_hegiht:  # 向上
            left_up[i], left_down[i] = left_up[i-1] + d, left_down[i-1]
        else:
            left_up[i], left_down[i] = left_up[i-1], left_down[i-1] + d
    else:  # 表示当前位置左侧不可到达 (左侧没有合适的起点)
        pass
    prev_hegiht = cur_height

peak_count = 0

# 从右往左侧走
right_up, right_down = inf, inf
for r in range(n - 1, -1, -1):
    if heights[r] == 0:
        right_up, right_down = 0, 0
    elif right_up != inf:
        d = abs(heights[r] - heights[r+1])
        if heights[r] > heights[r+1]:  # 向上
            right_up += d
        else:
            right_down += d

    # 当前 r 为峰值时
    if (r == 0 or heights[r - 1] < heights[r]) and (r + 1 == n or heights[r] > heights[r + 1]):
        min_up_cost, min_down_cost = inf, inf
        if left_up[r + 1] != inf:
            min_up_cost = min(left_up[r + 1] * 2 + left_down[r + 1], min_up_cost)
            min_down_cost = min(left_up[r + 1] + left_down[r + 1] * 2, min_down_cost)
        if right_up != inf:
            min_up_cost = min(min_up_cost, right_up * 2 + right_down)
            min_down_cost = min(min_down_cost, right_up + right_down * 2)
        if min_up_cost + min_down_cost < power:
            # print(f"山峰{r}可达， 上山最小消耗：{min_up_cost} ， 下山最小消耗： {min_down_cost}")
            peak_count += 1

print(peak_count)

C++

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    vector<int> heights;
    int height, power;
    while(cin >> height) {
        heights.push_back(height);
        if(cin.peek() == ',') {
            cin.ignore();
        } else { // 读取攀登者体力
            cin >> power;
            break;
        }
    };

    int n = heights.size();

    // left_up[i] 表示从左侧最近的地面出发到达当前位置需要向上走的总高度差
    // left_down[i] 表示从左侧最近的地面出发到达当前位置需要向下走的总高度差
    vector<int> left_up(n + 1, INT_MAX);
    vector<int> left_down(n + 1, INT_MAX);
    int prevHeight = -1;

    // 从左向右遍历地图，计算左侧最近的地面到当前位置的向上和向下的总高度差
    for (int i = 1; i <= n; i++) {
        int curHeight = heights[i - 1];

        if (curHeight == 0) {
            left_up[i] = 0;
            left_down[i] = 0;
        } else if (left_up[i - 1] != INT_MAX) {
            int d = abs(curHeight - prevHeight);

            if (curHeight >= prevHeight) {
                left_up[i] = left_up[i - 1] + d;
                left_down[i] = left_down[i - 1];
            } else {
                left_up[i] = left_up[i - 1];
                left_down[i] = left_down[i - 1] + d;
            }
        }
        prevHeight = curHeight;
    }

    int peakCount = 0;

    // 初始化变量用于记录从右侧最近的地面到当前位置的向上和向下的总高度差
    int right_up = INT_MAX, right_down = INT_MAX;

    // 从右向左遍历地图
    for (int r = n - 1; r >= 0; r--) {
        if (heights[r] == 0) {
            right_up = 0;
            right_down = 0;
        } else if (right_up != INT_MAX) {
            int d = abs(heights[r] - heights[r + 1]);

            if (heights[r] > heights[r + 1]) {
                right_up += d;
            } else {
                right_down += d;
            }
        }

        if ((r == 0 || heights[r - 1] < heights[r]) && (r + 1 == n || heights[r] > heights[r + 1])) {
            int minUpCost = INT_MAX;
            int minDownCost = INT_MAX;

            if (left_up[r + 1] != INT_MAX) {
                minUpCost = min(left_up[r + 1] * 2 + left_down[r + 1], minUpCost);
                minDownCost = min(left_up[r + 1] + left_down[r + 1] * 2, minDownCost);
            }

            if (right_up != INT_MAX) {
                minUpCost = min(minUpCost, right_up * 2 + right_down);
                minDownCost = min(minDownCost, right_up + right_down * 2);
            }

            if (minUpCost != INT_MAX && minUpCost + minDownCost < power) {
                peakCount++;
            }
        }
    }

    // 输出结果
    cout << peakCount << endl;

    return 0;
}

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏


http://www.niftyadmin.cn/n/5304096.html

相关文章

最优化理论期末复习笔记 Part 1

最优化理论期末复习笔记 Part 1

数学基础线性代数 从行的角度从列的角度行列式的几何解释向量范数和矩阵范数 向量范数矩阵范数的更强的性质的意义 几种向量范数诱导的矩阵范数 1 范数诱导的矩阵范数无穷范数诱导的矩阵范数2 范数诱导的矩阵范数 各种范数之间的等价性向量与矩阵序列的收敛性 函数的可微性与展…
阅读更多...
HttpClient库与代理IP在爬虫程序中的应用

HttpClient库与代理IP在爬虫程序中的应用

目录 前言 一、HttpClient库的基本使用方法 二、代理IP的使用方法 三、代理IP池的使用方法 四、总结 前言 在编写爬虫程序时&#xff0c;我们经常会使用HttpClient库来发送HTTP请求&#xff0c;获取网页内容。然而&#xff0c;有些网站可能会对频繁的请求进行限制&#x…
阅读更多...
大数据情况下如何保证企业数据交换安全

大数据情况下如何保证企业数据交换安全

数据交换是指在网络或其他方式下&#xff0c;不同主体按照规定的规则和标准实现数据的共享、传输和处理的过程。大数据时代的到来使得数据交换的重要性更为凸显&#xff0c;大数据带来了海量、多样、高速、低价值密度等特点&#xff0c;也带来了更多的价值挖掘和应用场景。 保障…
阅读更多...
【Git】Git版本控制工具使用详解

【Git】Git版本控制工具使用详解

1、版本控制 特点 协同修改: 多人可以并行修改服务器端的同一个文件 数据备份: 不仅保存目录和文件的当前状态,还可以保存每一个提交过的文件的历史状态 2、版本管理: 在保存每一个版本的文件信息时要做到不保存重复数据以节约存储空间 提高运行效率 SVN采用增量式更新 Git采用…
阅读更多...
PDF控件Spire.PDF for .NET【安全】演示：修改加密PDF的密码

PDF控件Spire.PDF for .NET【安全】演示：修改加密PDF的密码

修改PDF文件的密码确实是一个理性的选择&#xff0c;尤其是当密码被某人知道并且您的PDF文件不再安全时。Spire.PDF for .NET使您能够用 C#、VB.NET 修改加密 PDF 文件的密码。您可以修改所有者密码和用户密码&#xff0c;并设置访问 PDF 文件时的用户限制。现在请看修改加密PD…
阅读更多...
ubuntu远程桌面连接之vnc

ubuntu远程桌面连接之vnc

一、前言 ubuntu安装图形化桌面以后,有些时候出于需要会想要进行远程桌面连接。ubuntu想要进行远程桌面连接就需要vnc服务的支持，安装vnc的方法有很多，博主也试过一些方式，但是安装完后使用vnc连接工具发现是花屏，无法正常使用。后来发现一种简单的方式即可配置好vnc连接，…
阅读更多...
Spring Security 6.x 系列（14）—— 会话管理之源码分析

Spring Security 6.x 系列（14）—— 会话管理之源码分析

一、前言 在上篇 Spring Security 6.x 系列（13）—— 会话管理之会话概念及常用配置 Spring Security 6.x 系列（14）—— 会话管理之会话固定攻击防护及Session共享 中了清晰了协议和会话的概念、对 Spring Security 中的常用会话配置进行了说明，并了解会话固定攻击防护…
阅读更多...
ebay头像如何设置？eBay店铺的头像怎么改？-站斧浏览器

ebay头像如何设置？eBay店铺的头像怎么改？-站斧浏览器

ebay头像如何设置&#xff1f; eBay店铺的头像可以通过以下方式进行设置&#xff1a; 登录eBay账户&#xff1a;店主需要使用自己的eBay账号登录到eBay网站。 进入店铺管理后台&#xff1a;在登录后&#xff0c;店主可以点击页面右上角的用户名或店铺名称&#xff0c;从下拉…
阅读更多...
最新文章

Copyright @ 2022~2023