LeetCode 按摩师 python

这篇具有很好参考价值的文章主要介绍了LeetCode 按摩师 python。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

 

1.题目描述

2.普通解法(通过部分测试用例)

​编辑

3.动态规划解法

3.题目总结


 

1.题目描述

一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,替按摩师找到最优的预约集合(总预约时间最长),返回总的分钟数。

注意:本题相对原题稍作改动

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 选择 1 号预约和 3 号预约,总时长 = 1 + 3 = 4。
示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 选择 1 号预约、 3 号预约和 5 号预约,总时长 = 2 + 9 + 1 = 12。
示例 3:

输入: [2,1,4,5,3,1,1,3]
输出: 12
解释: 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约,总时长 = 2 + 4 + 3 + 3 = 12。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/the-masseuse-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2.普通解法(通过部分测试用例)

class Solution:
    def massage(self, nums: List[int]) -> int:
        sum = 0
        for i in range(len(nums)):
            tmp = 0
            for j in range(i, len(nums), 2):
                tmp += nums[j]
            if sum<tmp:
                t = tmp
                tmp = sum
                sum = t
        return sum

LeetCode 按摩师 python

 

3.动态规划解法

from typing import List

class Solution:
    def massage(self, nums: List[int]) -> int:
        cur, prev = 0, 0
        for num in nums:
            cur, prev = max(prev + num, cur), cur
        return cur
from typing import List

class Solution:
    def massage(self, nums: List[int]) -> int:
        # 初始化当前最大值cur和前一个最大值prev
        cur, prev = 0, 0
        # 遍历数组
        for num in nums:
            # 计算当前最大值cur,选择第i个数或不选择第i个数
            cur, prev = max(prev + num, cur), cur
            # 上一次的最大值prev变成当前最大值cur
            # 上一次的次大值cur变成当前最大值的前一个最大值prev
        # 返回最终结果cur
        return cur

LeetCode 按摩师 python

3.题目总结

时间复杂度:O(n),其中n为数组的长度。

空间复杂度:O(1),只需要常数级别的空间来存储当前最大值和前一个最大值。

算法思路

1.定义状态:

dp[i]表示前i个数中选择不相邻的数所能得到的最大和。

2.状态转移方程:

对于第i个数,有两种情况,选择或不选择。如果选择第i个数,则不能选择第i-1个数,所以dp[i] = dp[i-2] + nums[i]。如果不选择第i个数,则dp[i] = dp[i-1]。

综合两种情况,可以得到状态转移方程:dp[i] = max(dp[i-2] + nums[i], dp[i-1])。 3.边界条件:dp[0] = 0,dp[1] = nums[0]。

4.最终结果:dp[n],其中n为数组的长度。文章来源地址https://www.toymoban.com/news/detail-477347.html

到了这里,关于LeetCode 按摩师 python的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 多状态动态规划之按摩师

    题目链接选自力扣 : 面试题 17.16. 按摩师 还是一样, 根据给的示例 1 来分析看看 : 进过分析, 一共有这样几个规定 : 相邻预约不能同时接受 可以从任意一个预约开始 不能之前的 最终总的预约时长要最长的 以 i 位置为结尾, 表示从某一个位置预约开始到 i 位置结束时的预约最长

    2024年02月11日
    浏览(34)
  • 【LeetCode题目详解】1281题 整数的各位积和之差 面试题 01.01. 判定字符是否唯一 python题解(作业一二)

    问题描述: 1281. 整数的各位积和之差 给你一个整数 n,请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。 示例 1: 输入:n = 234 输出:15 解释: 各位数之积 = 2 * 3 * 4 = 24 各位数之和 = 2 + 3 + 4 = 9 结果 = 24 - 9 = 15 示例 2: 输入:n = 4421 输出:21 解释:

    2024年02月10日
    浏览(50)
  • 【LeetCode题目详解】(一些双指针的题目)27. 移除元素

    给你一个数组 nums   和一个值 val ,你需要 原地 移除所有数值等于  val   的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组 。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 说明: 为什

    2024年01月22日
    浏览(42)
  • leetcode 哈希表相关题目

    题目:https://leetcode.cn/problems/valid-anagram/description/ 题解:https://leetcode.cn/problems/valid-anagram/solutions/2602947/shu-zu-ha-xi-biao-tong-ji-mei-ge-zi-mu-c-vhh5/ 题目:https://leetcode.cn/problems/intersection-of-two-arrays/description/ 题解:https://leetcode.cn/problems/intersection-of-two-arrays/solutions/2603171/jie-guo-shu-zu-un

    2024年01月21日
    浏览(40)
  • 【LeetCode】丑数题目合辑

    思路 首先,丑数必须是 正整数 ,因此对于 n1 都可以直接返回 false; 对于 n = 1 ,如果 n 能够被 2/3/5 整除,说明它们是丑数。 代码 思路 要得到第 n 个丑数,可以使用 最小堆 实现。 初始化堆为空,首先将最小的丑数 1 加入。每次取出堆顶元素 x ,则 x 是堆中最小的丑数,

    2024年02月13日
    浏览(48)
  • 【LeetCode】动态规划类题目详解

    所有题目均来自于LeetCode,刷题代码使用的Python3版本 如果某一个问题有重叠的子问题,则使用动态规划进行求解是最有效的。 动态规划中每一个状态一定是由上一个状态推导出来的,这一点区别于贪心算法 动态规划五部曲 确定dp数组以及下标的含义 确定递推公式 dp数组如何

    2024年04月11日
    浏览(49)
  • 关于链表的题目—leetcode

    问题描述: 给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。 返回删除后的链表的头节点。 示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 - 1 - 9. 示例 2: 输入

    2023年04月25日
    浏览(36)
  • LeetCode-题目整理【3】:买卖股票的最佳时机

    买卖股票的最佳时机 都是求最大利润,但是在没有限制,如121和122,动态规划稍微复杂一些,建议不用,到最后两道难题,题目有限制,使用动态规划通过求解子问题的最优解来逐步求解原问题的最优解。 买卖股票的最佳时机 给定一个数组 prices ,它的第 i 个元素 prices[i]

    2024年01月23日
    浏览(66)
  • 【刷题笔记8.10】LeetCode题目:有效括号

    给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号 首先,解决此题,我们要明确使用 栈

    2024年02月13日
    浏览(37)
  • 【刷题笔记8.8】LeetCode题目:两数之和

    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是, 数组中同一个元素在答案里不能重复出现 。 你可以按任意顺序返回答案。 解法1:使用HashMap对数

    2024年02月13日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包