目录
73. 矩阵置零 Set Matrix Zeroes
m x n示例 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.lengthn == matrix[0].length1 <= 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.lengthn == matrix[i].length1 <= 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
nnums，原地012必须在不使用库的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.length1 <= n <= 300nums[i]012进阶：
- 你可以不使用代码库中的排序函数来解决这道题吗？
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
代码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)
}
输出：
[0 0 1 1 2 2]
[0 1 2]
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！