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

2023-11-10 13:58

本文主要是介绍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

相关文章

如何在 Spring Boot 中实现 FreeMarker 模板

《如何在SpringBoot中实现FreeMarker模板》FreeMarker是一种功能强大、轻量级的模板引擎,用于在Java应用中生成动态文本输出(如HTML、XML、邮件内容等),本文... 目录什么是 FreeMarker 模板?在 Spring Boot 中实现 FreeMarker 模板1. 环

SpringMVC 通过ajax 前后端数据交互的实现方法

《SpringMVC通过ajax前后端数据交互的实现方法》:本文主要介绍SpringMVC通过ajax前后端数据交互的实现方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价... 在前端的开发过程中,经常在html页面通过AJAX进行前后端数据的交互,SpringMVC的controll

Java中的工具类命名方法

《Java中的工具类命名方法》:本文主要介绍Java中的工具类究竟如何命名,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java中的工具类究竟如何命名?先来几个例子几种命名方式的比较到底如何命名 ?总结Java中的工具类究竟如何命名?先来几个例子JD

Java Stream流使用案例深入详解

《JavaStream流使用案例深入详解》:本文主要介绍JavaStream流使用案例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录前言1. Lambda1.1 语法1.2 没参数只有一条语句或者多条语句1.3 一个参数只有一条语句或者多

Spring Security自定义身份认证的实现方法

《SpringSecurity自定义身份认证的实现方法》:本文主要介绍SpringSecurity自定义身份认证的实现方法,下面对SpringSecurity的这三种自定义身份认证进行详细讲解,... 目录1.内存身份认证(1)创建配置类(2)验证内存身份认证2.JDBC身份认证(1)数据准备 (2)配置依

SpringBoot整合OpenFeign的完整指南

《SpringBoot整合OpenFeign的完整指南》OpenFeign是由Netflix开发的一个声明式Web服务客户端,它使得编写HTTP客户端变得更加简单,本文为大家介绍了SpringBoot... 目录什么是OpenFeign环境准备创建 Spring Boot 项目添加依赖启用 OpenFeig

Java Spring 中 @PostConstruct 注解使用原理及常见场景

《JavaSpring中@PostConstruct注解使用原理及常见场景》在JavaSpring中,@PostConstruct注解是一个非常实用的功能,它允许开发者在Spring容器完全初... 目录一、@PostConstruct 注解概述二、@PostConstruct 注解的基本使用2.1 基本代

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删

SpringBoot整合mybatisPlus实现批量插入并获取ID详解

《SpringBoot整合mybatisPlus实现批量插入并获取ID详解》这篇文章主要为大家详细介绍了SpringBoot如何整合mybatisPlus实现批量插入并获取ID,文中的示例代码讲解详细... 目录【1】saveBATch(一万条数据总耗时:2478ms)【2】集合方式foreach(一万条数

IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

《IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决》:本文主要介绍IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决,本文分步骤结合实例给大... 目录步骤 1:创建 Maven Web 项目步骤 2:添加 Spring MVC 依赖1、保存后执行2、将新的依赖