科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇技术指南以算法竞赛模板库 codeforces-go 中收录的题解 leetcode/biweekly/52/c/1861.md 为核心完整拆解 LeetCode 第 1861 题「旋转盒子Rotating the Box」的两种经典解法正序遍历统计计数法与倒序遍历双指针法并结合仓库内 c.go 的 Go 实现与 c_test.go 的测试用例从坐标变换推导、分语言实现到复杂度分析逐层讲透读完即可独立写出该题任意语言的 AC 代码。一、题目本质与核心思路给定一个 $m \times n$ 的字符矩阵boxGrid其中包含三种格子#石头stone*障碍物obstacle.空格子将整个盒子顺时针旋转 90° 后石头会在重力作用下垂直下落直到落到盒子底部、障碍物或另一块石头上障碍物和空位不受重力影响。要求返回旋转且石头掉落后的最终矩阵。题解给出的关键洞察是$\textit{boxGrid}$ 的每一行互相独立可以分别计算。旋转前同一行里的石头在旋转后落在同一列中按列排列因此逐行处理即可无需全局模拟。二、坐标变换旋转后 $(i,j)$ 位于 $(j,m-1-i)$题解文档特别强调了一个坐标细节第 $i$ 行的格子旋转后在倒数第 $i$ 列第 $j$ 列的格子旋转后在第 $j$ 行。因此$$(i,\ j) \xrightarrow{\text{顺时针旋转 }90^\circ} (j,\ m-1-i)$$这一变换贯穿两种解法原矩阵第 $i$ 行第 $j$ 列的字符写入结果矩阵的ans[j][m-1-i]。理解这一点后所有代码里的下标互换就不再是魔法数字而是一次确定的映射。三、方法一正序遍历 区间填充算法思想单独看每一行我们需要知道每个障碍物*的左边有多少个石头#。具体地设当前障碍物到上一个障碍物之间有 $\textit{cnt}$ 个石头。那么旋转后当前障碍物的左边有连续 $\textit{cnt}$ 个石头这些石头会堆叠在该障碍物的左侧据此遍历过程中统计石头的个数 $\textit{cnt}$如果下一个格子是障碍物或者当前格子是这一行的最后一个格子那么从当前格子往前填入连续 $\textit{cnt}$ 个石头并重置计数器 $\textit{cnt}0$。一个精妙的小技巧是遇到石头时先cnt同时把当前格子视为空格.写入结果等碰到障碍物或行尾时再统一用#回填。这样既完成了计数又天然实现了石头从障碍物处向左堆叠的效果。分语言实现class Solution: def rotateTheBox(self, boxGrid: list[list[str]]) - list[list[str]]: m, n len(boxGrid), len(boxGrid[0]) ans [[] * m for _ in range(n)] for i, row in enumerate(boxGrid): cnt 0 for j, ch in enumerate(row): if ch #: # 石头 cnt 1 ch . # 先把石头清空 ans[j][-1 - i] ch if j n - 1 or row[j 1] *: # 下一个格子是障碍物 # 石头垂直掉落后从 j 往前 cnt 个格子都是石头 for k in range(j, j - cnt, -1): ans[k][-1 - i] # cnt 0 # 重置计数器 return ansclass Solution { public char[][] rotateTheBox(char[][] boxGrid) { int m boxGrid.length; int n boxGrid[0].length; char[][] ans new char[n][m]; for (int i 0; i m; i) { char[] row boxGrid[i]; int cnt 0; for (int j 0; j n; j) { char ch row[j]; if (ch #) { // 石头 cnt; ch .; // 先把石头清空 } ans[j][m - 1 - i] ch; if (j n - 1 || row[j 1] *) { // 下一个格子是障碍物 // 石头垂直掉落后从 j 往前 cnt 个格子都是石头 for (int k j; k j - cnt; k--) { ans[k][m - 1 - i] #; } cnt 0; // 重置计数器 } } } return ans; } }class Solution { public: vectorvectorchar rotateTheBox(vectorvectorchar boxGrid) { int m boxGrid.size(), n boxGrid[0].size(); vector ans(n, vectorchar(m)); for (int i 0; i m; i) { auto row boxGrid[i]; int cnt 0; for (int j 0; j n; j) { char ch row[j]; if (ch #) { // 石头 cnt; ch .; // 先把石头清空 } ans[j][m - 1 - i] ch; if (j n - 1 || row[j 1] *) { // 下一个格子是障碍物 // 石头垂直掉落后从 j 往前 cnt 个格子都是石头 for (int k j; k j - cnt; k--) { ans[k][m - 1 - i] #; } cnt 0; // 重置计数器 } } } return ans; } };char** rotateTheBox(char** boxGrid, int boxGridSize, int* boxGridColSize, int* returnSize, int** returnColumnSizes) { int m boxGridSize, n boxGridColSize[0]; char** ans malloc(n * sizeof(char*)); *returnColumnSizes malloc(n * sizeof(int)); *returnSize n; for (int i 0; i n; i) { ans[i] malloc(m * sizeof(char)); (*returnColumnSizes)[i] m; } for (int i 0; i m; i) { char* row boxGrid[i]; int cnt 0; for (int j 0; j n; j) { char ch row[j]; if (ch #) { // 石头 cnt; ch .; // 先把石头清空 } ans[j][m - 1 - i] ch; if (j n - 1 || row[j 1] *) { // 下一个格子是障碍物 // 石头垂直掉落后从 j 往前 cnt 个格子都是石头 for (int k j; k j - cnt; k--) { ans[k][m - 1 - i] #; } cnt 0; // 重置计数器 } } } return ans; }func rotateTheBox(boxGrid [][]byte) [][]byte { m, n : len(boxGrid), len(boxGrid[0]) ans : make([][]byte, n) for i : range ans { ans[i] make([]byte, m) } for i, row : range boxGrid { cnt : 0 for j, ch : range row { if ch # { // 石头 cnt ch . // 先把石头清空 } ans[j][m-1-i] ch if j n-1 || row[j1] * { // 下一个格子是障碍物 // 石头垂直掉落后从 j 往前 cnt 个格子都是石头 for k : j; k j-cnt; k-- { ans[k][m-1-i] # } cnt 0 // 重置计数器 } } } return ans }var rotateTheBox function(boxGrid) { const m boxGrid.length, n boxGrid[0].length; const ans Array.from({ length: n }, () Array(m)); for (let i 0; i m; i) { const row boxGrid[i]; let cnt 0; for (let j 0; j n; j) { let ch row[j]; if (ch #) { // 石头 cnt; ch .; // 先把石头清空 } ans[j][m - 1 - i] ch; if (j n - 1 || row[j 1] *) { // 下一个格子是障碍物 // 石头垂直掉落后从 j 往前 cnt 个格子都是石头 for (let k j; k j - cnt; k--) { ans[k][m - 1 - i] #; } cnt 0; // 重置计数器 } } } return ans; };impl Solution { pub fn rotate_the_box(box_grid: VecVecchar) - VecVecchar { let m box_grid.len(); let n box_grid[0].len(); let mut ans vec![vec![\0; m]; n]; for (i, row) in box_grid.iter().enumerate() { let mut cnt 0; for (j, ch) in row.into_iter().enumerate() { let mut ch ch; if ch # { // 石头 cnt 1; ch .; // 先把石头清空 } ans[j][m - 1 - i] ch; if j n - 1 || row[j 1] * { // 下一个格子是障碍物 // 石头垂直掉落后从 j 往前 cnt 个格子都是石头 for k in j - cnt 1..j { ans[k][m - 1 - i] #; } cnt 0; // 重置计数器 } } } ans } }语言实现细节Rust 中row[j 1] *的写法要求row是可索引的切片因而先iter()再在循环体内取下标C 语言需要手动管理二维数组的malloc与returnColumnSizes其余语言的逻辑骨架完全一致。复杂度分析时间复杂度$\mathcal{O}(mn)$其中 $m$ 和 $n$ 分别是boxGrid的行数和列数。每行只做一次正序遍历障碍物之间的回填总量不超过该行石头的总数整体仍为线性。空间复杂度$\mathcal{O}(1)$。只使用常数个计数器返回值不计入空间开销。四、方法二倒序遍历 双指针算法思想对于每一行row倒着遍历可以直接确定每个石头落入的位置省去了方法一中统计 回填的二次循环如果row[j]是障碍物那么它左边最近的石头在旋转后掉落到row[j-1]。用一个变量 $k$ 维护石头掉落后的位置遇到障碍物时更新 $\textit{k} j-1$。注如果row[j]左边最近的不是石头而是另一个障碍物那么 $k$ 会继续被更新无需担心石头落到错误的位置。如果row[j]是石头那么它掉落到row[k]然后把 $k$ 减一表示左边下一块石头掉落后的位置。从最右侧开始维护下一个石头可落脚的位置 $k$本质上就是经典的双指针写法一个指针 $j$ 负责扫描原行一个指针 $k$ 负责指定石头最终下落位置。由于石头在重力作用下总是落在当前可达的最右端即 $k$无需模拟逐格下落。分语言实现class Solution: def rotateTheBox(self, boxGrid: list[list[str]]) - list[list[str]]: m, n len(boxGrid), len(boxGrid[0]) ans [[.] * m for _ in range(n)] for i, row in enumerate(boxGrid): k n - 1 for j in range(n - 1, -1, -1): if row[j] *: # 障碍物 ans[j][-1 - i] * k j - 1 # 障碍物左边最近的石头在旋转后掉落到 j-1 elif row[j] #: # 石头 ans[k][-1 - i] # # 旋转后石头掉落到 k k - 1 return ansclass Solution { public char[][] rotateTheBox(char[][] boxGrid) { int m boxGrid.length; int n boxGrid[0].length; char[][] ans new char[n][m]; for (char[] row : ans) { Arrays.fill(row, .); } for (int i 0; i m; i) { char[] row boxGrid[i]; int k n - 1; for (int j n - 1; j 0; j--) { if (row[j] *) { // 障碍物 ans[j][m - 1 - i] *; k j - 1; // 障碍物左边最近的石头在旋转后掉落到 j-1 } else if (row[j] #) { // 石头 ans[k][m - 1 - i] #; // 旋转后石头掉落到 k k--; } } } return ans; } }class Solution { public: vectorvectorchar rotateTheBox(vectorvectorchar boxGrid) { int m boxGrid.size(), n boxGrid[0].size(); vector ans(n, vectorchar(m, .)); for (int i 0; i m; i) { auto row boxGrid[i]; int k n - 1; for (int j n - 1; j 0; j--) { if (row[j] *) { // 障碍物 ans[j][m - 1 - i] *; k j - 1; // 障碍物左边最近的石头在旋转后掉落到 j-1 } else if (row[j] #) { // 石头 ans[k][m - 1 - i] #; // 旋转后石头掉落到 k k--; } } } return ans; } };char** rotateTheBox(char** boxGrid, int boxGridSize, int* boxGridColSize, int* returnSize, int** returnColumnSizes) { int m boxGridSize, n boxGridColSize[0]; char** ans malloc(n * sizeof(char*)); *returnColumnSizes malloc(n * sizeof(int)); *returnSize n; for (int i 0; i n; i) { ans[i] malloc(m * sizeof(char)); memset(ans[i], ., m * sizeof(char)); (*returnColumnSizes)[i] m; } for (int i 0; i m; i) { char* row boxGrid[i]; int k n - 1; for (int j n - 1; j 0; j--) { if (row[j] *) { // 障碍物 ans[j][m - 1 - i] *; k j - 1; // 障碍物左边最近的石头在旋转后掉落到 j-1 } else if (row[j] #) { // 石头 ans[k][m - 1 - i] #; // 旋转后石头掉落到 k k--; } } } return ans; }func rotateTheBox(boxGrid [][]byte) [][]byte { m, n : len(boxGrid), len(boxGrid[0]) ans : make([][]byte, n) for i : range ans { ans[i] bytes.Repeat([]byte{.}, m) } for i, row : range boxGrid { k : n - 1 for j : n - 1; j 0; j-- { if row[j] * { // 障碍物 ans[j][m-1-i] * k j - 1 // 障碍物左边最近的石头在旋转后掉落到 j-1 } else if row[j] # { // 石头 ans[k][m-1-i] # // 旋转后石头掉落到 k k-- } } } return ans }var rotateTheBox function(boxGrid) { const m boxGrid.length, n boxGrid[0].length; const ans Array.from({ length: n }, () Array(m).fill(.)); for (let i 0; i m; i) { const row boxGrid[i]; let k n - 1; for (let j n - 1; j 0; j--) { if (row[j] *) { // 障碍物 ans[j][m - 1 - i] *; k j - 1; // 障碍物左边最近的石头在旋转后掉落到 j-1 } else if (row[j] #) { // 石头 ans[k][m - 1 - i] #; // 旋转后石头掉落到 k k--; } } } return ans; };impl Solution { pub fn rotate_the_box(box_grid: VecVecchar) - VecVecchar { let m box_grid.len(); let n box_grid[0].len(); let mut ans vec![vec![.; m]; n]; for (i, row) in box_grid.into_iter().enumerate() { let mut k n - 1; for (j, ch) in row.into_iter().enumerate().rev() { if ch * { // 障碍物 ans[j][m - 1 - i] *; k j - 1; // 障碍物左边最近的石头在旋转后掉落到 j-1 } else if ch # { // 石头 ans[k][m - 1 - i] #; // 旋转后石头掉落到 k k - 1; } } } ans } }与方法一不同的是方法二的ans在初始化时就全部填入.如 Go 中用bytes.Repeat([]byte{.}, m)Rust 中用vec![.; m]因为倒序扫描只处理石头与障碍物空格天然保持为空位无需显式写入。复杂度分析时间复杂度$\mathcal{O}(mn)$。每行仅一次倒序遍历没有额外的回填循环。空间复杂度$\mathcal{O}(1)$返回值不计入。五、两种方法对比与选型建议维度方法一正序遍历方法二倒序遍历 双指针遍历方向每行从左到右每行从右到左核心变量石头计数 $\textit{cnt}$遇障碍物/行尾回填落点指针 $k$遇障碍物重置、遇石头递减结果数组初始化无需预填充回填覆盖需预填充.额外循环障碍物区间内有回填小循环无时间复杂度$\mathcal{O}(mn)$$\mathcal{O}(mn)$空间复杂度$\mathcal{O}(1)$$\mathcal{O}(1)$直观程度更贴近数石头再堆叠的物理直觉更简洁、编码量少一次扫描完成两种方法复杂度相同。方法一的正序思维适合初次理解题目石头向左堆叠的物理过程方法二的倒序双指针则是双指针分组循环类题目的典型范式代码更短、常数更小推荐在竞赛中优先采用。六、仓库源码实现与测试验证该题已被完整收录进 codeforces-go 仓库对应目录为 leetcode/biweekly/52/c与题解文档放在同一目录下方便对照阅读。核心实现Go仓库的 c.go 同时保留了两种解法的实现rotateTheBox1方法一正序遍历版本对应题解中的方法一rotateTheBox方法二倒序双指针版本对应题解中的方法二也是最终评测使用的版本。可以看到仓库代码与题解文档完全同源方法一的计数变量命名为stone文档中为cnt方法二用stone表示落点指针文档中为 $k$逻辑一一对应。这也印证了文档是仓库实现的设计说明书仓库实现是文档的可运行版本。测试用例c_test.goc_test.go 由仓库的模板生成器自动生成文件头标注Code generated by copypasta/template/leetcode/generator_test.go内置了三组官方示例输入输出覆盖要点[[#,.,#]][[.,],[#],[#]]单行盒子石头全部掉到旋转后的底部[[#,.,*,.],[#,#,*,.]][[#,.],[#,#],[*,*],[.,.]]障碍物参与堆叠两行独立处理[[#,#,*,.,*,.],[#,#,#,*,.,.],[#,#,#,.,#,.]][[.,#,#],[.,#,#],[#,#,*],[#,*,.],[#,.,*],[#,.,.]]多行多障碍物验证石头不会穿过障碍物测试通过 testutil.RunLeetCodeFuncWithExamples 运行该函数利用反射检查传入函数签名与示例数据是否匹配逐条将字符串输入解析为函数参数、对比输出支持targetCaseNum指定运行单个用例-1 表示最后一个与标准的go test流程无缝集成。七、如何用仓库模板复现并本地验证由于仓库以main包组织每个题目目录自带main包与测试文件可直接本地跑通进入题目目录当前工作目录为leetcode/biweekly/52/ccd leetcode/biweekly/52/c go test -v测试输出会依次显示三组用例的通过情况t.Log(Current test is [c])标明当前评测的是 biweekly 52 的 C 题。若想只跑第 2 个用例可修改 c_test.go 中的targetCaseNum为2再执行go test -run Test。注意仓库为只读参考用途本地运行时不要修改仓库内文件可复制题目文件到自己的工程中实验。八、专题归类与后续训练方向题解文档在专题训练一节指出本题属于**双指针题单中的「分组循环」**一类将数组/网格按障碍物切分成若干段每段内部独立处理段与段之间通过重置指针/计数器衔接。这类题的共同套路是找到段的边界条件本题为*障碍物与行尾段内利用计数或指针确定元素的最终归属遇到边界时重置状态进入下一段。掌握本题后可进一步练习同属滑动窗口与双指针定长/不定长/单序列/双序列/三指针/分组循环体系的题目以及网格图相关题型强化按行/列解耦、逐段处理的思维。九、小结LeetCode 1861「旋转盒子」是一道把矩阵旋转坐标变换与分组循环双指针结合的经典题。本文完整继承并展开了题解文档的两大解法正序遍历按障碍物分段统计石头数量、从右往左回填逻辑直白适合入门倒序遍历 双指针从右向左一次扫描确定每块石头的落点代码更短是竞赛实战推荐写法。两种方法时间复杂度均为 $\mathcal{O}(mn)$、空间复杂度 $\mathcal{O}(1)$。结合仓库 c.go 的双实现与 c_test.go 的三组官方用例读者既可以对照文档理解原理也可以直接运行测试验证正确性再将同一套思路迁移到任意语言的实现中。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 题解精讲双指针 循环递增判定子序列力扣第 111 场双周赛 T2codeforces go 题解精讲双指针 循环递增判定子序列力扣第 111 场双周赛 T2 本文围绕算法竞赛模板库 codeforces go 中科学计算LeetCode-Book 题解精讲LCR 181 反转字符串中的单词——双指针与分割倒序两种解法的原理与实现LeetCode Book 题解精讲LCR 181 反转字符串中的单词——双指针与分割倒序两种解法的原理与实现 本篇技术指南以《LeetCode Book》仓示例工程剑指 Offer 58 - I翻转单词顺序——基于 LeetCode-Book 的双指针与分割倒序双解法详解剑指 Offer 58 I翻转单词顺序——基于 LeetCode Book 的双指针与分割倒序双解法详解 本文基于《LeetCode Book》仓库中的 剑指示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考