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) }
输出：
[0 0 1 1 2 2]
[0 1 2]
