其他 刷题的几个实用建议

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

随着秋招热度的减退, 下一季准备求职的同学已经开始着手刷算法题夯基础了。下面提供一些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 }
暂无回复。
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册