巧解数学问题

1.判断一个数的阶乘结果有几个0（力扣172）

题解： 每个尾部的 0 由 2 × 5 = 10 而来，因此我们可以把阶乘的每一个元素拆成质数相乘，统计有 多少个 2 和 5。明显的，质因子 2 的数量远多于质因子 5 的数量，因此我们可以只统计阶乘结果 里有多少个质因子 5。

int trailingZeroes(int n) { return n == 0? 0: n / 5 + trailingZeroes(n / 5); }

2.数字字符串求和（力扣415）

题解： 因为相加运算是从后往前进行的，所以可以先翻转字符串，再逐位计算。这种类型的题考察 的是细节，如进位、位数差等等。

string addStrings(string num1, string num2) { string output(""); reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); int onelen = num1.length(), twolen = num2.length(); if (onelen <= twolen){ swap(num1, num2); swap(onelen, twolen); } int addbit = 0; for (int i = 0; i < twolen; ++i){ int cur_sum = (num1[i]-’0’) + (num2[i]-’0’) + addbit; output += to_string((cur_sum) % 10); addbit = cur_sum < 10? 0: 1; } for (int i = twolen; i < onelen; ++i){ int cur_sum = (num1[i]-’0’) + addbit; output += to_string((cur_sum) % 10); addbit = cur_sum < 10? 0: 1; } if (addbit) { output += "1"; } reverse(output.begin(), output.end()); return output; }

3.实现数组的打乱和重置函数（力扣384）

class Solution { vector<int> origin; public: Solution(vector<int> nums): origin(std::move(nums)) {} vector<int> reset() { return origin; } vector<int> shuffle() { if (origin.empty()) return {}; vector<int> shuffled(origin); int n = origin.size(); // 可以使用反向或者正向洗牌，效果相同。 // 反向洗牌： for (int i = n - 1; i >= 0; --i) { swap(shuffled[i], shuffled[rand() % (i + 1)]); } // 正向洗牌： // for (int i = 0; i < n; ++i) { // int pos = rand() % (n - i); // swap(shuffled[i], shuffled[i+pos]); // } return shuffled; } };

注意

vector<int> shuffled(origin);可以通过vector创建一个包含相同元素的vector；rand()直接可以获得随机整数。

4.等概率选择链表中的一个元素（力扣382）

题解： 不同于数组，在未遍历完链表前，我们无法知道链表的总长度。这里我们就可以使用水库采 1 样：遍历一次链表，在遍历到第 m 个节点时，有 m 的概率选择这个节点覆盖掉之前的节点选择。 我们提供一个简单的，对于水库算法随机性的证明。对于长度为 n 的链表的第 m 个节点，最 1 后被采样的充要条件是它被选择，且之后的节点都没有被选择。这种情况发生的概率为 $$1/m\times m/(m+1)\times (m+1)/(m+2)\times \cdot \cdot \cdot \times (n-1)/n=1/n$$。因此每个点都有均等的概率被选择。

class Solution { ListNode* head; public: Solution(ListNode* n): head(n) {} int getRandom() { int ans = head->val; ListNode* node = head->next; int i = 2; while (node) { if ((rand() % i) == 0) { ans = node->val; } ++i; node = node->next; } return ans; } };