程序员面试金典17.16-按摩师

原题(来源Leetcode)

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

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

示例 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。

解法

思想

动态规划,为了避免重复计算,可以使用自顶向下+记忆,或者是自底向上。

代码

自顶向下+记忆:

class Solution {
    int[] numsGlo;
    Integer[] dp;
    public int massage(int[] nums) {
        numsGlo = nums;
        dp = new Integer[nums.length];
        return dp(nums.length-1);
    }
    public int dp(int index){
        if(index < 0) return 0;
        if(index == 0) return numsGlo[index];
        if(dp[index]!=null) return dp[index];
        int result = Math.max(dp(index-2)+numsGlo[index],dp(index-1)); 
        dp[index] = result;
        return result;
    }
}

自底向上:(作者:sweetiee)

class Solution {
    public int massage(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return nums[0];
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];
    }
}

自底向上,不需要存储:(作者:sweetiee)

class Solution {
    public int massage(int[] nums) {
        int a = 0, b = 0;
        for (int i = 0; i < nums.length; i++) {
            int c = Math.max(b, a + nums[i]);
            a = b;
            b = c;
        }
        return b;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e7%a8%8b%e5%ba%8f%e5%91%98%e9%9d%a2%e8%af%95%e9%87%91%e5%85%b817-16-%e6%8c%89%e6%91%a9%e5%b8%88/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月23日
下一篇 2020年3月24日

相关推荐

  • leetcode85-最大矩形

    原题 给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例: 输入: [   ["1","0","1","0","0"…

    2020年1月24日
    0200
  • leetcode409-最长回文串

    原题 给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。 在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 注意:假设字符串的长…

    算法 2020年3月19日
    0570
  • leetcode322-零钱兑换

    原题 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 示例 1…

    算法 2020年3月8日
    0150
  • leetcode1014-最佳观光组合

    原题 给定正整数数组 A,A[i] 表示第 i 个观光景点的评分,并且两个景点 i 和 j 之间的距离为 j - i。 一对景点(i < j)组成的观光组合的得分为(A[i]…

    算法 2020年6月17日
    01980
  • leetcode145-二叉树的后序遍历

    原题 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2020年1月10日
    080
  • leetcode173-二叉搜索树迭代器

    原题 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例: BSTIterator iterator…

    2020年1月16日
    060
  • leetcode31-下一个排列

    原题 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1…

    算法 2022年4月13日
    02623
  • leetcode347-前K个高频元素

    原题 给定一个非空的整数数组,返回其中出现频率前 k 高的元素。 示例1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例2: 输入: n…

    算法 2019年12月28日
    0150
  • leetcode160-相交链表

    原题 编写一个程序,找到两个单链表相交的起始节点。 如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入: intersectVal = 8, listA = [4,1,…

    2019年12月14日
    090
  • leetcode16-最接近的三数之和

    原题 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存…

    算法 2020年5月4日
    080

发表回复

登录后才能评论