Golang每日一练(leetDay0025) 矩阵置零、搜索二维矩阵、颜色分类-阿里云开发者社区

Golang每日一练(leetDay0025) 矩阵置零、搜索二维矩阵、颜色分类

2024-01-30 45

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Golang每日一练(leetDay0025) 矩阵置零、搜索二维矩阵、颜色分类

73. 矩阵置零 Set Matrix Zeroes

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]

输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

进阶：

一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

代码1：

package main
import (
  "fmt"
)
func setZeroes(matrix [][]int) {
  m, n := len(matrix), len(matrix[0])
  row, col := make([]bool, m), make([]bool, n)
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if matrix[i][j] == 0 {
        row[i], col[j] = true, true
      }
    }
  }
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if row[i] || col[j] {
        matrix[i][j] = 0
      }
    }
  }
}
func main() {
  matrix := [][]int{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}}
  setZeroes(matrix)
  fmt.Println(matrix)
  matrix = [][]int{{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}}
  setZeroes(matrix)
  fmt.Println(matrix)
}

输出：

[[1 0 1] [0 0 0] [1 0 1]]

[[0 0 0 0] [0 4 5 0] [0 3 1 0]]

代码2：

package main
import (
  "fmt"
)
func setZeroes(matrix [][]int) {
  m, n := len(matrix), len(matrix[0])
  row0, col0 := false, false
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if matrix[i][j] == 0 {
        if i == 0 {
          row0 = true
        }
        if j == 0 {
          col0 = true
        }
        matrix[0][j], matrix[i][0] = 0, 0
      }
    }
  }
  for i := 1; i < m; i++ {
    for j := 1; j < n; j++ {
      if matrix[i][0] == 0 || matrix[0][j] == 0 {
        matrix[i][j] = 0
      }
    }
  }
  if row0 {
    for j := 0; j < n; j++ {
      matrix[0][j] = 0
    }
  }
  if col0 {
    for i := 0; i < m; i++ {
      matrix[i][0] = 0
    }
  }
}
func main() {
  matrix := [][]int{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}}
  setZeroes(matrix)
  fmt.Println(matrix)
  matrix = [][]int{{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}}
  setZeroes(matrix)
  fmt.Println(matrix)
}

74. 搜索二维矩阵 Search A 2d-Matrix

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4

代码1：

package main
import (
  "fmt"
)
func searchMatrix(matrix [][]int, target int) bool {
  m, n := len(matrix), len(matrix[0])
  l, r := 0, m*n-1
  for l <= r {
    mid := (l + r) >> 1
    if matrix[mid/n][mid%n] == target {
      return true
    } else if matrix[mid/n][mid%n] < target {
      l = mid + 1
    } else {
      r = mid - 1
    }
  }
  return false
}
func main() {
  matrix := [][]int{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}}
  fmt.Println(searchMatrix(matrix, 3))
  fmt.Println(searchMatrix(matrix, 13))
}

输出：

true

false

代码2：

package main
import (
  "fmt"
)
func searchMatrix(matrix [][]int, target int) bool {
  m, n := len(matrix), len(matrix[0])
  l, r := 0, m-1
  for l <= r {
    mid := (l + r) >> 1
    if matrix[mid][0] == target {
      return true
    } else if matrix[mid][0] < target {
      l = mid + 1
    } else {
      r = mid - 1
    }
  }
  if r < 0 {
    return false
  }
  row := r
  l, r = 0, n-1
  for l <= r {
    mid := (l + r) >> 1
    if matrix[row][mid] == target {
      return true
    } else if matrix[row][mid] < target {
      l = mid + 1
    } else {
      r = mid - 1
    }
  }
  return false
}
func main() {
  matrix := [][]int{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}}
  fmt.Println(searchMatrix(matrix, 3))
  fmt.Println(searchMatrix(matrix, 13))
}

75. 颜色分类 Sort Colors

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]

输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]

输出：[0,1,2]

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

进阶：

你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？

代码1：

package main
import (
  "fmt"
)
func sortColors(nums []int) {
  count := make([]int, 3)
  for _, num := range nums {
    count[num]++
  }
  index := 0
  for i := 0; i < 3; i++ {
    for j := 0; j < count[i]; j++ {
      nums[index] = i
      index++
    }
  }
}
func main() {
  nums := []int{2, 0, 2, 1, 1, 0}
  sortColors(nums)
  fmt.Println(nums)
  nums = []int{2, 0, 1}
  sortColors(nums)
  fmt.Println(nums)
}

代码2：

package main
import (
  "fmt"
)
func sortColors(nums []int) {
  index := 0
  for i := 0; i < len(nums); i++ {
    if nums[i] == 0 {
      nums[i], nums[index] = nums[index], nums[i]
      index++
    }
  }
  for i := index; i < len(nums); i++ {
    if nums[i] == 1 {
      nums[i], nums[index] = nums[index], nums[i]
      index++
    }
  }
}
func main() {
  nums := []int{2, 0, 2, 1, 1, 0}
  sortColors(nums)
  fmt.Println(nums)
  nums = []int{2, 0, 1}
  sortColors(nums)
  fmt.Println(nums)
}

代码3：

package main
import (
  "fmt"
)
func sortColors(nums []int) {
  left, right := 0, len(nums)-1
  for i := 0; i <= right; i++ {
    if nums[i] == 0 {
      nums[i], nums[left] = nums[left], nums[i]
      left++
    } else if nums[i] == 2 {
      nums[i], nums[right] = nums[right], nums[i]
      right--
      i--
    }
  }
}
func main() {
  nums := []int{2, 0, 2, 1, 1, 0}
  sortColors(nums)
  fmt.Println(nums)
  nums = []int{2, 0, 1}
  sortColors(nums)
  fmt.Println(nums)
}