【每日打卡】[程序员面试宝典]17.16-按摩师

马谦马谦马谦

615
文章

17
评论

2020年3月24日22:27:32数据结构和算法评论440字数 699阅读2分19秒阅读模式

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/the-masseuse-lcci

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

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

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

二、题解

这道题目和198-打家劫舍几乎完全一样，思路也完全一样，代码都不用做太多更改。

思路：对于第i个用户，有2种策略选择，预约或不预约。

如果预约，那么说明上一个用户不能预约，只能取上上个用户的最优解加上当前用户的预约时长。
如果不预约，最优解就是上一个用户的最优解。

总结出来的状态转移（递推）方程：

\(dp[i] = max(dp[i-1], dp[i-2]+nums[i]])\)

三、代码实现

class Solution {
public:
    int massage(vector<int> &nums) {
        int pprev, prev, output, i;
        output = prev = pprev = 0;

        if (nums.empty()) {
            return 0;
        } else if (nums.size() == 1) {
            return nums[0];
        }

        prev = nums[0];
        for (i = 1; i < nums.size(); i++) {
            output = max(prev, pprev + nums[i]);
            pprev = prev;
            prev = output;
        }

        return output;
    }
};

class Solution {

public:

int massage(vector<int> &nums) {

int pprev, prev, output, i;

output = prev = pprev = 0;

if (nums.empty()) {

return 0;

} else if (nums.size() == 1) {

return nums[0];

}

prev = nums[0];

for (i = 1; i < nums.size(); i++) {

output = max(prev, pprev + nums[i]);

pprev = prev;

prev = output;

}

return output;

}

};

单元测试：

TEST(leetcode, demo) {
    Solution s;
    // leetcode样本数据
    vector<int> v1{1, 2, 3, 1}, v2{2, 7, 9, 3, 1}, v3{2, 1, 4, 5, 3, 1, 1, 3};
    // 特殊数据
    vector<int> v4{1}, v5{1, 2}, v6;

    EXPECT_EQ(s.massage(v1), 4);
    EXPECT_EQ(s.massage(v2), 12);
    EXPECT_EQ(s.massage(v3), 12);

    // 1个元素的数组
    EXPECT_EQ(s.massage(v4), 1);
    // 2个元素的数组
    EXPECT_EQ(s.massage(v5), 2);
    // 空数组
    EXPECT_EQ(s.massage(v6), 0);
}