ARTS-2018-12-02
ARTS-2018-12-02
Algorithm
罗马数转阿拉伯数字。罗马数字是通过有限个字母,组合成各种数字,关键在于理解其计数逻辑:
- 相同的数字连写、所表示的数等于这些数字相加得到的数、如:Ⅲ=3;
- 小的数字在大的数字的右边、所表示的数等于这些数字相加得到的数、 如:Ⅷ=8、Ⅻ=12;
- 小的数字(限于 I、X 和 C)在大的数字的左边、所表示的数等于大数减小数得到的数、如:Ⅳ=4、Ⅸ=9;
- 正常使用时、连写的数字重复不得超过三次;
- 在一个数的上面画一条横线、表示这个数扩大 1000 倍。
根据逻辑可以推出把字符分成2类即可:加数和减数。
判断一个数是否是减数,需要依赖它后面的数字是否比他大。处理上我们可以先认为当前数为加数,延迟到下个字符时再判定其是否是减数,如果是则减去其2倍即可。
result = result + currentNumber
if currentNumber > lastNumber {
result -= lastNumber * 2
}
lastNumber = currentNumber
最长公共前缀。分治法即可,结果一定是最短字符串的子串。
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
}
检验括号是否有效。和 Two Sum 类似,思路都是找自己匹配的对象。但是区别在于,这次必须得全部都找到匹配的对象才算通过,并且这次限制了匹配顺序关系,即有些元素(左括号)必须“等着“后面的人来找他,还有位置顺序关系,即匹配对象间不能有“单身狗”?("([)]"这样不行,这样可以"{[]}")。
因为涉及到位置顺序,所以用栈来实现是比较理想的。凡是左括号,就入栈等着别人来翻牌子,遇到右括号就去栈里找自己匹配的对象,因为栈里面都是单身狗,所以你只能找第一元素,如果匹配皆大欢喜,如果不匹配,那就GG了。
因为找不到只有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
解决问题的能力本身是一项通用能力,你可以有很多方式去培养它,本篇是通过编程的角度来描述,但是要注意到编程只是方式之一,并不是唯一方式。
-
明白问题到底是什么。
这步很关键,很多时候你看到的只是表象,很多原因都会导致同一个结果。
比如服务器报错500了,这个时候你的第一反应是啥?直接搜索 "Internal Server Error 500" ?那样你会得到五花八门的答案,各种原因都有, 你一个个去尝试,一个个去解决,可能过程中又会遇到其他问题,解决路径会变得很深,那样会浪费很多时间和精力,导致问题更加复杂化。
你应该清楚知晓整个流程,知道整个链路上的交互式是什么样的,这样你就能知道问题可能发生在哪些节点,有针对性的去查询。那如何明白整个链路流程呢?
尝试用自己的话来描述它 ,要尽量简洁明了,比如橡皮鸭方法;或者画一个流程图,帮助自己树立其脉络。
当你清楚问题发生的地方的时候,就可以对症下药,开始解决它了。
-
选择合适的解决方案。
明白问题后,应该会有很多种不同的解决方案。它们彼此之间可能并不互斥,但是应该选择符合场景的最优解。
比如要支持用户发送 emoji 内容。短期解决方案是 RD 在代码逻辑上对 emoji 存取进行转换编码,长期方案是 DBA 修改 MySQL 存储配置支持 utf8mb4 编码。哪种方案更好,都是相对的,应该根据你面对的情况来进行评估,甚至可以并行。 -
细化解决方案。
所有解决方案都可以被划分成更细粒度的解决方案。第二步只是有了一个整体解决方案,但是方案的实施,必然会有很多细节,这个时候需要细化解决方案,有规划的完成方案的实施,特别是那些复杂的解决方案。当你把解决方案细化之后,解决方案会更精准,同时也会更简单。
还是支持 emoji 的方案。如果选择短期方案和长期方案并行,可以细化成几个子问题:
- 梳理出哪些地方会涉及到 emoji,比如内容、标题、昵称,而生日、性别这些就不会涉及到
- 评估字符集变更后会造成的存储压力,主从同步影响,可能这步由 DBA 来完成
- 代码逻辑上支持 emoji 的识别、编码、解码
- 当存储支持 emoji 后,需要关闭代码 emoji 的编码逻辑,需要一个灰度控制
- 当关闭代码 emoji 的编码逻辑后,已编码存储的数据是否需要脚本刷回
- 当已存储数据被刷回后,下掉代码逻辑上对 emoji 的识别、解码
-
灵活变通
但遇到某个无法解决的问题,不要死命坚持。条条大路通罗马,可以尝试换个角度思考,当你换个角度的时候,可能产生“降维打击“的效果。这种样的情况在数学、逻辑的知识上的体现会更多点。
仍然要强调的一点是,解决问题的能力是一项软技能,可以将上述方法应用于自己所处的工作领域,而不仅仅是编程领域。
Tip
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
这是一个支持自动补全和语法高亮的 MySQL 命令行工具。
本作品由 程小白 创作,采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可,可自由转载、引用但需署名作者且注明文章出处。
原文地址:https://www.chengxiaobai.cn/arts/20181202.html