【最新华为OD机试E卷】补种未成活胡杨(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解

🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目正在持续上线中~

最新华为OD机试专栏: https://www.nowcoder.com/creation/manager/columnDetail/MgbyJj

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

🌲 补种未成活胡杨

问题描述

近些年来，我国防沙治沙取得显著成果。某沙漠新种植 棵胡杨（编号 到 ），排成一排。一个月后，有 棵胡杨未能成活。现可补种胡杨 棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？

输入格式

输入共四行：

1. 第一行包含一个整数 ，表示总种植数量。
2. 第二行包含一个整数 ，表示未成活胡杨数量。
3. 第三行包含 个用空格分隔的整数，表示未成活胡杨的编号（按从小到大排列）。
4. 第四行包含一个整数 ，表示最多可以补种的数量。

输出格式

输出一个整数，表示最多的连续胡杨棵树。

样例输入1

5
2
2 4
1

样例输出1

3

样例解释1

补种到 2 或 4 结果一样，最多的连续胡杨棵树都是 3。

样例输入2

10
3
2 4 7
1

样例输出2

6

样例解释2

补种第 7 棵树，最多连续胡杨树棵数为 6（5、6、7、8、9、10）。

数据范围

题解

滑动窗口+双指针

这道题目要求在给定条件下，通过补种胡杨树来获得最长的连续胡杨树序列。

解题思路如下：

1. 首先，将胡杨树的状态表示为一个长度为 N 的数组，其中 1 表示存活的树，0 表示未成活的树。

2. 使用滑动窗口（双指针）技术来解决这个问题：

   • 用两个指针 left 和 right 表示当前考虑的区间。
   • 移动 right 指针扩大窗口，直到窗口内未成活的树木数量超过 K。
   • 记录当前窗口大小，这可能是一个潜在的最大连续序列。
   • 如果窗口内未成活的树木数量超过了 K，移动 left 指针缩小窗口，直到未成活的树木数量再次不超过 K。

3. 在整个过程中，持续更新最大连续树木数量。

参考代码

以下是五种语言的实现，每种实现都包含详细的注释：

• Python

def max_continuous_trees():
    # 读取输入
    N = int(input())
    M = int(input())
    dead_trees = list(map(int, input().split()))
    K = int(input())

    # 创建一个长度为 N+1 的数组，初始化为全 1（所有树都活着）
    trees = [1] * (N + 1)
    
    # 标记死亡的树
    for tree in dead_trees:
        trees[tree] = 0
    
    left = right = 1  # 滑动窗口的左右指针
    zeros = 0  # 当前窗口内 0 的数量
    max_length = 0  # 最大连续树木数量
    
    # 滑动窗口
    for right in range(1, N + 1):
        if trees[right] == 0:
            zeros += 1
        
        # 如果窗口内的 0 超过了可补种数量，移动左指针
        while zeros > K:
            if trees[left] == 0:
                zeros -= 1
            left += 1
        
        # 更新最大连续树木数量
        max_length = max(max_length, right - left + 1)
    
    return max_length

# 计算并输出结果
print(max_continuous_trees())

• C

#include <stdio.h>
#include <stdlib.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int max_continuous_trees() {
    int N, M, K;
    scanf("%d", &N);
    scanf("%d", &M);
    
    // 创建一个长度为 N+1 的数组，初始化为全 1（所有树都活着）
    int* trees = (int*)calloc(N + 1, sizeof(int));
    for (int i = 1; i <= N; i++) {
        trees[i] = 1;
    }
    
    // 标记死亡的树
    for (int i = 0; i < M; i++) {
        int dead_tree;
        scanf("%d", &dead_tree);
        trees[dead_tree] = 0;
    }
    
    scanf("%d", &K);
    
    int left = 1, right = 1;  // 滑动窗口的左右指针
    int zeros = 0;  // 当前窗口内 0 的数量
    int max_length = 0;  // 最大连续树木数量
    
    // 滑动窗口
    for (right = 1; right <= N; right++) {