📘 題目敘述
給你一個 m x n 的整數矩陣 mat 和一個整數 k，矩陣的列是 0-indexed。
以下操作會進行 k 次：
- 偶數列（
0, 2, 4, ...）會做循環左移 - 奇數列（
1, 3, 5, ...）會做循環右移
如果經過這 k 次操作後，最後得到的矩陣和原本的矩陣完全一樣，請回傳 true；否則回傳 false。
條件限制
1 <= mat.length <= 251 <= mat[i].length <= 251 <= mat[i][j] <= 251 <= k <= 50
🧠 解題思路
這題的重點是：
我其實不用真的把矩陣移動 k 次，只要直接看做完 k 次之後，每個位置會對應回哪個位置就可以了。
因為一列長度是 n，不管左移還是右移，做很多次之後其實都只跟：
k % n
有關。
而我這份寫法抓到的一個想法是：
- 不管原本題目說偶數列左移、奇數列右移
- 如果最後矩陣要和原本完全一樣
- 那每一列都必須滿足：每個位置的值和往後偏移
k格的位置值一樣
所以我直接檢查每一列是不是對這個循環位移保持不變。
如果所有列都符合，答案就是 true；只要有任何一格不符合，就是 false。
所有變數
m：矩陣列數n：矩陣行數x：第j格在循環位移後對應比較的位置
🪜 主要流程步驟
1. 先取得矩陣大小
int m = mat.size();
int n = mat[0].size();
這裡先把列數和行數存起來，後面做雙層迴圈時會用到。
2. 逐列逐格檢查，這一格在位移後是否還和原本相同
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
我這裡直接枚舉矩陣裡每一個位置 (i, j)。
目標是檢查：
- 如果這一列做完對應的循環位移
- 原本第
j格的值，最後是不是還能對回自己
3. 用 (j + k) % n 找到循環位移後對應的位置
int x = (j + k) % n;
這裡的 x 表示：
- 從第
j個位置往後移k格之後 - 會落到哪個位置
因為是循環位移，所以要對 n 取模。
例如一列長度是 5：
- 第
3格往後移4格 - 就會變成
(3 + 4) % 5 = 2
所以這樣就能直接算出位移後的對應位置，不需要真的模擬每一步。
4. 如果原本位置和對應位置的值不同，代表最後不可能和原矩陣一樣
if (mat[i][j] != mat[i][x]) return false;
這一步就是直接檢查：
- 原本第
j格的值 - 和位移後對應到的第
x格的值
如果不一樣，表示這一列在做完 k 次循環位移後，至少這個位置已經對不起來了，所以最後矩陣不可能和原本完全相同，直接回傳 false。
5. 如果全部位置都檢查通過，就回傳 true
return true;
如果整個矩陣所有位置都檢查完都沒有出現不相等，表示每一列在做完這樣的循環位移後，整體仍然保持和原本一樣，所以答案就是 true。
⏱️ 複雜度
設 m = mat.length，n = mat[0].length。
- 時間複雜度：
O(mn)
每個位置都檢查一次。 - 空間複雜度：
O(1)
只用了固定數量的變數。
💻 程式碼實作
class Solution {
public:
bool areSimilar(vector<vector<int>>& mat, int k) {
int m = mat.size();
int n = mat[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int x = (j + k) % n;
if (mat[i][j] != mat[i][x]) return false;
}
}
return true;
}
};
🔗 題目連結
https://leetcode.com/problems/matrix-similarity-after-cyclic-shifts/