 原地起飞：我与 AI 死磕 LeetCode 1260 的 6 阶进化录)
💡 一、 缘起：对官方 O(MN) 内存占用的“叛逆”
今天在刷 LeetCode 1260（二维网格迁移）时，官方给出的标准答案写得极其干净：
classSolution{public:vector<vector<int>>shiftGrid(vector<vector<int>>&grid,intk){intm=grid.size(),n=grid[0].size();vector<vector<int>>ret(m,vector<int>(n));// 👈 扎眼的额外 M*N 空间for(inti=0;i<m;i++){for(intj=0;j<n;j++){intindex1=(i*n+j+k)%(m*n);ret[index1/n][index1%n]=grid[i][j];}}returnret;}};官方虽然巧妙地利用一维线性映射顺畅地完成了搬运，逻辑挑不出毛病，但我越看那个 ret(m, vector(n)) 越觉得心里堵得慌。
一道简单题，核心就是挪动格子，凭什么要浪费一整个矩阵的备份空间？
我的极客强迫症瞬间被点燃了。为了打破官方的 O(M * N) 辅助空间限制，我和 AI 顺着“空间备份流 -> 原地洗牌流 -> 数论降维”的线索，硬生生把这道题撕裂出了 6 种完全不同的硬核演进形态！
二、 拓荒阶段：那些不得不开备份数组的尝试
在最开始，我的脑子还没有跳出“必须有一个备份数组来落脚”的思维惯性，在这个阶段，我经历了三次尝试。
1. 解法一：K 次单步大循环（最暴力的模拟）
- 核心思想：开一个临时变量，每次把整个矩阵所有元素整体向右挪动 1 位，外面套一个 while(k–) 的大循环。
- 代价：空间看似省了，但由于每次移动都要扫描全场，时间复杂度高达 O(K * M * N)。只要 K 一大，LeetCode 直接用 TLE（超时）教做人。
2. 解法二：纯二维分块拼接（顺着直觉的翻车现场）
既然挪 1 位会超时，那我先克隆一份原矩阵 auto back = grid;，然后拿着算好的 newRow 和 newColmn 偏移量，试图在二维层面上把 back 矩阵的前半段和后半段对调拼接。
然而，代码一提交，无情地弹出了 Runtime Error（下标越界崩溃）。我和 AI 一对齐，发现了两个二维死穴：
- “贪吃蛇”引发的阶梯形断裂：行末尾溢出会钻到下一行开头，导致数据断开的分界线根本不是直线，而是一个“L型阶梯折线”！我的双层循环按矩形去切，漏掉了大批格子。
- 列溢出的行波及效应：在二维坐标里单纯做 i + newRow 的加减，下标会随着循环不断膨胀，直接强行撞破了内存边界。
3. 解法三：一维扁平化映射（官方的标准答案）
也就是本文开头的官方解法。在同样开辟 O(M * N) 空间的前提下，官方放弃了死磕二维分块，直接利用 i * n + j 将矩阵拍平成一维，算好新的一维索引后，再 index1 / n 填回新矩阵。没有复杂的进位判断，极其优雅，但空间代价是扎扎实实的 O(M * N)。
三、 突破鸿沟：多米诺环状置换，肉身洗牌
看着解法二和解法三都死死绑在“必须开辟一个额外矩阵”的耻辱柱上，我向 AI 抛出了一个更疯狂的构想：
“有没有可能彻底放弃任何备份矩阵，直接在原矩阵的‘肉身’里进行多米诺骨牌式的链式追踪（A -> B -> C -> D），强行达成时间 O(MN) + 空间真 · O(1)？”
这一句话，直接推开了离散数学中“置换群循环分解（Cyclic Decomposition）”的大门！
网格平移在物理内存上，其实可以拆解为若干个互不相交的“闭合环”（Cycles）：位置 0 的数去往 K，被挤出来的数拿过接力棒去往 (K + K) % TOTAL，直到某个数字被挤回起点 0，宣告一轮闭环。
为了让这套多米诺追踪完美落地，我们卸掉了图遍历中常见的 visited 数组（因为我们有全场总量计数器宏观控场），演进出了两种硬核的原地解法：
4. 解法四：纯 DFS 原地环状递归版（无全局污染、优雅栈流转）
利用函数的系统栈帧（局部变量 next_old_val）天生驻留在栈中的特性，让被挤出来的数字拿着接力棒自顶向下流动。由 dfs 函数在成功归位一个格子时返回 1，外层循环直接累加返回值。
classSolution{private:intdfs(vector<vector<int>>&grid,intcurr_1d,intstart_1d,intprev_val,intk,inttotal,intn){intnext_1d=(curr_1d+k)%total;intnext_r=next_1d/n;intnext_c=next_1d%n;intnext_old_val=grid[next_r][next_c];grid[next_r][next_c]=prev_val;// 原地狸猫换太子if(next_1d==start_1d)return1;// 终止条件：当前环闭合return1+dfs(grid,next_1d,start_1d,next_old_val,k,total,n);}public:vector<vector<int>>&shiftGrid(vector<vector<int>>&grid,intk){intm=grid.size();intn=grid[0].size();inttotal=m*n;k%=total;if(k==0)returngrid;inttotal_moved=0;// 纯局部进度控场for(intstart=0;total_moved<total;++start){total_moved+=dfs(grid,start,start,grid[start/n][start%n],k,total,n);}returngrid;}};5. 解法五：无栈纯迭代版（真 · O(1) 空间的终极迭代形态）
递归版精美绝伦，但如果矩阵极大且形成超大单环，有系统栈溢出（Stack Overflow）的工程隐患。
我再度进行架构演进：既然手握全局计数器 count，迭代版本根本不需要任何显式或隐式的栈！直接用一个 do-while 循环让一维指针在原网格肉身内自行流转。没有任何多余空间开销，没有任何开辟大块内存的风险。
classSolution{public:vector<vector<int>>&shiftGrid(vector<vector<int>>&grid,intk){intm=grid.size();intn=grid[0].size();inttotal=m*n;k%=total;if(k==0)returngrid;intcount=0;// 核心总量计数器for(intstart=0;count<total;++start){intcurr_1d=start;intprev_val=grid[start/n][start%n];// 抓起首个接力棒do{intnext_1d=(curr_1d+k)%total;intnext_r=next_1d/n;intnext_c=next_1d%n;inttemp=grid[next_r][next_c];grid[next_r][next_c]=prev_val;// 原地换血prev_val=temp;curr_1d=next_1d;count++;}while(curr_1d!=start);// 当前链条闭合}returngrid;}};四、 艺术美学：AI 砸过来的王炸
6. 解法六：惊艳全场的三次翻转法（Vector Reverse）
就在我觉得原地环状迭代已经把这道题的空间 and 逻辑压榨到极限的时候，AI 突然在对话框里抛出了一套绝妙的代码艺术美学——矩阵版的“旋转数组”。
网格向右平移 K 位，本质上就是把逻辑一维管子里最末尾的 K 个元素整体拔起来，空降到了最车头。
我们甚至不需要写任何复杂的环路迭代，直接通过自定义 Lambda 表达式将一维索引映射为二维引用，配合 C++ 标准库的 std::swap，三行翻转，降维打击：
classSolution{public:vector<vector<int>>&shiftGrid(vector<vector<int>>&grid,intk){intm=grid.size();intn=grid[0].size();inttotal=m*n;k%=total;if(k==0)returngrid;// 一维索引到二维引用的神奇映射autoget_ref=[&](intidx)->int&{returngrid[idx/n][idx%n];};autoreverse_range=[&](intstart,intend){while(start<end){swap(get_ref(start),get_ref(end));start++;end--;}};// 🏆 震撼全场的三步翻转神迹reverse_range(0,total-1);// 1. 全局大翻转（车头车尾大颠倒）reverse_range(0,k-1);// 2. 翻转前 k 个元素（局部复位）reverse_range(k,total-1);// 3. 翻转剩下的元素（局部复位）returngrid;}};五、 王者升华：破译置换群的数论终极定理
在死磕的最后，我们将问题推向了纯数学的无上圣殿。
不管是写解法四的 DFS 还是解法五的纯迭代，我们外层循环都在兢兢业业地做 start++，并依赖计数器去盲目探索“下一个独立环的起点在哪里”。
但其实，这个矩阵里究竟存在多少个独立封闭的连通环，在数论里是一个早就被写死的定理！
📐物理置换群循环分解定理：
在一个长度为 TOTAL 的环形链表中，每次步长为 K 进行跳跃。全场互不相交的、独立封闭的连通环个数，有且仅有：
环的个数 = gcd(TOTAL, K) = gcd(m * n, k)
💥 数学发现带来的代码进化
这意味着，我们根本连全局计数器都可以退居二线！
我们明确地知道，全场就只有 gcd(total, k) 个环。外层循环的起点，精确地锁死在 0 到 gcd(total, k) - 1 之间，一步都不会多走，逻辑坚固得像一块花岗岩！
六、 结语：把简单题挖到尽头的魅力
回看整场死磕，这 6 种解法完美诠释了算法探索的无上乐趣：
- 从最初粗糙的 K次单步模拟 到直觉的 二维分块翻车；
- 看到官方完美的 一维映射新矩阵解法；
- 被激发出空间强迫症，跨越空间鸿沟推导出了 真 · O(1) 空间的环状多米诺置换（DFS与纯迭代）；
- 惊叹于 AI 抛出的 三次翻转美学；
- 最终，用 最大公约数（GCD）定理 在数论层面实现终极闭环。
刷题的乐趣从来不在于 AC 数量的堆砌，而在于你能不能在一个看似简单的官方及格方案后面，把问题的底层物理结构和数学本质，挖到它无法再优化的最尽头！
