二维数组的花式遍历技巧
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].length1 <= 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.