ARTS-2018-12-02

Algorithm

Roman to Integer

罗马数转阿拉伯数字。罗马数字是通过有限个字母，组合成各种数字，关键在于理解其计数逻辑：

1. 相同的数字连写、所表示的数等于这些数字相加得到的数、如：Ⅲ=3；
2. 小的数字在大的数字的右边、所表示的数等于这些数字相加得到的数、 如：Ⅷ=8、Ⅻ=12；
3. 小的数字（限于 I、X 和 C）在大的数字的左边、所表示的数等于大数减小数得到的数、如：Ⅳ=4、Ⅸ=9；
4. 正常使用时、连写的数字重复不得超过三次；
5. 在一个数的上面画一条横线、表示这个数扩大 1000 倍。

根据逻辑可以推出把字符分成2类即可：加数和减数。

判断一个数是否是减数，需要依赖它后面的数字是否比他大。处理上我们可以先认为当前数为加数，延迟到下个字符时再判定其是否是减数，如果是则减去其2倍即可。

result = result + currentNumber
if currentNumber > lastNumber {
    result -= lastNumber * 2
}

lastNumber = currentNumber

Longest Common Prefix

最长公共前缀。分治法即可，结果一定是最短字符串的子串。

func commonPrefix(strs []string) string {
	stringListLength := len(strs)

	if (stringListLength == 1) {
		return strs[0]
	}

	middle := int(stringListLength / 2)

	leftPrefix := commonPrefix(strs[0:middle])
	rightPrefix := commonPrefix(strs[middle:stringListLength])

	maxPrefixLength := math.Min(float64(len(leftPrefix)), float64(len(rightPrefix)))

	prefix := ""

	for i := 1; i <= int(maxPrefixLength); i++ {
		if (leftPrefix[0:i] == rightPrefix[0:i]) {
			prefix = leftPrefix[0:i]
		}
	}

	return prefix
}

Valid Parentheses

检验括号是否有效。和 Two Sum 类似，思路都是找自己匹配的对象。但是区别在于，这次必须得全部都找到匹配的对象才算通过，并且这次限制了匹配顺序关系，即有些元素（左括号）必须“等着“后面的人来找他，还有位置顺序关系，即匹配对象间不能有“单身狗”?（"([)]"这样不行，这样可以"{[]}"）。

因为涉及到位置顺序，所以用栈来实现是比较理想的。凡是左括号，就入栈等着别人来翻牌子，遇到右括号就去栈里找自己匹配的对象，因为栈里面都是单身狗，所以你只能找第一元素，如果匹配皆大欢喜，如果不匹配，那就GG了。

因为找不到只有2种情况：

1. 匹配的对象不在栈里，因为“匹配顺序”要求，就再也没有元素能与之匹配了
2. 匹配的对象不在第一位，因为“位置顺序”要求，匹配对象之间至有了一只单身狗（栈里第一位元素）

func isValid(s string) bool {
	parentheses := map[rune]rune{')': '(', ']': '[', '}': '{'}
	var stack []rune

	for _, char := range s {
		if char == '(' || char == '[' || char == '{' {
			stack = append(stack, char)
		} else if len(stack) > 0 && parentheses[char] == stack[len(stack)-1] {
			stack = stack[:len(stack)-1]
		} else {
			return false
		}
	}

	return len(stack) == 0
}

Review

How to think like a programmer — lessons in problem solving

如何培养解决问题的能力？

Everyone in this country should learn to program a computer, because it teaches you to think.

 — Steve Jobs

解决问题的能力本身是一项通用能力，你可以有很多方式去培养它，本篇是通过编程的角度来描述，但是要注意到编程只是方式之一，并不是唯一方式。

1. 明白问题到底是什么。

   这步很关键，很多时候你看到的只是表象，很多原因都会导致同一个结果。

   比如服务器报错500了，这个时候你的第一反应是啥？直接搜索 "Internal Server Error 500" ？那样你会得到五花八门的答案，各种原因都有， 你一个个去尝试，一个个去解决，可能过程中又会遇到其他问题，解决路径会变得很深，那样会浪费很多时间和精力，导致问题更加复杂化。

   你应该清楚知晓整个流程，知道整个链路上的交互式是什么样的，这样你就能知道问题可能发生在哪些节点，有针对性的去查询。那如何明白整个链路流程呢？

   尝试用自己的话来描述它 ，要尽量简洁明了，比如橡皮鸭方法；或者画一个流程图，帮助自己树立其脉络。

   当你清楚问题发生的地方的时候，就可以对症下药，开始解决它了。

2. 选择合适的解决方案。

   明白问题后，应该会有很多种不同的解决方案。它们彼此之间可能并不互斥，但是应该选择符合场景的最优解。 比如要支持用户发送 emoji 内容。短期解决方案是 RD 在代码逻辑上对 emoji 存取进行转换编码，长期方案是 DBA 修改 MySQL 存储配置支持 utf8mb4 编码。哪种方案更好，都是相对的，应该根据你面对的情况来进行评估，甚至可以并行。

3. 细化解决方案。

   所有解决方案都可以被划分成更细粒度的解决方案。第二步只是有了一个整体解决方案，但是方案的实施，必然会有很多细节，这个时候需要细化解决方案，有规划的完成方案的实施，特别是那些复杂的解决方案。当你把解决方案细化之后，解决方案会更精准，同时也会更简单。

   还是支持 emoji 的方案。如果选择短期方案和长期方案并行，可以细化成几个子问题：

   1. 梳理出哪些地方会涉及到 emoji，比如内容、标题、昵称，而生日、性别这些就不会涉及到
   2. 评估字符集变更后会造成的存储压力，主从同步影响，可能这步由 DBA 来完成
   3. 代码逻辑上支持 emoji 的识别、编码、解码
   4. 当存储支持 emoji 后，需要关闭代码 emoji 的编码逻辑，需要一个灰度控制
   5. 当关闭代码 emoji 的编码逻辑后，已编码存储的数据是否需要脚本刷回
   6. 当已存储数据被刷回后，下掉代码逻辑上对 emoji 的识别、解码

4. 灵活变通

   但遇到某个无法解决的问题，不要死命坚持。条条大路通罗马，可以尝试换个角度思考，当你换个角度的时候，可能产生“降维打击“的效果。这种样的情况在数学、逻辑的知识上的体现会更多点。

仍然要强调的一点是，解决问题的能力是一项软技能，可以将上述方法应用于自己所处的工作领域，而不仅仅是编程领域。

Tip

forward_static_call_array

forward_static_call_array将静态上下文转发到所调用的方法，而call_user_func_array则不。

class A {
    const NAME = 'A';
    public static function test() {
        $args = func_get_args();
        echo static::NAME, " ".join(',', $args)." \n";      // Will echo B
    }
}

class B extends A {
    const NAME = 'B';
    public static function test() {
        echo self::NAME, "\n";          // B
        forward_static_call_array(array('A', 'test'), array('more', 'args'));
    }
}

B::test('foo');
//B 
//B more,args

class B extends A {
    const NAME = 'B';
    public static function test() {
        echo self::NAME, "\n";          // B
        call_user_func_array(array('A', 'test'), array('more', 'args'));
    }
}
//B
//A more,args

Share

mycli

这是一个支持自动补全和语法高亮的 MySQL 命令行工具。