机考E卷100分题 - 补种未成活胡杨

题目描述

近些年来，我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨（编号1-N），排成一排。

一个月后，有M棵胡杨未能成活。

现可补种胡杨K棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？

输入描述

N 总种植数量，1 <= N <= 100000

M 未成活胡杨数量，M 个空格分隔的数，按编号从小到大排列，1 <= M <= N

K 最多可以补种的数量，0 <= K <= M

输出描述

最多的连续胡杨棵树

示例1

输入

5
2
2 4
1

输出

1

说明

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

示例2

输入

10
3
2 4 7
1

输出

1

说明

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

解题思路

这道题目主要是考察如何通过补种胡杨树，使得胡杨树形成【最长的连续序列】。

示例解释

示例1

输入：

5
2
2 4
1

解释：

  • 胡杨树总共有 5 棵，编号分别是 1, 2, 3, 4, 5。
  • 未成活的胡杨树编号是 2 和 4。
  • 只能补种 1 棵树。

选择补种位置：

  • 可以补种编号为2的树，得到序列 1, 2, 3，最多连续 3 棵树。
  • 或者补种编号为4的树，得到序列 3, 4, 5，同样可以得到最多连续 3 棵树。

因此，输出结果为 3。

示例2

输入：

10
3
2 4 7
1

解释：

  • 胡杨树总共有 10 棵，编号分别是 1 到 10。
  • 未成活的胡杨树编号是 2, 4, 7。
  • 只能补种 1 棵树。

选择补种位置：

  • 如果补种编号为7的树，可以形成最长连续序列 5, 6, 7, 8, 9, 10，连续的胡杨树棵数为 6。
  • 其他补种选择（如2或4）得到的最长连续胡杨树棵数较少。

因此，输出结果为 6。

代码思路

基本与下题一致：

1004. 最大连续1的个数 III

参考题解：https://leetcode.cn/problems/max-consecutive-ones-iii/solutions/608931/zui-da-lian-xu-1de-ge-shu-iii-by-leetcod-hw12/

双指针解法，容易理解

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 创建一个扫描器对象，用于读取输入
        Scanner scanner = new Scanner(System.in);
        
        // 读取总共的胡杨树数量
        int total = scanner.nextInt();
        
        // 读取未成活的胡杨树数量
        int deadCount = scanner.nextInt();
        
        // 创建一个数组来表示每棵树是否成活，0表示成活，1表示未成活
        int[] nums = new int[total];
        
        // 初始化数组，所有元素设为0，表示所有树最初都是成活的
        Arrays.fill(nums, 0);
 
        // 根据输入，将未成活的树的位置标记为1
        for (int i = 0; i < deadCount; i++) {
            int num = scanner.nextInt();
            nums[num - 1] = 1; // 树的编号从1开始，因此需要减1
        }
        
        // 读取可以补种的树的数量
        int supplementCount = scanner.nextInt();
        
        // 初始化滑动窗口的左右边界
        int left = 0;
        int maxLen = 0; // 用于存储最大连续成活区域的长度
        int sumLeft = 0; // 滑动窗口左边界的未成活树数量
        int sumRight = 0; // 滑动窗口右边界的未成活树数量
        
        // 遍历所有的树，right代表滑动窗口的右边界
        for (int right = 0; right < total; right++) {
            sumRight += nums[right]; // 更新右边界的未成活树数量
            
            // 如果窗口内的未成活树数量大于可以补种的数量
            while (sumRight - sumLeft > supplementCount) {
                sumLeft += nums[left]; // 缩小窗口，左边界右移
                left++;
            }
            
            // 更新最大成活区域的长度
            maxLen = Math.max(maxLen, right - left + 1);
        }
        
        // 输出最大连续成活区域的长度
        System.out.println(maxLen);
    }
}

Python

# 读取胡杨树的总数N
total = int(input())

# 读取未成活胡杨树的数量M
dead_count = int(input())

# 读取未成活胡杨树的编号列表
dead_list = list(map(int, input().split()))

