【2024年华为OD机试】 (B卷,100分)- 太阳能板最大面积(Java JS PythonC/C++)
一、问题描述
题目描述
给航天器一侧加装长方形或正方形的太阳能板(图中的红色斜线区域),需要先安装两个支柱(图中的黑色竖条),再在支柱的中间部分固定太阳能板。
但航天器不同位置的支柱长度不同,太阳能板的安装面积受限于最短一侧的那根支柱长度。如图:
现提供一组整形数组的支柱高度数据,假设每根支柱间距离相等为1个单位长度,计算如何选择两根支柱可以使太阳能板的面积最大。
输入描述
10,9,8,7,6,5,4,3,2,1
注:支柱至少有2根,最多10000根,能支持的高度范围1~10^9的整数。柱子的高度是无序的,例子中递减只是巧合。
输出描述
可以支持的最大太阳能板面积:(10米高支柱和5米高支柱之间)
25
用例
用例
输入
10,9,8,7,6,5,4,3,2,1
输出
25
备注
10米高支柱和5米高支柱之间宽度为5,高度取小的支柱高也是5,面积为25。
任取其他两根支柱所能获得的面积都小于25。
所以最大的太阳能板面积为25。
题目解析
考察点
考察双指针技巧和优化算法效率。
解析思路
- 暴力破解:
- 最直接的方法是使用两层循环,枚举所有可能的支柱对,计算每对支柱之间的面积,然后找出最大值。
- 对于每对支柱,面积等于两根支柱之间的距离乘以较短支柱的高度。
- 这种方法的时间复杂度为O(n^2),对于大规模数据(如10000根支柱)效率较低。
- 双指针法:
- 使用两个指针,一个指向数组的开始,另一个指向数组的末尾。
- 计算这两根支柱之间的面积,然后移动较短的那根支柱的指针,向中间移动一位,再次计算面积。
- 重复上述步骤,直到两个指针相遇。
- 这种方法的时间复杂度为O(n),效率较高。
- 面积计算:
- 面积 = (指针2的位置 - 指针1的位置) * min(指针1的高度, 指针2的高度)
- 每次移动指针时,都重新计算面积,并更新最大面积。
双指针法详细步骤
- 初始化指针:
- 初始化两个指针
i
和j
,i
指向数组的开始位置(0),j
指向数组的末尾位置(arr.length - 1
)。
- 初始化两个指针
- 计算初始面积:
- 计算初始面积
area = (j - i) * min(arr[i], arr[j])
。
- 计算初始面积
- 移动指针:
- 如果
arr[i] < arr[j]
,则arr[i]
是较短的支柱,对于arr[i]
来说,它作为矮柱的最大面积已经求出,移动i
指针到下一位(i++
)。 - 如果
arr[i] > arr[j]
,则arr[j]
是较短的支柱,对于arr[j]
来说,它作为矮柱的最大面积已经求出,移动j
指针到下一位(j--
)。
- 如果
- 更新最大面积:
- 每次移动指针后,重新计算面积,并更新最大面积。
- 终止条件:
- 当
i
和j
相遇时,终止循环。
- 当
注意事项
- 数据类型:由于最大太阳能板面积可能发生整型溢出,建议使用
long
类型来存储面积。 - 效率:双指针法的时间复杂度为O(n),适用于大规模数据。
- 边界条件:确保指针移动时不会越界,特别是在移动指针时要检查指针的位置。
二、JavaScript算法源码
以下是 JavaScript 代码的详细中文注释和讲解:
JavaScript 代码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
// 创建 readline 接口实例
const rl = readline.createInterface({
input: process.stdin, // 输入流为标准输入
output: process.stdout, // 输出流为标准输出
});
// 监听 'line' 事件,当用户输入一行数据时触发
rl.on("line", (line) => {
// 将输入的一行数据按逗号分割,并转换为整数数组
const arr = line.split(",").map((ele) => parseInt(ele));
// 调用 getMaxArea 函数并输出结果
console.log(getMaxArea(arr));
});
// 计算最大面积
function getMaxArea(arr) {
let i = 0; // 左指针,初始指向数组的第一个元素
let j = arr.length - 1; // 右指针,初始指向数组的最后一个元素
let maxArea = 0; // 记录最大面积
// 使用双指针法遍历数组
while (i < j) {
let x = j - i; // 计算两根柱子之间的距离(宽度)
let y = arr[i] < arr[j] ? arr[i++] : arr[j--]; // 选择较矮的柱子作为高度,并移动指针
maxArea = Math.max(maxArea, x * y); // 计算当前面积,并更新最大面积
}
// 返回最大面积
return maxArea;
}
详细讲解
1. 输入处理
const readline = require("readline");
// 创建 readline 接口实例
const rl = readline.createInterface({
input: process.stdin, // 输入流为标准输入
output: process.stdout, // 输出流为标准输出
});
// 监听 'line' 事件,当用户输入一行数据时触发
rl.on("line", (line) => {
// 将输入的一行数据按逗号分割,并转换为整数数组
const arr = line.split(",").map((ele) => parseInt(ele));
// 调用 getMaxArea 函数并输出结果
console.log(getMaxArea(arr));
});
- 功能:
- 使用
readline
模块从控制台读取输入。 - 将输入的一行数据按逗号分割,并转换为整数数组
arr
。 - 调用
getMaxArea
函数并输出结果。
- 使用
2. 核心函数 getMaxArea
function getMaxArea(arr) {
let i = 0; // 左指针,初始指向数组的第一个元素
let j = arr.length - 1; // 右指针,初始指向数组的最后一个元素
let maxArea = 0; // 记录最大面积
// 使用双指针法遍历数组
while (i < j) {
let x = j - i; // 计算两根柱子之间的距离(宽度)
let y = arr[i] < arr[j] ? arr[i++] : arr[j--]; // 选择较矮的柱子作为高度,并移动指针
maxArea = Math.max(maxArea, x * y); // 计算当前面积,并更新最大面积
}
// 返回最大面积
return maxArea;
}
- 功能:
- 计算数组中两根柱子之间的最大面积。
- 算法逻辑:
- 初始化两个指针
i
和j
,分别指向数组的起始和末尾。 - 使用
while
循环遍历数组,直到i
和j
相遇。 - 在每次循环中:
- 计算两根柱子之间的距离
x
(即j - i
)。 - 选择较矮的柱子作为高度
y
,并移动指针(如果左边柱子较矮,则i++
;否则j--
)。 - 计算当前面积
x * y
,并更新最大面积maxArea
。
- 计算两根柱子之间的距离
- 返回最大面积
maxArea
。
- 初始化两个指针
代码运行示例
示例 1:
输入:
1,8,6,2,5,4,8,3,7
输出:
49
解释:
- 最大面积由高度为
7
和宽度为7
的柱子组成,面积为7 * 7 = 49
。
示例 2:
输入:
4,3,2,1,4
输出:
16
解释:
- 最大面积由高度为
4
和宽度为4
的柱子组成,面积为4 * 4 = 16
。
总结
- 功能:
- 计算数组中两根柱子之间的最大面积。
- 优点:
- 使用双指针法,时间复杂度为
O(n)
,效率高。 - 代码简洁,逻辑清晰。
- 使用双指针法,时间复杂度为
- 适用场景:
- 适用于需要计算最大面积的场景,如容器盛水问题。
如果您有其他问题,欢迎随时提问!
三、Java算法源码
以下是 Java 代码的详细中文注释和讲解:
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 创建 Scanner 对象,用于从控制台读取输入
Scanner sc = new Scanner(System.in);
// 读取一行输入,按逗号分割并转换为整数数组
int[] heights = Arrays.stream(sc.nextLine().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// 调用 getResult 方法并输出结果
System.out.println(getResult(heights));
}
// 计算最大面积
public static long getResult(int[] heights) {
int l = 0; // 左指针,初始指向数组的第一个元素
int r = heights.length - 1; // 右指针,初始指向数组的最后一个元素
long maxArea = 0; // 记录最大面积
// 使用双指针法遍历数组
while (l < r) {
long x = r - l; // 计算两根柱子之间的距离(宽度)
long y = heights[l] < heights[r] ? heights[l++] : heights[r--]; // 选择较矮的柱子作为高度,并移动指针
maxArea = Math.max(maxArea, x * y); // 计算当前面积,并更新最大面积
}
// 返回最大面积
return maxArea;
}
}
详细讲解
1. 输入处理
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 创建 Scanner 对象,用于从控制台读取输入
Scanner sc = new Scanner(System.in);
// 读取一行输入,按逗号分割并转换为整数数组
int[] heights = Arrays.stream(sc.nextLine().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// 调用 getResult 方法并输出结果
System.out.println(getResult(heights));
}
}
- 功能:
- 使用
Scanner
从控制台读取输入。 - 将输入的一行数据按逗号分割,并转换为整数数组
heights
。 - 调用
getResult
方法并输出结果。
- 使用
2. 核心方法 getResult
public static long getResult(int[] heights) {
int l = 0; // 左指针,初始指向数组的第一个元素
int r = heights.length - 1; // 右指针,初始指向数组的最后一个元素
long maxArea = 0; // 记录最大面积
// 使用双指针法遍历数组
while (l < r) {
long x = r - l; // 计算两根柱子之间的距离(宽度)
long y = heights[l] < heights[r] ? heights[l++] : heights[r--]; // 选择较矮的柱子作为高度,并移动指针
maxArea = Math.max(maxArea, x * y); // 计算当前面积,并更新最大面积
}
// 返回最大面积
return maxArea;
}
- 功能:
- 计算数组中两根柱子之间的最大面积。
- 算法逻辑:
- 初始化两个指针
l
和r
,分别指向数组的起始和末尾。 - 使用
while
循环遍历数组,直到l
和r
相遇。 - 在每次循环中:
- 计算两根柱子之间的距离
x
(即r - l
)。 - 选择较矮的柱子作为高度
y
,并移动指针(如果左边柱子较矮,则l++
;否则r--
)。 - 计算当前面积
x * y
,并更新最大面积maxArea
。
- 计算两根柱子之间的距离
- 返回最大面积
maxArea
。
- 初始化两个指针
代码运行示例
示例 1:
输入:
1,8,6,2,5,4,8,3,7
输出:
49
解释:
- 最大面积由高度为
7
和宽度为7
的柱子组成,面积为7 * 7 = 49
。
示例 2:
输入:
4,3,2,1,4
输出:
16
解释:
- 最大面积由高度为
4
和宽度为4
的柱子组成,面积为4 * 4 = 16
。
总结
- 功能:
- 计算数组中两根柱子之间的最大面积。
- 优点:
- 使用双指针法,时间复杂度为
O(n)
,效率高。 - 代码简洁,逻辑清晰。
- 使用双指针法,时间复杂度为
- 适用场景:
- 适用于需要计算最大面积的场景,如容器盛水问题。
如果您有其他问题,欢迎随时提问!
四、Python算法源码
以下是 Python 代码的详细中文注释和讲解:
Python 代码
# 输入获取
heights = list(map(int, input().split(",")))
# 算法入口
def getResult():
l = 0 # 左指针,初始指向数组的第一个元素
r = len(heights) - 1 # 右指针,初始指向数组的最后一个元素
maxArea = 0 # 记录最大面积
# 使用双指针法遍历数组
while l < r:
x = r - l # 计算两根柱子之间的距离(宽度)
# 选择较矮的柱子作为高度,并移动指针
y = 0
if heights[l] < heights[r]:
y = heights[l]
l += 1
else:
y = heights[r]
r -= 1
# 计算当前面积,并更新最大面积
maxArea = max(maxArea, x * y)
# 返回最大面积
return maxArea
# 算法调用
print(getResult())
详细讲解
1. 输入处理
# 输入获取
heights = list(map(int, input().split(",")))
- 功能:
- 使用
input()
从控制台读取一行输入。 - 将输入的一行数据按逗号分割,并转换为整数列表
heights
。
- 使用
2. 核心函数 getResult
def getResult():
l = 0 # 左指针,初始指向数组的第一个元素
r = len(heights) - 1 # 右指针,初始指向数组的最后一个元素
maxArea = 0 # 记录最大面积
# 使用双指针法遍历数组
while l < r:
x = r - l # 计算两根柱子之间的距离(宽度)
# 选择较矮的柱子作为高度,并移动指针
y = 0
if heights[l] < heights[r]:
y = heights[l]
l += 1
else:
y = heights[r]
r -= 1
# 计算当前面积,并更新最大面积
maxArea = max(maxArea, x * y)
# 返回最大面积
return maxArea
- 功能:
- 计算数组中两根柱子之间的最大面积。
- 算法逻辑:
- 初始化两个指针
l
和r
,分别指向数组的起始和末尾。 - 使用
while
循环遍历数组,直到l
和r
相遇。 - 在每次循环中:
- 计算两根柱子之间的距离
x
(即r - l
)。 - 选择较矮的柱子作为高度
y
,并移动指针(如果左边柱子较矮,则l++
;否则r--
)。 - 计算当前面积
x * y
,并更新最大面积maxArea
。
- 计算两根柱子之间的距离
- 返回最大面积
maxArea
。
- 初始化两个指针
3. 算法调用
# 算法调用
print(getResult())
- 功能:
- 调用
getResult
函数并输出结果。
- 调用
代码运行示例
示例 1:
输入:
1,8,6,2,5,4,8,3,7
输出:
49
解释:
- 最大面积由高度为
7
和宽度为7
的柱子组成,面积为7 * 7 = 49
。
示例 2:
输入:
4,3,2,1,4
输出:
16
解释:
- 最大面积由高度为
4
和宽度为4
的柱子组成,面积为4 * 4 = 16
。
总结
- 功能:
- 计算数组中两根柱子之间的最大面积。
- 优点:
- 使用双指针法,时间复杂度为
O(n)
,效率高。 - 代码简洁,逻辑清晰。
- 使用双指针法,时间复杂度为
- 适用场景:
- 适用于需要计算最大面积的场景,如容器盛水问题。
如果您有其他问题,欢迎随时提问!
五、C/C++算法源码:
以下是 C语言 和 C++ 代码的详细中文注释和讲解:
C语言代码
#include <stdio.h>
// 定义宏,用于计算两个数的最大值
#define MAX(a, b) ((a) > (b) ? (a) : (b))
// 定义数组的最大容量
#define MAX_SIZE 10000
int main() {
int heights[MAX_SIZE]; // 存储输入的高度数组
int heights_size = 0; // 记录数组的实际大小
// 从标准输入读取数据,以逗号分隔
while (scanf("%d", &heights[heights_size++])) {
if (getchar() != ',') break; // 如果下一个字符不是逗号,则结束输入
}
int l = 0; // 左指针,初始指向数组的第一个元素
int r = heights_size - 1; // 右指针,初始指向数组的最后一个元素
long maxArea = 0; // 记录最大面积
// 使用双指针法遍历数组
while (l < r) {
long x = r - l; // 计算两根柱子之间的距离(宽度)
long y = heights[l] < heights[r] ? heights[l++] : heights[r--]; // 选择较矮的柱子作为高度,并移动指针
maxArea = MAX(maxArea, x * y); // 计算当前面积,并更新最大面积
}
// 输出最大面积
printf("%ld\n", maxArea);
return 0;
}
C++代码
#include <iostream>
#include <vector>
using namespace std;
// 定义宏,用于计算两个数的最大值
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int main() {
vector<int> heights; // 使用动态数组存储输入的高度
int num;
char sep;
// 从标准输入读取数据,以逗号分隔
while (cin >> num) {
heights.push_back(num); // 将数字添加到数组中
sep = cin.get(); // 读取分隔符
if (sep != ',') break; // 如果下一个字符不是逗号,则结束输入
}
int l = 0; // 左指针,初始指向数组的第一个元素
int r = heights.size() - 1; // 右指针,初始指向数组的最后一个元素
long maxArea = 0; // 记录最大面积
// 使用双指针法遍历数组
while (l < r) {
long x = r - l; // 计算两根柱子之间的距离(宽度)
long y = heights[l] < heights[r] ? heights[l++] : heights[r--]; // 选择较矮的柱子作为高度,并移动指针
maxArea = MAX(maxArea, x * y); // 计算当前面积,并更新最大面积
}
// 输出最大面积
cout << maxArea << endl;
return 0;
}
详细讲解
1. 输入处理
-
C语言:
int heights[MAX_SIZE]; // 存储输入的高度数组 int heights_size = 0; // 记录数组的实际大小 // 从标准输入读取数据,以逗号分隔 while (scanf("%d", &heights[heights_size++])) { if (getchar() != ',') break; // 如果下一个字符不是逗号,则结束输入 }
- 使用
scanf
读取整数,并通过getchar
判断是否继续读取。 - 将数据存储在静态数组
heights
中,并记录数组大小heights_size
。
- 使用
-
C++:
vector<int> heights; // 使用动态数组存储输入的高度 int num; char sep; // 从标准输入读取数据,以逗号分隔 while (cin >> num) { heights.push_back(num); // 将数字添加到数组中 sep = cin.get(); // 读取分隔符 if (sep != ',') break; // 如果下一个字符不是逗号,则结束输入 }
- 使用
cin
读取整数,并通过cin.get
判断是否继续读取。 - 将数据存储在动态数组
heights
中。
- 使用
2. 核心逻辑
- C语言和C++:
int l = 0; // 左指针,初始指向数组的第一个元素 int r = heights_size - 1; // 右指针,初始指向数组的最后一个元素 long maxArea = 0; // 记录最大面积 // 使用双指针法遍历数组 while (l < r) { long x = r - l; // 计算两根柱子之间的距离(宽度) long y = heights[l] < heights[r] ? heights[l++] : heights[r--]; // 选择较矮的柱子作为高度,并移动指针 maxArea = MAX(maxArea, x * y); // 计算当前面积,并更新最大面积 }
- 初始化两个指针
l
和r
,分别指向数组的起始和末尾。 - 使用
while
循环遍历数组,直到l
和r
相遇。 - 在每次循环中:
- 计算两根柱子之间的距离
x
(即r - l
)。 - 选择较矮的柱子作为高度
y
,并移动指针(如果左边柱子较矮,则l++
;否则r--
)。 - 计算当前面积
x * y
,并更新最大面积maxArea
。
- 计算两根柱子之间的距离
- 初始化两个指针
3. 输出结果
-
C语言:
printf("%ld\n", maxArea);
- 使用
printf
输出最大面积。
- 使用
-
C++:
cout << maxArea << endl;
- 使用
cout
输出最大面积。
- 使用
代码运行示例
示例 1:
输入:
1,8,6,2,5,4,8,3,7
输出:
49
解释:
- 最大面积由高度为
7
和宽度为7
的柱子组成,面积为7 * 7 = 49
。
示例 2:
输入:
4,3,2,1,4
输出:
16
解释:
- 最大面积由高度为
4
和宽度为4
的柱子组成,面积为4 * 4 = 16
。
总结
- 功能:
- 计算数组中两根柱子之间的最大面积。
- 优点:
- 使用双指针法,时间复杂度为
O(n)
,效率高。 - 代码简洁,逻辑清晰。
- 使用双指针法,时间复杂度为
- 适用场景:
- 适用于需要计算最大面积的场景,如容器盛水问题。
如果您有其他问题,欢迎随时提问!
六、尾言
什么是华为OD?
华为OD(Outsourcing Developer,外包开发工程师)是华为针对软件开发工程师岗位的一种招聘形式,主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分,算法题的机试至关重要。
为什么刷题很重要?
-
机试是进入技术面的第一关:
华为OD机试(常被称为机考)主要考察算法和编程能力。只有通过机试,才能进入后续的技术面试环节。 -
技术面试需要手撕代码:
技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。 -
入职后的可信考试:
入职华为后,还需要通过“可信考试”。可信考试分为三个等级:- 入门级:主要考察基础算法与编程能力。
- 工作级:更贴近实际业务需求,可能涉及复杂的算法或与工作内容相关的场景题目。
- 专业级:最高等级,考察深层次的算法以及优化能力,与薪资直接挂钩。
刷题策略与说明:
2024年8月14日之后,华为OD机试的题库转为 E卷,由往年题库(D卷、A卷、B卷、C卷)和全新题目组成。刷题时可以参考以下策略:
-
关注历年真题:
- 题库中的旧题占比较大,建议优先刷历年的A卷、B卷、C卷、D卷题目。
- 对于每道题目,建议深度理解其解题思路、代码实现,以及相关算法的适用场景。
-
适应新题目:
- E卷中包含全新题目,需要掌握全面的算法知识和一定的灵活应对能力。
- 建议关注新的刷题平台或交流群,获取最新题目的解析和动态。
-
掌握常见算法:
华为OD考试通常涉及以下算法和数据结构:- 排序算法(快速排序、归并排序等)
- 动态规划(背包问题、最长公共子序列等)
- 贪心算法
- 栈、队列、链表的操作
- 图论(最短路径、最小生成树等)
- 滑动窗口、双指针算法
-
保持编程规范:
- 注重代码的可读性和注释的清晰度。
- 熟练使用常见编程语言,如C++、Java、Python等。
如何获取资源?
-
官方参考:
- 华为招聘官网或相关的招聘平台会有一些参考信息。
- 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。
-
加入刷题社区:
- 找到可信的刷题交流群,与其他备考的小伙伴交流经验。
- 关注知名的刷题网站,如LeetCode、牛客网等,这些平台上有许多华为OD的历年真题和解析。
-
寻找系统性的教程:
- 学习一本经典的算法书籍,例如《算法导论》《剑指Offer》《编程之美》等。
- 完成系统的学习课程,例如数据结构与算法的在线课程。
积极心态与持续努力:
刷题的过程可能会比较枯燥,但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试,还是为了未来的职业发展,这些积累都会成为重要的财富。
考试注意细节
-
本地编写代码
- 在本地 IDE(如 VS Code、PyCharm 等)上编写、保存和调试代码,确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误,提高代码准确性。
-
调整心态,保持冷静
- 遇到提示不足或实现不确定的问题时,不必慌张,可以采用更简单或更有把握的方法替代,确保思路清晰。
-
输入输出完整性
- 注意训练和考试时都需要编写完整的输入输出代码,尤其是和题目示例保持一致。完成代码后务必及时调试,确保功能符合要求。
-
快捷键使用
- 删除行可用
Ctrl+D
,复制、粘贴和撤销分别为Ctrl+C
,Ctrl+V
,Ctrl+Z
,这些可以正常使用。 - 避免使用
Ctrl+S
,以免触发浏览器的保存功能。
- 删除行可用
-
浏览器要求
- 使用最新版的 Google Chrome 浏览器完成考试,确保摄像头开启并正常工作。考试期间不要切换到其他网站,以免影响考试成绩。
-
交卷相关
- 答题前,务必仔细查看题目示例,避免遗漏要求。
- 每完成一道题后,点击【保存并调试】按钮,多次保存和调试是允许的,系统会记录得分最高的一次结果。完成所有题目后,点击【提交本题型】按钮。
- 确保在考试结束前提交试卷,避免因未保存或调试失误而丢分。
-
时间和分数安排
- 总时间:150 分钟;总分:400 分。
- 试卷结构:2 道一星难度题(每题 100 分),1 道二星难度题(200 分)。及格分为 150 分。合理分配时间,优先完成自己擅长的题目。
-
考试环境准备
- 考试前请备好草稿纸和笔。考试中尽量避免离开座位,确保监控画面正常。
- 如需上厕所,请提前规划好时间以减少中途离开监控的可能性。
-
技术问题处理
- 如果考试中遇到断电、断网、死机等技术问题,可以关闭浏览器并重新打开试卷链接继续作答。
- 出现其他问题,请第一时间联系 HR 或监考人员进行反馈。
祝你考试顺利,取得理想成绩!