Week 1 @ 2025 算法周记【遍历二维数组 + 双指针数组】

3 min

遍历二维数组

LC 151. Reverse Words in a String 反转字符串中的单词

Reverse Words in a String - LeetCode

func reverseWords(s string) string { words := strings.Fields(s) slices.Reverse(words) return strings.Join(words, " ") }

原地解法

待复习

class Solution { public: string reverseWords(string s) { removeExtraSpaces(s); reverse(s.begin(), s.end()); string::iterator gh = s.begin(); for (auto p = s.begin(); p != s.end(); p++) { if (*p == ' ') { reverse(gh, p); gh = p+1; continue; } } reverse(gh, s.end()); return s; } void removeExtraSpaces(string& s) { int slow = 0; int fast = 0; while (fast < s.size() && s[fast] == ' ') { fast++; } bool isSpace = false; // 标记前一个字符是否为空格 while (fast < s.size()) { if (s[fast] == ' ') { if (!isSpace) { // 当前是空格，且前一个不是空格 s[slow++] = ' '; isSpace = true; } } else { // 非空格字符 s[slow++] = s[fast]; isSpace = false; } fast++; } if (slow > 0 && s[slow - 1] == ' ') { slow--; } s.resize(slow); } };

LC 48. Rotate Image 旋转图像

Rotate Image - LeetCode

待复习

func rotate(matrix [][]int) { n := len(matrix) for i := 0; i < n; i++ { for j := 0; j < i; j++ { matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] } } for i := 0; i < n; i++ { slices.Reverse(matrix[i]) } }

逆时针旋转图像

与 LC 48 类似，但从顺时针旋转 90 度改成逆时针旋转 90 度

待复习

func rotate(matrix [][]int) { n := len(matrix) for i := 0; i < n; i++ { for j := 0; j < n-i-1; j++ { matrix[i][j], matrix[n-j-1][n-i-1] = matrix[n-j-1][n-i-1], matrix[i][j] } } for i := 0; i < n; i++ { slices.Reverse(matrix[i]) } }

LC 54. Spiral Matrix 螺旋矩阵

Spiral Matrix - LeetCode

待复习

func spiralOrder(matrix [][]int) []int { m, n := len(matrix), len(matrix[0]) // matrix: m rows * n cols total := m * n T := 0 B := m-1 L := 0 R := n-1 result := make([]int, 0, total) for len(result) < total { // top if T <= B { i := T for j := L; j <= R; j++ { result = append(result, matrix[i][j]) } T++ } // right if L <= R { j := R for i := T; i <= B; i++ { result = append(result, matrix[i][j]) } R-- } // bottom if T <= B { i := B for j := R; j >= L; j-- { result = append(result, matrix[i][j]) } B-- } // left if L <= R { j := L for i := B; i >= T; i-- { result = append(result, matrix[i][j]) } L++ } } return result }

LC 59. Spiral Matrix II 螺旋矩阵 II

https://leetcode.com/problems/spiral-matrix-ii/description/

func generateMatrix(n int) [][]int { T := 0 B := n-1 L := 0 R := n-1 matrix := createMatrix(n) x := 1 total := n*n for x <= total { // top if T <= B { i := T for j := L; j <= R; j++ { matrix[i][j] = x x++ } T++ } // right if L <= R { j := R for i := T; i <= B; i++ { matrix[i][j] = x x++ } R-- } // bottom if T <= B { i := B for j := R; j >= L; j-- { matrix[i][j] = x x++ } B-- } // left if L <= R { j := L for i := B; i >= T; i-- { matrix[i][j] = x x++ } L++ } } return matrix } func createMatrix(n int) [][]int { matrix := make([][]int, n) for i := range matrix { matrix[i] = make([]int, n) } return matrix }

双指针数组

LC 125. Valid Palindrome 验证回文串

func isPalindrome(s string) bool { i, j := -1, len(s) for { i++ j-- for i < j && !isValid(s[i]) { i++ } for i < j && !isValid(s[j]) { j-- } if i >= j { break } if !equal(s[i], s[j]) { return false } } return true } func isValid(c byte) bool { return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') } func equal(a, b byte) bool { return a == b || lower(a) == lower(b) } func lower(b byte) byte { if b >= 'A' && b <= 'Z' { return b - 'A' + 'a' } return b }

 

Related content