wy的leetcode刷题记录_Day13

817. 链表组件

今天的每日一题是：817. 链表组件

题目介绍

给定链表头结点 head，该链表上的每个结点都有一个唯一的整型值。同时给定列表 nums，该列表是上述链表中整型值的一个子集。返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。

示例 1：
输入: head = [0,1,2,3], nums = [0,1,3]
输出: 2
解释: 链表中,0 和 1 是相连接的，且nums 中不包含 2，所以 [0, 1] 是 nums 的一个组件，同理 [3] 也是一个组件，故返回 2。

示例 2：
输入: head = [0,1,2,3,4], nums = [0,3,1,4]
输出: 2
解释: 链表中，0 和 1是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。

思路

首先我们分析题目得知在head中最长连续的子串并且要存在nums中，所以我们只需要寻找子串在head中出现的次数就ok。我们需要将nums中的数存在一个hashtable中，因为频繁的查询会增加时间复杂度而hashtable正好有效的解决了这个问题。遍历List我们判断其是否在nums中如果在的话我们置换inSet然后res++，如果不在的话置换inSet这样就可以保证一个符合题目要求的字串开头前的前一个字符是不在nums中的。

代码

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& nums) {
        unordered_set<int> numsSet;
        for (int num : nums) {
            numsSet.emplace(num);
        }
        bool inSet = false;
        int res = 0;
        while (head != nullptr) {
            if (numsSet.count(head->val)) {
                if (!inSet) {
                    inSet = true;
                    res++;
                }
            } else {
                inSet = false;
            }
            head = head->next;
        }
        return res;
    }
};

收获

熟悉了STL的应用，中等难度的模拟问题，题目意思较难理解。

213. 打家劫舍 II

题目介绍

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

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

示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。

思路

这道题与打家劫舍I比起来就是多了一个条件，房屋成环（nums中首尾的房间是相邻的）。根据题意我们就知道了如果我们要偷第一件房子的话我们就不能偷最后一间房子，同理如果我们偷最后一间房子的话我们就不能偷第一间房子。于是我们把情况分为：1.偷第一件房子不偷最后一间房子;2.偷最后一间房子不偷第一间房子。对这俩种情况用打家劫舍I的方法，返回其最大的值。

代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n =nums.size();
        if(n==0)
            return 0;
        if(n==1)
            return nums[0];
        if(n==2)
         return max(nums[0],nums[1]);

         int result1 = robway(nums, 0, nums.size() - 2); // 情况?
         int result2 = robway(nums, 1, nums.size() - 1); // 情况三
         return max(result1,result2);
    }

    int robway(vector<int>& nums,int start,int end)
    {
        vector<int> dp(nums.size(),0);
        dp[start]=nums[start];
        dp[start+1]=max(nums[start],nums[start+1]);
        for(int i=start+2;i<=end;i++)
        {
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);

        }
        return dp[end];
    }
};