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 命令行工具。

mycli

本文由程小白创作,本文可自由转载、引用,但需署名作者且注明文章出处。

原文地址:https://www.chengxiaobai.cn/arts/20181202.html