当前位置： 首页 > article >正文

golang LeetCode 热题 100(动态规划)-更新中

article 2024/12/25 6:30:18

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
 

提示：

1 <= n <= 45

dp

func climbStairs(n int) int {
    if n==0{
        return 0
    }
    if n==1||n==2{
        return n
    }
    dp:=make([]int,n+1,n+1)
    dp[1]=1
    dp[2]=2
    for i:=3;i<=n;i++{
        dp[i]=dp[i-1]+dp[i-2]
    }
    return dp[n]
}

杨辉三角形

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。在这里插入图片描述

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:

输入: numRows = 1
输出: [[1]]
 

提示:

1 <= numRows <= 30

func generate(numRows int) [][]int {
    result:=[][]int{}
    for i:=0;i<numRows;i++{
        result=append(result,[]int{})
        for j:=0;j<=i;j++{
            if j==0{
                result[i]=append(result[i],1)
            }else if i==j{
                result[i]=append(result[i],1)
            }else{
                result[i]=append(result[i],result[i-1][j]+result[i-1][j-1])
            }
        }
    }
    return result
}

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

func rob(nums []int) int {
    if len(nums)==0{
        return 0
    }
    if len(nums)==1{
        return nums[0]
    }
    dp:=make([]int,len(nums),len(nums))
    dp[0]=nums[0]
    dp[1]=max(nums[1],nums[0])
    for i:=2;i<len(nums);i++{
        dp[i]=max(dp[i-2]+nums[i],dp[i-1])
    }
    return dp[len(nums)-1]
}
func max(i,j int)int{
    if i>j{
        return i
    }else{
        return j
    }
}

完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4
示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9
 
提示：

1 <= n <= 104

func numSquares(n int) int {
    dp:=make([]int,n+1,n+1)
    nums:=[]int{}
    for i:=0;i<n+1;i++{
        dp[i]=math.MaxInt32
    }
    for i:=1;i*i<=n;i++{
        dp[i*i]=1
        nums=append(nums,i*i)
    }
    for i:=1;i<=n;i++{
        if dp[i]==math.MaxInt32{
            for _,value:=range nums{
                if i-value>0{
                    dp[i]=min(dp[i],dp[i-value]+1)
                }
            }
        }
    }
    return dp[n]
}

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0
 

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

func wordBreak(s string, wordDict []string) bool {
    mp:=make(map[string]bool)
    for _,w:=range wordDict{
        mp[w]=true
    }
    dp:=make([]bool,len(s)+1)
    dp[0]=true
    for i:=0;i<=len(s);i++{
        for j:=0;j<i;j++{
            if dp[j]&&mp[s[j:i]]{
                dp[i]=true
                break
            }
        }
    }
    return dp[len(s)]
}

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列
。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1
 

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 10^4

func lengthOfLIS(nums []int) int {
    ans:=1
    dp:=make([]int,len(nums)+1,len(nums)+1)
    for i:=0;i<len(nums);i++{
        dp[i]=1
    }
    for i:=1;i<len(nums);i++{
        for j:=0;j<i;j++{
            if nums[i]>nums[j]{
                dp[i]=max(dp[i],dp[j]+1)
                if dp[i]>ans{
                    ans=dp[i]
                }
            }
        }
    }
    return ans
}

乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续
子数组
（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 

提示:

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何子数组的乘积都 保证 是一个 32-位 整数

暴力172/190

func maxProduct(nums []int) int {
    ans:=math.MinInt32
    for i:=0;i<len(nums);i++{
        for j:=i+1;j<len(nums);j++{
            tmp:=1
            for k:=i;k<=j;k++{
                tmp*=nums[k]
                if tmp>ans{
                    ans=tmp
                }
            }
        }
    }
    return ans
}

官方题解

有点难懂，根据官方题解整一个带数组的

func maxProduct(nums []int) int {
    maxF,minF,ans:=nums[0],nums[0],nums[0]
    for i:=1;i<len(nums);i++{
        mx,mn:=maxF,minF
        maxF=max(mx*nums[i],max(nums[i],mn*nums[i]))
        minF=min(mn*nums[i],min(nums[i],mx*nums[i]))
        if minF<(-1<<31){
            minF=nums[i]
        }
        ans=max(maxF,ans)
    }
    return ans
}

dp数组

这样就容易看懂了，两个数组，一个存储以当前位置结尾的最大值，一个存储以当前位置结尾的最小值，两个数组主要是考虑到负负得正，最大的乘积有三种情况：当前数是正数上一个数的的dp也是正数，当前数是负数上一个数的dp也是负数，当前值最大。

