Week 1 @ 2025 算法周记【遍历二维数组 + 双指针数组】
- Bryan
Owned by Bryan
遍历二维数组
LC 151. Reverse Words in a String 反转字符串中的单词
https://leetcode.com/problems/reverse-words-in-a-string/
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 旋转图像
https://leetcode.com/problems/rotate-image/description/
待复习
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 度
待复习
LC 54. Spiral Matrix 螺旋矩阵
https://leetcode.com/problems/spiral-matrix/description/
待复习
LC 59. Spiral Matrix II 螺旋矩阵 II
https://leetcode.com/problems/spiral-matrix-ii/description/
双指针数组
LC 125. Valid Palindrome 验证回文串