Leetcode 740

5.5的题目740. 删除并获得点数和 198. 打家劫舍有点类似 , 需要在一些地方做出调整

为了做740，先去当了一遍小偷XDDD

打家劫舍，经典dp问题，偷还得隔间偷,甚至开了透视知道哪里最多钱（笑

一间的时候肯定只能偷那个，两间的时候就需要Math.max比较

n间的时候则需要 when i > 2 , Math.max(dp[i - 2] + num[i] , dp[i - 1])来比较金额大小

public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0 || nums == null)
            return 0;
        else if (n == 1)
            return nums[0];

        /**
         int[] dp = new int[n];
         dp[0] = nums[0];
         dp[1] = Math.max(nums[0], nums[1]);

         for (int i = 2; i < n; i++) {
         dp[i] = Math.max(dp[i - 2] + nums[i] , dp[i -1]);
         }
         return dp[n - 1];
         */
		
    	//最大金额只与前两间房子的最大值相关
    	//用滚动数组优化
        int first = nums[0], second = Math.max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }

时间复杂度：O(n) ，需要对整个num数组遍历一次

空间复杂度：O(1)，不需要存储每次计算结果

740的话，需要先找出最大值max , 因为需要用一个all数组来记录相同元素之和 , 防止out of bound

	/**
     * 根据题意,在选择了元素x后,该元素以及所有等于x-1或x+1的元素会从数组中删去。
     * 若还有多个值为x的元素,由于所有等于x-1或x+1的元素已经被删除,我们可以直接删除并获得其点数。
     * 因此若选择了x,所有等于x的元素也应同被选择,以尽可能多地获得点数。
     */
    public int deleteAndEarn(int[] nums){
        int n = nums.length;
        if (n == 0 || nums == null)
            return 0;
        else if (n == 1)
            return nums[0];

        int max = 0;
        for (int maxVal:nums) {
            max = Math.max(maxVal , max);//防止out of bounds
        }

        int[] all = new int[max + 1];
        for (int val : nums)
            all[val] += val;

        return rob(all);
    }

    private int rob(int[] nums){
        int n = nums.length;

        int first = nums[0] , second = Math.max(nums[0] , nums[1]);
        for (int i = 2; i < n; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }

        return second;
    }

时间复杂度O(N+M) , 其中N是数组nums的长度, M是num中元素的最大值。

空间复杂度:O(M)