Math

题型总结

第一种类型是最简单的， 就是对整数进行直接操作， 一般来说就是逐位操作， 比如反转， 比较等。

第二种题型是算术运算的题目， 比如乘除法， 阶乘， 开方等， LeetCode中这类题目有Sqrt(x)， Pow(x, n)和Divide Two Integers。 这种题目有时候看似复杂， 其实还是有几个比较通用的解法的， 下面主要介绍三种方法：

  1. 二分法
  2. 牛顿法
  3. 位移法

第三种题目是解析几何的题目， 一般来说解析几何题目的模型都比较复杂， 而且实现细节比较多， 在面试中并不常见， LeetCode中也只有Max Points on a Line是属于这种题型。

题目列表

二分法

  • sqrt(x)
  • pow(x, n)

basic concept

  • palindrome number

  • reverse integer

  • add binary

  • add digits

  • plus one

  • multiply strings

  • trailing zeros
  • max points on a line
  • ugly number
  • ugly number II
  • happy number
  • Gray code (递归的规律)
  • valid number(hard,状态转化图重要)

string 2 number, number 2 string

  • atoi
  • roman to integer
  • integer to roman

其他

  • gray code
  • permutation sequence

Reference