【2024年华为OD机试】(A卷,200分)- 探索地块建立 (Java JS PythonC/C++)

embedded/2025/1/24 12:19:04/

在这里插入图片描述

一、问题描述

题目描述

给一块nm的地块,相当于nm的二维数组,每个元素的值表示这个小地块的发电量;

求在这块地上建立正方形的边长为c的发电站,发电量满足目标电量k的地块数量。

输入描述

第一行为四个按空格分隔的正整数,分别表示n, m, c, k

后面n行整数,表示每个地块的发电量

输出描述

输出满足条件的地块数量

用例

输入

2 5 2 6
1 3 4 5 8
2 3 6 7 1

输出

4

说明

题目解析

本题最优解题思路是使用:二维矩阵前缀和。

解题思路
  1. 构建前缀和矩阵

    • 创建一个(n+1) x (m+1)的前缀和矩阵prefixSum,用于存储从(0,0)到(i,j)的子矩阵的发电量总和。
    • 遍历每个地块的发电量,更新前缀和矩阵:
      • prefixSum[i+1][j+1] = prefixSum[i+1][j] + prefixSum[i][j+1] - prefixSum[i][j] + grid[i][j]
  2. 计算每个可能的发电站的发电量

    • 遍历每个可能的发电站位置,计算其发电量:
      • 对于每个左上角位置(i, j),计算右下角位置(i+c, j+c)的发电量:
        • sum = prefixSum[i+c][j+c] - prefixSum[i+c][j] - prefixSum[i][j+c] + prefixSum[i][j]
    • 如果计算出的发电量等于目标电量k,则计数器加1。
  3. 输出结果

    • 输出满足条件的地块数量。
二维矩阵前缀和
  • 前缀和矩阵:前缀和矩阵prefixSum的每个元素prefixSum[i][j]表示从(0,0)到(i-1,j-1)的子矩阵的发电量总和。
  • 计算子矩阵发电量:通过前缀和矩阵,可以快速计算任意子矩阵的发电量:
    • sum = prefixSum[i2][j2] - prefixSum[i2][j1] - prefixSum[i1][j2] + prefixSum[i1][j1]

通过这种方法,我们可以高效地计算出满足条件的地块数量。时间复杂度为O(n * m),其中n和m分别是地块的行数和列数,因为我们只需要遍历地块几次。

二、JavaScript算法源码

以下是 JavaScript 代码的详细中文注释与讲解。此代码的功能是计算一个 n * m 的地块中,所有边长为 c 的正方形区域内的电量总和是否大于等于目标电量 k,并统计满足条件的正方形区域数量。


代码功能

  1. 输入格式:

    • 第一行输入四个整数:n(地块行数)、m(地块列数)、c(正方形边长)、k(目标电量)。
    • 接下来输入 n 行,每行 m 个整数,表示地块中每个位置的电量。
  2. 处理逻辑:

    • 使用二维前缀和(Prefix Sum)快速计算任意正方形区域内的电量总和。
    • 遍历所有可能的边长为 c 的正方形区域,统计满足电量总和大于等于 k 的区域数量。

代码:

javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");// 创建 readline 接口
const rl = readline.createInterface({input: process.stdin, // 输入流output: process.stdout, // 输出流
});const lines = []; // 存储输入行
let n, m, c, k; // 定义变量:地块行数、列数、正方形边长、目标电量// 监听输入事件
rl.on("line", (line) => {lines.push(line); // 将输入行存入数组// 如果输入行数为 1,解析第一行数据if (lines.length === 1) {[n, m, c, k] = lines[0].split(" ").map(Number); // 解析并转换为数字}// 如果输入行数为 n + 1,开始处理数据if (n && lines.length === n + 1) {// 解析地块矩阵const matrix = lines.slice(1).map((line) => line.split(" ").map(Number));// 调用算法函数并输出结果console.log(getResult(matrix, n, m, c, k));// 清空输入行数组lines.length = 0;}
});/*** 计算满足条件的正方形区域数量* @param {*} matrix n*m的地块* @param {*} n 地块行数* @param {*} m 地块列数* @param {*} c 正方形的发电站边长为c* @param {*} k 目标电量k*/
function getResult(matrix, n, m, c, k) {// 初始化二维前缀和数组const preSum = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));// 计算前缀和for (let i = 1; i <= n; i++) {for (let j = 1; j <= m; j++) {preSum[i][j] =preSum[i - 1][j] + // 上方前缀和preSum[i][j - 1] - // 左方前缀和preSum[i - 1][j - 1] + // 左上角重复计算的部分matrix[i - 1][j - 1]; // 当前地块的电量}}let ans = 0; // 统计满足条件的正方形区域数量// 遍历所有可能的正方形区域for (let i = c; i <= n; i++) {for (let j = c; j <= m; j++) {// 计算当前正方形区域内的电量总和const square =preSum[i][j] - // 右下角前缀和(preSum[i - c][j] + preSum[i][j - c]) + // 减去上方和左方的前缀和preSum[i - c][j - c]; // 加上左上角重复减去的部分// 如果电量总和大于等于目标电量,统计if (square >= k) ans++;}}return ans; // 返回结果
}

