CodingTour —

ARTS #132

Algorithm

本周选择的算法题是：Minimum Number of Operations to Move All Balls to Each Box。

规则

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith box is empty, and '1' if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes.

Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the ith box.

Each answer[i] is calculated considering the initial state of the boxes.

Example 1:

Input: boxes = "110"
Output: [1,1,3]
Explanation: The answer for each box is as follows:
1) First box: you will have to move one ball from the second box to the first box in one operation.
2) Second box: you will have to move one ball from the first box to the second box in one operation.
3) Third box: you will have to move one ball from the first box to the third box in two operations, and move one ball from the second box to the third box in one operation.

Example 2:

Input: boxes = "001011"
Output: [11,8,5,4,3,4]

Constraints:

• n == boxes.length
• 1 <= n <= 2000
• boxes[i] is either '0' or '1'.

Solution

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        ans = [0] * n
        count, steps = 0, 0
        for i in range(n):
            ans[i] += steps
            count += int(boxes[i])
            steps += count

        count, steps = 0, 0
        for i in reversed(range(n)):
            ans[i] += steps
            count += int(boxes[i])
            steps += count
        return ans

Review

REST is Dying. Get Rid of It.

作者回顾了浏览器、Web 的发展史，延伸到了对 REST 的讨论。REST 的“问题”是它实际上是一种架构风格，或者说模式，没有标准的实现手段，大家广泛使用的其实是 REST 的变种版本，比如只用 REST 的 POST and/or GET 这两个“动词”去发送、接收数据，很少用 DELETE。

作者大部分的内容都是介绍 TIGER 的设计，本质上 TIGER 并没有干掉 REST，更像是一种具体实现，偏标题党了。

Tip

学习 Axure 的用法，能产出一些基本的产品原型图并通过蓝湖在团队间共享了。

Share

过早优化(premature optimization)是一件危险的事情，同样的，对“过早设计”（premature design）也应该抱有同样的担忧，不要太早决定一个程序应该怎么做。

• 过早设计(premature design) - 过早决定一个程序的行为
• 过早优化(premature optimization) - 还没有写完程序，你就开始考虑它的性能问题

这样的行为好比姑娘还没有成年却已经嫁人了、明年计划要减肥今天就开始买 S 码的衣服，一个优秀的作品关键是要能迭代，而且它必须比它原本的样子要更好，这听起来似乎有点矛盾，但其实能让产品成功的点，和产品一开始做的事可能大相径庭，很多公司的业务也是如此，这不是说提前规划是不可取的，只是真正的落地是和业务阶段、市场环境、业界风向，乃至个人理解强相关的。