# 读取可以补种的胡杨树数量K
supplement_count = int(input())

# 初始化数组，所有树最初都是成活的，0表示成活，1表示未成活
nums = [0] * total

# 根据输入，将未成活的树的位置标记为1
for num in dead_list:
    nums[num - 1] = 1  # 树的编号从1开始，因此需要减1

# 初始化滑动窗口的左右边界
left = 0
max_len = 0  # 用于存储最大连续成活区域的长度
sum_left = 0  # 滑动窗口左边界的未成活树数量
sum_right = 0  # 滑动窗口右边界的未成活树数量

# 遍历所有的树，right代表滑动窗口的右边界
for right in range(total):
    sum_right += nums[right]  # 更新右边界的未成活树数量
    
    # 如果窗口内的未成活树数量大于可以补种的数量
    while sum_right - sum_left > supplement_count:
        sum_left += nums[left]  # 缩小窗口，左边界右移
        left += 1
    
    # 更新最大成活区域的长度
    max_len = max(max_len, right - left + 1)

# 输出最大连续成活区域的长度
print(max_len)

JavaScript

const readline = require('readline');


const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const inputLines = [];
rl.on('line', (input) => {
    inputLines.push(input);
});

rl.on('close', () => {
    // 读取胡杨树的总数N
    const total = parseInt(inputLines[0]);

    // 读取未成活胡杨树的数量M
    const deadCount = parseInt(inputLines[1]);

    // 读取未成活胡杨树的编号列表
    const deadList = inputLines[2].split(' ').map(Number);

    // 读取可以补种的胡杨树数量K
    const supplementCount = parseInt(inputLines[3]);

    // 初始化数组，所有树最初都是成活的，0表示成活，1表示未成活
    const nums = new Array(total).fill(0);

    // 根据输入，将未成活的树的位置标记为1
    deadList.forEach(num => {
        nums[num - 1] = 1; // 树的编号从1开始，因此需要减1
    });

    // 初始化滑动窗口的左右边界
    let left = 0;
    let maxLen = 0; // 用于存储最大连续成活区域的长度
    let sumLeft = 0; // 滑动窗口左边界的未成活树数量
    let sumRight = 0; // 滑动窗口右边界的未成活树数量

    // 遍历所有的树，right代表滑动窗口的右边界
    for (let right = 0; right < total; right++) {
        sumRight += nums[right]; // 更新右边界的未成活树数量
        
        // 如果窗口内的未成活树数量大于可以补种的数量
        while (sumRight - sumLeft > supplementCount) {
            sumLeft += nums[left]; // 缩小窗口，左边界右移
            left++;
        }
        
        // 更新最大成活区域的长度
        maxLen = Math.max(maxLen, right - left + 1);
    }

    // 输出最大连续成活区域的长度
    console.log(maxLen);
});

C++

#include <iostream>
#include <vector>
#include <algorithm> 

using namespace std;

int main() {
    int total, deadCount;
    cin >> total >> deadCount;

    // 初始化数组，所有树最初都是成活的，0表示成活，1表示未成活
    vector<int> nums(total, 0);

    // 根据输入，将未成活的树的位置标记为1
    for (int i = 0; i < deadCount; i++) {
        int num;
        cin >> num;
        nums[num - 1] = 1; // 树的编号从1开始，因此需要减1
    }

    // 读取可以补种的树的数量
    int supplementCount;
    cin >> supplementCount;

    // 初始化滑动窗口的左右边界
    int left = 0, maxLen = 0, sumLeft = 0, sumRight = 0;

    // 遍历所有的树，right代表滑动窗口的右边界
    for (int right = 0; right < total; right++) {
        sumRight += nums[right]; // 更新右边界的未成活树数量

        // 如果窗口内的未成活树数量大于可以补种的数量
        while (sumRight - sumLeft > supplementCount) {
            sumLeft += nums[left]; // 缩小窗口，左边界右移
            left++;
        }

        // 更新最大成活区域的长度
        maxLen = max(maxLen, right - left + 1);
    }

    // 输出最大连续成活区域的长度
    cout << maxLen << endl;

    return 0;
}