详细讲解:


1. 输入获取
javascript">const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});
  • readline 模块:
    • 用于从控制台逐行读取输入。
    • rl.on("line", callback) 监听输入事件。

javascript">rl.on("line", (line) => {lines.push(line); // 将输入行存入数组if (lines.length === 1) {[n, m, c, k] = lines[0].split(" ").map(Number); // 解析第一行数据}if (n && lines.length === n + 1) {const matrix = lines.slice(1).map((line) => line.split(" ").map(Number));console.log(getResult(matrix, n, m, c, k)); // 调用算法函数lines.length = 0; // 清空输入行数组}
});
  • 输入处理:
    1. 第一行解析为 n, m, c, k
    2. 接下来的 n 行解析为地块矩阵 matrix
    3. 调用 getResult 函数计算结果并输出。

2. 二维前缀和
javascript">const preSum = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
  • 初始化前缀和数组:
    • preSum 是一个 (n+1) * (m+1) 的二维数组,初始值为 0。
    • 多一行一列是为了方便边界计算。

javascript">for (let i = 1; i <= n; i++) {for (let j = 1; j <= m; j++) {preSum[i][j] =preSum[i - 1][j] + // 上方前缀和preSum[i][j - 1] - // 左方前缀和preSum[i - 1][j - 1] + // 左上角重复计算的部分matrix[i - 1][j - 1]; // 当前地块的电量}
}
  • 计算前缀和:
    • preSum[i][j] 表示从 (0,0)(i,j) 的矩形区域内的电量总和。
    • 公式:
      preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1]
      

3. 计算正方形区域电量
javascript">for (let i = c; i <= n; i++) {for (let j = c; j <= m; j++) {const square =preSum[i][j] - // 右下角前缀和(preSum[i - c][j] + preSum[i][j - c]) + // 减去上方和左方的前缀和preSum[i - c][j - c]; // 加上左上角重复减去的部分if (square >= k) ans++; // 统计满足条件的区域}
}
  • 计算正方形区域电量:
    • 对于每个右下角 (i,j),计算边长为 c 的正方形区域内的电量总和。
    • 公式:
      square = preSum[i][j] - preSum[i-c][j] - preSum[i][j-c] + preSum[i-c][j-c]
      
    • 如果 square >= k,则统计。

代码运行示例

示例 1:

输入:

3 3 2 5
1 2 3
4 5 6
7 8 9

执行过程:

  1. 解析输入:
    • n = 3, m = 3, c = 2, k = 5
    • 地块矩阵:
      [ [1, 2, 3],[4, 5, 6],[7, 8, 9] ]
      
  2. 计算前缀和:
    [ [0, 0, 0, 0],[0, 1, 3, 6],[0, 5, 12, 21],[0, 12, 27, 45] ]
    
  3. 遍历正方形区域:
    • (2,2)12 - 1 - 3 + 0 = 8(满足条件)
    • (2,3)21 - 3 - 6 + 1 = 13(满足条件)
    • (3,2)27 - 5 - 12 + 1 = 11(满足条件)
    • (3,3)45 - 12 - 21 + 5 = 17(满足条件)
  4. 输出结果:
    4
    

示例 2:

输入:

2 2 1 3
1 2
3 4

执行过程:

  1. 解析输入:
    • n = 2, m = 2, c = 1, k = 3
    • 地块矩阵:
      [ [1, 2],[3, 4] ]
      
  2. 计算前缀和:
    [ [0, 0, 0],[0, 1, 3],[0, 4, 10] ]
    
  3. 遍历正方形区域:
    • (1,1)1(不满足条件)
    • (1,2)3(满足条件)
    • (2,1)4(满足条件)
    • (2,2)10 - 1 - 3 + 0 = 6(满足条件)
  4. 输出结果:
    3
    

