Leetcode Math问题

https://lefttree.gitbooks.io/leetcode-categories/content/Math/index.html

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

Math without Operator

类型描述

这类题目一般是指进行数学运算，但不要使用operator， 比如除法不要使用/, , %; 加法不要使用+,/,,-

题目列表

解题方法

这种类型的题目，一般都往bit manipulation方向想

• 对于乘除的题目， << 1是乘以2， >> 1是除以2。
• 对于加减的题目，a ^ b是sum, a & b是得到carry

注意点

• 正负数的问题
• 是否会overflow的问题（虽然对于Python不会，但是可以跟面试官提一下）

signed 32int integer的range是-2147483648 - 2147483647

题目列表

• Divide Two Integers
• A + B Problem
• multiply two integers