<
ARTS 第十五周
>
上一篇

ARTS 第十四周

没有下一篇咯
Toc
ARTS Week-15

Algorithm

213. 打家劫舍 II

    你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
    
    给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
    
    示例 1:
    
    输入: [2,3,2]
    输出: 3
    解释: 你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。
    示例 2:
    
    输入: [1,2,3,1]
    输出: 4
    解释: 你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
         偷窃到的最高金额 = 1 + 3 = 4 。

这道题是在 198. 打家劫舍 的基础上增加了一个条件 「所有房屋都围成一圈」,但是思路还是一样的,这道也是一道动态规划的题目。

首先我们来写出动态规划方程,根据规则我们可以知道:

    example: [1,2,3,1]
    dp[0] = nums[0] = 1
    dp[1] = max(dp[0], nums[1]) = max(1, 2) = 2
    dp[2] = max(dp[0] + nums[2], dp[1]) = max(1 + 3, 2) = 4
    dp[3] = max(dp[1] + nums[3], dp[2]) = max(2 + 1, 4) = 4
    
    example: [2, 7, 9, 3, 1]
    dp[0] = nums[0] = 2
    dp[1] = max(dp[0], nums[1]) = max(2, 7) = 7
    dp[2] = max(dp[0] + nums[2], dp[1]) = max(2 + 9, 7) = 11
    dp[3] = max(dp[1] + nums[3], dp[2]) = max(7 + 3, 11) = 11
    dp[4] = max(dp[2] + nums[4], dp[3]) = max(11 + 1, 11) = 12
    
    example: [2, 1, 1, 2]
    dp[0] = nums[0] = 2
    dp[1] = max(dp[0], nums[1]) = max(2, 1) = 2
    dp[2] = max(dp[0] + nums[2], dp[1]) = max(2 + 1, 2) = 3
    dp[3] = max(dp[1] + nums[3], dp[2]) = max(2 + 2, 3) = 4

198. 打家劫舍 这道题的动态规划方程还是很容易得到的:

dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

但是增加了一个条件后,数组的首尾值不能同时取,那么我们就分两种情况计算最大值,分别是去头和取尾的数组,接下来写一下代码:

    class Solution:
        def rob(self, nums: List[int]) -> int:
            if not nums:
                return 0
            
    				# 这个条件可以不加
            if len(nums) <= 3:
                return max(nums)
            
    				# 分别计算去头和去尾的数组最大值
            return max(self._rob(nums[:-1]), self._rob(nums[1:]))
        
        def _rob(self, nums):
            
            length = len(nums)
            
            if length <= 2:
                return max(nums)
            
            dp = [nums[0], max(nums[0], nums[1])]
            
            for i in range(2, length):
                dp.append(max(dp[i - 1], dp[i - 2] + nums[i]))
            
            return dp[-1]

这种解法的空间复杂度为 O(N),时间复杂度也为 O(N)。

空间复杂度还是可以优化的,优化后的代码如下:

    class Solution:
        def rob(self, nums: List[int]) -> int:
            if not nums:
                return 0
            
            length = len(nums)
            if length <= 3:
                return max(nums)
            
            return max(self._rob(nums, 0, length - 1), self._rob(nums, 1, length))
        
        def _rob(self, nums, start, end):
            
            length = len(nums)
            
            if length <= 2:
                return max(nums)
            
            pre, cur = nums[start], max(nums[start], nums[start + 1])
            
            for i in range(start + 2, end):
                pre, cur = cur, max(cur, pre + nums[i])
            
            return cur

Review

Choose Boring Technology

这是一篇非常有意思的文章,提醒着我们这群年轻人,不能盲目的选用新技术或者自己喜欢的技术,有时候需要优先考虑那些「无聊的」但往往适合目前开发团队的技术。

而且不是引入越多的技术栈越好,恰恰相反引入更少的技术栈并且能优雅的解决大多数问题,并且只有较少的维护成本,才是更好的。

英语不太好的可以看这篇译文,译文 《我是一名技术总监,被技术选型给埋坑里了》

img1

Tip

Intro Guide to Dockerfile Best Practices - 如何写好 Dockerfile
这篇文章将会教会你怎么样写出更好的 Dockerfile,如果你刚开始学习使用 Docker 那更应该看这篇文章!

img2

Share

笔者最近看到一篇文章的片段非常有感触。

摘自《领域驱动设计在前端中的应用》作者:Vince_

垃圾桶现象


在开始本篇文章前,我给读者们分享一个很考验人性的有趣现象,在公司洗手间的洗漱台旁边,放置了一个垃圾桶,每次我洗完手,用纸巾擦干手后,将其扔进垃圾桶,但是偶尔扔不准会扔到垃圾桶外面。

一般情况下,我会将其捡起,再放入垃圾桶,心里想着:“不能破坏这么干净的环境呀”。 但是,当垃圾桶周边有很多别人没扔进去的餐巾纸时,我就不会那么愿意将自己没扔进去的餐巾纸再捡起来扔进去,想着:“反正都这么邋遢了,多了一个也不会怎样”。 万恶的人心呀!

过了很久,我接手了一个老的项目,这个项目经过近十个人手迭代,传到我这里时,已经是非常混乱的状态了,阅读代码时,发现了很多不合理的写法与隐藏式BUG,当我在写新的需求时,很自然地,我不会那么精益求精地编写业务逻辑,甚至也会留下一些隐藏的坑给后人。

恰恰相反,前段时间有幸接手一个大佬的项目,阅读其代码仿佛如沐春风,整个结构堪称完美,逻辑条理清晰,看代码就像看需求文档一样,堪称一绝。这个时候,当我要在其写新的需求,我会模仿其设计,小心翼翼地将自己代码插入其中,就像不忍心破坏这件艺术品一样。

以上故事纯属我一个理想主义程序员虚构。

但是回到现实当中,我们维护一个混乱项目和一个优雅项目的心情肯定是不一样的,就像上面讲的那个垃圾桶现象,混乱的项目就像周围遍布很多垃圾的垃圾桶,当你在混乱项目里再添加一些混乱代码后会良心也不会很痛,而优雅的项目你就会注意自己的行为,不能一颗老鼠屎坏了一锅粥。


严格的 Review

在合入分支前进行严格的 Code Review 是非常有必要的,领域驱动设计是非常不抗“腐蚀”的,不能接受不规范的代码或结构,在初期的 Review 成本或许有些大,等成员之间认知统一后,后续便能愉快地一起写代码了~

Top
Foot