Android学习总结之算法篇三（打家劫舍）

打家劫舍一

// 动态规划
class Solution {public int rob(int[] nums) {if (nums == null || nums.length == 0) return 0;if (nums.length == 1) return nums[0];int[] dp = new int[nums.length];dp[0] = nums[0];dp[1] = Math.max(dp[0], nums[1]);for (int i = 2; i < nums.length; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[nums.length - 1];}
}

 打家劫舍二（环）

public class HouseRobberCircular {/*** 计算在环形房屋布局下，不触动警报装置时能偷窃到的最大金额* 由于房屋围成一圈，所以需要分别考虑不偷第一间房屋和不偷最后一间房屋的情况* @param nums 每个房屋存放的金额数组* @return 最大偷窃金额*/public int rob(int[] nums) {// 如果数组长度为 1，直接返回该房屋的金额if (nums.length == 1) {return nums[0];}// 计算不偷第一间房屋时能获得的最大金额int max1 = robRange(nums, 1, nums.length - 1);// 计算不偷最后一间房屋时能获得的最大金额int max2 = robRange(nums, 0, nums.length - 2);// 返回两种情况中的最大值return Math.max(max1, max2);}/*** 计算在指定范围内的房屋中，不触动警报装置时能偷窃到的最大金额* @param nums 每个房屋存放的金额数组* @param start 起始房屋索引* @param end 结束房屋索引* @return 指定范围内的最大偷窃金额*/private int robRange(int[] nums, int start, int end) {// 记录前一个房屋的最大偷窃金额int prevMax = 0;// 记录当前房屋的最大偷窃金额int currMax = 0;// 遍历指定范围内的房屋for (int i = start; i <= end; i++) {// 临时保存当前房屋的最大偷窃金额int temp = currMax;// 更新当前房屋的最大偷窃金额，取偷当前房屋和不偷当前房屋的最大值currMax = Math.max(prevMax + nums[i], currMax);// 更新前一个房屋的最大偷窃金额prevMax = temp;}// 返回指定范围内的最大偷窃金额return currMax;}public static void main(String[] args) {// 创建 HouseRobberCircular 类的实例HouseRobberCircular solution = new HouseRobberCircular();// 定义测试数组int[] nums = {2, 3, 2};// 调用 rob 方法计算最大偷窃金额并打印输出System.out.println(solution.rob(nums)); }
}    

打家劫舍三（二叉树）

// 定义二叉树节点类
class TreeNode {// 节点存储的金额int val;// 左子节点TreeNode left;// 右子节点TreeNode right;// 构造函数，用于初始化节点的值TreeNode(int x) { val = x; }
}public class HouseRobberBinaryTree {/*** 计算在不触发警报的情况下，小偷能从二叉树结构的房屋布局中盗取的最大金额* @param root 二叉树的根节点* @return 可盗取的最大金额*/public int rob(TreeNode root) {// 调用 dfs 方法获取两个值，分别是不偷根节点和偷根节点时的最大金额int[] result = dfs(root);// 返回两者中的最大值作为最终结果return Math.max(result[0], result[1]);}/*** 深度优先搜索方法，递归计算以当前节点为根的子树中，不偷和偷当前节点时的最大金额* @param node 当前处理的节点* @return 包含两个元素的数组，第一个元素是不偷当前节点的最大金额，第二个元素是偷当前节点的最大金额*/private int[] dfs(TreeNode node) {// 如果当前节点为空，意味着没有房屋可偷，返回 [0, 0]if (node == null) {return new int[]{0, 0};}// 递归计算左子树的结果，得到不偷和偷左子树根节点的最大金额int[] left = dfs(node.left);// 递归计算右子树的结果，得到不偷和偷右子树根节点的最大金额int[] right = dfs(node.right);// 不偷当前节点的最大金额：左子树偷或不偷的最大金额 + 右子树偷或不偷的最大金额int notRobCurrent = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);// 偷当前节点的最大金额：当前节点金额 + 左子树不偷的最大金额 + 右子树不偷的最大金额int robCurrent = node.val + left[0] + right[0];// 返回包含不偷和偷当前节点最大金额的数组return new int[]{notRobCurrent, robCurrent};}public static void main(String[] args) {// 示例构建二叉树TreeNode root = new TreeNode(3);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.right = new TreeNode(3);root.right.right = new TreeNode(1);// 创建 HouseRobberBinaryTree 类的实例HouseRobberBinaryTree solution = new HouseRobberBinaryTree();// 调用 rob 方法计算可盗取的最大金额int maxAmount = solution.rob(root);// 输出可盗取的最大金额System.out.println("可盗取的最大金额为: " + maxAmount);}
}    

打家劫舍四（最少金额） 

public class MinimumRobberyCapability {/*** 检查在给定的窃取能力下，是否能够窃取至少 k 间房屋* @param nums 每间房屋存放的现金金额数组* @param k 窃贼将会窃取的最少房屋数* @param capability 小偷的窃取能力* @return 如果能窃取至少 k 间房屋返回 true，否则返回 false*/private boolean canRob(int[] nums, int k, int capability) {// 记录已窃取的房屋数量int count = 0;// 标记上一间房屋是否被窃取boolean lastRobbed = false;// 遍历每间房屋for (int num : nums) {// 如果上一间房屋未被窃取且当前房屋的现金金额不超过窃取能力if (!lastRobbed && num <= capability) {// 窃取当前房屋，窃取房屋数量加 1count++;// 标记当前房屋已被窃取lastRobbed = true;} else {// 当前房屋不被窃取，标记上一间房屋未被窃取lastRobbed = false;}}// 判断窃取的房屋数量是否至少为 kreturn count >= k;}/*** 计算小偷的最小窃取能力* @param nums 每间房屋存放的现金金额数组* @param k 窃贼将会窃取的最少房屋数* @return 小偷的最小窃取能力*/public int minCapability(int[] nums, int k) {// 二分查找的左边界，最小窃取能力从 1 开始int left = 1;// 二分查找的右边界，设置一个较大的初始值int right = (int) 1e9;// 初始化结果为右边界的值int result = right;// 二分查找过程while (left <= right) {// 计算中间值int mid = left + (right - left) / 2;// 检查在中间值表示的窃取能力下，是否能窃取至少 k 间房屋if (canRob(nums, k, mid)) {// 如果可以，更新结果为中间值，并缩小右边界result = mid;right = mid - 1;} else {// 如果不可以，增大左边界left = mid + 1;}}// 返回最小窃取能力return result;}public static void main(String[] args) {// 创建 MinimumRobberyCapability 类的实例MinimumRobberyCapability solution = new MinimumRobberyCapability();// 示例房屋现金金额数组int[] nums = {2, 3, 5, 9};// 窃贼需要窃取的最少房屋数int k = 2;// 调用 minCapability 方法计算最小窃取能力int minCap = solution.minCapability(nums, k);// 输出结果System.out.println("小偷的最小窃取能力为: " + minCap);}
}