总结

  1. 功能:

    • 统计满足条件的正方形区域数量。
  2. 优点:

    • 使用二维前缀和优化计算,时间复杂度为 O(n * m)
  3. 适用场景:

    • 适用于需要快速计算矩形区域和的场景。

如果您有其他问题,欢迎随时提问!

三、Java算法源码

以下是 Java 代码的详细中文注释与讲解。此代码的功能是计算一个 n * m 的地块中,所有边长为 c 的正方形区域内的电量总和是否大于等于目标电量 k,并统计满足条件的正方形区域数量。


代码功能

  1. 输入格式:

    • 第一行输入四个整数:n(地块行数)、m(地块列数)、c(正方形边长)、k(目标电量)。
    • 接下来输入 n 行,每行 m 个整数,表示地块中每个位置的电量。
  2. 处理逻辑:

    • 使用二维前缀和(Prefix Sum)快速计算任意正方形区域内的电量总和。
    • 遍历所有可能的边长为 c 的正方形区域,统计满足电量总和大于等于 k 的区域数量。

代码:

java">import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in); // 创建 Scanner 对象,用于读取输入// 读取输入的第一行数据int n = sc.nextInt(); // 地块行数int m = sc.nextInt(); // 地块列数int c = sc.nextInt(); // 正方形边长int k = sc.nextInt(); // 目标电量// 初始化地块矩阵int[][] matrix = new int[n][m];// 读取地块矩阵数据for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {matrix[i][j] = sc.nextInt(); // 读取每个位置的电量}}// 调用算法函数并输出结果System.out.println(getResult(matrix, n, m, c, k));}/*** 计算满足条件的正方形区域数量* @param matrix n*m的地块* @param n 地块行数* @param m 地块列数* @param c 正方形的发电站边长为c* @param k 目标电量k* @return 可以建设几个发电站*/public static int getResult(int[][] matrix, int n, int m, int c, int k) {// 初始化二维前缀和数组int[][] preSum = new int[n + 1][m + 1];// 计算前缀和for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {preSum[i][j] =preSum[i - 1][j] + // 上方前缀和preSum[i][j - 1] - // 左方前缀和preSum[i - 1][j - 1] + // 左上角重复计算的部分matrix[i - 1][j - 1]; // 当前地块的电量}}int ans = 0; // 统计满足条件的正方形区域数量// 遍历所有可能的正方形区域for (int i = c; i <= n; i++) {for (int j = c; j <= m; j++) {// 计算当前正方形区域内的电量总和int square =preSum[i][j] - // 右下角前缀和(preSum[i - c][j] + preSum[i][j - c]) + // 减去上方和左方的前缀和preSum[i - c][j - c]; // 加上左上角重复减去的部分// 如果电量总和大于等于目标电量,统计if (square >= k) ans++;}}return ans; // 返回结果}
}

详细讲解:


1. 输入获取
java">Scanner sc = new Scanner(System.in); // 创建 Scanner 对象,用于读取输入
  • Scanner 类:
    • 用于从控制台读取输入。
    • nextInt() 方法用于读取整数。

java">int n = sc.nextInt(); // 地块行数
int m = sc.nextInt(); // 地块列数
int c = sc.nextInt(); // 正方形边长
int k = sc.nextInt(); // 目标电量
  • 读取第一行数据:
    • 解析并存储 nmck

java">int[][] matrix = new int[n][m]; // 初始化地块矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {matrix[i][j] = sc.nextInt(); // 读取每个位置的电量}
}
  • 读取地块矩阵数据:
    • 使用双重循环读取 n * m 的地块矩阵。

2. 二维前缀和
java">int[][] preSum = new int[n + 1][m + 1]; // 初始化前缀和数组
  • 初始化前缀和数组:
    • preSum 是一个 (n+1) * (m+1) 的二维数组,初始值为 0。
    • 多一行一列是为了方便边界计算。

java">for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {preSum[i][j] =preSum[i - 1][j] + // 上方前缀和preSum[i][j - 1] - // 左方前缀和preSum[i - 1][j - 1] + // 左上角重复计算的部分matrix[i - 1][j - 1]; // 当前地块的电量}
}
  • 计算前缀和:
    • preSum[i][j] 表示从 (0,0)(i,j) 的矩形区域内的电量总和。
    • 公式:
      preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1]
      

