重新开始刷LeetCode了…Fighting!!
累加数是一个字符串，组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
给定一个只包含数字 ‘0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是累加数。
说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
示例：
1 2 3 4 5 6 7 输入: "112358" 输出: true 解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 输入: "199100199" 输出: true 解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
Ps：处理一个溢出的过大的整数输入?
思路：
首先想到的就是处理过长整数的相加，肯定是采用字符串的方法来求解加法啊！就是不断的相加进位。
其实会发现，在第一二个数确定之后，整个串是否为累加数就可以确定了。因此，我们只需要枚举前两个数的情况就可以了。进一步，这两个数可以用在字符串的下标位置来确定
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 string add (const string & s1, const string & s2) string res; int n1 = s1.size(); int n2 = s2.size(); int carry = 0 ; int i = n1 - 1 ; int j = n2 - 1 ; while (i >= 0 || j >= 0 || carry > 0 ) { int t1 = (i >= 0 ) ? s1[i--] - '0' : 0 ; int t2 = (j >= 0 ) ? s2[j--] - '0' : 0 ; res += ((t1 + t2 + carry) % 10 ) + '0' ; carry = (t1 + t2 + carry) / 10 ; } reverse(res.begin(), res.end()); return res; } bool valid (string & num, int l1, int r1, int l2, int r2) if ((r1 > l1 && num[l1] == '0' ) || (r2 > l2 && num[l2] == '0' )) return false ; if (r2 == num.size() - 1 ) return true ; string s1 = num.substr(l1, r1 - l1 + 1 ); string s2 = num.substr(l2, r2 - l2 + 1 ); string s3 = add(s1, s2); int n = s3.size(); if (r2 + n >= num.size() || s3.compare(0 , n, num, r2 + 1 , n) != 0 ) return false ; return valid(num, l2, r2, r2 + 1 , r2 + n); } bool isAdditiveNumber (string num) int N = num.size(); for (int i = 0 ; i < N / 2 ; ++i) { for (int j = i + 1 ; j < N - 1 ; ++j) { if (valid(num, 0 , i, i + 1 , j)) return true ; } } return false ; }
对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。
格式
该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。
你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。
示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]] 0 | 1 / \ 2 3 输出: [1] 输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]] 0 1 2 \ | / 3 | 4 | 5 输出: [3, 4]
思路：
参考了某些大神的思路，他们真的太厉害了趴~
通过分析我们可以得到，其实这个树的根越在中心，这个数的高度就越小，如果取边缘的值，则输的高度一定很高。
同时，我们也可以证明，最后剩下的只可能为一个节点或两个节点。因为题目中有说具有树特征，即不存在环，因此我们一定可以通过不断的去除叶子节点，最后得到树根。因此最后只可能剩下一个或者两个节点。
因此，我们可以采用贪心的方法：
先计算每个节点的度，然后选取边缘的节点（即degree=1），然后删去，同时，更新一下与该节点相连的节点的度（即degree -= 1）。
不断重复上述操作，直至节点个数小于等于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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 vector <int > findMinHeightTrees(int n, vector <vector <int > >& edges) { int in_degrees[n] = {0 }; bool isDelete[n] = {0 }; vector <vector <int > > adjs(n, vector <int >()); int m = edges.size(); int num = n; for (int i = 0 ; i < m; i++) { in_degrees[edges[i][0 ]] += 1 ; in_degrees[edges[i][1 ]] += 1 ; adjs[edges[i][0 ]].push_back(edges[i][1 ]); adjs[edges[i][1 ]].push_back(edges[i][0 ]); } queue <int > q; for (int i = 0 ; i < n; i++) { if (in_degrees[i] == 1 ) { q.push(i); } } while (num > 2 ) { int size = q.size(); for (int i = 0 ; i < size; i++) { isDelete[q.front()] = true ; int temp = q.front(); for (int j = 0 ; j < adjs[temp].size(); j++) { if (!isDelete[adjs[temp][j]]) { in_degrees[adjs[temp][j]]--; if (in_degrees[adjs[temp][j]] == 1 ) { q.push(adjs[temp][j]); } } } q.pop(); } num -= size; } vector <int > res; for (int i = 0 ; i < n; i++) { if (!isDelete[i]) { res.push_back(i); } } return res; }
以后可以用图的方式去存储这种比较稀疏的图，否则可能会出现超出内存的问题，因此可以采用邻接表的方式，存储与每个顶点相连的顶点即可。
善用队列！
编写一段程序来查找第 n 个超级丑数。
超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
示例:
1 2 3 输入: n = 12, primes = [2,7,13,19] 输出: 32 解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32]
思路：这个问题我想了好久才想明白，但想通之后又挺简单的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 int nthSuperUglyNumber (int n, vector <int >& primes) int size = primes.size(); int id[size] = {0 }, res[n]; int i = 0 ; res[i++] = 1 ; while (i < n) { int minNum = INT_MAX; int pos = 0 ; for (int j = 0 ; j < size; j++) { int tmin = primes[j] * res[id[j]]; if (tmin < minNum) { minNum = tmin; pos = j; } else if (tmin == minNum) { id[j]++; } } id[pos]++; res[i++] = minNum; } return res[n - 1 ]; }
给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
示例 :
1 2 3 4 5 6 7 8 9 10 11 输入: ["abcw","baz","foo","bar","xtfn","abcdef"] 输出: 16 解释: 这两个单词为 "abcw", "xtfn"。 输入: ["a","ab","abc","d","cd","bcd","abcd"] 输出: 4 解释: 这两个单词为 "ab", "cd"。 输入: ["a","aa","aaa","aaaa"] 输出: 0 解释: 不存在这样的两个单词。
思路：
主要是对二进制的使用。
因为字符串全部都由小写字母组成，因此可以用26个bit来表示每个字母是否出现在此字符串当中。然后两个字符串是否有交集，即这两个比特串按位与是否等于0。（实际上是用32bit去表示的，因为方便）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int str2int (const string & s) int res = 0 ; for (auto c : s) res |= 1 << (c - 'a' ); return res; } int maxProduct (vector <string >& words) int N = words.size(); vector <int > m(N, 0 ); for (int i = 0 ; i < N; ++i) m[i] = str2int(words[i]); int res = 0 ; for (int i = 0 ; i < N; ++i) { for (int j = 0 ; j < i; ++j) { if ((m[i] & m[j]) == 0 && words[i].size() * words[j].size() > res) res = words[i].size() * words[j].size(); } } return res; }
初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。
示例:
1 2 3 4 5 6 7 8 9 输入: 3 输出: 1 解释: 初始时, 灯泡状态 [关闭, 关闭, 关闭]. 第一轮后, 灯泡状态 [开启, 开启, 开启]. 第二轮后, 灯泡状态 [开启, 关闭, 开启]. 第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 你应该返回 1，因为只有一个灯泡还亮着。
我没想到这个题这么简单。
其实就是求一下n个数里面有多少个平方数。
因为：如果不是平方数的话，他的两个对应的两个乘积是对称的，因此比自己小的因子一定是偶数个。
所以答案直接开方然后强制类型转换返回即可。