func maxProduct(nums []int) int {
    maxF:=make([]int,len(nums),len(nums))
    minF:=make([]int,len(nums),len(nums))
    for i:=0;i<len(nums);i++{
        maxF[i]=nums[i]
        minF[i]=nums[i]
    }
    for i:=1;i<len(nums);i++{
        maxF[i]=max(maxF[i-1]*nums[i],max(nums[i],minF[i-1]*nums[i]))
        minF[i]=min(minF[i-1]*nums[i],min(nums[i],maxF[i-1]*nums[i]))
        if minF[i]<(-1<<31){
            minF[i]=nums[i]
        }
    }
    ans:=maxF[0]
    for i:=0;i<len(nums);i++{
        ans=max(ans,maxF[i])
    }
    return ans
}

分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
 

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

求和+递归37/144

func searchEqual(nums []int,start int,end int,total int)bool{
    if start>end||total<0{
        return false
    }
    if total==0{
        return true
    }
    if searchEqual(nums,start+1,end,total){
        return true
    }
    if total-nums[start]<0{
        return false
    }
    if total-nums[start]>=0&&searchEqual(nums,start+1,end,total-nums[start]){
        return true
    }
    return false
}
func canPartition(nums []int) bool {
    if nums==nil||len(nums)==0{
        return true
    }
    if len(nums)==1{
        return false
    }
    total:=0
    for i:=0;i<len(nums);i++{
        total+=nums[i]
    }
    if total%2!=0{
        return false
    }
    return searchEqual(nums,0,len(nums)-1,total/2)
}

二维dp

func canPartition(nums []int) bool {
    n:=len(nums)
    if n<2{
        return false
    }
    sum,max:=0,0
    for _,v:=range nums{
        sum+=v
        if v>max{
            max=v
        }
    }
    if sum%2!=0{
        return false
    }
    target:=sum/2
    if max>target{
        return false
    }
    dp:=make([][]bool,n)
    for i:=range dp{
        dp[i]=make([]bool,target+1)
    }
    for i:=0;i<n;i++{
        dp[i][0]=true
    }
    dp[0][nums[0]]=true
    for i:=1;i<n;i++{
        v:=nums[i]
        for j:=1;j<=target;j++{
            if j>=v{
                dp[i][j]=dp[i-1][j]||dp[i-1][j-v]
            }else{
                dp[i][j]=dp[i-1][j]
            }
        }
    }
    return dp[n-1][target]
}

优化一些我的暴力

func searchEqual(nums []int,start int,end int,total int)bool{
    if start>end||total<0{
        return false
    }
    if total==0{
        return true
    }
    if searchEqual(nums,start+1,end,total){
        return true
    }
    if total-nums[start]<0{
        return false
    }
    if total-nums[start]>=0&&searchEqual(nums,start+1,end,total-nums[start]){
        return true
    }
    return false
}
func canPartition(nums []int) bool {
    if nums==nil||len(nums)==0{
        return true
    }
    if len(nums)==1{
        return false
    }
    total:=0
    max:=0
    for i:=0;i<len(nums);i++{
        total+=nums[i]
        if nums[i]<max{
            max=nums[i]
        }
    }
    if total%2!=0{
        return false
    }
    if max>total/2{
        return false
    }
    if max==total/2{
        return true
    }
    return searchEqual(nums,0,len(nums)-1,total/2)
}

还是没过


http://www.kler.cn/a/450358.html

相关文章：

  • 无人设备遥控器之定向天线篇
  • 信创源代码加密的答案：信创沙箱
  • openssl交叉编译（这次基本上正规了）
  • Android自定义吐司三
  • 漏洞检测工具：HOST头部攻击
  • LeetCode 343.整数拆分
  • Redis大Key问题全解析
  • 鸿蒙项目云捐助第二十讲云捐助项目物联网IOT的使用
  • python11-函数
  • NS3学习——tcpVegas算法代码详解（1）
  • 基底展开（Expansion in a Basis）：概念、推导与应用 (中英双语)
  • Java 并发流程工具的实战探索
  • 帧缓存的分配
  • shardingsphere分库分表项目实践3-分库分表算法原理
  • 并发编程（19）——引用计数型无锁栈
  • 【UI自动化】从WebDriver看Selenium与Appium的底层关联
  • 【python 逆向分析某有道翻译】分析有道翻译公开的密文内容，webpack类型，全程扣代码，最后实现接口调用翻译，仅供学习参考
  • SQL面试题——奖金瓜分问题
  • ChatGPT与Postman协作完成接口测试（一）
  • 处理字体图标、js、html及其他资源
  • 精读 84页华为BLM战略规划方法论
  • 概率论得学习和整理32： 用EXCEL描述正态分布，用δ求累计概率，以及已知概率求X的区间
  • css一道光闪过动效
  • 鸿蒙开发-ArkTS的ContainerSpan组件
  • 二进制部署k8s
  • Vite +Vue3打包生产环境去除项目中的console.log