备战秋招60天算法挑战,Day32

2024-09-05 21:44

本文主要是介绍备战秋招60天算法挑战,Day32,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接: https://leetcode.cn/problems/house-robber-ii/

视频题解: https://www.bilibili.com/video/BV1WRYKeKEQE/

LeetCode 213. 打家劫舍 II

题目描述

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

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

举个例子:

输入: nums = [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

视频题解

打家劫舍 II

思路来源

思路来源

知识回顾

动态规划是一种通过将原问题分解为子问题来求解复杂问题的算法思想。它通常用于求解最优化问题,例如最长公共子序列、背包问题等。动态规划的核心思想是将原问题分解为若干个子问题,通过求解子问题的最优解推导出原问题的最优解。可以通过两点来判断一个问题能不能通过动态规划来解,一是该问题是否存在递归结构,二是对应的子问题能否记忆化。动态规划可以通过带备忘录的自上而下的递归自下而上的迭代来分别实现。由于递归需要用到栈来实现,一些语言对递归的深度是有限制的,所以自下而上的迭代是动态规划的最佳实现方式

思路解析

本题是一道经典的动态规划问题,要找到解决动态规划问题的两个突破点:推导出状态转移公式边界条件处理

本题是「198.打家劫舍」的进阶版,他们之间唯一的区别是房子变成了首尾相连,因为第1间房第n间房相连,我们需要考虑要不要偷第1间房

  1. 如果偷第1间房,那么第n间房一定不能偷。这个时候我们可以偷的区间就变成[0,n-1]
  2. 如果不偷第1间房,那么我们可以偷的区间就变成[1,n]

最终就变成了求[0,n-1][1,n]这两个非首尾相连区间能够偷窃到的最高金额,这样就可以复用「198.打家劫舍」的思路。

首先定义dp[n]表示总共有n间房所能偷到的最高金额。

对于非首尾相连的数组nums=[1, 2, 3, 1]其所以可能的打劫路线如下:

根节点到叶子节点就是一条偷盗路线,每个节点表示偷到的总金额,对于上面的例子dp[4] = 4

状态转移公式需要分两种情况讨论:

  • 偷盗路线包含第4间房nums[3]),根据规则这个时候第3间房nums[2])一定是没有被偷的,那么前2间房偷到的最大金额加上第4间房偷到的金额有可能是前4间房偷的最大金额dp[4] = dp[2] + nums[3]
  • 偷盗路线不包含第4间房nums[3]),这个时候前3间房偷到的最大金额有可能也是前4间房偷的最大金额dp[4] = dp[3]

上面两种情况选取最大值就可以得到4间房偷到的最大金额dp[4]=max(dp[2] + nums[3], dp[3]);

扩展到一般情况dp[n]可以分解为dp[n-1]dp[n-2]两个子问题的组合,得到状态转移公式

dp[n] = max{dp[n-2] + nums[n-1], dp[n-1]}

其中dp[n-2] + nums[n-1]表示偷第n间房整条路线可以偷到的最大金额。 dp[n-1]表示不偷第n间房整条路线可以偷到的最大金额。

对于边界条件 dp[0] = 0dp[1] = nums[0]dp[2] = max{nums[0], nums[1]}

C++ 代码

