ARTS #2

Algorithm

本周选择的算法题是：ZigZag Conversion

规则如下：

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

顾名思义，是将字符串以 Z 字形重新排列并输出。

Solution

我实现的方案：

Runtime：60 ms，快过 94.09%。

Memory：13.3 MB，低于 43.72%。

class Solution:

    def convert(self, s: str, numRows: int) -> str:
        length = len(s)
        if numRows < 2:
            return s

        cycle_length = 2 * numRows - 2 # numRows + numRows - 2
        result, index = [None] * length, 0
        for row in range(0, numRows, 1):
            location = row
            step_reverse = False
            while location < length:
                result[index] = s[location]
                index += 1

                if row == 0 or row == numRows - 1:
                    location += cycle_length
                else:
                    step_reverse = not step_reverse
                    location += cycle_length - 2 * row if step_reverse else 2 * row

        return "".join(result)

实现起来不难，但是花了很多时间找其中的规律，首行和尾行比较简单，主要是中间行的步长需要切换：

# numRows = 4
p  i 	= 2 * numRows - 2
a ls	= 4 -> 2
ya h 	= 2 -> 4
p  i 	= 2 * numRows - 2

# numRows = 5
p   h	= 2 * numRows - 2
a  si	= 6 -> 2
y i r	= 4 -> 4
pl  i	= 2 -> 6
a   n	= 2 * numRows - 2

另外用了一个 list，没有直接用 str 的原因是不想在运行时反复创建 str。

Review

Notes to Myself on Software Engineering
全文谈了三个部分：

研发
设计
生产力

有很多建议，更多的是一种对待软件的严肃性，或者叫态度。

我看到的几个关键字：

cognitive load，认知负担，提高产品的易用性就是减少用户的认知负担，换句话说，产品好不好用不是只影响你的产品本身，它对用户是有伤害的
mental models，心智模型，一般来说，要判断工程师的好坏通过同行评审会比较公正，心智模型的好坏就取决于你对领域、行业的认识有多深，如果一位资深的行业专家都看不懂你的设计(API、功能等)，那么它对普通用户就是有伤害的
ethic，道德，Technology is never neutral — 技术不是中立的，有人受益就会有人受到伤害，无论当初是因为什么做的技术决策
values，价值观，你的价值观能让你的选择变得简单，如果一个产品对世界有影响，那么这个影响一定会有方向(正面 or 负面)，将你的价值观融入进去，深思熟虑它可能会产生的影响，不要急于做出决定，模糊的正确比精确的错误更重要

Tip

本周学习到的一些内容：

Top K 的一些应用场景以及解决方案
Vue + Antd 的技术栈

本周分享 WWDC 2019 ：优秀的开发习惯，虽然是 WWDC 的主题，但是聊的范围不局限在 iOS，如果你想成为优秀的开发者，首先要明确的知道“什么是优秀”，其次才是如何做到优秀，作者在文中提到的观点大纲如下：

代码的组织
源码的跟踪
文档的重要性
测试的重要性
分析你的 App（iOS）
代码评审的好处
解耦的好处
依赖管理

Algorithm

Solution

Review

Tip

Share