面试题生成

问题描述

给定一个二维网格 grid，其中每个单元格包含一个整数，表示可以获得的金币数量。你可以从网格中的任意一个单元格出发，按照以下规则收集金币：

1. 移动规则: 你可以从当前位置移动到其上下左右相邻的单元格，但不能移出网格边界，也不能移动到已经访问过的单元格。
2. 停止条件: 你需要从某个开始单元格开始，在路径上收集金币，直到无法继续收集金币后停止。
3. 目标: 找到一条路径，使得收集到的金币总数最大。

注意：你可以从任意一个网格中的单元格开始，但在每次路径的采集过程中，不能重复访问同一个单元格。

输入的 grid 是一个大小为 m x n 的二维数组，其中：

• grid[i][j] 是一个非负整数，表示该位置的金币数。
• 0 表示该位置无法进入（即不可用，障碍物）。

返回一个整数，表示能够收集到的最大金币数量。

输入示例及输出

示例 1：

输入：

grid = 
[
  [0, 6, 0],
  [5, 8, 7],
  [0, 9, 0]
]

输出：

24

解释： 最优路径为从 (1,1) → (1,2) → (2,1) 收集的金币，路径总金币数为 8 + 7 + 9 = 24。

示例 2：

输入：

grid =
[
  [1, 0, 7],
  [2, 0, 6],
  [3, 4, 5],
  [0, 3, 0]
]

输出：

28

解释： 最优路径为从 (2,2) → (2,1) → (1,0) → (0,0) 收集的金币，路径金币总数为 5 + 4 + 2 + 1 = 28。

解法

使用“Java”编写的代码

public class MaxGoldCollector {
    public int getMaximumGold(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int maxGold = 0;

        // Iterate over all cells as potential starting points
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // Start DFS only if the cell contains gold
                if (grid[i][j] > 0) {
                    maxGold = Math.max(maxGold, dfs(grid, i, j));
                }
            }
        }

        return maxGold;
    }

    private int dfs(int[][] grid, int x, int y) {
        // Boundary check and obstacle check
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0) {
            return 0;
        }

        // Capture the current cell's gold value and mark it as visited
        int currentGold = grid[x][y];
        grid[x][y] = 0; // Temporarily mark as visited

        // Explore all 4 possible directions (up, down, left, right)
        int up = dfs(grid, x - 1, y);
        int down = dfs(grid, x + 1, y);
        int left = dfs(grid, x, y - 1);
        int right = dfs(grid, x, y + 1);

        // Restore the current cell's gold (backtracking)
        grid[x][y] = currentGold;

        // Return the maximum gold collectable from this cell
        return currentGold + Math.max(Math.max(up, down), Math.max(left, right));
    }

    public static void main(String[] args) {
        MaxGoldCollector solver = new MaxGoldCollector();

        int[][] grid1 = {
            {0, 6, 0},
            {5, 8, 7},
            {0, 9, 0}
        };
        System.out.println(solver.getMaximumGold(grid1)); // Output: 24

        int[][] grid2 = {
            {1, 0, 7},
            {2, 0, 6},
            {3, 4, 5},
            {0, 3, 0}
        };
        System.out.println(solver.getMaximumGold(grid2)); // Output: 28
    }
}

解题逻辑的逐步讲解

1. 从每个单元格作为起点进行搜索：对于网格中的每个单元格，如果其金币数大于零，假设它是起点，并计算从该位置可以获得的最大金币数。
2. 深度优先搜索 (DFS) 实现路径查找：在 DFS 中，从当前单元格向其上下左右四个方向进行递归查找，直到无法继续前进为止（超出边界或碰到空单元格）。
3. 回溯处理：为了确保路径中的单元格不会被重复访问，在访问单元格时，将其金币数标记为零（暂时清空）。递归结束后，恢复其金币数。
4. 累计最大值：通过从所有可能的起点调用 DFS，找到最大的金币数并返回。

时间复杂度与空间复杂度

时间复杂度

设网格的尺寸为 m x n，同时假设平均每个单元格的 DFS 最大深度为 d：

• 最坏情况下，每个单元格都可能作为起点，因此需要调用一次 DFS。每次 DFS 最多访问 m * n 个单元格。
• 因此时间复杂度为 O(m * n * d)。但在实际问题中，d 通常不会太大。

空间复杂度