C

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

// 定义一个max函数，用于求两个数中的最大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    int total, deadCount;

    scanf("%d %d", &total, &deadCount);

    // 初始化数组，所有树最初都是成活的，0表示成活，1表示未成活
    int *nums = (int *)calloc(total, sizeof(int));

    // 根据输入，将未成活的树的位置标记为1
    for (int i = 0; i < deadCount; i++) {
        int num;
        scanf("%d", &num);
        nums[num - 1] = 1; // 树的编号从1开始，因此需要减1
    }

    // 读取可以补种的树的数量
    int supplementCount;
    scanf("%d", &supplementCount);

    // 初始化滑动窗口的左右边界
    int left = 0, maxLen = 0, sumLeft = 0, sumRight = 0;

    // 遍历所有的树，right代表滑动窗口的右边界
    for (int right = 0; right < total; right++) {
        sumRight += nums[right]; // 更新右边界的未成活树数量

        // 如果窗口内的未成活树数量大于可以补种的数量
        while (sumRight - sumLeft > supplementCount) {
            sumLeft += nums[left]; // 缩小窗口，左边界右移
            left++;
        }

        // 更新最大成活区域的长度
        maxLen = max(maxLen, right - left + 1);
    }

    // 输出最大连续成活区域的长度
    printf("%d\n", maxLen);

    // 释放动态分配的内存
    free(nums);

    return 0;
}

单指针解法，比较难理解

Java

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取胡杨树的总数N
        int total = scanner.nextInt();
        
        // 读取未成活胡杨树的数量M
        int deadCount = scanner.nextInt();

        // 存储未成活胡杨树编号的列表
        ArrayList<Integer> deadList = new ArrayList<>();
        
        // 读取未成活胡杨树的编号
        for (int i = 0; i < deadCount; i++) {
            int num = scanner.nextInt();
            deadList.add(num);
        }

        // 读取可以补种的胡杨树数量K
        int supplementCount = scanner.nextInt();
        
        // 初始化最大连续胡杨树的长度
        int maxLen = 0;
        
        // 遍历可能的补种位置，寻找最长连续胡杨树的长度
        for (int i = supplementCount - 1; i < deadCount; i++) {
            if (i == supplementCount - 1) {
                // 考虑补种后，从开头到第一个无法成活的区域
                maxLen = Math.max(maxLen, supplementCount == deadCount ? total : deadList.get(supplementCount) - 1);
            } else if (i == deadCount - 1) {
                // 考虑补种后，从最后一个无法成活的区域到结尾
                maxLen = Math.max(maxLen, total - deadList.get(i - supplementCount));
            } else {
                // 计算补种后的最大连续胡杨树
                maxLen = Math.max(maxLen, deadList.get(i + 1) - deadList.get(i - supplementCount) - 1);
            }
        }

        // 输出结果
        System.out.println(maxLen);
    }
}

Python

# 读取胡杨树的总数N
total = int(input())

# 读取未成活胡杨树的数量M
deadCount = int(input())

# 读取未成活胡杨树的编号列表
deadList = list(map(int, input().split()))

# 读取可以补种的胡杨树数量K
supplementCount = int(input())

# 初始化最大连续胡杨树的长度
maxLen = 0

# 遍历可能的补种位置，寻找最长连续胡杨树的长度
for i in range(supplementCount-1, deadCount):
    if i == supplementCount-1:
        # 考虑补种后，从开头到第一个无法成活的区域
        maxLen = max(maxLen, total if supplementCount == deadCount else deadList[supplementCount]-1)
    elif i == deadCount-1:
        # 考虑补种后，从最后一个无法成活的区域到结尾
        maxLen = max(maxLen, total - deadList[i-supplementCount])
    else:
        # 计算补种后的最大连续胡杨树
        maxLen = max(maxLen, deadList[i+1]-deadList[i-supplementCount]-1)

# 输出结果
print(maxLen)

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let totalNum, deadNum, deadIdx, maxReplantNum;