3. 计算正方形区域电量
java">int ans = 0; // 统计满足条件的正方形区域数量for (int i = c; i <= n; i++) {for (int j = c; j <= m; j++) {// 计算当前正方形区域内的电量总和int square =preSum[i][j] - // 右下角前缀和(preSum[i - c][j] + preSum[i][j - c]) + // 减去上方和左方的前缀和preSum[i - c][j - c]; // 加上左上角重复减去的部分// 如果电量总和大于等于目标电量,统计if (square >= k) ans++;}
}
  • 计算正方形区域电量:
    • 对于每个右下角 (i,j),计算边长为 c 的正方形区域内的电量总和。
    • 公式:
      square = preSum[i][j] - preSum[i-c][j] - preSum[i][j-c] + preSum[i-c][j-c]
      
    • 如果 square >= k,则统计。

代码运行示例

示例 1:

输入:

3 3 2 5
1 2 3
4 5 6
7 8 9

执行过程:

  1. 解析输入:
    • n = 3, m = 3, c = 2, k = 5
    • 地块矩阵:
      [ [1, 2, 3],[4, 5, 6],[7, 8, 9] ]
      
  2. 计算前缀和:
    [ [0, 0, 0, 0],[0, 1, 3, 6],[0, 5, 12, 21],[0, 12, 27, 45] ]
    
  3. 遍历正方形区域:
    • (2,2)12 - 1 - 3 + 0 = 8(满足条件)
    • (2,3)21 - 3 - 6 + 1 = 13(满足条件)
    • (3,2)27 - 5 - 12 + 1 = 11(满足条件)
    • (3,3)45 - 12 - 21 + 5 = 17(满足条件)
  4. 输出结果:
    4
    

示例 2:

输入:

2 2 1 3
1 2
3 4

执行过程:

  1. 解析输入:
    • n = 2, m = 2, c = 1, k = 3
    • 地块矩阵:
      [ [1, 2],[3, 4] ]
      
  2. 计算前缀和:
    [ [0, 0, 0],[0, 1, 3],[0, 4, 10] ]
    
  3. 遍历正方形区域:
    • (1,1)1(不满足条件)
    • (1,2)3(满足条件)
    • (2,1)4(满足条件)
    • (2,2)10 - 1 - 3 + 0 = 6(满足条件)
  4. 输出结果:
    3
    

总结

  1. 功能:

    • 统计满足条件的正方形区域数量。
  2. 优点:

    • 使用二维前缀和优化计算,时间复杂度为 O(n * m)
  3. 适用场景:

    • 适用于需要快速计算矩形区域和的场景。

如果您有其他问题,欢迎随时提问!

四、Python算法源码

以下是 Python 代码的详细中文注释与讲解。此代码的功能是计算一个 n * m 的地块中,所有边长为 c 的正方形区域内的电量总和是否大于等于目标电量 k,并统计满足条件的正方形区域数量。


代码功能

  1. 输入格式:

    • 第一行输入四个整数:n(地块行数)、m(地块列数)、c(正方形边长)、k(目标电量)。
    • 接下来输入 n 行,每行 m 个整数,表示地块中每个位置的电量。
  2. 处理逻辑:

    • 使用二维前缀和(Prefix Sum)快速计算任意正方形区域内的电量总和。
    • 遍历所有可能的边长为 c 的正方形区域,统计满足电量总和大于等于 k 的区域数量。

代码:

python"># 输入获取
n, m, c, k = map(int, input().split())  # 读取第一行输入:n, m, c, k
matrix = [list(map(int, input().split())) for i in range(n)]  # 读取地块矩阵# 算法入口
def getResult(n, m, c, k, matrix):""":param n: 调研区域的长,行数:param m: 调研区域的宽,列数:param c: 正方形电站的边长:param k: 正方形电站的最低发电量:param matrix: 调研区域每单位面积的发电量矩阵:return: 返回调研区域有几个符合要求正方形电站"""# 初始化二维前缀和数组preSum = [[0 for j in range(m + 1)] for i in range(n + 1)]# 计算前缀和for i in range(1, n + 1):for j in range(1, m + 1):preSum[i][j] = (preSum[i - 1][j]  # 上方前缀和+ preSum[i][j - 1]  # 左方前缀和- preSum[i - 1][j - 1]  # 左上角重复计算的部分+ matrix[i - 1][j - 1]  # 当前地块的电量)ans = 0  # 统计满足条件的正方形区域数量# 遍历所有可能的正方形区域for i in range(c, n + 1):for j in range(c, m + 1):# 计算当前正方形区域内的电量总和square = (preSum[i][j]  # 右下角前缀和- (preSum[i - c][j] + preSum[i][j - c])  # 减去上方和左方的前缀和+ preSum[i - c][j - c]  # 加上左上角重复减去的部分)# 如果电量总和大于等于目标电量,统计if square >= k:ans += 1return ans  # 返回结果# 算法调用
print(getResult(n, m, c, k, matrix))

