目录
73. 矩阵置零 Set Matrix Zeroes 🌟🌟
74. 搜索二维矩阵 Search A 2d-Matrix 🌟🌟
75. 颜色分类 Sort Colors 🌟🌟
🌟 每日一练刷题专栏 🌟
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
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.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
给定一个包含红色、白色和蓝色、共 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.length1 <= n <= 300nums[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)
}
输出：
[0 0 1 1 2 2]
[0 1 2]
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
 | Golang每日一练 专栏 |
 | Python每日一练 专栏 |
 | C/C++每日一练 专栏 |
 | Java每日一练 专栏 |
