Leetcode 中的数学类题目

这里不探讨涉及到二分法的数学题 （详见 Leetcode Array 中的 Binary Search II 一文）。 这里讲的题目大部分都和某些数学概念有关，只要搞清了这些数学概念，题目就迎刃而解了。
1. Reverse Integer
此题主要考/和%的用法。 /取高位，%取低位。注意整数越界判断
2. String to Integer
此题考点与上题类似， 多了些corner case： ' ', +/-. bigger than INT_MAX, smaller than INT_MIN

3. Palindrome Number
考点类似。/取高位，%取低位。 注意%10总是取到最低位，但%div 取最高位时，div是跟着当前数字变化的（依次缩小十倍）。 因此需要有一个变量div记录当前最高位。

4. Integer to Roman
此题考罗马数字原理。不懂的话肯定是写不出来，但看到面经这题概率还不小，因此需要记一下简单的罗马数字原理。（来自wiki） 羅馬數字共有7個，即I（1）、V（5）、X（10）、L（50）、C（100）、D（500）和M（1000）

在較大的羅馬數字的右邊記上較小的羅馬數字，表示大數字加小數字。

在較大的羅馬數字的左邊記上較小的羅馬數字，表示大數字减小數字。

左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV

左減數字必須為一位，比如8寫成VIII，而非IIX。

右加數字不可連續超過三位，比如14寫成XIV，而非XIIII

这道题题目输入1-3999，简化了计算。通过观察，阿拉伯数字的各位可以由I V X 搞定，十位可以由XLC搞定，百位由CDM搞定。因此可以有一个变量base初始化为0，阿拉伯数字没增一位base增2. 剩下的部分每一个位上其实是一样的。比如 8=VIII, 80=LXXX, 800=DCCC. 这允许我们又一次利用/ %同样的方法来对待每一位。

5. Roman to Integer

这题比上题要更简单一些，做法是从低位（string的末端）开始向前扫描，若当前位的罗马数字大于等于它后面的那一位，两者相加，否则两者相减
6. Plus One
先判断最后一位是否是9，如果不是直接加一返回。否则从倒数第二位开始检查，如果当前位不是9，那么加一返回，否则置为零检查前一位。如果前面位都是9，则需要增加一位放到最前面
7.Add Binary
思路很简单，从最后一位开始加直到任意一个数组到头，继续加剩下一个数组其余部分。注意模取余都是以2为底。
8. Valid Number 这题是数学类题目中最难的，难不是因为算法，而是状态转化图。 我认为这题最重要的是和面试官讨论状态图，代码很简单。注意终止状态只能是数字或者空格。其他一律非法。 代码不贴了，参考http://discuss.leetcode.com/questions/241/valid-number
9. Multiply Strings
笔算乘法的方法。Str1的最后一位和Str2的每一位相成，记录下进位： 10. Permutation Sequence Example n=3, k=3. str="123",fac=[1,1,2,6]. 第一个数字是str[2/2]=2,str="13";第二个数字是str[0/1]=1, str="3";第三个数字是str[0/1]=3; 11. Gray Code The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given n = 2, return [0,1,3,2]. Its gray code sequence is: 00, 01, 11, 10 规律是 [0]+1->[1], [1,0]+2->[3,2]. [2,3,1,0]+4=[6,7,5,4] i.e. n=k时的Gray Code，相当于n=k-1时的Gray Code的逆序 加上 pow(2,k-1)。