【秋招笔试】24-07-31-影石insta-秋招笔试题

大家好这里是清隆学长 ，一枚热爱算法的程序员

ACM金牌团队️ | 多次AK大厂笔试 ｜ 编程一对一辅导

✨ 本系列打算持续跟新 秋招笔试题

感谢大家的订阅➕ 和 喜欢 和 手里的小花花

✨ 笔试合集传送们 -> 春秋招笔试合集

第一题

题目描述

给定一个字符串矩阵，例如：

##......
..##....
....##..
......##
....##..
..##....
##......

实现函数 solution(矩阵)，将矩阵顺时针旋转90°后返回。例如，上述矩阵旋转后的结果为：

#.....#
#.....#
.#...#.
..#.#..
..#.#..
.#...#.
#.....#

题解

要将矩阵顺时针旋转90度，可以按照以下步骤进行：将矩阵的每一列变成新的行，从最后一列开始，依次将每一列变成新的行。

参考代码

• Python

def solution(matrix):
    n = len(matrix)
    m = len(matrix[0])
    rotated_matrix = ['' for _ in range(m)]
    
    # 遍历每一列
    for i in range(m):
        # 遍历每一行
        for j in range(n):
            # 将当前列的元素添加到新行中
            rotated_matrix[i] += matrix[n - 1 - j][i]
    
    return rotated_matrix

• Java

import java.util.*;

public class Main {
    public static List<String> solution(List<String> matrix) {
        int n = matrix.size();
        int m = matrix.get(0).length();
        List<String> rotatedMatrix = new ArrayList<>();
        
        // 遍历每一列
        for (int i = 0; i < m; i++) {
            StringBuilder newRow = new StringBuilder();
            // 遍历每一行
            for (int j = n - 1; j >= 0; j--) {
                // 将当前列的元素添加到新行中
                newRow.append(matrix.get(j).charAt(i));
            }
            rotatedMatrix.add(newRow.toString());
        }
        
        return rotatedMatrix;
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> solution(const vector<string>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    vector<string> rotatedMatrix(m, string(n, ' '));
    
    // 遍历每一列
    for (int i = 0; i < m; ++i) {
        // 遍历每一行
        for (int j = 0; j < n; ++j) {
            // 将当前列的元素添加到新行中
            rotatedMatrix[i][j] = matrix[n - 1 - j][i];
        }
    }
    
    return rotatedMatrix;
}

第二题

题目描述

给定一个由随机数组成的正方形二维数组，例如：

var square = [
    [1, 2, 3],
    [4, 8, 2],
    [1, 5, 3]
];

请计算从左上角移动到给定坐标所需的最小成本路径，只能向右或向下移动。

在上面的例子中，移动到 (2, 2) 的最小总成本为 11，包括起始和结束位置。

注意：坐标在水平方向记为 x，在垂直方向记为 y。

实现代码

• Python

def solution(square, a, b):
    n = len(square)
    dp = [[0] * n for _ in range(n)]
    
    dp[0][0] = square[0][0]
    
    # 初始化第一行
    for i in range(1, n):
        dp[0][i] = dp[0][i - 1] + square[0][i]
    
    # 初始化第一列
    for i in range(1, n):
        dp[i][0] = dp[i - 1][0] + square[i][0]
    
    # 填充动态规划表
    for i in range(1, n):
        for j in range(1, n):
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + square[i][j]
    
    return dp[a][b]

• Java

public class Main {
    public static int solution(int[][] square, int a, int b) {
        int n = square.length;
        int[][] dp = new int[n][n];
        
        dp[0][0] = square[0][0];
        
        // 初始化第一行
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + square[0][i];
        }
        
        // 初始化第一列
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + square[i][0];
        }
        
        // 填充动态规划表
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + square[i][j];
            }
        }
        
        return dp[a][b];
    }
}

• Cpp

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

using namespace std;

int solution(const vector<vector<int>>& square, int a, int b) {
    int n = square.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    dp[0][0] = square[0][0];
    
    // 初始化第一行
    for (int i = 1; i < n; ++i) {
        dp[0][i] = dp[0][i - 1] + square[0][i];
    }
    
    // 初始化第一列
    for (int i = 1; i < n; ++i) {
        dp[i][0] = dp[i - 1][0] + square[i][0];
    }
    
    // 填充动态规划表
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + square[i][j];
        }
    }
    
    return dp[a][b];
}