华为OD机试真题-补种未成活胡杨（Java/C++/Go/Python）

华为OD机试真题-补种未成活胡杨（Java/C++/Go/Python）

题目描述

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

一个月后，有M棵胡杨未能成活。现可补种胡杨K棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？

输入描述

N 总种植数量 1<=N<=100000 M 未成活胡杨数量 1<=M<=N M 个空格分隔的数，按编号从小到大排列 K 最多可以补种的数量 0<=K<=M

输出描述

最多的连续胡杨棵树

示例1

输入

5

2

2 4

1
1
2
3
4
5
6
7

输出

3
1

说明

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

示例2

输入

10

3

2 4 7

1
1
2
3
4
5
6
7

输出

6
1

说明

补种第7棵树，最多的连续胡杨棵树为6(5,6,7,8,9,10)

解题思路

1.用0代表死树，1代表活着的树，把题目转化为求含有k个0的最长子串

2，采用滑动窗口，每当窗口含有k个0时，求子串最大长度，同时用queue

存储每个0的下标，窗口有k个0时，将queue栈顶的下标更新为left

考点

滑动窗口

代码

Java代码

import java.util.*;  
  
public class Main {  
    // Function to calculate the maximum distance between 0s  
    public static int slide(int[] all, int k) {  
        int res = 0; // Result to be returned  
        Queue<Integer> q = new LinkedList<>(); // Queue to store indices of 0s  
        int left = 1; // Start index for the current 0  
  
        for (int i = 1; i < all.length; i++) {  
            if (all[i] == 0) {  
                q.add(i); // Add index of 0 to the queue  
            }  
            if (q.size() > k) {  
                res = Math.max(res, i - left); // Calculate the distance and update res  
                left = q.peek() + 1; // Calculate the next start index  
                q.remove(); // Remove the first element from queue  
                continue; // Continue to next iteration  
            }  
            if ((k == q.size() && i == all.length - 1)) {  
                res = Math.max(res, i - left + 1); // Calculate the distance for the last 0  
            }  
        }  
        return res;  
    }  
  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        int n = scanner.nextInt(); // Read the number of elements  
        int M = scanner.nextInt(); // Read the number of zeros to be inserted  
        int k = scanner.nextInt(); // Read the distance threshold  
        int[] all = new int[n + 1]; // Create an array with size n+1, initialized to all 1s  
  
        for (int i = 0; i < M; i++) {  
            int tmp = scanner.nextInt(); // Read the position of next zero to be inserted  
            all[tmp] = 0; // Insert the zero at the specified position  
        }  
  
        int res = slide(all, k); // Calculate the maximum distance between zeros  
        System.out.println(res); // Print the result  
    }  
}
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
41
42

这个Java代码首先读取路灯的个数和每个路灯的照明半径。接下来，它使用一个循环来计算无法照明的区间的长度和。
在每次迭代中，它计算当前路灯与前一个路灯之间以及当前路灯与后一个路灯之间的区间长度，
并将它们累加到totalLength变量中。最后，输出totalLength的值作为结果。
需要注意的是，由于题目中给出的路灯个数和照明半径的范围很大，因此需要使用长整型变量来存储totalLength，以避免整数溢出的问题。
1
2
3
4

C++代码

#include 
using namespace std;
int slide(vector<int> all, int k) {
    int res=0;
    queue<int> q;
    int left=1;
    for(int i=1;i<all.size();i++) {
        if(all[i]==0) {
            q.push(i);//q存0的下标
        }
        if(q.size()>k) {
            res=max(res,i-left);
            left=q.front()+1; //不要忘记加1
            q.pop();
            continue;
        }
        if((k==q.size() && i==all.size()-1)) {
            res=max(res,i-left+1);
        }
    }
    return res;
}
int main() {
    int n,M,k;
    cin>>n>>M;
    vector<int> all(n+1,1);
    for(int i=0;i<M;i++) {
        int tmp;
        cin>>tmp;
        all[tmp]=0;
    }
    cin>>k;
    int res=slide(all,k);
    cout<<res<<endl;
    system("pause");
    return 0;
}
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

Python代码

n=int(input())
arr=[]
for i in range(n):
    arr.append(1)
M=int(input()) # 死树棵树
line=input().split()
for i in  line:
    tmp=int(i)-1
    arr[tmp]=0
k=int(input()) # 补种棵树
left=0
res=0
sum=0 # 记录0的个数
for i in range(n):
    if arr[i]==0:
        sum+=1
    if sum==k:
        res=max(res,i-left+1)
    if sum>k:
        while sum>k:
            if arr[left]==0:
                sum-=1
            left+=1
print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Go代码

package main  
  
import (  
 "fmt"  
)  
  
func main() {  
 var N int  
 fmt.Scanln(&N) // 读取路灯个数  
  
 radii := make([]int, N) // 存储每个路灯的照明半径  
 for i := 0; i < N; i++ {  
 fmt.Scan(&radii[i]) // 读取每个路灯的照明半径  
 }  
  
 // 计算无法照明的区间的长度和  
 var totalLength int  
 for i := 0; i < N; i++ {  
 if i > 0 {  
 totalLength += (radii[i] + radii[i-1] - 100) // 当前路灯与前一个路灯之间的区间长度  
 }  
 if i < N-1 {  
 totalLength += (radii[i] + radii[i+1] - 100) // 当前路灯与后一个路灯之间的区间长度  
 }  
 }  
  
 fmt.Println(totalLength) // 输出结果  
}
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

这段代码首先读取路灯的个数和每个路灯的照明半径。然后，使用一个循环来计算无法照明的区间的长度和。在每次迭代中，它计算当前路灯与前一个路灯之间以及当前路灯与后一个路灯之间的区间长度，并将它们累加到totalLength变量中。最后，输出totalLength的值作为结果。
注意，在读取输入时，使用fmt.Scanln()函数来读取整数值。而在输出结果时，使用fmt.Println()函数来打印结果。另外，为了方便计算，将照明半径存储在一个切片中，使用索引来访问每个路灯的照明半径。
1
2