算法刷题笔记 (7) 螺旋矩阵 搜索旋转排序数组 反转链表Ⅱ

螺旋矩阵

螺旋矩阵

解题思路

设定上下左右边界：

• 从左到右遍历上边界，重新定义上边界，即上边界指向下一行，若上边界越过下边界，则退出循环
• 从上到下遍历右边界，重新定义右边界，即右边界指向左边一行，若右边界越过左边界，则退出循环
• 同理依次遍历下边界、左边界
• 循环指向上述步骤

解题代码

func spiralOrder(matrix [][]int) []int {
    ret := []int{}

    // 上下左右的边界
    up, down, left, right := 0, len(matrix)-1, 0, len(matrix[0])-1

    for {
        // 从左向右遍历上边界
        for i := left; i <= right; i++ {
            ret = append(ret, matrix[up][i])
        }
        // 重新设定上边界
        if up++; up > down {
            break
        }
        // 从上到下遍历右边界
        for i := up; i <= down; i++ {
            ret = append(ret, matrix[i][right])
        }
        // 重新设定右边界
        if right--; right < left {
            break
        }
        //从右向左遍历下边界
        for i := right; i >= left; i-- {
            ret = append(ret, matrix[down][i])
        }
        // 重新设定下边界
        if down--; down < up {
            break
        }
        // 从下到上遍历左边界
        for i := down; i >= up; i-- {
            ret = append(ret, matrix[i][left])
        }
        // 重新设定左边界
        if left++; left > right {
            break
        }
    }
    
    return ret
}

搜索旋转排序数组

搜索旋转排序数组

解题思路

利用二分查找的基本思想，数组可以分成两段有序数组，首先判断mid指向的是前半段还是后半段有序数组：

• 若nums[low] <= nums[mid]，则mid在前半段数组中：

  • 若nums[low] <= target && target < nums[mid]，则target位于mid之前
  • 否则target位于mid之后

• 若nums[low] > nums[mid]，则mid在后半段数组中：

  • 若nums[mid] < target && target <= nums[high]，则target位于mid之后
  • 否则位于mid之前

解题代码

func search(nums []int, target int) int {
    low, high := 0, len(nums)-1
    var mid int

    for low <= high {
        mid = (low + high) / 2

        if nums[mid] == target {
            return mid
        }
        if nums[low] <= nums[mid] {
            // 若mid在前半段有序数组中
            if nums[low] <= target && target < nums[mid] {
                // 在low...mid-1中
                high = mid -1
            } else {
                // 在mid+1...high中
                low = mid + 1
            }
        } else {
            // mid在后半段有序数组中
            if nums[mid] < target && target <= nums[high] {
                // 在mid+1...high中
                low = mid + 1
            } else {
                // 在low...mid-1中
                high = mid -1
            }
        }
    }
    // 没有找到target
    return -1
}

反转链表 II

反转链表 II

解题思路

1. 利用栈保存需要反转的部分的值，将这些节点的值依次入栈，接着从需要反转的第一个节点开始，依次弹栈并改变节点的值，实现反转
2. 基于头插法实现链表反转，使cur指向第left位置的节点，leftPre指向第left位置节点的前驱，每次将cur的后继从链表中摘下来，插入到leftPre的后面，实现链表的反转。

解题代码

1. 利用栈保存需要反转的部分的值

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    var cur, reverseHead *ListNode  // cur指向当前节点，reverseHead指向反转链表部分的第一个节点
    cur = head
    // 使用栈记录反转部分的值Val
    stack := make([]int, right-left+1)
    top := 0    // 栈顶指针

    // 首先使cur指向left位置的节点
    for i := 1; i < left; i++ {
        cur = cur.Next
    }
    reverseHead = cur   // reverseHead指向反转链表部分的第一个节点

    // 将第left位置~第right位置节点的值入栈
    for i := left; i <= right; i++ {
        stack[top] = cur.Val
        top++
        cur = cur.Next
    }

    // 重新遍历left位置~第right位置节点，依次出栈并完成这段节点数值的反转
    cur = reverseHead
    for i := left; i <= right; i++ {
        top--
        cur.Val = stack[top]
        cur = cur.Next
    }

    return head

}

2. 头插法

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    newHead := &ListNode{}  // 使链表带头节点
    newHead.Next = head 

    cur, pre := head, newHead  // cur指向当前遍历节点，pre指向cur的前驱
    var leftPre *ListNode   // leftPre指向第left位置节点的前驱
    cur = head

    // 首先使cur指向left位置的节点
    for i := 1; i < left; i++ {
        pre = cur
        cur = cur.Next
    }

    leftPre = pre

    // left~right反转链表
    for i := left; i < right; i++ {
        // 将cur.Next从链表上摘下
        r := cur.Next   // r指向cur的下一个节点
        cur.Next = r.Next
        // 将r插入到leftPre之后（头插）
        r.Next = leftPre.Next
        leftPre.Next = r
    }

    return newHead.Next
}