[LeetCode] Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

思路：

解这个平面几何题有3个要点：

1. 如何判断共线?

两点成一直线，所以两点没有共线不共线之说。对于点p1(x1, y1)，p2(x2, y2)，p3(x3, y3)来说，共线的条件是p1-p2连线的斜率与p1-p3连线的斜率相同，即

(y2-y1)/(x2-x1) = (y3-y1)/(x3-x1)

所以对共线的n点，其中任意两点连线的斜率相同。

2. 如何判断最多的共线点?

对于每个点p出发，计算该点到所有其他点qi的斜率，对每个斜率统计有多少个点符合。其中最多的个数加1（出发点本身）即为最多的共线点。

3. 特殊情况

当x1 = x2，y1!=y2时，为垂直连线。计算斜率时分母为0会出错。

当x1 = x2，y1 = y2时，两点重合。则(x2, y2)和所有(x1, y1)的连线共线。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { public: int maxPoints(vector<Point> &points) { int maxPts = 0; for(int i=0; i<points.size(); i++) { int nMax = 0, nSame = 0, nInf = 0; unordered_map<float,int> comSlopes; for(int j=i+1; j<points.size(); j++) { if(points[j].x==points[i].x) { if(points[j].y==points[i].y) nSame++; else nInf++; continue; } float slope = (float)(points[j].y-points[i].y)/(float)(points[j].x-points[i].x); comSlopes[slope]++; nMax = max(nMax, comSlopes[slope]); } nMax = max(nMax, nInf)+nSame+1; maxPts = max(maxPts,nMax); } return maxPts; } };

[LeetCode] Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

思路：

同样先通过举例来获得更好的理解。以n = 4，k = 9为例：

1234

1243

1324

1342

1423

1432

2134

2143

2314  <= k = 9

2341

2413

2431

3124

3142

3214

3241

3412

3421

4123

4132

4213

4231

4312

4321

最高位可以取{1, 2, 3, 4}，而每个数重复3! = 6次。所以第k=9个permutation的s[0]为{1, 2, 3, 4}中的第9/6+1 = 2个数字s[0] = 2。

而对于以2开头的6个数字而言，k = 9是其中的第k' = 9%(3!) = 3个。而剩下的数字{1, 3, 4}的重复周期为2! = 2次。所以s[1]为{1, 3, 4}中的第k'/(2!)+1 = 2个，即s[1] = 3。

对于以23开头的2个数字而言，k = 9是其中的第k'' = k'%(2!) = 1个。剩下的数字{1, 4}的重复周期为1! = 1次。所以s[2] = 1.

