# 二维数组的花式遍历技巧

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode | Difficulty |
---|---|

151. Reverse Words in a String | 🟠 |

48. Rotate Image | 🟠 |

54. Spiral Matrix | 🟠 |

59. Spiral Matrix II | 🟠 |

61. Rotate List | 🟠 |

Prerequisites

Before reading this article, you should familiarize yourself with:

Some readers have mentioned that after reading many articles on this site and mastering the framework thinking, they can solve most problems that follow a certain pattern.

However, framework thinking is not a panacea. There are specific techniques that are easy for those who know them and difficult for those who don't. These can only be mastered through extensive problem-solving and accumulation.

In this article, I will share some clever operations on two-dimensional arrays. Once you have an impression of these techniques, you won't be confused when encountering similar problems in the future.

## Clockwise/Counterclockwise Matrix Rotation

Rotating a two-dimensional array is a common question in written exams. LeetCode problem #48 "Rotate Image" is a classic example:

**48. Rotate Image** | 力扣 | LeetCode |

You are given an `n x n`

2D `matrix`

representing an image, rotate the image by **90** degrees (clockwise).

You have to rotate the image **in-place**, which means you have to modify the input 2D matrix directly. **DO NOT** allocate another 2D matrix and do the rotation.

**Example 1:**

Input:matrix = [[1,2,3],[4,5,6],[7,8,9]]Output:[[7,4,1],[8,5,2],[9,6,3]]

**Example 2:**

Input:matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]Output:[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

**Constraints:**

`n == matrix.length == matrix[i].length`

`1 <= n <= 20`

`-1000 <= matrix[i][j] <= 1000`

The problem is straightforward: you need to rotate a two-dimensional matrix 90 degrees clockwise. The **challenge is to modify it "in place"**, with the function signature as follows:

`void rotate(int[][] matrix)`

`void rotate(vector<vector<int>>& matrix)`

`def rotate(matrix: List[List[int]]) -> None:`

`func rotate(matrix [][]int) {}`

`var rotate = function(matrix) {}`

How to rotate a 2D matrix "in place"? At first thought, it seems very complex, requiring a clever algorithm to rotate the matrix "ring by ring":

**However, this problem requires an unconventional approach.** Before diving into the clever solution, let's warm up with another algorithm question Google once asked:

Given a string `s`

containing several words and spaces, write an algorithm to **in-place** reverse the order of all words.

For example, if you are given the following string:

`s = "hello world labuladong"`

Your algorithm needs to **in-place** reverse the order of the words in this string:

`s = "labuladong world hello"`

The conventional approach is to `split`

`s`

by spaces into several words, then `reverse`

the order of these words, and finally `join`

them back into a sentence. However, this method uses extra space and is not an "in-place" reversal.

**The correct approach is to first reverse the entire string s:**

`s = "gnodalubal dlrow olleh"`

**Then reverse each word individually:**

`s = "labuladong world hello"`

This way, we achieve the goal of reversing the order of all words in place. LeetCode problem 151, "Reverse Words in a String," is a similar issue, and you can try it out.

The little trick mentioned above can be further wrapped up. For example, you can take a look at LeetCode problem 61, "Rotate List": given a singly linked list, you need to rotate the list by moving each node to the right by `k`

positions.

For instance, if the input linked list is `1 -> 2 -> 3 -> 4 -> 5`

and `k = 2`

, your algorithm should return `4 -> 5 -> 1 -> 2 -> 3`

, which means moving each node 2 positions to the right.

For this problem, don't naively move the nodes one by one. Let me translate this for you: it's essentially about moving the last `k`

nodes to the head of the list. Got it?

If you haven't figured it out yet, here's another hint: moving the last `k`

nodes to the head is the same as reversing the first `n - k`

nodes and the last `k`

nodes in place, right?

So, isn't this the same principle as reversing words in a string in place? You just need to reverse the entire list first, then reverse the first `n - k`

nodes and the last `k`

nodes separately to get the result.

Of course, there are some minor details in this problem. For example, `k`

might be greater than the length of the list. In that case, you need to find the length `n`

of the list first, then take the modulus `k = k % n`

. This way, `k`

won't be greater than the length of the list, and the final result will still be correct.

If you have time, try solving this problem yourself. It's relatively simple, so I won't include the code here.

What's the purpose of discussing these two problems?

**It aims to illustrate that sometimes our intuitive thinking might not be the most elegant solution in the eyes of a computer; however, what the computer considers the most elegant solution might not be intuitive to us.** Perhaps this is the charm of algorithms.