LeetCode:房屋抢劫犯I C#

Question

https://leetcode.com/problems/house-robber/

你是一个职业抢劫犯，打算抢劫街道上的房屋。每间房子都藏着一定数量的钱，唯一能阻止你抢劫的是相邻的房子都有保安系统连接，如果相邻的两栋房子在同一个晚上被闯入，它就会自动联系警察。给出一张代表每所房子的金额的非负整数的清单，确定你今晚可以抢劫的最高金额，而无需报警。示例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:

例2:输入:输出:12个解释: Rob 1 (money = 2)，rob 3 (money = 9)和rob 5 (money = 1)。你可以抢劫的总数=2+9+1= 12。

using System;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{
    /// 
    ///  https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/576/
    /// 
    [TestClass]
    public class HouseRobber
    {
        [TestMethod]
        public void HouseRobberTest()
        {
            int[] nums = {1, 2, 3, 1};
            HouseRobberClass robber = new HouseRobberClass();
            Assert.AreEqual(4, robber.Rob(nums));
        }


        [TestMethod]
        public void HouseRobber2Test()
        {
            int[] nums = { 1, 2, 3, 1 };
            HouseRobberClass robber = new HouseRobberClass();
            Assert.AreEqual(4, robber.Rob2(nums));
        }
    }

    public class HouseRobberClass
    {
        private int[] _mem;
        //option 1 for a solution - this is easier for me to think this way
        public int Rob(int[] nums)
        {
            _mem = Enumerable.Repeat(-1, nums.Length).ToArray();

            return Helper(nums,  0);
        }

        private int Helper(int[] nums, int index)
        {
            if (index >= nums.Length)
            {
                return 0;
            }

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

            _mem[index] = Math.Max(Helper(nums, index + 2) + nums[index], Helper(nums, index + 1));
            return _mem[index];
        }

       // option 2 for a solution
        public int Rob2(int[] nums)
        {
            if (nums.Length == 0)
            {
                return 0;
            }
            int[] memo = new int[nums.Length + 1];
            memo[0] = 0;
            memo[1] = nums[0];
            for (int i = 1; i < nums.Length; i++)
            {
                int val = nums[i];
                memo[i + 1] = Math.Max(memo[i], memo[i - 1] + val);
            }

            return memo[nums.Length];
        }
    }
}

Answer 1

确定第一个解决方案的时间复杂性并不简单，因为它会耗尽堆栈，而第二个解决方案显然需要线性时间(最优)，并且不太可能耗尽内存，所以我会立即放弃第一个解决方案。

第一种解决方案也因为_mem成员而劣等。没有理由在Rob中创建它，也没有理由让它成为成员。使它成为一个成员意味着：-不能同时调用此代码--一旦该方法存在，它就会留下内存--它容易受到其他成员的干扰--它比变量更难推理，因为它被从使用它的方法中删除。

一个很好的解决方案是让_mem成为局部变量，而Helper是Rob中的一个本地函数:这样您就不必传递nums和_mem，也就没有办法误用代码了。然后，您可以使所有这些方法static。

命名

命名可能会更好：

• _mem和memo都是神秘的(_mem提供回忆录，memo可以说不是)
• Rob和Rob2几乎没有传达任何信息
• Helper什么也没说(这有什么用？)它是做什么的？)

Documentation

• 请花时间添加文档。如果您正在练习面试，这并不重要:真正的代码需要文档(以便可以使用和维护)，编写它是一项值得练习的技能，这样做可以帮助您更好地解释代码并巩固边缘案例行为。

测试

测试是有限的，也不是很好。它们不测试需要“跳过”一对(例如9, 1, 1, 9)的情况，也不包括任何边缘情况。

这两种方法都会在null输入上抛出一个D35，而它们可能应该抛出一个很好的ArgumentException，以便调用者立即知道他们做错了什么:理想情况下，这将被测试。