• 递归调用时的栈空间：递归深度与网格的大小相关，最坏情况下需要 O(m * n) 的额外栈空间。
• 除此之外，算法本身未使用任何额外的数据结构。

因此，空间复杂度为 O(m * n)。

总结

通过这道动态规划与回溯结合的题目，可以有效地考察 Java 开发者在编写递归、处理特殊边界情况以及实现问题优化时的能力。此实现既遵循了清晰的逻辑，又是性能合理的解法。

编程面试题：使用递归计算数组元素之和

1. 问题描述

编写一个递归函数，用于计算一个整数数组中所有元素的和。

要求如下：

• 函数接收两个参数：一个整数数组 arr，以及数组的长度 n。
• 函数需使用递归来解决问题，不能使用任何循环语句（如 for 或 while）。
• 如果数组为空（即 n == 0），函数应返回 0。

2. 输入示例及预期输出

输入 1：

arr = [1, 2, 3, 4, 5]
n = 5

输出 1：

15

输入 2：

arr = [10, -2, 3]
n = 3

输出 2：

11

输入 3：

arr = []
n = 0

输出 3：

0

3. 使用 C++ 编写的解法

#include <iostream>
#include <vector>
using namespace std;

// 递归函数定义
int recursiveSum(const int arr[], int n) {
    // 基本情况：如果数组为空
    if (n == 0) {
        return 0;
    }
    // 递归关系：当前元素 + 剩余部分的和
    return arr[n - 1] + recursiveSum(arr, n - 1);
}

// 主函数用于测试
int main() {
    // 示例输入 1
    int arr1[] = {1, 2, 3, 4, 5};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    cout << "Sum of arr1: " << recursiveSum(arr1, n1) << endl;
    
    // 示例输入 2
    int arr2[] = {10, -2, 3};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    cout << "Sum of arr2: " << recursiveSum(arr2, n2) << endl;

    // 示例输入 3
    int arr3[] = {};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    cout << "Sum of arr3: " << recursiveSum(arr3, n3) << endl;

    return 0;
}

4. 解题逻辑逐步讲解

1. 递归基础：
   递归的本质是将一个问题分解为规模更小的子问题，并通过函数的自身调用来解决子问题，逐步返回结果。对于求数组的和问题，可以将数组划分为两部分：最后一个元素和其余数组，问题规模随着数组长度逐步减少，最终变为一个基本情况。

2. 基本情况：
   如果数组的长度 n == 0，说明已经没有任何元素，直接返回 0，这是递归的终止条件。

3. 递归关系：
   对于任意非空数组，可以将其表示为前 n-1 个元素以及最后一个元素的组合。因此，数组的和为：

   recursiveSum(arr, n) = arr[n-1] + recursiveSum(arr, n-1)
   

4. 递归调用：
   每次函数调用会将当前数组的元素 arr[n-1] 加到递归处理结果中。再次调用函数会进一步减少数组的规模，直到触发基本情况，递归返回开始。

5. 举例分析：
   对数组 [1, 2, 3, 4, 5]，递归调用的过程如下：

   recursiveSum(arr, 5)
   => arr[4] + recursiveSum(arr, 4) // 5 + (递归)
   => arr[4] + (arr[3] + recursiveSum(arr, 3)) // 5 + 4 + (递归)
   => arr[4] + (arr[3] + (arr[2] + recursiveSum(arr, 2))) // 5 + 4 + 3 + (递归)
   => arr[4] + (arr[3] + (arr[2] + (arr[1] + recursiveSum(arr, 1)))) // 5 + 4 + 3 + 2 + (递归)
   => arr[4] + (arr[3] + (arr[2] + (arr[1] + (arr[0] + recursiveSum(arr, 0))))) // 5 + 4 + 3 + 2 + 1 + 0
   => 15
   

5. 时间复杂度与空间复杂度分析

1. 时间复杂度：
   假设数组的大小为 n，每次递归调用都会减少数组的规模 1，因此递归的深度为 n。每次递归进行一个简单的加法操作，耗时为 O(1)。因此，总时间复杂度为：

   O(n)
   

2. 空间复杂度：
   每次递归调用都会在调用栈中创建一个栈帧以存储函数参数和局部变量，因此递归的空间复杂度等同于递归深度。在最坏情况下（数组大小为 n），递归深度为 n。因此，空间复杂度为：

   O(n)
   

3 tighten