你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋扎拣。每間房內(nèi)都藏有一定的現(xiàn)金赴肚，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入二蓝，系統(tǒng)會(huì)自動(dòng)報(bào)警誉券。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下刊愚，能夠偷竊到的最高金額横朋。
輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)百拓。
偷竊到的最高金額 = 1 + 3 = 4 琴锭。
解釋:這道題不是簡單地隔一家偷一家這么簡單,要用動(dòng)態(tài)規(guī)劃去計(jì)算最優(yōu)的收益,如下面這個(gè)例子
[1,3,1,3,100]最大收益為103,就是偷了3和100
代碼:(注釋在代碼中)
import java.lang.reflect.Array;
import java.util.Arrays;
public class Rob {
public static int rob(int[] nums) {
int n = nums.length;
if (n==0) return 0;
if (n==1) return nums[0];
if (n==2) return Math.max(nums[1],nums[0]);
//在此之前都沒有問題,
// 當(dāng)n=3時(shí),如[1,5,3],在我要去偷第三家時(shí),我
// 就要考慮到底是選擇當(dāng)前已經(jīng)最大的收益還是把當(dāng)前的放棄去拿走之前和和去偷下一家
//就相當(dāng)于我之前偷了1,看到下一家有5,那我把這一家是1的還回去,然后偷了5,然后到了第三家,看到有3,然后
//計(jì)算了一下,如果偷之前的1然后再偷3加起來也沒有5多,就不去偷了
//再舉一個(gè)栗子[1,3,1,3,100]
//先偷了1,然后看到3,還回去1,偷了3,看到1,1+1<3,不管,看到3,偷了,看到100,計(jì)算了一下3+100>6,于是把3 還回去
//把一百偷了,
//pre相當(dāng)于上一家,cur相當(dāng)于當(dāng)前最大收益,num相當(dāng)于將要偷的一家
int pre = 0;
int cur = 0;
for (int num : nums){
int temp = cur;
cur = Math.max(pre+num,cur);
pre = temp;
//System.out.println("pre="+pre+"cur="+cur+"num="+num);
}
return cur;
}
}
打家劫舍 二
你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋衙传，每間房內(nèi)都藏有一定的現(xiàn)金决帖。這個(gè)地方所有的房屋都圍成一圈，這意味著第一個(gè)房屋和最后一個(gè)房屋是緊挨著的蓖捶。同時(shí)地回，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入俊鱼，系統(tǒng)會(huì)自動(dòng)報(bào)警刻像。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你在不觸動(dòng)警報(bào)裝置的情況下并闲，能夠偷竊到的最高金額细睡。
解釋:因?yàn)椴荒芡瑫r(shí)偷第一家和最后一家,其他情況和第一題不變,那就稍微改一下第一題的代碼,取兩種情況的最大值就好
import java.lang.reflect.Array;
import java.util.Arrays;
public class Rob {
public static int rob(int[] nums) {
int n = nums.length;
if (n==0) return 0;
if (n==1) return nums[0];
if (n==2) return Math.max(nums[1],nums[0]);
return Math.max(rob_max(Arrays.copyOfRange(nums,0,n-1)),rob_max(Arrays.copyOfRange(nums,1,n)));
}
private static int rob_max(int[] nums) {
int pre = 0;
int cur = 0;
for (int num : nums) {
int temp = cur;
cur = Math.max(pre + num, cur);
pre = temp;
//System.out.println("pre=" + pre + "cur=" + cur + "num=" + num);
}
return cur;
}
}
打家劫舍 三
在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)帝火。這個(gè)地區(qū)只有一個(gè)入口溜徙，我們稱之為“根”湃缎。 除了“根”之外，每棟房子有且只有一個(gè)“父“房子與之相連蠢壹。一番偵察之后嗓违，聰明的小偷意識到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹”。 如果兩個(gè)直接相連的房子在同一天晚上被打劫图贸，房屋將自動(dòng)報(bào)警蹂季。
計(jì)算在不觸動(dòng)警報(bào)的情況下，小偷一晚能夠盜取的最高金額疏日。
示例 1:
輸入: [3,2,3,null,3,null,1]
輸出: 7
解釋: 小偷一晚能夠盜取的最高金額 = 3 + 3 + 1 = 7.
解釋:一種情況是第二層,另一種情況是第一層+第三層
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public static int rob(TreeNode root) {
return SolutionTree(root).val;
}
public static TreeNode SolutionTree(TreeNode root){
if (root == null){
TreeNode treeNode = new TreeNode(0);
return SolutionTree(treeNode);
}
if (root.left == null &&root.right == null){
root.left = new TreeNode(0);
root.right = new TreeNode(0);
return root;
}
root.left = SolutionTree(root.left);
root.right = SolutionTree(root.right);
root.val = Math.max(root.left.val+root.right.val,root.val+root.left.left.val+
root.left.right.val+root.right.left.val+root.right.right.val);
return root;
}
}
可以變化為打家劫舍的題:
給定一個(gè)整數(shù)數(shù)組 nums 乏盐，你可以對它進(jìn)行一些操作。
每次操作中制恍，選擇任意一個(gè) nums[i] 父能，刪除它并獲得 nums[i] 的點(diǎn)數(shù)。之后净神，你必須刪除每個(gè)等于 nums[i] - 1 或 nums[i] + 1 的元素何吝。
開始你擁有 0 個(gè)點(diǎn)數(shù)。返回你能通過這些操作獲得的最大點(diǎn)數(shù)鹃唯。
輸入: nums = [3, 4, 2]
輸出: 6
解釋:
刪除 4 來獲得 4 個(gè)點(diǎn)數(shù)爱榕，因此 3 也被刪除。
之后坡慌，刪除 2 來獲得 2 個(gè)點(diǎn)數(shù)黔酥。總共獲得 6 個(gè)點(diǎn)數(shù)洪橘。
class Solution {
public static int deleteAndEarn(int[] nums) {
int n = nums.length;
if (n==0) return 0;
if (n==1) return nums[0];
int max1 = 0;
for (int i=0;i<n;i++){
max1 = Math.max(nums[i],max1);
}
int[] trans = new int[max1+1];
for (int num:nums){
trans[num-1] += num;
}
//System.out.println(Arrays.toString(trans));
int cur = 0;
int pre = 0;
for (int num : trans){
int temp = cur;
cur = Math.max(pre+num,cur);
pre = temp;
}
return cur;
}
}
