腾讯音乐笔试 源码 0926
第一题（AC）：
一次可以变2个，将字符串变为全0或全1
思路：暴力
class Solution {
public:
int minOperations(string str) {
int len = str.length();
// all to 0
int ans0 = 0;
for (int i = 0; i < len; ++i) {
if (str[i] == '1') {
++ans0;
++i;
}
}
int ans1 = 0;
for (int i = 0; i < len; ++i) {
if (str[i] == '0') {
++ans1;
++i;
}
}
return min(ans0, ans1);
}
};
第二题（AC）： 给一个数组，找一段区间，其区间内的积的后缀有不少于x个0；给定x之后求有多少种这样的区间。
思路：
统计每个数内2和5的个数，然后前缀和。
class Solution {
public:
int getSubarrayNum(vector<int>& a, int x) {
const int mod = 1e9 + 7;
int size = a.size();
vector<int> n2(size, 0);
vector<int> n5(size, 0);
for (int i = 0; i < size; ++i) {
if (i) {
n2[i] = n2[i - 1];
n5[i] = n5[i - 1];
}
int num = a[i];
while (num % 2 == 0) {
++n2[i];
num /= 2;
}
while (num % 5 == 0) {
++n5[i];
num /= 5;
}
}
long long ans = 0;
for (int i = 0; i < size; ++i) {
int num = (i ? n2[i - 1] : 0) + x;
int dis2 = 0, dis5 = 0;
auto p = lower_bound(n2.begin(), n2.end(), num);
dis2 = distance(p, n2.end());
num = (i ? n5[i - 1] : 0) + x;
p = lower_bound(n5.begin(), n5.end(), num);
dis5 = distance(p, n5.end());
ans = (ans + min(dis2, dis5)) % mod;
}
return ans;
}
};
求好矩阵。
思路：每增加一行/一列，种类就*2.
所以总的种类有
其中8是2*2矩阵能带来的种类数。
然后x为偶数，也就是说每一个格子有x/2种选择，所以一共有
种可能。
然后对结果取模就可以。
注意
%mod要根据费马小定理求
不知道为什么只过了15%
class Solution {
public:
const long long mod = 1e9 + 7;
int numsOfGoodMatrix(int n, int m, int x) {
// write code here
long long y = (long long)m + (long long)n;
y %= mod;
long long num1 = quickM(x, y);
long long num2 = quickM(2, mod - 2);
return (int)((num1 * num2) % mod);
}
long long quickM(int b, long long y) {
long long base = b % mod;
long long ans = 1;
while (y) {
if (y & 1) ans = (ans * base) % mod;
base = (base * base) % mod;
y >>= 1;
}
return ans;
}
}; 
