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) {
                // 窃取当前房屋，窃取房屋数量加 1
                count++;
                // 标记当前房屋已被窃取
                lastRobbed = true;
            } else {
                // 当前房屋不被窃取，标记上一间房屋未被窃取
                lastRobbed = false;
            }
        }
        // 判断窃取的房屋数量是否至少为 k
        return 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);
    }
}