跳转至

总结和技巧

一般步骤

  1. 读懂题目
  2. 确定输入、输出
  3. 确认输入值的范围、条件
  4. 思路
  5. 想一下大致思路
  6. 分析时空复杂度，注意递归的栈 stack 空间
  7. 分类列举各种情况（含边缘条件）
  8. 还有没有更好的方法
  9. 复杂的情况要列举
  10. 跑一下例子，看思路对不对
  11. 这个时候思路不清楚、不跑一下、不想全情况的话，写了错误的代码再改就难了！
  12. 写代码
  13. 不一定按顺序，可以先搭个大框架、步骤，再填充细节
  14. 检查
  15. 厘清容易错的循环判断条件等
  16. 白板的话要自己手动跑一遍
  17. 再确认一下复杂度
  18. 分析总结
  19. 可能的缺陷、改进
  20. 更好的办法

Tips

  1. Logarithm (对数)

log10(x) = ln(x) / ln(10)

loga(b) = ln(b) / ln(a)

log(a * b) = log(a) + log(b)

log(a / b) = log(a) - log(b)

  1. How many digits does a number have?

For positive integers, floor(log10(n)) + 1.

For all integers?

function number_of_digits(n):
  if n = 0:
    return 1
  else:
    return floor(log10(abs(n))) + 1
  1. When using two pointers, what would the index of the number we need to fill given the pointers' indices as l and r, if we are filling numbers from the start or from the end respectively?

Forward: It would be n - 1 + l - r because there are l + (n - 1 - r) = n - 1 + l - r numbers already filled, and the next number is at index n - 1 + l - r.

Backward: It would be r - l because there are r - l + 1 numbers waiting to be filled and the r - l + 1th number is at index r - l.

You can use a variable to track it if you don't remember.

  1. When using two pointers, it is good to maintain a meaning of the pointers. For example, l is the next the position to write, r is the biggest number when have found so far. It makes the code meaningful and often simpler.

  2. When the algorithm needs to manually handle many edge cases, your idea might be wrong.

他山之石