rl.on('line', (input) => {
  if (!totalNum) {
    // 读取胡杨树的总数N
    totalNum = parseInt(input);
  } else if (!deadNum) {
    // 读取未成活胡杨树的数量M
    deadNum = parseInt(input);
  } else if (!deadIdx) {
    // 读取未成活胡杨树的编号列表
    deadIdx = input.split(' ').map(Number);
  } else {
    // 读取可以补种的胡杨树数量K
    maxReplantNum = parseInt(input);
    
    let max = 0;
    
    // 遍历可能的补种位置，寻找最长连续胡杨树的长度
    for (let i = maxReplantNum - 1; i < deadNum; i++) {
      if (i === maxReplantNum - 1) {
        // 考虑补种后，从开头到第一个无法成活的区域
        max = Math.max(max, maxReplantNum === deadNum ? totalNum : deadIdx[maxReplantNum] - 1);
      } else if (i === deadNum - 1) {
        // 考虑补种后，从最后一个无法成活的区域到结尾
        max = Math.max(max, totalNum - deadIdx[i - maxReplantNum]);
      } else {
        // 计算补种后的最大连续胡杨树
        max = Math.max(max, deadIdx[i + 1] - deadIdx[i - maxReplantNum] - 1);
      }
    }
    
    // 输出结果
    console.log(max);
    rl.close();
  }
});

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 读取胡杨树的总数N
    int total;
    int deadCount;
    cin >> total >> deadCount;

    // 存储未成活胡杨树编号的列表
    vector<int> deadList;
    for (int i = 0; i < deadCount; i++) {
        int num;
        cin >> num;
        deadList.push_back(num);
    }

    // 读取可以补种的胡杨树数量K
    int supplementCount;
    cin >> supplementCount;

    // 初始化最大连续胡杨树的长度
    int maxLen = 0;

    // 遍历可能的补种位置，寻找最长连续胡杨树的长度
    for (int i = supplementCount - 1; i < deadCount; i++) {
        if (i == supplementCount - 1) {
            // 考虑补种后，从开头到第一个无法成活的区域
            maxLen = max(maxLen, supplementCount == deadCount ? total : deadList[supplementCount-1] - 1);
        } else if (i == deadCount - 1) {
            // 考虑补种后，从最后一个无法成活的区域到结尾
            maxLen = max(maxLen, total - deadList[i - supplementCount]);
        } else {
            // 计算补种后的最大连续胡杨树
            maxLen = max(maxLen, deadList[i + 1] - deadList[i - supplementCount] - 1);
        }
    }

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

    return 0;
}

C

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

int main() {
    // 读取胡杨树的总数N
    int total, deadCount;
    scanf("%d %d", &total, &deadCount);

    // 分配内存用于存储未成活胡杨树的编号
    int* deadList = (int*)malloc(deadCount * sizeof(int));
    for (int i = 0; i < deadCount; i++) {
        scanf("%d", &deadList[i]);
    }

    // 读取可以补种的胡杨树数量K
    int supplementCount;
    scanf("%d", &supplementCount);

    // 初始化最大连续胡杨树的长度
    int maxLen = 0;

    // 遍历可能的补种位置，寻找最长连续胡杨树的长度
    for (int i = supplementCount - 1; i < deadCount; i++) {
        if (i == supplementCount - 1) {
            // 考虑补种后，从开头到第一个无法成活的区域
            maxLen = maxLen > (supplementCount == deadCount ? total : deadList[supplementCount] - 1) 
                     ? maxLen : (supplementCount == deadCount ? total : deadList[supplementCount] - 1);
        } else if (i == deadCount - 1) {
            // 考虑补种后，从最后一个无法成活的区域到结尾
            maxLen = maxLen > (total - deadList[i - supplementCount]) 
                     ? maxLen : (total - deadList[i - supplementCount]);
        } else {
            // 计算补种后的最大连续胡杨树
            maxLen = maxLen > (deadList[i + 1] - deadList[i - supplementCount] - 1) 
                     ? maxLen : (deadList[i + 1] - deadList[i - supplementCount] - 1);
        }
    }

    // 输出结果
    printf("%d\n", maxLen);

    // 释放分配的内存
    free(deadList);

    return 0;
}
#华为##OD##牛客创作赏金赛#
大厂原题(全网最全，持续更新) 文章被收录于专栏

