为什么我在 leetcode 问题“House Robber”上遇到错误？

Question

class Solution {    
public:     
    int rob(vector<int>& nums) {     
        int max=0,sum=0,temp;     
        for(int i=0;i<nums.size();i++)      
        {     
            if(nums[i]!=0)
            {
                if(nums[i]>max)   
                {   
                    max=nums[i];   
                    temp=i;    
                }    
            }   
        }   
        nums[temp]=0;   
        if((temp+1)!=NULL)   
        nums[temp+1]=0;    
        if((temp-1)!=NULL)        
        nums[temp-1]=0;
        sum=sum+max;   
        for(int i=0;i<nums.size();i++)   
        {   
            if(nums[i]!=0)   
            {   
                return rob(nums);     
            }    
        }         
        return sum;     
    }
};

有个问题是： https://leetcode.com/problems/house-robber/description/ 我不知道为什么会出现错误：

Line 1037: Char 34: runtime error: addition of unsigned offset to 0x602000000090 overflowed to 0x60200000008c (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/stl_vector.h:1046:34

它在空运行时工作正常，但leetcode不断显示错误

Answer 1

您的代码有一些问题。一般建议：leetcode 作为学习 C++ 的方式并没有良好的声誉。其次，多利用空白。将所有内容放在一起会使代码更难阅读。我将包含您的代码并对其进行一些清理。我会在看到问题的地方添加内嵌评论。

class Solution {    
public:     
    int rob(vector<int>& nums) {
        // Most coding standards will tell you to define variables
        // one per line instead of all together like this. It's just
        // a style and not a real issue.     
        int max=0,sum=0,temp;     
        for (int i = 0; i < nums.size(); i++)      
        {     
            if (nums[i] != 0)
            {
                if(nums[i]>max)   
                {   
                    max = nums[i];   
                    temp = i;    
                }    
            }   
        }   
        nums[temp] = 0;   
        // Why are you treating temp like a pointer? This code
        // is almost certainly wrong.
        // You probably mean if (temp + 1 < nums.size()
        if ((temp + 1) != NULL)   
            nums[temp+1] = 0;    
        // This code is probably also wrong.
        // What you probably mean is "if (temp > 0)"
        if ((temp - 1) != NULL)        
            nums[temp-1]=0;
        sum = sum+max;   
        for (int i = 0; i < nums.size(); i++)   
        {   
            if (nums[i] != 0)   
            {   
                return rob(nums);     
            }    
        }         
        return sum;     
    }
};

有关 if 语句的注释可能是问题的原因。但是，我不知道这将如何真正解决您的问题。您已经正确地识别了递归方法。然而，你的基本算法是行不通的。

在任何特定的房子里，如果你抢劫了前一栋房子，你就不能抢劫这一栋。在任何给定的房子里，你必须决定你是否最好抢劫这一栋或下一栋。这就是递归的地方。所以你的代码确实需要使用一种带有“下一个要抢劫的房子”参数的方法。

   int sumRobFirst = nums[first] + bestResultRobbing(nums, first+2);
   int sumRobNext = bestResultRobbing(nums, first+1);

   if (sumRobFirst > sumRobNext) ...