打家劫舍(二)

C++ 解法, 执行用时: 22ms, 内存消耗: 5724KB, 提交时间: 2022-08-02

const auto io_sync_off=[]() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
        // write code here
        vector<int> nums1(nums.begin(), nums.end() - 1);
        vector<int> nums2(nums.begin() + 1, nums.end());
        return max(rob__(nums1), rob__(nums2));
    }
    
private:
    int rob__(vector<int>& nums) {
        vector<int> dp(nums.size() + 3);
        for (int i = nums.size() - 1; i >= 0; i--)
            dp[i] = nums[i] + max(dp[i+2], dp[i+3]);
        return max(dp[0], dp[1]);
    }
};

C++ 解法, 执行用时: 22ms, 内存消耗: 6808KB, 提交时间: 2022-07-25

static const auto io_sync_off = [](){
    std::ios::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    int robR(vector<int>& nums,int start,int end)
    {
        if(end==start)
            return nums[start];
        vector<int>dp(nums.size());
        dp[start]=nums[start];
        dp[start+1]=max(nums[start],nums[start+1]);
        for(int i=start+2;i<=end;i++)
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
        return dp[end];
    }
    int rob(vector<int>& nums) {
        if(nums.size()==1)
            return nums[0];
        int res1=robR(nums,0,nums.size()-2);
        int res2=robR(nums,1,nums.size()-1);
        return max(res1,res2);
    }
};

Rust 解法, 执行用时: 23ms, 内存消耗: 5260KB, 提交时间: 2022-04-08

struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param nums int整型一维数组 
        * @return int整型
    */
    pub fn rob(&self, nums: Vec<i32>) -> i32 {
        let n = nums.len();
        match n {
            1 => nums[0],
            2 => nums[0].max(nums[1]),
            _ => self.rob_range(&nums, 0usize, n-2).max(self.rob_range(&nums, 1usize, n-1)),
        }
    }
    
    fn rob_range(&self, nums: &Vec<i32>, s :usize, e :usize) -> i32 {
        let mut last1 = 0i32;
        let mut last2 = 0i32;
        for i in (s..=e).rev() {
            let tmp = last2.max(last1 + nums[i]);
            
            last1 = last2;
            last2 = tmp;
        }
        
        last2
    }
}

C++ 解法, 执行用时: 24ms, 内存消耗: 5688KB, 提交时间: 2021-12-07

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
        // write code here
        int n = nums.size();
        if(n <= 0) return 0;
        if(n == 1) return nums[0];
        if(n == 2) return max(nums[0],nums[1]);
        return max(rob2(nums,0,n-2),rob2(nums,1,n-1));
    }
    int rob2(vector<int>& nums, int start, int end)
    {
        if(start >= end) return 0;
        int rob = 0, no_rob = 0;
        for(int i = start; i <= end; i++)
        {
            int rob_ = no_rob + nums[i];
            no_rob = max(rob,no_rob);
            rob = rob_;
        }
        return max(rob,no_rob);
    }
};

C++ 解法, 执行用时: 25ms, 内存消耗: 5644KB, 提交时间: 2022-01-16

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int robNum(vector<int>& nums, int start, int end) {
        int n = nums.size();
        vector<int> dp(n - 1, 0);
        dp[0] = nums[start];
        dp[1] = max(nums[start], nums[start + 1]);
        dp[2] = max(nums[start] + nums[start + 2], nums[start + 1]);
        for (int i = 3; i < n - 1; i++) {
            dp[i] = max(dp[i - 2], dp[i - 3]) + nums[i + start];
        }
        return max(dp[n - 2], dp[n - 3]);
    }
    int rob(vector<int>& nums) {
        // write code here
        int n = nums.size();
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);
        if (n == 3) return max(nums[0], max(nums[2], nums[1]));
        int result1 = robNum(nums, 0, n - 2);
        int result2 = robNum(nums, 1, n - 1);
        return max(result1, result2);
    }
};

详情