leetcode-198-打家劫舍(house robber)-java

題目及用例

package pid198;
/* 打家劫舍

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。

示例 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 。


*/




public class main {
	
	public static void main(String[] args) {
		int[][] testTable = {{1,2,3,1},{2,7,9,3,1},{7,10,4,3,1},{11,6,2,7}};
		for (int[] ito : testTable) {
			test(ito);
		}
	}
		 
	private static void test(int[] ito) {
		Solution solution = new Solution();
		int rtn;
		long begin = System.currentTimeMillis();
		for (int i = 0; i < ito.length; i++) {
		    System.out.print(ito[i]+" ");		    
		}
		System.out.println();
		//開始時列印數組
		
		rtn = solution.rob(ito);//執行程式
		long end = System.currentTimeMillis();	
		
		//System.out.println(ito + ": rtn=" + rtn);
		System.out.println( " rtn=" +rtn);
//		for (int i = 0; i < ito.length; i++) {
//		    System.out.print(ito[i]+" ");
//		}//列印結果幾數組
		
		System.out.println();
		System.out.println("耗時：" + (end - begin) + "ms");
		System.out.println("-------------------");
	}

}

           

解法1（成功，1ms，超快）

如果nums隻有一個，傳回那一個

如果2個，傳回中間大的那個

之後

現在i的max=max( （i-2）的max+num[i] ,(i-1)的max)

max[i]=max[i-2]+nums[i] / max[i-1]

用動态規劃，不斷max上去

public int rob(int[] nums) {
       //max[i]=max[i-2]+nums[i] / max[i-1]
    	int length=nums.length;
    	if(length==0){
    		return 0;
    	}
    	if(length==1){
    		return nums[0];
    	}
    	//即max[i-2]
    	int prev2=nums[0];
    	//即max[i-1]
    	int prev1=nums[0]>nums[1]?nums[0]:nums[1];
    	for(int i=2;i<length;i++){
    		int now=nums[i];
    		int nowMax=prev2+now>prev1?prev2+now:prev1;
    		prev2=prev1;
    		prev1=nowMax;
    	}    	   	   	
    	return prev1;
    }

           

解法2（别人的）

不優秀

暴力搜尋方法

思路：文中給出不能連續搶兩家，是以假設從最後一個房屋開始搶，最後一個房屋為index。将原問題分割成子問題，子問題的最優決策可以導出原問題的最優決策。現有兩種可能情況，目前房屋搶和目前房屋不搶。若目前房屋搶，則下一房屋不能搶；若目前房屋不搶，則下一房屋可搶；選出這兩種情況的最大值，遞歸執行，直到index<0。

public int solve(int index, int[] nums){
        if(index < 0){
            return 0;
        }
        int max = Math.max(nums[index] + solve(index - 2, nums), solve(index - 1, nums));
        return max;
    }

    public int rob(int[] nums) {
        return solve(nums.length-1, nums);
    }


           

解法3（别人的）

自頂向下解法

也就是map法，每個的結果都放在數組中

為了避免上述的重複計算，我們初始化一個數組來記錄所有記錄為-1，如果目前index被算過，就記錄下來。是以，每次判斷該屋搶還是不搶後，都會得到一個index值。這就是去備援，用采用空間換時間的方法。是以當n-1房屋的最優解算過後，就能推導出n房屋的最優解。這就是動态規劃的思想。

是以，我們考慮使用動态規劃，設定result[]數組記錄搶奪該房屋可能的最大收益。

class Solution {
    public static int[] result;

    public int solve(int index, int[] nums){
        if(index < 0){
            return 0;
        }

        if(result[index] >= 0){
            return result[index];
        }

        result[index] = Math.max(nums[index] + solve(index-2 , nums), solve(index-1, nums));
        return result[index];
    }

    public int rob(int[] nums) {
        result = new int[nums.length];
        for(int i=0; i < result.length; i++){
            result[i]=-1;
        }
        return solve(nums.length-1, nums);
    }
}

           

解法4（别人的）

自底向上的map法

public int rob(int[] nums) {
        if (nums.length == 0){
            return 0;
        }

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

        if (nums.length == 2){
            return Math.max(nums[0], nums[1]);
        }

        int[] result = new int[nums.length];   
        result[0] = nums[0];
        result[1] = Math.max(nums[0], nums[1]);

        for(int index=2; index < result.length; index++){
            result[index] = Math.max(nums[index] + result[index-2], result[index -1]);
        }

        return result[nums.length -1];
    }
}