class Solution {
public:int rob(vector<int>& nums) {int nums_len = nums.size();if (nums_len == 0) return 0;if (nums_len == 1) return nums[0];return max(help(nums, 0, nums_len - 1), help(nums, 1, nums_len - 1));}int help(vector<int>& nums, int start, int len) {if (len == 0) {return 0;}if (len == 1) {return nums[start];}vector<int> dp(len + 1, 0);//边界条件dp[1] = nums[start];dp[2] = max(nums[start], nums[start + 1]);for (int i = start + 3; i < start + len + 1; ++i) {//状态转移公式dp[i - start] = max(dp[i - start - 1], dp[i - start - 2] + nums[i - 1]);}return dp[len];}
};

java代码

class Solution {public int rob(int[] nums) {int nums_len = nums.length;if (nums_len == 0) return 0;if (nums_len == 1) return nums[0];return Math.max(help(nums, 0, nums_len - 1), help(nums, 1, nums_len - 1));}public int help(int[] nums, int start, int len) {if (len == 0) {return 0;}if (len == 1) {return nums[start];}int[] dp = new int[len + 1];// 边界条件dp[1] = nums[start];dp[2] = Math.max(nums[start], nums[start + 1]);for (int i = start + 3; i < start + len + 1; ++i) {// 状态转移公式dp[i - start] = Math.max(dp[i - start - 1], dp[i - start - 2] + nums[i - 1]);}return dp[len];}
}

python代码

class Solution:def rob(self, nums: List[int]) -> int:nums_len = len(nums)if nums_len == 0:return 0if nums_len == 1:return nums[0]return max(self.help(nums, 0, nums_len - 1), self.help(nums, 1, nums_len - 1))def help(self, nums: List[int], start: int, length: int) -> int:if length == 0:return 0if length == 1:return nums[start]dp = [0] * (length + 1)# 边界条件dp[1] = nums[start]dp[2] = max(nums[start], nums[start + 1])for i in range(start + 3, start + length + 1):# 状态转移公式dp[i - start] = max(dp[i - start - 1], dp[i - start - 2] + nums[i - 1])return dp[length]

复杂度分析

时间复杂度: 只需要遍历两遍数组nums,所以时间复杂度为O(n)nnums的长度。

空间复杂度: 需要借助一个dp数组,空间复杂度为O(n)nnums的长度。

实现优化

上面的空间复杂度是O(n),其实根据状态转移公式的特点,当前的状态只依赖前面的两个状态,我们可以不使用数组保存所有的状态,使用两个整型变量prenext来实现help函数。

c++代码

class Solution {
public:int rob(vector<int>& nums) {int nums_len = nums.size();if (nums_len == 0) return 0;if (nums_len == 1) return nums[0];return max(help(nums, 0, nums_len - 1), help(nums, 1, nums_len - 1));}int help(vector<int>& nums, int start, int len) {if (len == 0) {return 0;}if (len == 1) {return nums[start];}//边界条件int pre = nums[start];int next = max(nums[start], nums[start + 1]);for (int i = start + 2; i < start + len; ++i) {//状态转移公式int temp = next; next = max(pre + nums[i], next);pre = temp;}return next;}
};

java代码

class Solution {public int rob(int[] nums) {int nums_len = nums.length;if (nums_len == 0) return 0;if (nums_len == 1) return nums[0];return Math.max(help(nums, 0, nums_len - 1), help(nums, 1, nums_len - 1));}public int help(int[] nums, int start, int len) {if (len == 0) {return 0;}if (len == 1) {return nums[start];}// 边界条件int pre = nums[start];int next = Math.max(nums[start], nums[start + 1]);for (int i = start + 2; i < start + len; ++i) {// 状态转移公式int temp = next;next = Math.max(pre + nums[i], next);pre = temp;}return next;}
}

python代码

class Solution:def rob(self, nums: List[int]) -> int:nums_len = len(nums)if nums_len == 0:return 0if nums_len == 1:return nums[0]return max(self.help(nums, 0, nums_len - 1), self.help(nums, 1, nums_len - 1))def help(self, nums: List[int], start: int, length: int) -> int:if length == 0:return 0if length == 1:return nums[start]# 边界条件pre = nums[start]next = max(nums[start], nums[start + 1])for i in range(start + 2, start + length):# 状态转移公式temp = nextnext = max(pre + nums[i], next)pre = tempreturn next

优化后复杂度分析

时间复杂度: 只需要遍历两遍数组nums,所以时间复杂度为O(n)nnums的长度。

空间复杂度: 只借助了几个整型变量,空间复杂度为O(1)

这篇关于备战秋招60天算法挑战,Day32的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1140148

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

跨国公司撤出在华研发中心的启示:中国IT产业的挑战与机遇

近日,IBM中国宣布撤出在华的两大研发中心,这一决定在IT行业引发了广泛的讨论和关注。跨国公司在华研发中心的撤出,不仅对众多IT从业者的职业发展带来了直接的冲击,也引发了人们对全球化背景下中国IT产业竞争力和未来发展方向的深思。面对这一突如其来的变化,我们应如何看待跨国公司的决策?中国IT人才又该如何应对?中国IT产业将何去何从?本文将围绕这些问题展开探讨。 跨国公司撤出的背景与

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码