Moment For Technology

【DP】 ring arrangement | Java brush problem punch card

Posted on Aug. 5, 2023, 9:17 a.m. by Anika Badami
Category: The back-end Tag: The back-end

This article is participating in the "Java Theme Month - Java Brush questions punch card", see the activity link for details

First, the topic overview

LeetCode 213Burglary II

You are a professional thief, planning to rob the houses along the street, each with a certain amount of cash hidden inside. All the houses in this place are in a circle, which means that the first house and the last house are next to each other. At the same time, adjacent houses are equipped with an interconnected security system, if two adjacent houses are broken into on the same night, the system will automatically alarm.

Given an array of non-negative integers representing the amount stored in each house, calculate the maximum amount you can steal without setting off the alarm.

Example 1: Input: nums = [2,3,2] Output: 3 Explanation: You cannot steal House 1 (amount = 2) and then House 3 (amount = 2) because they are adjacent. Example 2: Input: nums = [1,2,3,1] Output: 4 Explanation: You can steal House 1 first (amount = 1) and then House 3 (amount = 3). Maximum amount stolen = 1 + 3 = 4. Example 3: Input: nums = [0] Output: 0Copy the code


1 = nums.length = 100 0 = nums[i] = 1000

Dry problem analysis

If money cannot be withdrawn at the same time, there can only be three different situations:

  1. The first house and the last house don't take any money.
  2. I only take the first house, I don't take the last house.
  3. I'm only taking money from the last house, not the first house.

As shown in figure:

Final answer: Whichever of these three scenarios has the greatest result is the final answer.

You don't have to compare all three, you just have to compare two and three, because it's easy to see from the diagram that the choice of house in these two cases already covers case one.

Second, the idea of implementation

The solution to the original problem is slightly modified:

public class LeetCode_213 {

    // Time: o(n), Space: o(1), Faster: 100.00%
    public int rob(int[] nums) {

        if (nums == null || nums.length == 0) return 0;

        if (nums.length == 1) return nums[0];

        int withoutTailResult = this.robInternal(Arrays.copyOfRange(nums, 0, nums.length - 1));

        int withoutHeadResult = this.robInternal(Arrays.copyOfRange(nums,1 , nums.length));

        return Math.max(withoutHeadResult, withoutTailResult);

    private int robInternal(int[] nums) {

        if (nums == null || nums.length == 0) return 0;

        if (nums.length == 1) return nums[0];

        int d1 = nums[0];

        int d2 = Math.max(nums[0], nums[1]);

        for (int i = 2; i  nums.length; ++i) {

            int temp = d2;

            d2 = Math.max(d1 + nums[i], d2);

            d1 = temp;
        returnd2; }}Copy the code
About (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.