遍历二维数组
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 度
待复习
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 螺旋矩阵
https://leetcode.com/problems/spiral-matrix/description/
待复习
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
}