wy的leetcode刷题记录_Day73

wy的leetcode刷题记录_Day73

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间：2024-01-09

前言

2707. 字符串中的额外字符

今天的每日一题是：2707. 字符串中的额外字符

题目介绍

给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。

请你采取最优策略分割 s ，使剩下的字符 最少 。

示例 1：
输入：s = “leetscode”, dictionary = [“leet”,“code”,“leetcode”]
输出：1
解释：将 s 分成两个子字符串：下标从 0 到 3 的 “leet” 和下标从 5 到 8 的 “code” 。只有 1
个字符没有使用（下标为 4），所以我们返回 1 。

示例 2： 输入：s = “sayhelloworld”, dictionary =[“hello”,“world”]
输出：3
解释：将 s 分成两个子字符串：下标从 3 到 7 的 “hello” 和下标从 8 到 12 的 “world” 。下标为 0 ，1 和 2 的字符没有使用，所以我们返回 3 。

思路

动态规划：把问题s分解成子字符串s1+一个字符s2的过程，设s长度为n，则s1为n-1：

• 将最后一个字符当作额外字符，那dp[n]=dp[n-1]+1;
• 若最后一个字符s2与s1合并起来后，存在一个以j开始的后缀使得其在dictionary中，那么则可以消去，则dp[n]=min(dp[n],dp[n-j]);

则答案为dp[n]。

代码

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        int n=s.size();
        int m=dictionary.size();
        vector<int> dp(n+1);
        unordered_map<string,int> mpl;
        for(auto s :dictionary)
        {
            mpl[s]++;
        }
        for(int i=1;i<=n;i++)
        {
            dp[i]=dp[i-1]+1;
            for(int j=i-1;j>=0;j--)
            {
                if(mpl.count(s.substr(j,i-j)))
                {
                    dp[i]=min(dp[i],dp[j]);
                }
            }
        }
        return dp[n];
    }   
};

收获

看的答案写的，算是复习动态规划了。

198. 打家劫舍

198. 打家劫舍

题目介绍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

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

示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路

动态规划：很明显的一道动态规划问题：首先确定能划分为很多子问题，从n个房子到k个房子（0——n），而前i个房子偷取的总额由前一次偷取觉得即前俩个房子是否偷取：

• 若偷取第i个房子那么就不能偷取第i-1个房子转化为子问题求前i-2个房子的偷取总额；
• 若不偷取第i个房子那么转化为子问题求前i-1个房子的偷取总额；

最后得出 dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])，且根据递推公式得到我们是从左往右推的，所以是自底向上的遍历，而不是备忘录式，最后返回答案dp[n]。

代码

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

收获

巩固了动态规划