其他 刷题的几个实用建议

arth · 2016年11月02日 · 7136 次阅读

随着秋招热度的减退,下一季准备求职的同学已经开始着手刷算法题夯基础了。下面提供一些 tips,希望对刷题的朋友有帮助。

一、明确输入输出

包括 1) 明确数据类型 or null;2)取值范围(如数字是否为正整数); 3) corner case

拿到题目后,先明确输入输出类型,并考虑几个典型的 case 以便于分析。有思路之后,需要考虑潜在 corner case。 Leetcode 上的 word break 一题,如果考虑不到字符串为"wwwwwwwwww.....wwwwwwwwwww",字典为 ['w','ww',...,'wwwwwwww...w'] 的情形,直接搜索会导致中间状态过多而超时。

二、尽情使用 map, reduce, select, reject

能使用 map, reduce, select, reject 就尽量避免 nums.each, x.times do 类型的迭代。这会帮你精简大量的无效代码并减少踩坑。 下面是一个对树进行层序遍历的例子。

def level_order(root)
  queue, result = [root], []
  while queue.any?
    result << queue.map(&:val)
    queue.map! { |node| [node.left, node.right].compact }.flatten!
  end
  result
end

三、把分支语句尽可能提取出循环体,减少执行开销。

有一个同学曾这样写一个关于链表的解法:

def method_list(head)
new_head = nil
node = head
last_node =nil
while node
  if condition
    new_head ? last_node.next = node : new_head = node
...
....

这里,他判断当前节点符合条件时,需要加入结果中。由于头结点可能不存在,他每一次循环都进行了对头结点判空再做处理。这个分支语句的执行成本是 O(n),但仅实现了为头结点赋值。 在链表类题目中,一般通过使用哑(dummy) 节点来避免这种情况。

四、Debug

1)注意与语言特性相关的坑:负数除法的实现

cond = -10/3 == -3 这个语句在在 ruby、python 中均为真,但在 java 中为假。java 让结果更偏向于 0,而 ruby、python 更倾向于将结果偏向负无穷大。

2)在链式方法调用中对数组使用 tap 快速查看内容。 例子如下:

(1..10).to_a.map{ |i| i * i - 4 * i + 3 }.tap{ |i| puts i }.min

五、减少中间变量

中间变量越多,代码量越大,出错概率也越高。例如,对需要根据数组的大小进行循环操作。常见的写法是下面例子中的 bad 写法。一些人认为 ary.length 可能会变化,在循环过程中可能会执行多次。经实验,该方法并不会在循环过程中执行多次。

#bad
len =  ary.length
len.times do {|i| #somthing }

# good
ary.length.times { |i| # something }
暂无回复。
需要 登录 后方可回复, 如果你还没有账号请 注册新账号