leetcode

leetcode 213题

Posted by franki on September 13, 2021

leetcode 213题 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [0]
输出：0

思路

循环

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const n = nums.length;
    
    if (n === 0) {
        return 0;
    }

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

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

    // 返回 [0, n-1] 与 [1, n] 之间的最大值
    return Math.max(robs(nums, 0, n-2), robs(nums, 1, n-1));
};

function robs(nums, start, end) {
    let preMax = nums[start];
    let curMax = Math.max(preMax, nums[start+1]);

    for (let i=start+2; i<=end; i++) {
        const temp = curMax;
        curMax = Math.max(curMax, preMax + nums[i]);
        preMax = temp;
    }

    return curMax;
}

复杂度分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS