Dawn's Blogs

分享技术 记录成长

0%

算法刷题笔记 (23) 回文数 搜索二维矩阵 旋转链表

发表于 更新于 分类于

回文数

回文数

解题思路

  1. 将数字转化为字符串，再判断是否是回文字符串
  2. 反转一半数字，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。
    • 如何知道反转数字的位数已经达到原始数字位数的一半？当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了。

反转一半数字

解题代码

反转一半数字：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func isPalindrome(x int) bool {
    // 当 x < 0 时，x 不是回文数
    // 如果数字的最后一位是 0，为了使该数字为回文，
    // 则其第一位数字也应该是 0，只有0符合
    if x < 0 || (x%10 == 0 && x != 0) {
        return false
    }
    reversedNum := 0
    for x > reversedNum {
        reversedNum = reversedNum*10 + x%10
        x = x/10
    }

    return x==reversedNum || x==reversedNum/10
}

搜索二维矩阵

搜索二维矩阵

解题思路

借助于二叉搜索树的思想，可以从二维矩阵的右上角开始查找：

  • 左边的元素看作是右子树
  • 下边的元素看作是左子树

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func searchMatrix(matrix [][]int, target int) bool {
    m := len(matrix)
    n := len(matrix[0])
    row, col := 0, n-1  // 从二维矩阵的右上角开始查找
    for row < m && col >= 0 {
        if target == matrix[row][col] {
            // 找到目标
            return true
        } else if target >  matrix[row][col] {
            // 目标大于当前元素，向下移动
            row++
        } else {
            // 目标小于当前元素，向左移动
            col--
        }
    }

    return false
}

旋转链表

旋转链表

解题思路

利用反转链表，首先找到倒数第k个节点（要求k小于链表长度len，否则需要对k%len的修正），以倒数第k个节点为第二个链表的头节点，将原链表分为两个链表，分别对两个链表进行反转，最后将反转后的两个链表连接在一起进行一次反转。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil {
        // 链表为空或者只有一个节点，直接返回
        return head
    }
    len := length(head)     // 链表长度
    k = k % len             // 修正k不超过其长度
    if k == 0 {
        // 相当于不用移动，直接返回
        return head
    }
    // 找到倒数第k个节点cur和它的前驱pre
    var pre *ListNode
    cur := head
    for i := 0; i < len-k; i++{
        pre = cur
        cur = cur.Next
    }
    // 从倒数第k个节点处断开
    pre.Next = nil
    // 反转两个链表
    head1 := reverse(head)
    head2 := reverse(cur)
    // 连接两个链表
    head.Next = head2
    // 反转整个链表
    return reverse(head1)
}

func reverse(head *ListNode) *ListNode {    // 反转链表
    var pre *ListNode
    cur := head
    for cur != nil {
        cur.Next, cur, pre = pre, cur.Next, cur
    }

    return pre
}

func length(head *ListNode) int {   // 返回链表长度
    count := 0
    cur := head
    for cur != nil {
        count++
        cur = cur.Next
    }

    return count
}

颜色分类

颜色分类

解题思路

  1. 两次遍历，第一次遍历时，将所有的0置换到前面去；第二次遍历时，从所有0的后一个位置开始，将所有的1置换到前面去。
  2. 双指针，两次遍历。用指针zero来交换0，指针one来交换1：
    • 如果找到了1，那么与nums[one]交换，并将one向后移动一个位置
    • 如果找到了0，那么与nums[zero]交换，若zero<one，说明之前zero指向的1被交换到了后面，所以nums[one]与nums[i]进行交换。最后zero和one都向后移动一个位置。

解题代码

  1. 两次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func sortColors(nums []int)  {
    zero := 0   // 指向数字0
    // 第一次遍历，将0置换到前面去
    for i := 0; i < len(nums); i++ {
        if nums[i] == 0 {
            nums[zero], nums[i] = nums[i], nums[zero]
            zero++
        }
    }
    // 第二次遍历，从前面的0后面的位置开始，将1置换到前面去
    one := zero
    for i := one; i < len(nums); i++ {
        if nums[i] == 1 {
            nums[one], nums[i] = nums[i], nums[one]
            one++
        }
    }
}
  1. 双指针，一次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func sortColors(nums []int)  {
    zero, one := 0, 0      // zero指向当前0的位置，one指向当前1的位置
    for i := 0; i < len(nums); i++ {
        if nums[i] == 1 {
            nums[one], nums[i] = nums[i], nums[one]
            one++
        } else if nums[i] == 0 {
            nums[zero], nums[i] = nums[i], nums[zero]
            if zero < one {
                nums[one], nums[i] = nums[i], nums[one]
            }
            zero++
            one++
        }
    }
}