安达网站制作dede网站文档不能更新

当前位置： 首页 > news >正文

安达网站制作,dede网站文档不能更新,长沙公司网站建设,定制v教程免费题一.按摩师#xff08;LeetCode#xff09; 题目描述 一个有名的按摩师会收到源源不断的预约请求#xff0c;每个预约都可以选择接或不接。在每次预约服务之间要有休息时间#xff0c;因此她不能接受相邻的预约。给定一个预约请求序列#xff0c;替按摩师找到最优的预约集…题一.按摩师LeetCode 题目描述 一个有名的按摩师会收到源源不断的预约请求每个预约都可以选择接或不接。在每次预约服务之间要有休息时间因此她不能接受相邻的预约。给定一个预约请求序列替按摩师找到最优的预约集合总预约时间最长返回总的分钟数。 示例 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。 题目分析 每一个nums[i]都有两种状态即选择与不选择且这两种状态对后续有影响。因此可以定义两个dp表。f[i]表示到达i处nums[i]必选情况下预约时长最大值g[i]表示到达i处nums[i]不选情况下预约时长最大值。 可以得到状态转移方程f[i] g[i - 1] nums[i]g[i] max(f[i - 1], g[i - 1]) 然后解决一下初始化问题f[0] nums[0], g[0] 0。 题解 class Solution { public:int massage(vectorint nums){//f[i]表示到达i处nums[i]必选情况下预约时长最大值//g[i]表示到达i处nums[i]不选情况下预约时长最大值int n nums.size();vectorint f(n), g(n);if (n 0) return 0;f[0] nums[0], g[0] 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]);} }; 题二.打家劫舍ⅠLeetCode 题目描述 你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 示例 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 。 题解  class Solution{ public:int rob(vectorint nums){int n nums.size();vectorint f(n), g(n);if (n 0) return 0;f[0] nums[0], g[0] 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]);} }; 题三.打家劫舍ⅡLeetCode 题目描述 你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。 示例 1 输入nums [2,3,2]输出3解释你不能先偷窃 1 号房屋金额 2然后偷窃 3 号房屋金额 2, 因为他们是相邻的。 示例 2 输入nums [1,2,3,1]输出4解释你可以先偷窃 1 号房屋金额 1然后偷窃 3 号房屋金额 3。偷窃到的最高金额 1 3 4 。 示例 3 输入nums [1,2,3]输出3 题目分析 此题和上题的不同仅在于此题是环形的即nums[0]的情况会影响到nums[n-1]。因此我们先考虑nums[0]的情况a.偷 —考虑[2,n-2]位置上的线性结构  b.不偷[1,n-1]的线性结构。将前一题的rob函数稍加修改即可。 题解  class Solution{ public:int rob1(vectorint nums,int left,int right){if (left right) return 0;int n nums.size();vectorint f(n), g(n);f[left] nums[left], g[0] 0;for (int i left; 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 rob2(vectorint nums){//将环形结构变形//第一个位置 a.偷 —考虑[2,n-2]位置上的线性结构 b.不偷[1,n-1]的线性结构int n nums.size();return max(nums[0] rob1(nums, 2, n - 2), rob1(nums, 1, n - 1));} }; 题四.删除并获得点数 (LeetCode 题目描述 给你一个整数数组 nums 你可以对它进行一些操作。 每次操作中选择任意一个 nums[i] 删除它并获得 nums[i] 的点数。之后你必须删除 所有 等于 nums[i] - 1 和 nums[i] 1 的元素。 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。 示例 1 输入nums [3,4,2]输出6解释 删除 4 获得 4 个点数因此 3 也被删除。 之后删除 2 获得 2 个点数。总共获得 6 个点数。 示例 2 输入nums [2,2,3,3,3,4]输出9解释 删除 3 获得 3 个点数接着要删除两个 2 和 4 。 之后再次删除 3 获得 3 个点数再次删除 3 获得 3 个点数。总共获得 9 个点数。 提示 1 nums.length 2 * 104 1 nums[i] 104 题目分析  尝试将未见过的问题向做过的模式转换 容易想到如果是一串数值连续的序列选择了i则i-1和i1则无法选择。因此我们可以将序列中数值相等的合并示例二的序列转化成 [22,333,4]。我们可以发现跟打家劫舍有点像。但是若是数值出现了中断如 [2,2,3,3,3,5]先转化成 [22,333,5]我们发现取“3”只妨碍我们取“2”、“4”并不妨碍我们取“5”。 因此我们做如下需要预处理。 int arr[N] { 0 }; for (auto i : nums) arr[i] i; 题解  class Solution{ public:int deleteAndEarn(vectorint nums){const int N 10000 5;int arr[N] { 0 };for (auto i : nums) arr[i] i;//在arr数组上进行“打家劫舍”vectorint f(N);auto g f;for (int i 1; i N; i){f[i] g[i - 1] arr[i];g[i] max(f[i - 1], g[i - 1]);}return max(f[N - 2], g[N - 1]);} }; 题五.粉刷房子 LeetCode 题目描述 假如有一排房子共 n 个每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。 当然因为市场上不同颜色油漆的价格不同所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。 例如costs[0][0] 表示第 0 号房子粉刷成红色的成本花费costs[1][2] 表示第 1 号房子粉刷成绿色的花费以此类推。 请计算出粉刷完所有房子最少的花费成本。 示例 1 输入: costs [[17,2,17],[16,16,5],[14,3,19]]输出: 10解释: 将 0 号房子粉刷成蓝色1 号房子粉刷成绿色2 号房子粉刷成蓝色。 最少花费: 2 5 3 10。 示例 2 输入: costs [[7,6,2]]输出: 2 题目分析 costs[i][j]表示第i号房粉刷成对应颜色的花费j 0,1,2。由于经验我们先设dp[i]表示粉刷到第i套房时的最小花费。但是由于其粉刷的颜色会对后续粉刷产生影响因此我们需要考虑颜色。因此我们创建一个二维dp表。 dp[i][0]粉刷成红色时的最小花费dp[i][1]第i套房粉刷成蓝色时的最小花费dp[i][2]第i套房粉刷成绿色时的最小花费。 题解 class Solution1 { public:int minCost(vectorvectorint costs) {int ncosts.size();vectorvectorint dp(n, vectorint(3,0));for(int i0;i3;i){dp[0][i]costs[0][i];}for(int i1;in;i){dp[i][0]min(dp[i-1][1],dp[i-1][2])costs[i][0];dp[i][1]min(dp[i-1][0],dp[i-1][2])costs[i][1];dp[i][2]min(dp[i-1][0],dp[i-1][1])costs[i][2];}return min(min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);} }; 我们也可以采用虚拟节点的方法进行优化 class Solution2 { public:int minCost(vectorvectorint costs){int n costs.size();vectorvectorint dp(n 1, vectorint(3,0));//虚拟节点for (int i 1; i n; i){dp[i][0] min(dp[i - 1][1], dp[i - 1][2]) costs[i - 1][0];dp[i][1] min(dp[i - 1][0], dp[i - 1][2]) costs[i - 1][1];dp[i][2] min(dp[i - 1][1], dp[i - 1][0]) costs[i - 1][2];}return min(min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);} };