详细讲解:


1. 输入获取
python">n, m, c, k = map(int, input().split())  # 读取第一行输入:n, m, c, k
matrix = [list(map(int, input().split())) for i in range(n)]  # 读取地块矩阵
  • input().split()
    • 读取一行输入,并按空格分割成字符串列表。
  • map(int, ...)
    • 将字符串列表转换为整数列表。
  • matrix
    • 使用列表推导式读取 n 行输入,每行转换为一个整数列表。

2. 二维前缀和
python">preSum = [[0 for j in range(m + 1)] for i in range(n + 1)]  # 初始化前缀和数组
  • 初始化前缀和数组:
    • preSum 是一个 (n+1) * (m+1) 的二维数组,初始值为 0。
    • 多一行一列是为了方便边界计算。

python">for i in range(1, n + 1):for j in range(1, m + 1):preSum[i][j] = (preSum[i - 1][j]  # 上方前缀和+ preSum[i][j - 1]  # 左方前缀和- preSum[i - 1][j - 1]  # 左上角重复计算的部分+ matrix[i - 1][j - 1]  # 当前地块的电量)
  • 计算前缀和:
    • preSum[i][j] 表示从 (0,0)(i,j) 的矩形区域内的电量总和。
    • 公式:
      preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1]
      

3. 计算正方形区域电量
python">ans = 0  # 统计满足条件的正方形区域数量for i in range(c, n + 1):for j in range(c, m + 1):# 计算当前正方形区域内的电量总和square = (preSum[i][j]  # 右下角前缀和- (preSum[i - c][j] + preSum[i][j - c])  # 减去上方和左方的前缀和+ preSum[i - c][j - c]  # 加上左上角重复减去的部分)# 如果电量总和大于等于目标电量,统计if square >= k:ans += 1
  • 计算正方形区域电量:
    • 对于每个右下角 (i,j),计算边长为 c 的正方形区域内的电量总和。
    • 公式:
      square = preSum[i][j] - preSum[i-c][j] - preSum[i][j-c] + preSum[i-c][j-c]
      
    • 如果 square >= k,则统计。

代码运行示例

示例 1:

输入:

3 3 2 5
1 2 3
4 5 6
7 8 9

执行过程:

  1. 解析输入:
    • n = 3, m = 3, c = 2, k = 5
    • 地块矩阵:
      [ [1, 2, 3],[4, 5, 6],[7, 8, 9] ]
      
  2. 计算前缀和:
    [ [0, 0, 0, 0],[0, 1, 3, 6],[0, 5, 12, 21],[0, 12, 27, 45] ]
    
  3. 遍历正方形区域:
    • (2,2)12 - 1 - 3 + 0 = 8(满足条件)
    • (2,3)21 - 3 - 6 + 1 = 13(满足条件)
    • (3,2)27 - 5 - 12 + 1 = 11(满足条件)
    • (3,3)45 - 12 - 21 + 5 = 17(满足条件)
  4. 输出结果:
    4
    

示例 2:

输入:

2 2 1 3
1 2
3 4

执行过程:

  1. 解析输入:
    • n = 2, m = 2, c = 1, k = 3
    • 地块矩阵:
      [ [1, 2],[3, 4] ]
      
  2. 计算前缀和:
    [ [0, 0, 0],[0, 1, 3],[0, 4, 10] ]
    
  3. 遍历正方形区域:
    • (1,1)1(不满足条件)
    • (1,2)3(满足条件)
    • (2,1)4(满足条件)
    • (2,2)10 - 1 - 3 + 0 = 6(满足条件)
  4. 输出结果:
    3
    

总结

  1. 功能:

    • 统计满足条件的正方形区域数量。
  2. 优点:

    • 使用二维前缀和优化计算,时间复杂度为 O(n * m)
  3. 适用场景:

    • 适用于需要快速计算矩形区域和的场景。

如果您有其他问题,欢迎随时提问!

