算法刷题笔记 (17) 搜索二维矩阵II 最大正方形 最长公共前缀 岛屿的最大面积

搜索二维矩阵 II

搜索二维矩阵 II

解题思路

1. 对每一行进行二分查找

2. 从二维矩阵的右上角开始，会发现每次都是向左数字会变小，向下数字会变大，有点和二分查找树相似。所以可以把target与当前值进行比较：

   • 如果target大于当前值，向下走
   • 如果target小于当前值，向左走
   • 如果target等于当前值，返回true

解题代码

1. 对每一行进行二分查找

func searchMatrix(matrix [][]int, target int) bool {
    for _, row := range matrix {    // 对每一行进行二分查找
        if biSearch(row, target) {
            // 找到
            return true
        }
    }

    return false
}

func biSearch(nums []int, target int) bool {    // 二分查找
    low, high := 0, len(nums)-1
    for low <= high {
        mid := (low+high) / 2
        if nums[mid] == target {
            // 找到元素
            return true
        } else if nums[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    return false
}

2. 从二维矩阵的右上角开始查找，与二分查找树类似：

func searchMatrix(matrix [][]int, target int) bool {
    row, col := 0, len(matrix[0])-1
    for row < len(matrix) && col >= 0 {
        cur := matrix[row][col]     // 当前元素
        if target > cur {
            // 向下走
            row++
        } else if target < cur {
            // 向左走
            col--
        } else {
            // 找到元素
            return true
        }
    }

    return false
}

最大正方形

最大正方形

解题思路

利用动态规划，设dp[i][j]为以matrix[i][j]为右下角的只包含1的正方形的边长：

• 初始化dp数组：

  • 若matrix[i][0] == '1'，dp[i][0] = 1，否则为0
  • 若matrix[0][j] == '1'，dp[0][j] = 1，否则为0

• 更新dp数组：

  • 若matrix[i][j] == '1'，dp[i][0] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
  • 若matrix[i][j] == '0'，dp[0][j] = 0

利用遍历max记录最长的边长即可，最大面积 = 边长 * 边长

解题代码

func maximalSquare(matrix [][]byte) int {
    m := len(matrix)
    n := len(matrix[0])
    max := 0    // 找到只包含 '1' 的最大正方形边长
    // 声明dp数组
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }
    // 初始化dp数组
    for i := 0; i < m; i++ {    // 初始化dp[i][0]
        if matrix[i][0] == '1' {
            dp[i][0] = 1
            max = 1
        } else {
            dp[i][0] = 0
        }
    }
    for j := 0; j < n; j++ {    // 初始化dp[0][j]
        if matrix[0][j] == '1' {
            dp[0][j] = 1
            max = 1
        } else {
            dp[0][j] = 0
        }
    }
    // 计算dp数组
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if matrix[i][j] == '1' {
                dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
                if dp[i][j] > max {
                    max = dp[i][j]
                }
            } else {
                dp[i][j] = 0
            }
        }
    }

    return max * max  // 面积 = 边长*边长
}

func min(n1, n2, n3 int) int {
    if n1 < n2 {
        if n1 < n3 {
            return n1
        } else {
            return n3
        }
    } else {
        if n2 < n3 {
            return n2
        } else {
            return n3
        }
    }
}

最长公共前缀

最长公共前缀

解题思路

扫描字符串组中的每一列：

• 若当前列上的所有字符相同，就将当前字符加入到公共前缀中去
• 否则，直接返回当前的公共前缀

解题代码

func longestCommonPrefix(strs []string) string {
    var commomPrefix string // 公共前缀
    i := 0  // 字符串的下标
    for i < len(strs[0]) {
        cur := strs[0][i]   // 当前字符
        for j := 1; j < len(strs); j++ {
            if i >= len(strs[j]) || strs[j][i] != cur {
                return commomPrefix
            }
        }
        commomPrefix += string(cur)
        i++
    }
    
    return commomPrefix
}

岛屿的最大面积

岛屿的最大面积

解题思路

将矩阵grid看作是一个图，图中的每一个顶点都有上下左右四条边相连。把1看作是连同分量的顶点，那么计算岛屿的面积就是遍历这个图中所有连通分量所包含的顶点数目：

1. 基于深度优先遍历
2. 基于广度优先遍历

解题代码

1. 深度优先遍历

func maxAreaOfIsland(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    max := 0    // 岛屿最大面积
    var cur int    // 当前岛屿面积
    var dfs func(i, j int)
    dfs = func(i, j int) {      // 从grid[i][j]开始深度优先遍历
        if i < 0 || i >= m || j < 0 || j >= n {     // 超出了边界
            return
        }
        if grid[i][j] == 0 {    // 是海水
            return
        } else {
            cur++   // 当前岛屿的面积+1
            grid[i][j] = 0      // 标0，已经遍历过了
            dfs(i-1, j)     // 遍历上方
            dfs(i+1, j)     // 遍历下方
            dfs(i, j-1)     // 遍历左方
            dfs(i, j+1)     // 遍历右方
        }
    }
    // 对整张图进行深度优先遍历
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                cur = 0
                dfs(i, j)
                if cur > max {
                    max = cur
                }
            }
        }
    }

    return max
}

2. 广度优先遍历

func maxAreaOfIsland(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    max := 0    // 岛屿最大面积
    var bfs func(i, j int) int
    bfs = func(i, j int) int {      // 从grid[i][j]开始广度优先遍历, 返回当前岛屿面积
        var cur int    // 当前岛屿面积
        queue := make([][]int, 0)   // 队列记录待遍历的节点下标(i, j)
        // 起始节点入队
        queue = append(queue, []int{i, j})

        for len(queue) > 0 {    // 队不空时循环
            // 队头出队
            i, j = queue[0][0], queue[0][1]
            queue = queue[1:]
            // 超出了边界
            if i < 0 || i >= m || j < 0 || j >= n {
                continue
            }
            if grid[i][j] == 1 {    // 访问grid[i][j]
                grid[i][j] = 0
                cur++
                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})      // 右方节点入队
            }
        }

        return cur
    }
    // 对整张图进行广度优先遍历
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                cur := bfs(i, j)
                if cur > max {
                    max = cur
                }
            }
        }
    }

    return max
}