Golang每日一练(leetDay0088) 数组的乘积、搜索二维矩阵II

简介: Golang每日一练(leetDay0088) 数组的乘积、搜索二维矩阵II

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 main
import  "fmt"
func productExceptSelf(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    for i := 0; i < n; i++ {
        ans[i] = 1
        for 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 main
import "fmt"
func productExceptSelf(nums []int) []int {
  n := len(nums)
  prefix := make([]int, n)
  suffix := make([]int, n)
  ans := make([]int, n)
  prefix[0] = 1
  for i := 1; i < n; i++ {
    prefix[i] = prefix[i-1] * nums[i-1]
  }
  suffix[n-1] = 1
  for 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 main
import "fmt"
func productExceptSelf(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    ans[0] = 1
    for i := 1; i < n; i++ {
        ans[i] = ans[i-1] * nums[i-1]
    }
    suffix := 1
    for i := n-1; i >= 0; i-- {
        ans[i] *= suffix
        suffix *= 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 main
import "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 main
import "fmt"
func searchMatrix(matrix [][]int, target int) bool {
  m := len(matrix)
  n := len(matrix[0])
  i, j := 0, n-1
  for 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 main
import "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-1
  for left <= right {
    mid := left + (right-left)/2
    row, col := mid/n, mid%n
    if 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)暂停更


目录
相关文章
|
1月前
|
Go
Golang语言之数组(array)快速入门篇
这篇文章是关于Go语言中数组的详细教程,包括数组的定义、遍历、注意事项、多维数组的使用以及相关练习题。
21 5
|
2月前
|
监控 Serverless Go
Golang 开发函数计算问题之Go 语言中切片扩容时需要拷贝原数组中的数据如何解决
Golang 开发函数计算问题之Go 语言中切片扩容时需要拷贝原数组中的数据如何解决
|
5月前
|
程序员 Go
第七章 Golang数组和切片
第七章 Golang数组和切片
43 2
|
5月前
|
Linux 监控 Ubuntu
Linux 终端操作命令(1)
Linux 终端操作命令(1)
91 1
Linux 终端操作命令(1)
|
5月前
|
Go
【Golang】使用泛型对数组进行去重
【2月更文挑战第11天】使用泛型对数组进行去重
63 0
|
5月前
|
Shell Linux 算法
Shell编程——弱数据类型的脚本语言快速入门指南
Shell编程——弱数据类型的脚本语言快速入门指南
82 0
Shell编程——弱数据类型的脚本语言快速入门指南
|
5月前
|
Go Linux Shell
Linux 终端命令之文件浏览(2) more
Linux 终端命令之文件浏览(2) more
57 0
Linux 终端命令之文件浏览(2) more
|
5月前
|
Shell Linux 机器学习/深度学习
Linux 终端操作命令(3)内部命令用法
Linux 终端操作命令(3)内部命令用法
74 0
Linux 终端操作命令(3)内部命令用法
|
5月前
|
Shell 机器学习/深度学习 Linux
Linux 终端操作命令(2)内部命令
Linux 终端操作命令(2)内部命令
50 0
Linux 终端操作命令(2)内部命令
|
5月前
|
C++ 算法 存储
力扣 C++|一题多解之动态规划专题(2)
力扣 C++|一题多解之动态规划专题(2)
59 0
力扣 C++|一题多解之动态规划专题(2)