House Robber

DocumentsAlgorithms
Algorithms, Leetcode, Python
Catalogue
  1. 1. Question
  2. 2. Explanation
  3. 3. Code

Question

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 > (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money > = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Explanation

The maximum value the robber can get when he comes to a house is nums[i]+max(nums[i-2], nums[i-3]) when i-3 and i-2 exist. Therefore, we can separate the question into two situations. The first one is to determine the max reward when i<=3. The second one is to calculate the maximum value for i based on the maximum value we get in nums[i-2] and nums[i-3].

Code

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        elif len(nums) < 3:
            return max(nums)
        elif len(nums) == 3:
            return max(nums[1], nums[0]+nums[2])
        else:
            nums[2] += nums[0]
            globalMax = max(nums[1], nums[2])
            for i in range(3, len(nums)):
                nums[i] += max(nums[i-2], nums[i-3])
                globalMax = max(globalMax, nums[i])
        return globalMax
Comments
Posts
Leetcode 5 Longest Palindromic Substring （With Manacher's Algorithms)

QuestionGiven a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: “babad”O

Leedcode 160 Intersection of Two Linked Lists

QuestionWrite a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A:

Leetcode 94 - Binary Tree Inorder Traversal （中值遍历）

QuestionGiven a binary tree, return the inorder traversal of its nodes’ values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recu

Leetcode 328 - Odd Even Linked List

QuestionGiven a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and

Leetcode 2 - Add Two Numbers

QuestionYou are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their node

Leetcode 334 - Increasing Triplet Subsequence

QuestionGiven an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should: Return

Leetcode 101 - Symmetric Tree

QuestionGiven a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] i

Leetcode 98 - Validate Binary Search Tree

QuestionGiven a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node conta

Leetcode 20 - Valid Parentheses

QuestionGiven a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid. An input string is vali

Leetcode 268 - Missing Number

QuestionGiven an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array. Example 1: Input: [3,0,1]O

Leetcode 13 - Roman to Integer

QuestionRoman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For examp

Leetcode 326 - Power of Three

QuestionGiven an integer, write a function to determine if it is a power of three. Example 1: Input: 27Output: trueExample 2: Input: 0Output: falseExa

Leetcode 204 - Count Primes

QuestionCount the number of prime numbers less than a non-negative number, n. Example: Input: 10Output: 4Explanation: There are 4 prime numbers less t

Leetcode 412 - Fizz Buzz

QuestionWrite a program that outputs the string representation of numbers from 1 to n. But for multiples of three it should output “Fizz” instead of t

Leetcode 155 - Min Stack

QuestionDesign a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) – Push element x onto stack. pop() –

House Robber

QuestionYou are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint sto

Merge sorted array

QuestionGiven two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.Note:The number of elements initialized in nums1 a

First bad version

QuestionYou are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the q

Maximum Subarray

QuestionGiven an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Examp

Pages
About

TBC

Documents
Tags
Categories
DocumentsDocuments
AlgorithmsDocuments/Algorithms
Tags
LeetcodeLeetcode
AlgorithmsAlgorithms
PythonPython
StringString
Linked ListsLinked-Lists
TreeTree
AlgoroithmsAlgoroithms