对于以231开头的一个数字而言，k = 9是其中的第k''' = k''/(1!)+1 = 1个。s[3] = 4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: string getPermutation(int n, int k) { string ret; vector<int> factorial(n,1); vector<char> num(n,1); for(int i=1; i<n; i++) factorial[i] = factorial[i-1]*i; for(int i=0; i<n; i++) num[i] = (i+1)+'0'; k--; for(int i=n; i>=1; i--) { int j = k/factorial[i-1]; k %= factorial[i-1]; ret.push_back(num[j]); num.erase(num.begin()+j); } return ret; } };

[LeetCode] Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

思路：

这题概念上很简单，有几种方法可以做。比如将每个[i, j]对应旋转对称的四个点的坐标算出来，然后pixel by pixel的旋转。但个人感觉这种计算面试中比较容易出错。想了看了几种方法后，觉得“剥洋葱”法一层一层地旋转最容易理解和写对。注意这里offset的使用以及中止条件start<end。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public: void rotate(vector<vector<int> > &matrix) { int start = 0, end = matrix.size()-1; while(start<end) { for(int i=start; i<end; i++) { // rotate a layer int offset = i - start; int temp = matrix[start][i]; matrix[start][i] = matrix[end-offset][start]; matrix[end-offset][start] = matrix[end][end-offset]; matrix[end][end-offset] = matrix[start+offset][end]; matrix[start+offset][end] = temp; } start++; end--; } } };

[LeetCode] Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

思路：

做过Plus One，Add Binary等题后，这类按位运算的题就是一个葫芦里的药了。按照最原始的按位相乘，最后移位相加的法则来计算。

      3 2 1

x       4 3

_______

      9 6 3

1 2 8 4

_______

1 3 8 0 3

注意：

1. m位的数字乘以n位的数字的结果最大为m+n位：

999*99 < 1000*100 = 100000，最多为3+2 = 5位数。

2. 先将字符串逆序便于从最低位开始计算。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public: string multiply(string num1, string num2) { if(num1.empty() || num2.empty()) return ""; reverse(num1.begin(),num1.end()); reverse(num2.begin(),num2.end()); string ret(num1.size()+num2.size(),'0'); for(int j=0; j<num2.size(); j++) { int carry = 0; int val = num2[j] - '0'; for(int i=0; i<num1.size(); i++) { carry += ((num1[i]-'0')*val + (ret[i+j]-'0')); ret[i+j] = carry%10 + '0'; carry /= 10; } if(carry!=0) ret[num1.size()+j] = carry + '0'; } reverse(ret.begin(),ret.end()); int count = 0; while(count<ret.size()-1 && ret[count]=='0') count++; ret.erase(0,count); return ret; } };

总结：

题目虽然不难。要完全写对也不容易。
1. 首先要注意num1[i] * num2[j]的结果应该加到ret[i+j]的位置上。
2. 其次要注意ln 17不能遗漏最高位的进位，由于此时ret中该位为0，所以只需要将carry转为字符即可。
3. 最容易遗漏的corner case是ln 22-24。如999*0 = 0000，此时需要去掉开始的0，但又需要保留最后一个0。

[LeetCode] Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

思路：

Integer to Roman那题的follow up。关键还是解决例如IV = 4的subtractive notation的情况。可以用与Integer to Roman那题一样的思路扩展罗马字符到字符组合：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: int romanToInt(string s) { string dict[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}; int num[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1}; int i=0, index=0, ret=0; while(i<s.size() && index<13) { string target = dict[index]; string cur = s.substr(i,target.size()); if(cur==target) { ret += num[index]; i += target.size(); } else { index++; } } return ret; } };

更简洁清楚的解法：
找下subtractive notation的规律，以简单的例子s = IX 说明。
1. 如果按照additive性质的话应该ret = 1+10 = 11。但因为num(X)=10>num(I)=1，ret = 10 - 1。
2. 将subtractive rule转换成等效的additive rule：ret = 1 + (10 - 2*1)

建立一个罗马字符对应整数的hash table ht。
当ht[s[i]] > ht[s[i-1]]，即为subtractive nontation：ret += (ht[s[i]] - 2*ht[s[i-1]])
否则为additive nontation：ret+=ht[s[i]]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: int romanToInt(string s) { if(s.empty()) return 0; unordered_map<char,int> ht({{'I',1}, {'V',5}, {'X',10}, {'L',50}, {'C',100}, {'D',500}, {'M',1000}}); int ret = 0; for(int i=0; i<s.size(); i++) { if(ht.count(s[i])==0) return 0; ret += ht[s[i]]; if(i!=0 && ht[s[i]]>ht[s[i-1]]) ret -= 2*ht[s[i-1]]; } return ret; } };

[LeetCode] Integer to Roman

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

思路：

这题需要一些背景知识，首先要知道罗马数字是怎么表示的：

http://en.wikipedia.org/wiki/Roman_numerals

I: 1
V: 5
X: 10
L: 50
C: 100
D: 500
M: 1000

字母可以重复，但不超过三次，当需要超过三次时，用与下一位的组合表示：
I: 1, II: 2, III: 3, IV: 4
C: 100, CC: 200, CCC: 300, CD: 400

s = 3978

3978/1000 = 3: MMM

978>(1000-100), 998/900 = 1: CM

78<(100-10), 78/50 = 1 :L

28<(50-10), 28/10 = XX

8<(100-1), 8/5 = 1: V
3<(5-1), 3/1 = 3: III

ret = MMMCMLXXVIII

所以可以将单个罗马字符扩展成组合形式，来避免需要额外处理类似IX这种特殊情况。

I: 1

IV: 4
V: 5

IX: 9
X: 10

XL: 40
L: 50

XC: 90
C: 100

CD: 400
D: 500

CM: 900
M: 1000

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public: string intToRoman(int num) { string dict[13] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}; int val[13] = {1000,900,500,400,100,90,50,40,10,9,5,4,1}; string ret; for(int i=0; i<13; i++) { if(num>=val[i]) { int count = num/val[i]; num %= val[i]; for(int j=0; j<count; j++) { ret.append(dict[i]); } } } return ret; } };

[LeetCode] Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

思路：

检查回文最直接的方法是将整数转换成字符串，然后用Valid Palindrome那题的算法来检查。但是这么做需要有额外内存。

另一种思路是利用Reverse Integer的算法反转整数，对于回文来说，反转后的整数应该与原整数相同。如果反转时overflow则一定不是回文。这里需要明确负数到底算不算回文。解中假设不算。

1 2 3 4 5 6 7 8 9 10 11 12 13

class Solution { public: bool isPalindrome(int x) { if(x<0) return false; int res=0, y=x; while(y) { if(abs(res)>(INT_MAX/10)) return false; res = res * 10 + y % 10; y /= 10; } return res==x; } };

网上找到另一个解法：

比较最高位与最低位的数字：如果不同则不是回文，如果相同，则去掉最高和最低位，继续判断。直到所有位数字都被去掉，则一定是回文。关键点在于，如何取出最高和最低位的数字？比较之后如何去掉？

以x = 2332为例：最高位为L，最低位为R
L = 2332/1000 = 2
R = 2332%10 = 2

L = R所以要去掉最高最低位继续判断：令y = 1000
2332 % y = 332
332 / 10 = 33
x = (x%y)/10 = 33

如何继续取出最高位？由于删除了两位，y = y/100 = 10
L = 33/10 = 3
R = 33%10 = 3

L = R所以继续去掉最高最低位：
x = (33%10)/10 = 0

x = 0标志了判断结束。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { public: bool isPalindrome(int x) { if(x<0) return false; int y = 1; while(x/y>=10) y *= 10; while(x) { if(x/y != x%10) return false; x = (x % y)/10; y /= 100; } return true; } };

[LeetCode] Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

思路:

凡是整数操作类的题目，都需要注意几类情况：

1. 整数为负数。

2. 整数为0或者数字中含有0的情况。

3. 是否可能溢出。

具体到这题：

1. 负数情况可以先记录符号，并转为正数

2. x = 10, return 1

3. x的reverse很可能大于INT_MAX或小于INT_MIN。需用一个unsigned long long来存储x。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: int reverse(int x) { unsigned long long xx; if(x==INT_MIN) xx = (unsigned long long)INT_MAX+1; else xx = x<0 ? -x : x; unsigned long long res = 0; while(xx) { res = (res*10) + (xx%10); xx /= 10; } if((res>(unsigned long long)INT_MAX && x>0) || (res>(unsigned long long)INT_MAX+1 && x<0)) return 0; return x<0 ? -res : res; } };

网上参考的一个更优解：

1 2 3 4 5 6 7 8 9 10 11 12 13

class Solution { public: int reverse(int x) { int ret = 0; while (x != 0) { // handle overflow/underflow if (abs(ret) > 214748364) return 0; ret = ret * 10 + x % 10; x /= 10; } return ret; } };

由于INT_MAX = 2147483647, INT_MIN = -21474836478
如果ret > 214748364，那么abs(ret*10)>=2147483650一定会overflow。
反之如果ret = 214748364，则一定有x % 10 = 1。若x%10 = 2，则原来的x = 2463847412 > INT_MAX，与输入参数为int类型矛盾。

[LeetCode] Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

思路：

又是逐位加法，和Add Two Numbers以及Add Binary两题类似。需要注意最低最高位的顺序以及进位的处理。

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public: vector<int> plusOne(vector<int> &digits) { int carry = 1; vector<int> res(digits.size(),0); for(int i=digits.size()-1; i>=0; i--) { carry += digits[i]; res[i] = carry%10; carry /= 10; } if(carry) res.insert(res.begin(),1); return res; } };

[LeetCode] Divide Two Integers

Divide two integers without using multiplication, division and mod operator.


思路:

整数近似除法：32/3 = 10

显然求近似除法可以用乘法来二分查找：32 ~ 3*10 = 3*[1*(2^3) + 0*(2^2) + 1*(2^1) + 0*(2^0)]

res = 0

1. 先找到a使x*2^a <= y < x*2^(a+1)，res += 2^a，y = y - x*2^a

2. if(y >= x*2^(a-1) {res+=2^(a-1); y = y - x*2^(a-1);}

3. if(y >= x*2^(a-2) {res+=2^(a-2); y = y - x*2^(a-2);}

...

但题目不允许用乘法，可以用移位代替：x*2^i = x<<i：

corner case，非常重要：

(1) x, y可能会是负数
(2) x可能为0时，返回INT_MAX或INT_MIN
(3) INT_MIN / -1 > INT_MAX，overflow

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { public: int divide(int dividend, int divisor) { if(!divisor) return dividend>=0 ? INT_MAX : INT_MIN; if(dividend==INT_MIN && divisor==-1) return INT_MAX; //overflow problem bool isNeg = false; if((dividend<0 && divisor>0) || (dividend>0 && divisor<0)) isNeg = true; unsigned long long dvd = abs((long long)dividend); unsigned long long dvs = abs((long long)divisor); unsigned long long dvs_original = dvs; int i = 0; while(dvs<<(i+1) <= dvd) i++; int res = 0; while(dvd>=dvs_original) { if(dvd >= dvs<<i) { dvd -= dvs<<i; res += 1<<i; } i--; } return isNeg ? 0-res : res; } };

总结：

这题要考虑到所有corner case并写对不容易。另外还有一个非常容易犯错的地方：

找到a使x*2^a <= y < x*2^(a+1)，这一步对应程序里的while(dvs<<(i+1) <= dvd) i++;

这里dvs和dvd必须将原来的dividend和divisor转化成unsigned long long类型。不然divisor左移时可能会变成负数从而陷入死循环。

[LeetCode] Pow(x, n)

Implement pow(x, n).

思路1：利用整数n的二进制表达
性质：(x^y)^z = x^(y*z)
例如：(5^3)^2 = 5^3 * 5^3 = 5^(3*2)

10: 二进制(1010)b = (2^3)*1 + (2^2)*0 + (2^1)*1 + (2^0)*0
3^10 = 3^[(2^3)*1] * 3^[(2^2)*0] * 3^[(2^1)*1] * 3^[(2^0)*0] 
res = 1
res = res^2 * 3^1 = 3^(1)b
res = res^2 * 3^0 = 3^2 = 3^(10)b
res = res^2 * 3^1 = 3^5 = 3^(101)b
res = res^2 * 3^0 = 3^10 = 3^(1010)b
需要特殊处理 n<0的情况。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: double pow(double x, int n) { bool negPow = n<0 ? true : false; n = abs(n); double res = 1; for(int i=31; i>=0; i--) { res = res*res; if(n & (1<<i)) res = res*x; } if(negPow) res = 1/res; return res; } };

思路2：分治递归

递归公式为：x^n = x^(n/2) * x^(n/2) * x^(n%2)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: double pow(double x, int n) { if(n>=0) return powPositive(x,n); else return 1/powPositive(x,-n); } double powPositive(double x, int n) { if(n==0) return 1; // base case double res = powPositive(x, n/2); res *= res; if(n%2) res *= x; return res; } };

[leetCode] Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

思路：

整数近似平方根 y = sqrt(x)，则：y^2 <= x < (y+1)^2，或y <= x/y < y+1，并且0 <  y <= x

二分法查找：start = 0, end = x, mid = (start+end)/2

问题转化成一个sorted序列 1^2, 2^2, 3^2, ... x^2
寻找y满足y^2 = x，如果不存在这样的y，则寻找y使x插入该序列时，y^2为x前一个元素。这样问题转化为Insertion Position那题的变种。区别仅仅在于base case

(1) x/mid = mid：return mid

(2) x/mid < mid：end = mid-1

(3) x/mid > mid：start = mid+1

之所以用x/mid来判断是为了防止overflow

base case：当y^2 = x不存在，即x为非完全平方数
(1) start = end = mid：
(a) mid^2 < x，此时mid应为结果。下一步start = mid+1, end = mid，查找结束，此时应返回end
(b) mid^2 > x，此时mid-1应为结果。下一步start = mid, end = mid-1，查找结束，此时应返回end

(2) start = end-1 = mid：
mid^2 < x，下一步start = mid+1, end = mid，进入(1)的情况
mid^2 > x，此时mid-1应为结果。下一步start = mid, end = mid-1，查找结束，此时应返回end

综上所述：查找结束后：return end

Corner case: 

(1) x<0，return -1表示出错（需要和面试官讨论）。

(2) x=0或1，此时mid=0，会形成x/y = 0/0。需要特殊处理。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: int sqrt(int x) { if(x<=1) return x; int start=0, end=x; while(start<=end) { int mid = start + (end-start)/2; if(x/mid==mid) return mid; else if(x/mid<mid) end = mid-1; else start = mid+1; } return end; } };

总结：这里有必要总结下binary search的一个规律
当x不存在于一个sorted array A[0:n-1]中时，binary search的循环必然会因为start > end而终止。此时必然有：A[end] < x < A[start]，如果end >=0 且 start<n。

这也就是为什么这题需要返回end，而Insertion Position那题却要返回start的原因。