五、C/C++算法源码:

以下是 C++C 语言 的版本,并附上详细的中文注释和讲解。


C++ 代码

代码:

#include <iostream>
#include <vector>
using namespace std;/*** 计算满足条件的正方形区域数量* @param matrix n*m的地块* @param n 地块行数* @param m 地块列数* @param c 正方形的发电站边长为c* @param k 目标电量k* @return 可以建设几个发电站*/
int getResult(vector<vector<int>>& matrix, int n, int m, int c, int k) {// 初始化二维前缀和数组vector<vector<int>> preSum(n + 1, vector<int>(m + 1, 0));// 计算前缀和for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];}}int ans = 0; // 统计满足条件的正方形区域数量// 遍历所有可能的正方形区域for (int i = c; i <= n; i++) {for (int j = c; j <= m; j++) {// 计算当前正方形区域内的电量总和int square = preSum[i][j] - (preSum[i - c][j] + preSum[i][j - c]) + preSum[i - c][j - c];if (square >= k) ans++; // 如果电量总和大于等于目标电量,统计}}return ans; // 返回结果
}int main() {int n, m, c, k;cin >> n >> m >> c >> k; // 读取输入vector<vector<int>> matrix(n, vector<int>(m)); // 初始化地块矩阵// 读取地块矩阵数据for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> matrix[i][j];}}// 调用算法函数并输出结果cout << getResult(matrix, n, m, c, k) << endl;return 0;
}

C++ 代码讲解:

  1. 输入获取:

    • 使用 cin 读取输入数据。
    • 使用 vector<vector<int>> 存储地块矩阵。
  2. 前缀和计算:

    • 初始化 preSum(n+1) * (m+1) 的二维数组,初始值为 0。
    • 使用双重循环计算前缀和:
      preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
      
  3. 遍历正方形区域:

    • 使用双重循环遍历所有可能的正方形区域。
    • 计算当前正方形区域内的电量总和:
      int square = preSum[i][j] - (preSum[i - c][j] + preSum[i][j - c]) + preSum[i - c][j - c];
      
    • 如果电量总和大于等于 k,则统计。
  4. 输出结果:

    • 使用 cout 输出结果。

C 语言代码

代码:

#include <stdio.h>
#include <stdlib.h>/*** 计算满足条件的正方形区域数量* @param matrix n*m的地块* @param n 地块行数* @param m 地块列数* @param c 正方形的发电站边长为c* @param k 目标电量k* @return 可以建设几个发电站*/
int getResult(int** matrix, int n, int m, int c, int k) {// 初始化二维前缀和数组int** preSum = (int**)malloc((n + 1) * sizeof(int*));for (int i = 0; i <= n; i++) {preSum[i] = (int*)malloc((m + 1) * sizeof(int));for (int j = 0; j <= m; j++) {preSum[i][j] = 0; // 初始化为 0}}// 计算前缀和for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];}}int ans = 0; // 统计满足条件的正方形区域数量// 遍历所有可能的正方形区域for (int i = c; i <= n; i++) {for (int j = c; j <= m; j++) {// 计算当前正方形区域内的电量总和int square = preSum[i][j] - (preSum[i - c][j] + preSum[i][j - c]) + preSum[i - c][j - c];if (square >= k) ans++; // 如果电量总和大于等于目标电量,统计}}// 释放动态分配的内存for (int i = 0; i <= n; i++) {free(preSum[i]);}free(preSum);return ans; // 返回结果
}int main() {int n, m, c, k;scanf("%d %d %d %d", &n, &m, &c, &k); // 读取输入// 动态分配地块矩阵内存int** matrix = (int**)malloc(n * sizeof(int*));for (int i = 0; i < n; i++) {matrix[i] = (int*)malloc(m * sizeof(int));for (int j = 0; j < m; j++) {scanf("%d", &matrix[i][j]); // 读取地块矩阵数据}}// 调用算法函数并输出结果printf("%d\n", getResult(matrix, n, m, c, k));// 释放动态分配的内存for (int i = 0; i < n; i++) {free(matrix[i]);}free(matrix);return 0;
}

