Math
这是所有类型里我觉得最有趣的一个类型，哈哈。
来被虐一下。
258. Add Digits
数字根的性质：
- 任何数字加9的数字根都是本身：加9的过程，就是在个位数-1，十位数+1的过程，所以加上9以后，个位数和十位数的数字和不变
- 任何数字乘9的数字根都是9：任何数字乘以9，就是9一直加很多很多次，利用第一个性质，还是会回到9
- 计算一般数字的数字根：前两个性质都跟9密切相关，那么对于一般数字，我们也尽量跟9扯上关系。比如12=9+3，那么利用第一个性质，数字根就是3。123 = 13*9 + 6，利用前两个性质，数字根是6。对于数字N，N - floor(N / 9) * 9是它的数字根。而对于数字9，9 = 1 * 9 + 0，余数是0时，数字根为9。另外还有一种情况，0 = 0 * 9 + 0，余数是0时，数字根也可能是9。为了区分这两种情况，可以将公式改成N - floor((N - 1) / 9) * 9，由于floor函数的性质
- 另外一个我没想出原理的性质：计算一个大数的数字根，可以把那个数字中相加为9的数字先划掉。比如123456789，数字根是0，因为9，18，27，36，45，都可以被划掉——why？
168. Excel Sheet Column Title
Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example:
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
从数字10进制比拟到26进制。
class Solution {
public:
string convertToTitle(int n)
{
string res;
while (n)
{
// 将数字转换为char的方法和26进制的对应关系，避免最后翻转字符串
res = char('A' + (n - 1) % 26) + res;
// 就像我们从尾到头遍历一个十进制的数的时候，用/10来得出下一位是什么
// 但在这里，要注意对应关系
n = (n - 1) / 26;
}
return res;
}
};
171. Excel Sheet Column Number
接上题，从字符串转换成数字。
我的做法，从后往前遍历：
class Solution {
public:
int titleToNumber(string s)
{
// ADS=S:19*1
// AD=D:4*26
// A=1*26*26
int n = 0, p = 0;
while (s.size())
{
int add = (s.back() - 'A' + 1);
n += add * pow(26, p++);
s.pop_back();
}
return n;
}
};
看了答案，从前往后遍历，但本质是一样的：
class Solution {
public:
// ADS
// A:ans=0+1=1
// D:ans=1*26+4=30
// S:ans=30*26+19=(1*26+4)*26+19
int titleToNumber(string s) {
int base = 26;
int ans = 0;
for(int i = 0; i < s.size(); i++) {
ans = ans* base + (s[i] - 'A' + 1);
}
return ans;
}
};
我一开始觉得有点不可思议，从前往后的怎么知道第一个数字要乘几遍26呢？比如第一个数我乘了26，下一个数要乘26的时候，已经加上第一个数了，会起到什么影响呢？其实这就是起到了正确的影响，每次加现在的数之前把前面的数*26，最后每个数都会乘了正确的次数。
我们做10进制时其实也是这样。比如1234。第一次ans=1，第二次ans=110+2=12，第三次ans=1210+3=123，第四次12310+4。最后这个1234=(((1)10+2)10 + 3)10 + 4。
172. Factorial Trailing Zeroes
Given an integer n, return the number of trailing zeroes in n!.
我们知道，只有2*5的组合能产生0。所以我们要想办法找到一个数是由几个2，几个5组成。而由于我们需要2和5来产生0，而2是每两个数字产生一个，5是每五个数字产生一个，5的频率比2小得多，所以我们要找的其实是5出现的频率。
举例：n=5，10，15，20 => 5出现的次数=N/5。而25中5出现的次数为6，因为25=5*5。相应地，像50，75，100，125都有这种情况。所以我们可以通过/5, /25, /125...来寻找5出现的次数。/25的结果中不包括/5的结果，因此我们直接将结果相加就好了。终止条件在于，n/i要大于0。
int trailingZeroes(int n) {
int result = 0;
for(long long i=5; n/i>0; i*=5){
result += (n/i);
}
return result;
}
观察以上代码，i*=5，其实就相当于n/=5，所以也可以转化写成递归式子：
class Solution {
public:
int trailingZeroes(int n)
{
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}
};
202. Happy Number
Write an algorithm to determine if a number is "happy".
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
这道题的解法很简单，用map（如果一个数[即两个之前数的平方和]出现了两次的话，肯定是进入循环模式了）或者fast/slow pointer.
7. Reverse Integer
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
这道题第一反应是转化为string来做，但是仔细一想，应该考虑几个edge case：
1、leading/trailing zero的情况
2、interger overflow的情况
319. Bulb Switcher
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
这道题要求的是一个数有几个因子，更准确地说，是一个数的因子的奇偶性。如果是偶数个那灯就是关的，如果是奇数个那灯就是亮的。除了因式分解之外，还有什么办法来知道因子的奇偶性呢？
一个insight：因子成对出现。只有平方数的因子是奇数。所以如果现在有N盏灯，那么第N盏灯假如是个平方数，那么sqrt（N）代表了[1,N]之中有多少个平方数，也就是有多少个数的因子数是奇数，也就是这个问题的答案。如果N不是平方数，那么floor（sqrt（N））就是答案。所以代码为：
class Solution {
public:
int bulbSwitch(int n)
{
return sqrt(n);
}
};
223. Rectangle Area
Find the total area covered by two rectilinear rectangles in a 2D plane.
这道要求两个长方形的和减去重合部分的面积。因为ABCD和EFGH的相对位置太不确定了，任何情况都要讨论两遍，所以我先把A确定为四条竖边中最左边的边，算出宽，然后把C确定为四条横边中最上面的边，算出高。这样减少了很多讨论情况，但是速度有点慢，主要是花在swap上了。
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H)
{
int two_rec_sum = (C - A) * (D - B) + (G - E) * (H - F);
int h, w;
if (E >= C || G <= A || H <= B || F >= D) return two_rec_sum;
if (E < A) swap(A, E), swap(B, F), swap(C, G), swap(D, H);
w = G <= C ? G - E : C - E;
if (D < H) swap(A, E), swap(B, F), swap(C, G), swap(D, H);
h = F <= B ? H - B : H - F;
return two_rec_sum - w * h;
}
};
其实还可以减少讨论情况。一个insight是，重合长方形的左边是两个左边横坐标较大的那个，右边是两个右边横坐标较小的那个，上边是两个上边纵坐标较小的那个，下边是两个下边纵坐标较大的那个。另外，检查一下是否有没重合的情况。
class Solution {
public:
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H)
{
int two_rec_sum = (C - A) * (D - B) + (G - E) * (H - F);
int left = max(A, E);
int right = min(C, G);
int top = min(D, H);
int bottom = max(B, F);
if (left <= right && top >= bottom)
{ return two_rec_sum - (right - left) * (top - bottom); }
return two_rec_sum;
}
};
这种题的类型或者说思维挺常见的——有很多种情况要讨论，怎样去抽象出同样的情况，避免讨论的情形，最后用简单的思路去写出代码。之前遇到过的情况是，两种我以为应该分开讨论的情况其实有先后顺序，还有就是类似这道题的，看似很多种情况，但是其实可以简化啦。
166. Fraction to Recurring Decimal
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".
这种题我觉得是math里最适合编程的一种题，就是对公理定理的要求不多，主要考你发现规律的能力，以及更重要的，在编程中把握细节、思考edge case的能力。这道题的总体思路很简单，不停将余数*10，除以被除数，用map检查有无重复出现的情况。但是这里有很多的edge case需要考虑：
- 正负——如果不提前处理好符号的问题，答案中会出现像“6.-2-3”这样的情况。可以用亦或（^）的逻辑来判定
- 零——用亦或的逻辑判断出来的结果只有正负之分，还要考虑0的情况
- 整数溢出。一旦遇到integer，就要考虑一下这道题会不会有整数溢出的情况。这道题有很多的整数溢出，比如INT_MIN/-1，1/INT_MIN等等，所以我们要将所有数字都转换为64位整数来做（long long or int64_t）
class Solution {
public:
string fractionToDecimal(int numerator, int denominator)
{
// edge case
if (!numerator) return "0";
// in case integer overflow
long long n = (long long)numerator;
long long d = (long long)denominator;
unordered_map<int, int> map;
string res;
// decide the sign
if (n < 0 ^ d < 0) res += '-';
// convert the sign
n = abs(n), d = abs(d);
long long q = n / d;
res += to_string(q);
long long r = n - q * d;
if (!r) return res;
res += '.';
while (r)
{
if (map.find(r) != map.end())
{
res.insert(map[r], "(");
res.push_back(')');
break;
}
map[r] = res.size();
r *= 10;
q = r / d;
res += to_string(q);
r = r - d * q;
}
return res;
}
};
368. Largest Divisible Subset
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.
这道题我用DFS做，思路和答案都很明显，但是比较慢，占用空间也大，因为每个index都存了一个vector。这个其实可以用dp的思想方法做，并用一个parent vector来backtrace。dp的思想方法，经常用到的有背包问题、状态转换、定义子问题、定义递归关系式等思路。DP的递归式可推出：dp[i] = dp[j] + 1 if i % j == 0, else dp[i] = 1. 也就是说以dp[i]结尾的集合中元素的个数，要么是能被之前元素除断的，要么只有dp[i]本身。写码的时候，空集、只有一个元素的集合、dp数组的初始值等条件要考虑过。
453. Minimum Moves to Equal Array Elements
Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.
这道题有两个方法：令一开始的和为sum，最小值是min，操作次数为k次。
- 逆向思维——每次n-1个元素都+1，就是每次1个元素-1。看减几次能每个元素都变成最小数。
- 顺向思维——最小值min在每一轮的操作中都应该+1，而在操作之后它还是会是最小的值。因为min和其它几个比它大的数一起+1，其它几个比它大但又不是最大数的数（[S]）+1之后一定比min+1大，而原来的最大数max虽然没有变，但也比min大，因为max>=all([S]+1)。（[S]中的数各加一）所以这个最小值从开始到结束都是最小值，我们知道最后我们达到的值是min+k。可以列出等式：sum + (n - 1) * k = (min + k) * n，所以k=sum-min*n。
264. Ugly Number II
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number, and n does not exceed 1690.
这道题的关键是在O（1）的时间内找到下一个ugly number是什么。建立一个vector来保存现在已经有的ugly number。下一个ugly number的情况要么是这个number * 2，要么 * 3，要么 * 5，取其中的最小值——这由定义而来。同时每次进行指标的更新，注意乘积相同时一起更新指标。
class Solution {
public:
int nthUglyNumber(int n)
{
vector<int> nums {1};
int two = 0, three = 0, five = 0;
while (nums.size() != n)
{
nums.push_back(min(nums[two] * 2, min(nums[three] * 3, nums[five] * 5)));
if (nums.back() == nums[two] * 2) two++;
if (nums.back() == nums[three] * 3) three++;
if (nums.back() == nums[five] * 5) five++;
}
return nums.back();
}
};
247. Strobogrammatic Number II
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Find all strobogrammatic numbers that are of length = n.
For example,
Given n = 2, return ["11","69","88","96"].
这道题的思路很简单，但是我觉得我第一次写的代码充分暴露了丑陋。。。第一次代码：
class Solution {
public:
vector<string> findStrobogrammatic(int n)
{
vector<string> res;
vector<string> next({"0", "1", "8"});
vector<string> basic({"11", "69", "96", "88", "00"});
vector<string> next_next = basic;
if (n == 1) return next;
for (int i = 3; i <= n; ++i)
{
vector<string> v;
for (int j = 0; j < basic.size(); ++j)
{
for (int k = 0; k < next.size(); ++k)
{
string ele = basic[j];
v.push_back(ele.insert(1, next[k]));
}
}
next = next_next;
next_next = v;
}
for (string num: next_next)
{
if (num[0] == '0' && num.size() != 1) continue;
res.push_back(num);
}
return res;
}
};
改进后的代码：
class Solution {
public:
vector<string> findStrobogrammatic(int n)
{
vector<string> next({""});
vector<string> next_next({"0", "1", "8"});
if (n == 0) return next;
if (n == 1) return next_next;
for (int i = 2; i <= n; ++i)
{
vector<string> v;
for (string s: next)
{
if (i < n) v.push_back("0" + s + "0");
v.push_back("1" + s + "1");
v.push_back("6" + s + "9");
v.push_back("8" + s + "8");
v.push_back("9" + s + "6");
}
next = next_next;
next_next = v;
}
return next_next;
}
};
改进的地方在于：
- （最大的）处理case 0的方式。除了最后一次，“00”，“010”这样的形式也允许存在，这是递归的条件的一部分。之前我是完成后还要遍历一次去寻找是否有非法0的存在，但改进后以i==n为终止条件。这也减少了一个向量的空间
- 第一次我是以某个array为基础，对每一个element进行insert。这样的一个坏处在于，因为我们不能改变basic向量，同时又要进行insert，所以每次都要复制里面的元素，再进行操作，这样一来这个向量不知道被复制了多少遍了。改进后的代码里，用+的形式来进行操作，更明了，code更干净。当情况数量有限的时候，可以采取这样的写法
时间复杂度上，每次n+1，遍历的元素数量都是原来的5倍。所以我觉得时间复杂度是O（n）。
367. Valid Perfect Square
这道题应该是让我们养成一种想法——很多明显的遍历能做的题目，其实都能用二分法来做吧。另外，凡是关于integer的加减乘除，都要想想overflow的问题哦。
360. Sort Transformed Array
这道题我的思路是：
- 变量index表示离最小值/最大值最近的index
- 若a=0：b>0，index是第一个值，从第一个至最后一个排列；b<0，index是最后一个值，从第一个至最后一个排列
- 若a!=0，用二分法找出index值（-b/2a入手）
- 取决于a的符号，a>0时，找出离a最近至最远的元素，并从第一个至最后一个排列。a<0时，找出离a最近至最远的元素，并从最后一个到第一个排列
看了评论区的答案，可以简化的思路步骤：
- 用二分法找出index的步骤可以省略，我们可以不从中点入手，而从端点入手
- 可以避免讨论a=0的情况，因为我们只需将端点比较大小然后从前至后/从后至前排列就行了
class Solution {
private:
int func(int x, int a, int b, int c)
{
return a * x * x + b * x + c;
}
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c)
{
int i = 0, j = nums.size() - 1;
vector<int> res(nums.size());
int index = a >= 0 ? nums.size() - 1 : 0;
while (i <= j)
{
// we can compare func(nums[i]) and func(nums[j]) and decide which is larger
// but is this the "larger of small" or "larger of large"?
// when a >= 0, it's either monotonous or "larger of large"
// otherwise, "larger of small"
if (a >= 0)
{
res[index--] = func(nums[i], a, b, c) > func(nums[j], a, b, c) ? func(nums[i++], a, b, c) : func(nums[j--], a, b, c);
}
else
{
res[index++] = func(nums[i], a, b, c) > func(nums[j], a, b, c) ? func(nums[j--], a, b, c) : func(nums[i++], a, b, c);
}
}
return res;
}
};
469. Convex Polygon
Given a list of points that form a polygon when joined sequentially, find if this polygon is convex (Convex polygon definition).
这道完全是数学题了，判断一个形状是不是凸面体（任何两点之间的连线都在此形状内）。判断方法是：将每两条相邻的边进行cross product（二维向量的cross product：<a,b>x<c,d>=ad - bc），看所得数（z向量）是正还是负。如果全为正或全为负，则是凸面体，反之不是。
356. Line Reflection
Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points.
这道题主要考察对可能出现的case进行分析的能力，以及编程能力（如何选择相应的数据结构）。
要考虑的case有（前两个比较edge）：
- 纵坐标只有一个点，这个点与自己对称
- 两个坐标重合，此时只需考虑其中一个坐标即可
- 两个坐标不重合且成对出现，将同一个纵坐标上出现的横坐标进行递增排序，用两个指针求出对称轴并在循环中检查
数据结构中要考虑的：
- 利用set是为了实现【递增】和【去重】两个功能
- set的pointer不是random access pointer，所以我们不能像vector一样对pointer进行大小比较，我们只能每次将pointer++或者--，并且判断两个pointer是否相等。这就要求我们在编程的时候对终止条件要进行一点点小的灵巧的改变，见代码
class Solution {
public:
bool isReflected(vector<pair<int, int>>& points)
{
unordered_map<int, set<int>> map;
for (auto &p: points) map[p.second].insert(p.first);
double x = (double)INT_MAX;
for (auto &item: map)
{
for (auto l = item.second.begin(), r = item.second.end(); l != r; l++)
{
// 先将r pointer--。由于先减了r，我们可以对终止条件有更灵活的判断方式
double mid = (double)(*l + *(--r)) / 2;
if (x == (double)INT_MAX) x = mid;
else if (x != mid) return false;
// 若此时l和r相等，表示已经进行到了同一个元素，可以退出了
if (l == r) break;
}
}
return true;
}
};
537. Complex Number Multiplication
这道题考察stringstream的用法。想在字符串中取出整数，或者用整数去构造字符串，分别可以用istringstream和ostringstream。另外用istream& getline (istream& is, string& str, char delim);也可以取出相关信息。
class Solution {
public:
string complexNumberMultiply(string a, string b)
{
int ra, ia, rb, ib;
char buff;
stringstream aa(a), bb(b), ans;
aa >> ra >> buff >> ia >> buff;
bb >> rb >> buff >> ib >> buff;
ans << ra*rb - ia*ib << "+" << ra*ib + rb*ia << "i";
return ans.str();
}
};
523. Continuous Subarray Sum
Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.
这道题用O（n^2）的解法考虑0的edge case就可以了。不过有一种数学的解法挺巧妙的。题目似乎给了一个不太用的上的restriction——sums up to the multiple of k。为什么不是直接sum up to k呢？而且让我们返回的是一个boolean，而不是一个vector。实际上，
483. Smallest Good Base
For an integer n, we call k>=2 a good base of n, if all digits of n base k are 1.
Now given a string representing n, you should return the smallest good base of n in string format.
Example 1:
Input: "13"
Output: "3"
Explanation: 13 base 3 is 111.
Example 2:
Input: "4681"
Output: "8"
Explanation: 4681 base 8 is 11111.
Example 3:
Input: "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.
Note:
The range of n is [3, 10^18].
The string representing n is always valid and will not have leading zeros.
对于每一个大于2的数，我们总能找出一个base k，因为最后一位digit1其实代表的就是数字1，只要n-1就是我们能找到的最大base，k进制表示为11。那么对于更小的base，其实肯定有更多的数位来表示。如果一个数能表示成111...11（m+1位），那么我们知道，这个base k肯定比n^(1/m)小，因为 k^m + k^(m-1) + ... + 1 = n。所以举例来说，对于111这样的进制形式，我们只要测试k < n^(1/3)就可以了。但这样还是有很多情况要测定。 但是我们真的有必要测试比n^(1/m) 小的数吗？对于111这样的进制形式，当我们测定k=sqrt(n)不正确的时候，由于(sqrt(n)-1)^ 2+(sqrt(n)-1)^ 1+(sqrt(n)-1)^0 < (sqrt(n))^ 2（相差n），我们知道n^ (1/3)以下的base其实都不会成立（太小了）。更general的case来说，k=n^(1/m) 不正确的时候，由于(n^(1/m) - 1)^m + (n^(1/m) - 1)^(m-1) + ... + 1 < (n^ (1/m))^m （因为n^a + n^ (a-1)+...+1<(n+1)^k ，说明当k=n^(1/m) - 1的时候，k^m + k^(m-1) +...+1 < (k+1)^m < n），n^(1/m) 以下的base其实也不会成立。所以当k=n^(1/m)过大的时候，我们没有必要再检查小于
k的数了。当k=n^(1/m) 过小的时候，我们也没有必要再检查大于k的数了，因为(k+1)^m > n。所以我们只要检查k=n^(1/m)这一种情况即可。
所以在进制上，每加一个1，我们就要检查一次，最多检查logn次。
517. Super Washing Machines
365. Water and Jug Problem
两瓶水倒来倒去，能否倒到一个指定的高度（一瓶中的容量或两瓶容量之和）。我们能准确地测量出两瓶水的容量（Aml和Bml）。这道题让我觉得很麻烦的是，只有两个瓶子。如果有第三个瓶子的话，我们每次会向这个瓶子里倒进/出Aml/Bml，能否最后倒成Zml的话，只要看AX+BY=Z这个方程有没有解。根据Bézout's theorem，Z必须是A和B的最大公约数的倍数。按这样的思路来，编程就很简单了。但这里剩下两个问题：
- 有无这个假设的第三个瓶子对最后的解有无影响
- 如果不知道这个定理，如何进行解答
50. Pow(x, n)
x ^ 8 = ((x ^ 2) ^ 2) ^ 2
x ^ 10 = (((x ^ 2) ^ 2) ^ 2) * (x ^ 2)
x ^ 16 = (((x ^ 2) ^ 2) ^ 2) ^ 2
x ^ 17 = x * (((x ^ 2) ^ 2) ^ 2) ^ 2
举几个例子可以看到，n由几次2相乘，与n的bit个数有关。8=1000，10=1010，16=10000，17=10001。所以我们可以以bit数计数，将n *= n进行（bit个数）次，如果bit值为1的话，就乘到
