💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

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

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🍥 目前来看，有很多套卷，根据网友的投稿以及反馈，保底至少有3套

1️⃣ 非常简单的数学题，可以直接模拟做，也可以根据公式直接计算

2️⃣ 经典BFS走迷宫的改编题，难度不大。

01.硬币阶梯

问题描述

K 小姐最近对硬币收集产生了浓厚的兴趣。她喜欢将硬币摆成一个个整齐的阶梯形状。对于一个阶梯形状，第 行必须正好有 枚硬币。K 小姐想知道，如果她有 枚硬币，最多可以摆成多少完整的阶梯行。

输入格式

输入包含一个整数 ，表示硬币的总数。

输出格式

输出一个整数，表示可以形成的完整阶梯行数。

样例输入

5

样例输出

2

数据范围

题解

贪心

从第一行开始，一行一行地放置硬币，直到不能再完整地放置下一行为止。每次放置时，检查剩余的硬币是否足够放置当前行所需的硬币数量。

参考代码

• Python

def arrange_coins(total_coins):
    # 初始化行数和当前行需要的硬币数量
    current_row = 1
    complete_rows = 0
    # 当硬币足够放置当前行时，继续放置
    while current_row <= total_coins:
        complete_rows += 1  # 增加完整行数
        total_coins -= current_row  # 减去当前行所需的硬币
        current_row += 1  # 进入下一行
    return complete_rows

# 读取输入的硬币总数
n = int(input())
# 计算并输出完整的阶梯行数
print(arrange_coins(n))

• Java

import java.util.Scanner;

public class CoinStaircase {
    public static int arrangeCoins(int totalCoins) {
        int currentRow = 1;
        int completeRows = 0;
        // 当硬币足够放置当前行时，继续放置
        while (currentRow <= totalCoins) {
            completeRows++;  // 增加完整行数
            totalCoins -= currentRow;  // 减去当前行所需的硬币
            currentRow++;  // 进入下一行
        }
        return completeRows;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        // 计算并输出完整的阶梯行数
        System.out.println(arrangeCoins(n));
        scanner.close();
    }
}

• Cpp

#include <iostream>
using namespace std;

int arrangeCoins(int totalCoins) {
    int currentRow = 1;
    int completeRows = 0;
    // 当硬币足够放置当前行时，继续放置
    while (currentRow <= totalCoins) {
        completeRows++;  // 增加完整行数
        totalCoins -= currentRow;  // 减去当前行所需的硬币
        currentRow++;  // 进入下一行
    }
    return completeRows;
}

int main() {
    int n;
    cin >> n;
    // 计算并输出完整的阶梯行数
    cout << arrangeCoins(n) << endl;
    return 0;
}

02.K小姐的逃脱

题目描述

在一个神秘的古老城市中，K小姐被困在一个错综复杂的迷宫中。为了逃脱，她必须找到通往出口的最短路径。迷宫由一个二维网格表示，其中：

1. 每个单元格可能是空地（用 '0' 表示）、墙壁（用 '1' 表示）、起点（用 'S' 表示，且只有一个）、终点（用 'E' 表示，且只有一个）。
2. K小姐可以在空地上移动，并且只能向相邻的四个方向（上、下、左、右）移动，不能穿过墙壁。
3. 迷宫中可能有单向门，用特殊字符（'90'、'U'、'L'、'R'）标记在空地上。这些门只允许按照指示方向移动，反方向视为墙壁。

请设计一个算法，帮助 K小姐找到从起点到终点的最短路径，并返回路径的长度（以步数计）。如果路径不存在，则返回 -1。

输入格式

输入为一个二维字符数组 maze，表示迷宫的布局。

输出格式

输出一个整数，表示从起点到终点的最短路径长度（包括起点），如果不存在路径，则输出 -1。

样例输入

[
    ['S', '0', '0', '0'],
    ['0', '1', '0', '0'],
    ['0', '0', '0', 'E'],
    ['0', 'U', '0', '0']
]

样例输出

7

数据范围

1. 迷宫的大小不会超过 。
2. 迷宫中只包含一个起点和一个终点。

题解

走迷宫的拓展版本，本质还是BFS。

从起点开始跑一遍 BFS 即可。

参考代码

• Python

from collections import deque

def shortest_path(maze):
    rows, cols = len(maze), len(maze[0])
    start = None
    end = None

    # 找到起点和终点的位置
    for i in range(rows):
        for j in range(cols):
            if maze[i][j] == 'S':
                start = (i, j)
            elif maze[i][j] == 'E':
                end = (i, j)
    
    if not start or not end:
        return -1
    
    # 初始化队列和已访问集合
    queue = deque([(start[0], start[1], 1)]) 
    visited = set([start])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右
    
    while queue:
        row, col, dist = queue.popleft()
        
        # 如果到达终点，返回距离
        if (row, col) == end:
            return dist
        
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            if 0 <= new_row < rows and 0 <= new_c