C 语言代码讲解:

  1. 输入获取:

    • 使用 scanf 读取输入数据。
    • 使用动态分配的二维数组存储地块矩阵。
  2. 前缀和计算:

    • 使用 malloc 动态分配 preSum 数组。
    • 使用双重循环计算前缀和:
      preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
      
  3. 遍历正方形区域:

    • 使用双重循环遍历所有可能的正方形区域。
    • 计算当前正方形区域内的电量总和:
      int square = preSum[i][j] - (preSum[i - c][j] + preSum[i][j - c]) + preSum[i - c][j - c];
      
    • 如果电量总和大于等于 k,则统计。
  4. 内存管理:

    • 使用 malloc 动态分配内存。
    • 使用 free 释放动态分配的内存,避免内存泄漏。
  5. 输出结果:

    • 使用 printf 输出结果。

总结

  1. 功能:

    • 统计满足条件的正方形区域数量。
  2. 优点:

    • 使用二维前缀和优化计算,时间复杂度为 O(n * m)
  3. 适用场景:

    • 适用于需要快速计算矩形区域和的场景。

如果您有其他问题,欢迎随时提问!

六、尾言

什么是华为OD?

华为OD(Outsourcing Developer,外包开发工程师)是华为针对软件开发工程师岗位的一种招聘形式,主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分,算法题的机试至关重要。

为什么刷题很重要?

  1. 机试是进入技术面的第一关:
    华为OD机试(常被称为机考)主要考察算法和编程能力。只有通过机试,才能进入后续的技术面试环节。

  2. 技术面试需要手撕代码:
    技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

  3. 入职后的可信考试:
    入职华为后,还需要通过“可信考试”。可信考试分为三个等级:

    • 入门级:主要考察基础算法与编程能力。
    • 工作级:更贴近实际业务需求,可能涉及复杂的算法或与工作内容相关的场景题目。
    • 专业级:最高等级,考察深层次的算法以及优化能力,与薪资直接挂钩。

刷题策略与说明:

2024年8月14日之后,华为OD机试的题库转为 E卷,由往年题库(D卷、A卷、B卷、C卷)和全新题目组成。刷题时可以参考以下策略:

  1. 关注历年真题:

    • 题库中的旧题占比较大,建议优先刷历年的A卷、B卷、C卷、D卷题目。
    • 对于每道题目,建议深度理解其解题思路、代码实现,以及相关算法的适用场景。
  2. 适应新题目:

    • E卷中包含全新题目,需要掌握全面的算法知识和一定的灵活应对能力。
    • 建议关注新的刷题平台或交流群,获取最新题目的解析和动态。
  3. 掌握常见算法:
    华为OD考试通常涉及以下算法和数据结构:

    • 排序算法(快速排序、归并排序等)
    • 动态规划(背包问题、最长公共子序列等)
    • 贪心算法
    • 栈、队列、链表的操作
    • 图论(最短路径、最小生成树等)
    • 滑动窗口、双指针算法
  4. 保持编程规范:

    • 注重代码的可读性和注释的清晰度。
    • 熟练使用常见编程语言,如C++、Java、Python等。

如何获取资源?

  1. 官方参考:

    • 华为招聘官网或相关的招聘平台会有一些参考信息。
    • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。
  2. 加入刷题社区:

    • 找到可信的刷题交流群,与其他备考的小伙伴交流经验。
    • 关注知名的刷题网站,如LeetCode、牛客网等,这些平台上有许多华为OD的历年真题和解析。
  3. 寻找系统性的教程:

    • 学习一本经典的算法书籍,例如《算法导论》《剑指Offer》《编程之美》等。
    • 完成系统的学习课程,例如数据结构与算法的在线课程。

积极心态与持续努力:

刷题的过程可能会比较枯燥,但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试,还是为了未来的职业发展,这些积累都会成为重要的财富。