主要记录自己的刷题日常，学而时习之。

全部评论

相关推荐

11-21 13:08
蚌埠坦克学院 C++
金山WPS
服从性笔试吗，发这么多笔，现在还在发。
蟑螂恶霸zZ：傻 x 公司，发两次笔试，两次部门匹配挂，
投递金山WPS等公司10个岗位 >
点赞 评论 收藏
分享
11-24 11:40
北京城市学院 项目经理
点赞 评论 收藏
分享
10-13 13:35
第一拖拉机制造厂拖拉机学院 Java
逆天
太逆天了这个
挣K存W养DOG：他真的很中意你，为什么不回他
点赞 评论 收藏
分享
11-08 13:58
门头沟学院 Java
鼠鼠我啊终于有 offer 了！！
喜大普奔
程序员小白条：竟然是蓝桥杯人才doge,还要花钱申领的offer，这么好的公司哪里去找
点赞 评论 收藏
分享
11-23 23:34
旷视_运营_HR
旷视11月缺人岗位
11月这两个岗位比较缺人，大家还没投的继续试试！大模型产品经理（北京）职位描述：1.负责大模型ToB业务的规划设计，包括ToB产品的设计迭代以及关键项目的落地；2.根据落地场景把控大模型优化方向，设计大模型产品效果评估指标体系，参与产品的评估、验收相关工作；3.与基座模型、研发、设计、销售团队紧密合作，高效协同各方资源，保证项目高质量交付；4.关注行业及竞品最新动态，输出市场调研与分析，为产品优化提供有效建议。职位要求：1.&nbsp;计算机相关专业本科及以上学历；2.有责任心和owner意识，有优秀的沟通和协调能力；3.具备优秀的自学能力和独立思考能力，善于思考和表达自己的想法，具备良好的团队合作精神...
投递旷视等公司10个岗位 >
点赞 评论 收藏
分享
点赞 收藏 评论
分享

招聘动态

查看更多

字节跳动

2025校园招聘

阿里云管培生

2025届校园招聘

快手Star

2025届招聘

快手

销售类投递专区

全站热榜

正在热议
# 25届秋招总结 #
368652次浏览 3643人参与
# 如果再来一次，你还会选择这个工作吗？ #
96000次浏览 929人参与
# 百度开奖 #
223934次浏览 1458人参与
# 地方国企笔面经互助 #
5749次浏览 13人参与
# ai智能作图 #
7891次浏览 136人参与
# 发工资后，你做的第一件事是什么 #
3593次浏览 15人参与
# 北方华创开奖 #
51811次浏览 488人参与
# 我的实习求职记录 #
6097647次浏览 83775人参与
# 简历被挂麻了，求建议 #
2520175次浏览 33418人参与
# 牛客租房专区 #
2056次浏览 74人参与
# 上班到公司第一件事做什么？ #
14443次浏览 164人参与
# 阿里求职进展汇总 #
71482次浏览 772人参与
# 听到哪句话就代表面试稳了or挂了？ #
96129次浏览 807人参与
# 华为工作体验 #
108845次浏览 851人参与
# 网易求职进展汇总 #
38725次浏览 319人参与
# 如何写一份好简历 #
614996次浏览 8692人参与
# 如果有时光机，你最想去到哪个年纪？ #
26435次浏览 545人参与
# 面试体验感最好的是哪家？ #
91225次浏览 902人参与
# 还记得你第一次面试吗？ #
27465次浏览 362人参与
# 如何一边实习一边秋招 #
1001639次浏览 12726人参与
# 腾讯求职进展汇总 #
204135次浏览 1684人参与
# 实习中的菜狗时刻 #
279681次浏览 2753人参与
牛客网
牛客企业服务