今日OJ练习题写的感觉比较成功的俩道题~二维网络迁移和找小镇法官
发布日期:2021-05-07 13:55:45 浏览次数:16 分类:精选文章

本文共 1190 字,大约阅读时间需要 3 分钟。

为了解决这个问题,我们需要将给定的二维网格迁移 k 次。每次迁移操作会使每个元素向右移动一位,如果遇到网格边界,则向下移动。最终,我们需要返回迁移 k 次后的网格状态。

方法思路

  • 问题分析:每次迁移操作类似于环形移动,四次迁移后每个元素会回到原位。因此,我们可以将 k 分解为 r = k % (m * n),其中 m 和 n 分别是网格的行数和列数。这样,我们只需要计算 r 次迁移即可得到最终结果。
  • 索引转换:将二维网格转换为一个一维数组,通过计算每个元素的索引来确定其在迁移后的位置。新的索引可以通过公式 (i * n + j + r) % (m * n) 计算。
  • 重建网格:根据计算出的新索引,将每个元素放置到正确的位置,重建二维网格。
  • 解决代码

    public class Solution {    public int[][] shiftGrid(int[][] grid, int k) {        if (grid == null || grid.length == 0 || grid[0].length == 0) {            return new int[0][0];        }        int m = grid.length;        int n = grid[0].length;        int total = m * n;        int r = k % total;        int[][] result = new int[m][n];        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                int index = i * n + j;                int newIndex = (index + r) % total;                int newI = newIndex / n;                int newJ = newIndex % n;                result[newI][newJ] = grid[i][j];            }        }        return result;    }}

    代码解释

  • 边界检查:首先检查输入网格是否为空,若为空则返回空数组。
  • 计算 r:通过计算 k % (m * n) 得到实际需要迁移的次数。
  • 遍历元素:遍历每个元素,计算其在迁移后的索引,确定其在新网格中的位置。
  • 重建网格:根据新索引将元素放置到正确的位置,构建新的二维网格。
  • 这种方法有效地利用了环形移动的特性,避免了多次迁移的高计算复杂度,确保了算法的高效性。

    上一篇:Java~IO输入输出流练习题~车库管理(停车、离开、查找、显示车库车辆信息)
    下一篇:Java~分别用顺序表和链表实现栈和队列,以及库的栈和队列的使用

    发表评论

    最新留言

    很好
    [***.229.124.182]2025年03月28日 03时53分27秒

    关于作者

        喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
    -- 愿君每日到此一游!

    推荐文章