考试注意细节

  1. 本地编写代码

    • 在本地 IDE(如 VS Code、PyCharm 等)上编写、保存和调试代码,确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误,提高代码准确性。
  2. 调整心态,保持冷静

    • 遇到提示不足或实现不确定的问题时,不必慌张,可以采用更简单或更有把握的方法替代,确保思路清晰。
  3. 输入输出完整性

    • 注意训练和考试时都需要编写完整的输入输出代码,尤其是和题目示例保持一致。完成代码后务必及时调试,确保功能符合要求。
  4. 快捷键使用

    • 删除行可用 Ctrl+D,复制、粘贴和撤销分别为 Ctrl+CCtrl+VCtrl+Z,这些可以正常使用。
    • 避免使用 Ctrl+S,以免触发浏览器的保存功能。
  5. 浏览器要求

    • 使用最新版的 Google Chrome 浏览器完成考试,确保摄像头开启并正常工作。考试期间不要切换到其他网站,以免影响考试成绩。
  6. 交卷相关

    • 答题前,务必仔细查看题目示例,避免遗漏要求。
    • 每完成一道题后,点击【保存并调试】按钮,多次保存和调试是允许的,系统会记录得分最高的一次结果。完成所有题目后,点击【提交本题型】按钮。
    • 确保在考试结束前提交试卷,避免因未保存或调试失误而丢分。
  7. 时间和分数安排

    • 总时间:150 分钟;总分:400 分。
    • 试卷结构:2 道一星难度题(每题 100 分),1 道二星难度题(200 分)。及格分为 150 分。合理分配时间,优先完成自己擅长的题目。
  8. 考试环境准备

    • 考试前请备好草稿纸和笔。考试中尽量避免离开座位,确保监控画面正常。
    • 如需上厕所,请提前规划好时间以减少中途离开监控的可能性。
  9. 技术问题处理

    • 如果考试中遇到断电、断网、死机等技术问题,可以关闭浏览器并重新打开试卷链接继续作答。
    • 出现其他问题,请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利,取得理想成绩!


http://www.ppmy.cn/embedded/154211.html

相关文章

模糊查询在sqlserver、dm8、mysql的编写示例

模糊查询要求&#xff1a;字段值以 25D 开头&#xff0c;并以 4 位数字结尾 sqlserver&#xff1a; select * from table_name where column_name like 25D[0-9][0-9][0-9][0-9] 说明&#xff1a; 25D&#xff1a;表示字符串以 25D 开头。 [0-9][0-9][0-9][0-9]&#xf…

7 分布式定时任务调度框架

先简单介绍下分布式定时任务调度框架的使用场景和功能和架构&#xff0c;然后再介绍世面上常见的产品 我们在大型的复杂的系统下&#xff0c;会有大量的跑批&#xff0c;定时任务的功能&#xff0c;如果在独立的子项目中单独去处理这些任务&#xff0c;随着业务的复杂度的提高…

R语言在森林生态研究中的魔法:结构、功能与稳定性分析——发现数据背后的生态故事!

森林生态系统结构、功能与稳定性分析与可视化研究具有多方面的重要意义&#xff0c;具体如下&#xff1a; 一、理论意义 ●深化生态学理论 通过研究森林生态系统的结构、功能与稳定性&#xff0c;可以深化对生态系统基本理论的理解。例如&#xff0c;生物多样性与生态系统稳定性…

接口测试Day09-数据库工具类封装

封装目的 将 常用的数据库操作&#xff0c;封装到 一个方法。 后续再操作数据库时&#xff0c;通过调用该方法来实现。 提高代码的 复用性&#xff01; # 封装数据库工具类class DBUtil(object):classmethoddef __get_conn(cls): # 私有方法passclassmethoddef __close_conn(c…

【MATLAB】subplot如何增加title

在 Matlab 中&#xff0c;使用 subplot 函数将图形窗口划分为多个子图&#xff0c;并使用 title 函数为每个子图添加标题。以下是一个示例&#xff1a; matlab % 生成示例数据 x 0:0.1:10; y1 sin(x); y2 cos(x); % 创建一个 2 行 1 列的子图布局&#xff0c;并选…

把PX4及子仓库添加到自己的gitee

导入主仓库 此处以导入PX4为例 先用gitee导入仓库然后clone gitee仓库先checkout到v1.11&#xff0c;git submodule update --init --recursive&#xff0c;确保可以make之后再新建branchgit checkout -b my1.11.0按照提示连接到origin改代码然后三件套就行了git add ./*git …

Gitlab流水线配置

由于格式和图片解析问题&#xff0c;为了更好阅读体验可前往 阅读原文 流水线的流程是&#xff0c;提交代码后&#xff0c;gitlab会检测项目根目录里的.github-ci.yml文件&#xff0c;根据文件中的流水线自动构建&#xff0c;配置文件格式正确性可以在gitlab进行文件校验&#…

排序算法的实现(插入,希尔,选择,冒泡,堆排,快排)

目录 1.选择排序 2.冒泡排序 3.堆排序 4.插入排序 5.希尔排序 6.快排 6.1快排的优化 6.2快排&#xff08;双指针法&#xff09; 6.3快排&#xff08;非递归&#xff09; 7.归并排序 7.1归并非递归 8.计数排序 1.选择排序 对n个元素进行选择排序&#xff0c;我们可以…