目录

238. 除自身以外数组的乘积 Product of Array Except Self  🌟🌟

240. 搜索二维矩阵 II Search A 2d Matrix ii  🌟🌟

🌟 每日一练刷题专栏 🌟

Rust每日一练 专栏

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

---

238. 除自身以外数组的乘积 Product of Array Except Self

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

代码1： 暴力循环

package mainimport 	"fmt"func productExceptSelf(nums []int) []int {n := len(nums)ans := make([]int, n)for i := 0; i < n; i++ {ans[i] = 1for j := 0; j < n; j++ {if j != i {ans[i] *= nums[j]}}}return ans
}func main() {nums := []int{1,2,3,4}fmt.Println(productExceptSelf(nums))nums = []int{-1,1,0,-3,3}fmt.Println(productExceptSelf(nums))
}

代码2： 前缀积和后缀积

package mainimport "fmt"func productExceptSelf(nums []int) []int {n := len(nums)prefix := make([]int, n)suffix := make([]int, n)ans := make([]int, n)prefix[0] = 1for i := 1; i < n; i++ {prefix[i] = prefix[i-1] * nums[i-1]}suffix[n-1] = 1for i := n - 2; i >= 0; i-- {suffix[i] = suffix[i+1] * nums[i+1]}for i := 0; i < n; i++ {ans[i] = prefix[i] * suffix[i]}return ans
}func main() {nums := []int{1, 2, 3, 4}fmt.Println(productExceptSelf(nums))nums = []int{-1, 1, 0, -3, 3}fmt.Println(productExceptSelf(nums))
}

代码3： 优化掉前缀数据的空间

package mainimport "fmt"func productExceptSelf(nums []int) []int {n := len(nums)ans := make([]int, n)ans[0] = 1for i := 1; i < n; i++ {ans[i] = ans[i-1] * nums[i-1]}suffix := 1for i := n-1; i >= 0; i-- {ans[i] *= suffixsuffix *= nums[i]}return ans
}func main() {nums := []int{1, 2, 3, 4}fmt.Println(productExceptSelf(nums))nums = []int{-1, 1, 0, -3, 3}fmt.Println(productExceptSelf(nums))
}

输出：

[24 12 8 6]
[0 0 9 0 0]

---

240. 搜索二维矩阵 II Search A 2d Matrix ii

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10^9 <= matrix[i][j] <= 10^9
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -10^9 <= target <= 10^9

相关题目：

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

代码1： 暴力法

package mainimport "fmt"func searchMatrix(matrix [][]int, target int) bool {m := len(matrix)n := len(matrix[0])for i := 0; i < m; i++ {for j := 0; j < n; j++ {if matrix[i][j] == target {return true}}}return false
}func main() {matrix := [][]int{{1, 4, 7, 11, 15},{2, 5, 8, 12, 19},{3, 6, 9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}}fmt.Println(searchMatrix(matrix, 5))fmt.Println(searchMatrix(matrix, 20))
}

代码2： 缩小搜索范围

package mainimport "fmt"func searchMatrix(matrix [][]int, target int) bool {m := len(matrix)n := len(matrix[0])i, j := 0, n-1for i < m && j >= 0 {if matrix[i][j] == target {return true} else if matrix[i][j] < target {i++} else {j--}}return false
}func main() {matrix := [][]int{{1, 4, 7, 11, 15},{2, 5, 8, 12, 19},{3, 6, 9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}}fmt.Println(searchMatrix(matrix, 5))fmt.Println(searchMatrix(matrix, 20))
}

代码3： 二分查找

package mainimport "fmt"func searchMatrix(matrix [][]int, target int) bool {m, n := len(matrix), len(matrix[0])if m == 0 || n == 0 {return false}left, right := 0, m*n-1for left <= right {mid := left + (right-left)/2row, col := mid/n, mid%nif matrix[row][col] == target {return true} else if matrix[row][col] < target {left = mid + 1} else {right = mid - 1}}return false
}func main() {matrix := [][]int{{1, 4, 7, 11, 15},{2, 5, 8, 12, 19},{3, 6, 9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}}fmt.Println(searchMatrix(matrix, 5))fmt.Println(searchMatrix(matrix, 20))
}

输出：

true
false

---

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/ 

	Rust每日一练 专栏 （2023.5.16~）更新中...
	Golang每日一练 专栏 （2023.3.11~）更新中...
	Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更
	C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更
	Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更