题目一 小红的二进制删数字：
小红拿到了一个二进制字符串 s，她可以删掉其中的一些字符，使得最终该字符串为一个2的幂（即可以表示为 2^k 形式的数）。小红想知道，自己最少删几个字符可以达成？请你编写一个函数返回这个答案。
具体思路：
看到这道题目，我们要联想一个2次幂的整数在二进制中是如何表示的，在整个二进制字符串中只有1个数是1，其余的数字全是0，这样一个数是一个2次幂的整数。
所以题意就变成了我要消去字符串中多余的1，使得整个二进制字符串中只含有一个1，这样就符合题意了。我们先统计所有的1的个数，再减去1就是答案。
代码：
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ int minCnt(string s) { // write code here int n = s.size(); int cnt = 0; for(int i = 0; i < n; i++) { if(s[i] == '1') cnt++; } return cnt - 1; } };
应该注意的地方：
当题目中出现2次幂的字眼时，我们应该往二进制的方向去想。
题目二 嘤嘤的新平衡树：
给定一棵二叉树，二叉树的每个结点只有0或2个孩子。你需要对每个结点赋值一个正整数，使得每个结点的左右子树权值和相等。你需要返回所有结点的最小权值和对 10^9+7 取模的结果。二叉树结点个数不超过10^5。
具体思路：
这道题目要求的是所有结点的权值和最小，题目中又没有限制根节点的权值必须是子节点的权值和，所以这道题目，我首先想到的是每一个节点的权值都是1，这样就是最小的权值和。但是又这种情况：这个二叉树不是完全二叉树。
这样又要求左右子树的权值和相同，我们只要将这个树抽象为完全二叉树，但是并不是真的二叉树，只是权值和满足完全二叉树。类似于下图的情况：
所以，这道题目的思路是先算出整个二叉树的最大深度，然后进行倍增计算。
代码：
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param tree TreeNode类 * @return int整型 */ int dfs(TreeNode* tree) { if(tree == NULL) return 0; int len = max(dfs(tree->left), dfs(tree->right)) + 1; return len; } int getTreeSum(TreeNode* tree) { // write code here int ans = 1; int len = dfs(tree); int mod = 1e9 + 7; for(int i = 0; i < len; i++) { ans = ans * 2 % mod; } return ans - 1; } };
应该注意的地方：
注意最后答案要减一，等比公式告诉我们要减一hhh。基本树的题目要往递归的方向去思考。
题目三 连续子数组数量：
给定一个数组，请你编写一个函数，返回元素乘积末尾零数量大于等于x的连续子数组数量。答案可能太大，请将答案对10^9+7取模再返回。 数组长度不超过10^5。数组元素、x均为不超过10^9的正整数。
具体思路：
这个就是将每一个的数对于2和5的因子是多少，然后利用双指针建立滑动窗口来计算有多少个方案。先让左右指针都指向0，然后让右指针先走，如果满足2或5的因子个数的最小值大于等于x的话，就说明满足题意不管后面数组中的数字是几，都满足题意，直接用n-r来计算，同时，我们可以左移左指针，来缩小数组长度看是否满足题意。
代码：
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param a int整型vector * @param x int整型 * @return int整型 */ int getSubarrayNum(vector<int>& a, int x) { // write code here int n = a.size(); vector<int> c2(n), c5(n); for(int i = 0; i < n; i++) { int x = a[i]; while (x % 2 == 0) { c2[i]++; x /= 2; } while (x % 5 == 0) { c5[i]++; x /= 5; } } int res = 0; int l = 0; int cnt2 = 0, cnt5 = 0; int mod = 1e9 + 7; for(int r = 0; r < n; r++) { cnt2 += c2[r]; cnt5 += c5[r]; while (min(cnt2, cnt5) >= x) { res = (res + n - r) % mod; cnt2 -= c2[l]; cnt5 -= c5[l]; l++; } } return res; } };
应该注意的地方：
这道题目还是要多想一想。
题目四 好矩阵：
我们定义一个矩阵为“好矩阵”，当且仅当该矩阵所有2*2的子矩阵数字和为偶数。
例如：
是好矩阵，两个2*2的子矩阵的和分别是8和12。请问n行m列，矩阵中每个数均在[1,x]范围内的好矩阵有多少种？由于答案过大，请对10^9+7取模。数据范围：2≤n,m,x≤10^9 保证x为偶数。
具体思路：
看到数据范围很大，说明不是用一般的循环来实现算法的，而是需要我们利用这个数学公式来实现算法的，这道题目就是一个典型的组合数学。
2x2格子总合是偶数，其实主要关注0-1奇偶就行，不需要关注其具体是什么值。在这个基础上，我们可以找到如下规律：就是第一行，每个位子可以随意选择，即0-1奇偶都行，然后从第二行开始，除了第一列，可以0-1奇偶选择，其他列的值都是固定的，因此其总方案数为: 2^m * 2^(n - 1) == 2^(n+m-1)
然后我们在回过来头考虑在[1，x]具体的选择值。由于x为偶数，所以根据乘法原理，其附带选择数位 (x/2)^(m*n)。最终的结果为： 2^(n+m-1) * (x/2)^(m*n)。利用快速幂可以进行求解。
代码：
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @param m int整型 * @param x int整型 * @return int整型 */ int mod = 1e9 + 7; long long quickpow(long long a, long long b) { long long res = 1; while (b) { if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res % mod; } int numsOfGoodMatrix(int n, int m, int x) { // write code here int res = 0; res = quickpow(2, m + n - 1) * quickpow(x / 2, 1ll * m * n) % mod; return res; } };
应该注意的地方：
一看到数据范围比较大，就要往数学的方向来看。
