算法刷题笔记 (8) 岛屿的数量 最长上升子序列 用栈实现队列

岛屿的数量

岛屿数量

解题思路

可以将grid看作是一个有向图，每个节点最多有上下左右四条边，竖直或水平相邻的 1 之间有边相连，那么岛屿的数量就是图的连通分量个数。所以可以进行图的遍历，来求得连通分量的个数：

1. 图的深度优先遍历
2. 图的广度优先遍历

解题代码

1. 图的深度优先遍历

func numIslands(grid [][]byte) int {
    var landsNum int    // 岛屿数量
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' {
                // 深度优先遍历的次数就是岛屿的数量
                dfs(grid, i, j)
                landsNum++
            }
        }
    }

    return landsNum
}

func dfs(grid [][]byte, i int, j int) {
    // 以grid[i][j]为起点进行深度优先遍历
    if i < 0 || i > len(grid)-1 || j < 0 || j > len(grid[0])-1 {
        // grid[i][j]超出边界，直接返回
        return
    }
    if grid[i][j] == '0' {
        // 是“海水”或者已经遍历过，直接返回
        return
    }
    grid[i][j] = '0'
    // 遍历上方
    dfs(grid, i-1, j)
    // 遍历下方
    dfs(grid, i+1, j)
    // 遍历左边
    dfs(grid, i, j-1)
    // 遍历右边
    dfs(grid, i, j+1)
}

2. 广度优先遍历

func numIslands(grid [][]byte) int {
    var landsNum int    // 岛屿数量
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' {
                // 广度优先遍历的次数就是岛屿的数量
                bfs(grid, i, j)
                landsNum++
            }
        }
    }

    return landsNum
}

func bfs(grid [][]byte, i int, j int) {
    // 以grid[i][j]为起点进行广度优先遍历
    queue := [][]int{}    // 定义一个队列
    queue = append(queue, []int{i, j})  // grid[i][j]入队

    for len(queue) > 0 {    // 队列不空时循环
        // 队头出队
        cur := queue[0]
        i = cur[0]
        j = cur[1]
        queue = queue[1:]
        if i < 0 || i > len(grid)-1 || j < 0 || j > len(grid[0])-1 {
            // grid[i][j]超出边界，直接跳过
            continue
        }
        if grid[i][j] == '0' {
            // 是“海水”或者已经遍历过，直接跳过
            continue
        }
        // 访问当前节点
        grid[i][j] = '0'
        // 当前节点的上下左右节点入队
        queue = append(queue, []int{i-1, j})
        queue = append(queue, []int{i+1, j})
        queue = append(queue, []int{i, j-1})
        queue = append(queue, []int{i, j+1})
    }
}

最长上升子序列

最长上升子序列

解题思路

利用动态规划，设dp[i]为以nums[i]为结尾的最长上升子序列（被初始化为1），则对于j < i且nums[j] < nums[i]，dp[i] = max{ dp[j] }+1。那么最长上升子序列的长度为max{ dp[i] }, 0<= i< len(dp)

解题代码

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    dp := make([]int, len(nums))
    dp[0] = 1
    maxLength := 1  // 最大子序列长度

    for i := 1; i < len(nums); i++ {
        dp[i] = 1
        // dp[i] = max{dp[j]} + 1，j满足j < i 且 nums[j] < nums[i]
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                dp[i] = max(dp[j]+1, dp[i])
            }
        }
        maxLength = max(dp[i], maxLength)
    }

    return maxLength
}

func max(n1, n2 int) int {
    if n1 > n2 {
        return n1
    }
    return n2
}

用栈实现队列

用栈实现队列

解题思路

将一个栈当作输入栈，用于压入push传入的数据；另一个栈当作输出栈，用于pop和peek 操作。

每次pop或peek时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

解题代码

type MyQueue struct {
    inStack, outStack []int
}


func Constructor() MyQueue {
    return MyQueue{}
}


func (this *MyQueue) Push(x int)  {
    this.inStack = append(this.inStack, x)
}

func (this *MyQueue)in2out() {  // 将inStack中的元素转移到outStack中
    for len(this.inStack) > 0 {
        // 将inStack的全部元素依次弹出，压入outStack中
        this.outStack = append(this.outStack, this.inStack[len(this.inStack)-1])
        this.inStack = this.inStack[:len(this.inStack)-1]
    }
}

func (this *MyQueue) Pop() int {
    var ret int
    if len(this.outStack) == 0{
        // outStack为空，将inStack中的元素转移到outStack中
        this.in2out()
    }
    
    // 直接弹出outStack栈顶元素
    ret = this.outStack[len(this.outStack)-1]
    this.outStack = this.outStack[:len(this.outStack)-1]
    return ret
}


func (this *MyQueue) Peek() int {
    if len(this.outStack) == 0{
        // outStack为空，将inStack中的元素转移到outStack中
        this.in2out()
    }
    return this.outStack[len(this.outStack)-1]
}


func (this *MyQueue) Empty() bool {
    if len(this.inStack) == 0 && len(this.outStack) == 0 {
        // 若两个栈均为空，则队列为空
        return true
    }
    // 否则队列不空
    return false
}