54. Spiral Matrix

Problem

Để giải bài toán Spiral Matrix trên LeetCode, bạn có thể sử dụng cách tiếp cận dựa trên việc thu hẹp các biên của ma trận (top, bottom, left, right) khi duyệt các phần tử theo thứ tự xoắn ốc. Dưới đây là một số ý tưởng và cách triển khai:

Approach

Xác định biên

Khởi tạo các biến top, bottom, left, và right để đại diện cho bốn biên của ma trận.

Duyệt theo thứ tự xoắn ốc

Duyệt từ trái sang phải trên hàng top

Duyệt từ trên xuống dưới trên cột right

Duyệt từ phải sang trái trên hàng bottom (nếu còn hàng)

Duyệt từ dưới lên trên trên cột left (nếu còn cột)

Thu hẹp biên: Sau mỗi bước duyệt, cập nhật các biên tương ứng (top++, bottom--, left++, right--) để tiếp tục duyệt phần ma trận chưa được xử lý.

Dừng lại khi các biên giao nhau: Khi top > bottom hoặc left > right, việc duyệt kết thúc.

Solution

typescripttypescript

1function spiralOrder(matrix: number[][]): number[] {
2    const res: number[] = [];
3    if (matrix.length === 0) return res;
4
5    let top = 0;
6    let bottom = matrix.length - 1;
7    let left = 0;
8    let right = matrix[0].length - 1;
9
10    while (top <= bottom && left <= right) {
11        // Top row: left -> right
12        for (let i = left; i <= right; i++) {
13            res.push(matrix[top][i]);
14        }
15        top++;
16
17        // Right column: top -> bottom
18        for (let i = top; i <= bottom; i++) {
19            res.push(matrix[i][right]);
20        }
21        right--;
22
23        // Bottom row: right -> left
24        if (top <= bottom) {
25            for (let i = right; i >= left; i--) {
26                res.push(matrix[bottom][i]);
27            }
28            bottom--;
29        }
30
31        // Left column: bottom -> top
32        if (left <= right) {
33            for (let i = bottom; i >= top; i--) {
34                res.push(matrix[i][left]);
35            }
36            left++;
37        }
38    }
39
40    return res;
41}
42

Loading content...

1function spiralOrder(matrix: number[][]): number[] { 2 const res: number[] = []; 3 if (matrix.length === 0) return res; 4 5 let top = 0; 6 let bottom = matrix.length - 1; 7 let left = 0; 8 let right = matrix[0].length - 1; 9 10 while (top <= bottom && left <= right) { 11 // Top row: left -> right 12 for (let i = left; i <= right; i++) { 13 res.push(matrix[top][i]); 14 } 15 top++; 16 17 // Right column: top -> bottom 18 for (let i = top; i <= bottom; i++) { 19 res.push(matrix[i][right]); 20 } 21 right--; 22 23 // Bottom row: right -> left 24 if (top <= bottom) { 25 for (let i = right; i >= left; i--) { 26 res.push(matrix[bottom][i]); 27 } 28 bottom--; 29 } 30 31 // Left column: bottom -> top 32 if (left <= right) { 33 for (let i = bottom; i >= top; i--) { 34 res.push(matrix[i][left]); 35 } 36 left++; 37 } 38 } 39 40 return res; 41} 42

54. Spiral Matrix

Related Posts

Related Posts

54. Spiral Matrix

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists