JAVA算法：House Robber IIIIII JAVA版本解题

2023-11-10 13:58
文章标签 java 算法 版本 解题 house robber iiiiii

本文主要是介绍JAVA算法：House Robber IIIIII JAVA版本解题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

JAVA算法：House Robber I&II&III JAVA版本解题

LeetCode198. House Robber https://leetcode.com/problems/house-robber/

LeetCode 213. House Robber II https://leetcode.com/problems/house-robber-ii/

LeetCode 337. House Robber III https://leetcode.com/problems/house-robber-iii/

 

LeetCode 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 。

 

LeetCode 213 题目的描述

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

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

示例 1:

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

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

LeetCode 337 题目描述

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]3/ \2   3\   \ 3   1输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]3/ \4   5/ \   \ 1   3   1输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

这三个题目之间的区别和联系：

198题目是基础，描述的房屋是直线型；

213题目描述的房屋是圆形，收尾相接。所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。

337题目描述的房屋是树形结构。

算法设计

198题目的两种解法

public static int rob(int[] nums) {// 如果数组的长度小于或者等于1的情况：数组中没有元素，则返回0；数组中只有一个元素时，就返回该元素的值。if (nums.length <= 1)return nums.length == 0 ? 0 : nums[0];// last表示上一次的最大值，初始时将数组中的第一个元素赋值给lastint last = nums[0];// now表示当前的最大值，初始时要决定是从数组中的第一个元素开始，还是第二个元素开始。int now = Math.max(nums[1], nums[0]);for (int i = 2; i < nums.length; i++) {// 把现在的now暂存起来int tmp = now;// 找到新的now最大值now = Math.max(last + nums[i], now);// 找到之后，由于有了新的now，那么暂存的now就变成了lastlast = tmp;}return now;
}

动态规划求解

public static int rob2(int[] nums) {if (nums == null || nums.length == 0) {return 0;}if (nums.length == 1) {return nums[0];}if (nums.length == 2) {return Math.max(nums[0], nums[1]);}int dp[] = new int[nums.length];dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for (int i = 2; i < nums.length; i++) {dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);}return dp[nums.length - 1];
}

213题目的求解

package com.bean.algorithmexec;public class HouseRobberII {public static int rob(int[] nums) {if (nums.length == 0)return 0;if (nums.length == 1)return nums[0];int N = nums.length;int[] dp = new int[2 * N];dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for (int i = 2; i < 2 * N; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i >= N ? i - N : i]);}return dp[2 * N - 1] - dp[N - 1];}public static void main(String[] args) {// TODO Auto-generated method stubint[] nums = new int[] { 1, 2, 3, 1 };int result = rob(nums);System.out.println("RESULT = " + result);}}

程序运行结果：

RESULT = 4

337题目求解

题目为：有很多互相连接的房间，这些房间正好连成一棵二叉树的样子，小偷需要从这棵树的根结点房间出发开始偷东西。为了不被抓住，小偷不能偷相连的两个房间。

于是，有这么两个要求：

  1. 如果当前结点的父结点没有被偷，那么当前结点可偷可不偷
  2. 如果当前结点的父结点被偷了，那么当前结点不可偷

所以，当从根结点判断开始的时候，有：

  1. 如果偷当前结点，那么下面能偷的只能是自己的孙子结点
  2. 如果不偷当前结点，那么下面可以偷自己的孩子结点

代码如下：

public static int rob(TreeNode node) {if (node == null) return 0;int max = rob(node.left) + rob(node.right);int m = node.val;if (node.left != null) {m += rob(node.left.left) + rob(node.left.right);}if (node.right != null) {m += rob(node.right.left) + rob(node.right.right);}max = Math.max(max, m);return max;
}

在这种方法中可以看到，从结点 node 有两条线，分别是走向 node 的子结点和孙子结点，这就导致一个问题：会产生重复计算。比如，对于从 node 结点到它的孙子结点，可以有两种方式：node -> 孙子和node -> 孩子 -> 孩子。从两条路大到达同一结点，就是说会从两个递归函数分别进入 node 的孙子结点，那么势必会计算两次这个结点的解。

所以需要采取一定的措施，使得重复进入同一结点的时候避免重复计算，即使用缓存：

public static int rob(TreeNode root) {return rob(root, new HashMap<>());
}
private static int rob(TreeNode node, Map<TreeNode, Integer> saved) {if (node == null) return 0;if (saved.containsKey(node)) return saved.get(node);int max = rob(node.left, saved) + rob(node.right, saved);int m = node.val;if (node.left != null) {m += rob(node.left.left, saved) + rob(node.left.right, saved);}if (node.right != null) {m += rob(node.right.left, saved) + rob(node.right.right, saved);}max = Math.max(max, m);saved.put(node, max);return max;
}

使用一个 HashMap 保存已经求解过的结点，就是一种缓存的思想。

再看本方法的缺陷，这是一种“跳跃式”的解法，从一个结点出发到另一个结点，会有多条路径，而多条路径会导致重复计算，那么如果能使它不再跳跃，只能一步一步往下走的话，这个重复计算也就不复存在了。

如何改进？小偷对于每个结点有两种处理：偷或不偷。

  1. 如果小偷偷了当前结点，那么它的子结点不能偷
  2. 如果小偷不偷当前结点，那么子结点可以偷，也可以不偷（取其中较大的即可）

这次的条件好像与上面的条件一样，但是还是有区别的，那个涉及到了孙子结点，而这个，只涉及到孩子，如果上面那个是“跳跃式”的，那么这个就是“步进式”的。当一个结点的解，只与它的孩子结点有关时，这个问题就变得简单了。如下：

public static int rob(TreeNode root) {int[] rob = max(root);return Math.max(rob[0], rob[1]);
}
private static int[] max(TreeNode node) {if (node == null) {return new int[]{0, 0};}int[] rob = new int[2];int[] left = max(node.left);int[] right = max(node.right);rob[0] = left[1] + right[1] + node.val;rob[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);return rob;
}

函数rob返回了一个数组，数组的第一个数是偷了当前结点的解，第二个数是不偷当前结点的解，那么对于一个结点 node 来说，它只要知道了它的左右孩子结点的这样一个数组，就可以根据上面那个条件求出当前结点的最优解，因为没有了跳跃访问，所有的结点只会访问到一遍。

 

这篇关于JAVA算法：House Robber IIIIII JAVA版本解题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/383077。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
不懂推荐算法也能设计推荐系统

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

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

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（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]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2