ARTS #38

Algorithm

本周选择的算法题是：Integer to Roman

规则如下：

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: 3
Output: "III"

Example 2:

Input: 4
Output: "IV"

Example 3:

Input: 9
Output: "IX"

Example 4:

Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Solution

解法一

我实现的方案：

Runtime：44 ms，快过 82.19%。

Memory：12.7 MB，低于 100%。

class Solution:

    integer_dict = {
        1: "I",
        4: "IV",
        5: "V",
        9: "IX",
        10: "X",
        40: "XL",
        50: "L",
        90: "XC",
        100: "C",
        400: "CD",
        500: "D",
        900: "CM",
        1000: "M",
    }

    def intToRoman(self, num: int) -> str:
        ans, carry = "", 1
        while num > 0:
            digit = num % 10 * carry
            num = num // 10
            carry *= 10
            if digit == 0: continue

            roman = Solution.integer_dict.get(digit)
            if roman is None:
                nearest, fill_count = digit, 0
                while nearest not in Solution.integer_dict:
                    nearest -= carry // 10
                    fill_count += 1
                if nearest * (fill_count + 1) == digit:
                    ans = Solution.integer_dict[nearest] * (fill_count + 1) + ans
                else:
                    ans = Solution.integer_dict[nearest] + Solution.integer_dict[nearest - 4 * carry // 10] * fill_count + ans
            else:
                ans = roman + ans

        return ans

结果比预想的要好一些，没超时。

解法二

Runtime：40 ms，快过 90.16%。

Memory：12.8 MB，低于 100%。

class Solution:
    integer_mapper = [
        (1000, "M"),
        (900, "CM"),
        (500, "D"),
        (400, "CD"),
        (100, "C"),
        (90, "XC"),
        (50, "L"),
        (40, "XL"),
        (10, "X"),
        (9, "IX"),
        (5, "V"),
        (4, "IV"),
        (1, "I"),
    ]

    def intToRoman(self, num: int) -> str:
        ans = ""
        for integer, roman in Solution.integer_mapper:
            ans += (num // integer) * roman
            num %= integer
            if num == 0: break
        return ans

代码简洁，面对小数字时的循环量会更大。

解法三

Runtime：40 ms，快过 92.16%。

Memory：12.7 MB，低于 100%。

class Solution:
    integer_mapper = [
        (1000, "M"),
        (900, "CM"),
        (500, "D"),
        (400, "CD"),
        (100, "C"),
        (90, "XC"),
        (50, "L"),
        (40, "XL"),
        (10, "X"),
        (9, "IX"),
        (5, "V"),
        (4, "IV"),
        (1, "I"),
    ]

    def intToRoman(self, num: int) -> str:
        ans = ""
        for integer, roman in Solution.integer_mapper:
            while num >= integer:
                ans += roman
                num -= integer
            if num == 0: break

        return ans

和解法二很像，用减少代替了整除和乘法。

解法四

Runtime：36 ms，快过 97.20%。

Memory：12.8 MB，低于 100%。

class Solution:
    
    M = ["", "M", "MM", "MMM"]
    C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
    X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
    I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]

    def intToRoman(self, num: int) -> str:
        return Solution.M[num // 1000] + Solution.C[num % 1000 // 100] + Solution.X[num % 100 // 10] + Solution.I[num % 10]

一个 Trick，充分利用了题目规则。

Review

React Higher-Order Components

从这篇文章里可以学到：

什么是 HOC
为什么需要 HOC
HOC 的缺陷

什么是 HOC

HOC 的概念是函数式编程 Higher-Order Function（高阶函数）的变种。先看一段代码：

function add (x, y) {
  return x + y
}

function addFive (x, addReference) {
  return addReference(x, 5)
}

addFive(10, add) // 15

这段代码用到了两个概念：

回调函数 - 函数 add 作为参数传递给了 addFive，add 即是回调函数
高阶函数 - addFive 作为函数接收了另一个函数参数，addFive 即是高阶函数

高阶函数的应用：

function add (x, y) {
  return x + y
}

function makeAdder (x, addReference) {
  return function (y) {
    return addReference(x, y)
  }
}

const addFive = makeAdder(5, add)
const addTen = makeAdder(10, add)
const addTwenty = makeAdder(20, add)

addFive(10) // 15
addTen(10) // 20
addTwenty(10) // 30

高阶函数可以让我们提高代码的重用性，并借助高阶函数创建出更多方便好用的函数（如一元函数）。

总结下什么是高阶函数：

是一个函数
接收一个回调函数参数
返回一个新函数
这个新函数会调用原始的回调函数

function higherOrderFunction (callback) {
  return function () {
    return callback()
  }
}

高阶组件与之对应：

是一个组件
接收一个组件参数
返回一个新组件
这个新组件能渲染原始的组件

function higherOrderComponent (Component) {
  return class extends React.Component {
    render() {
      return <Component />
    }
  }
}

为什么需要 HOC

HOC 通过将相关逻辑封装进一个组件，提高了内聚性，并重用这个组件来提高代码的重用性
得到了函数式编程的体验

HOC 的缺陷

嵌套地狱 - HOC 的封装粒度要低，在需要多个状态的情况下会带来嵌套地狱的问题
命名冲突 - 有 Props 命名冲突的潜在风险

Tip

Python3 中检查一个对象的内存使用：

import sys
x=1
print(sys.getsizeof(x))

#-> 28

如何才能拥有技术领导力

吃透基础技术，基础技术是各种上层技术的基石
- 学习 C 语言，C 语言更接近底层，有助于更好的理解和思考
- 学习编程范式，有助于培养抽象思维，提高编程、程序运行效率
- 关注算法和数据结构，算法是编程中最重要的东西
- 了解计算机系统原理，推荐书籍《深入理解计算机系统》
- 了解操作系统原理和基础，推荐书籍《UNIX 系统环境编程》、《UNIX 网络编程》和《Windows 核心编程》，了解物理世界的“物理定律”
- 学好网络基础，推荐书籍《TCP/IP详解》
- 学好数据库原理，了解数据库访问性能调优的要点
- 学习分布式技术架构，
提高学习能力
- 好的基础才能提高学习能力
- 信息源要好
- 与高手交流
- 举一反三的思考，如对比不同语言之间的线程模型等
- 克服困难的决心
- 开放的心态，了解方案之间的利弊与优缺点
坚持做正确的事
- 提高效率的事
- 自动化的事
- 掌握前沿技术的事
- 知识密集型的事
- 技术驱动的事
严格要求自己
- 要有敏锐的技术嗅觉
- 强调实践，学以致用
- Lead by Example，不断实践，保持对技术细节的敏感度