来源：力扣（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;
    }
};

单元测试：

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);
}

头一回打败全部打败100%（其实是新题提交的人太少了）：

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/compress-string-lcci

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

一、题目描述

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

示例1：

• 输入："aabcccccaaa"
• 输出："a2b1c5a3"

示例2：

• 输入："abbccd"
• 输出："abbccd"
• 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。

提示：字符串长度在[0, 50000]范围内。

二、题解

一道很简单的字符串处理题型，思路：

1. 使用一个计数器保存每个重复字符的个数。
2. 遇到相同字符，计数加一。
3. 遇到不同字符，把前面的字符和计数加到输出字符串末尾，计数器归零。

三、代码

class Solution {
public:
    string compressString(string S) {
        char ch;
        int i, cnt;
        string output;
        stringstream ss;

        if (S.size() <= 1)
            return S;

        cnt = 1;
        ch = S[0];
        for (i = 1; i < S.size(); i++) {
            if (S[i] == ch) {
                cnt++;
            } else {
                // 压入到字符串流
                ss << ch << cnt;
                // 重新计数
                cnt = 1;
                ch = S[i];
            }
        }
        // 最后一个字符和计数也放到字符串流里面去
        ss << ch << cnt;
        // 打印到输出字符串
        ss >> output;

        return output.size() < S.size() ? output : S;
    }
};