【算法挨揍日记】day22——面试题 17.16. 按摩师、213. 打家劫舍 II

喜欢ヅ旅行 2024-02-20 11:39 96阅读 0赞

## 面试题 17.16. 按摩师 ##

[面试题 17.16. 按摩师][17.16.]

### 题目描述： ###

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

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

### ![3569707d691340f38002fd8c032a5ce8.png][] 解题思路： ###

> 状态表示：f\[i\]，g\[i\]表示以i为结尾，i预约和i不预约的最长的预约时长
> 
> 状态转移方程：
> 
> f\[i\]=g\[i-1\]+nums\[i\]
> 
> g\[i\]=max(f\[i-1\],g\[i-1\])
> 
> 初始化：
> 
> f\[0\]=nums\[0\],g\[0\]=0
> 
> 填表顺序：左到右
> 
> 返回值：max(f\[n-1\],g\[n-1\])

### 解题代码： ###

class Solution {
    public:
        int massage(vector<int>& nums) {
            int n=nums.size();
            if(n==0)return 0;
            vector<int>f(n,0);
            vector<int>g(n,0);
            f[0]=nums[0];
            for(int i=1;i<n;i++)
            {
                f[i]=g[i-1]+nums[i];
                g[i]=max(f[i-1],g[i-1]);
            }
            return max(f[n-1],g[n-1]);
        }
    };

--------------------

## 213. 打家劫舍 II ##

[213. 打家劫舍 II][213. _ II]

### 题目描述： ###

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 **围成一圈** ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，**如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警** 。

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

![93d32e8034ee48f0839bfa622891ed0e.png][]

### 解题思路： ###

> 本题分为两种情况：
> 
> 一种是选第一个位置
> 
> 一种是不选第一个位置
> 
> 状态表示：
> 
> f\[i\]，g\[i\]表示以i为结尾，i偷和i不偷的最大金额
> 
> 状态转移方程：
> 
> f\[i\]=g\[i-1\]+nums\[i\]
> 
> g\[i\]=max(f\[i-1\],g\[i-1\])
> 
> 初始化：
> 
> f\[0\]=nums\[0\],g\[0\]=0
> 
> 填表顺序：左到右
> 
> 返回值：max(f\[n-1\],g\[n-1\])

### 解题代码; ###

class Solution {
    public:
        
        int rob1(vector<int>& nums,int left,int right) {
            int n=nums.size();
            if(left>right)return 0;
            vector<int>f(n,0);
            vector<int>g(n,0);
            f[left]=nums[left];
            for(int i=left+1;i<=right;i++)
            {
                f[i]=g[i-1]+nums[i];
                g[i]=max(f[i-1],g[i-1]);
            }
            return max(f[right],g[right]);
        }
        int rob(vector<int>& nums)
        {
            int n=nums.size();
            return max(rob1(nums,1,n-1),rob1(nums,2,n-2)+nums[0]);
        }
    };

[17.16.]: https://leetcode.cn/problems/the-masseuse-lcci/
[3569707d691340f38002fd8c032a5ce8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/a043da882292409ca626f4f7e50196c7.png
[213. _ II]: https://leetcode.cn/problems/house-robber-ii/
[93d32e8034ee48f0839bfa622891ed0e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/4f017eb6a99a49fab7e6c8fa30185014.png