最近的题目貌似有点简单
第一题,直接暴力对比每位是否相等,统计所有不相等位的数量
class Solution {
public:
int minBitFlips(int start, int goal) {
int ans = 0;
while(start || goal)
{
int a = start%2;
int b = goal%2;
if(a != b)
ans++;
start=start>>1;
goal=goal>>1;
}
return ans;
}
};
第二题同样暴力通过。
(这题貌似和刚学c++入门的时候做杨辉三角一样)
class Solution {
public:
int triangularSum(vector& nums) {
int n = nums.size();
if(n == 1)
return nums[0];
for(int i = n-1; i >= 0; i--)
for(int j = 0; j < i; j++)
nums[j] = (nums[j]+nums[j+1])%10;
return nums[0];
}
};
第三题,有点c动态规划的意思,统计当前0,1,01,10的数量,如果0,1的数量用来更新01,10的数量,01,10用来更新101,010的数量,也就是最终结果。
(忘记看返回的是longlong,直接WA了一次,血亏)
class Solution {
public:
long long numberOfWays(string s) {
long long cur_0 = 0, cur_1=0,cur_01=0, cur_10=0;
long long ans = 0;
for(auto c:s)
{
if(c == '0')
{
cur_0+=1;
ans += cur_01;
cur_10 += cur_1;
}
else
{
cur_1+=1;
ans += cur_10;
cur_01 += cur_0;
}
}
return ans;
}
};
第四题最长公共前缀,但是难度增加了,看了大佬们的题解才知道是KMP算法的扩展,叫做Z函数
class Solution {
public:
vector z_function(string s) {
int n = (int)s.length();
vector z(n);
for (int i = 1, l = 0, r = 0; i < n; ++i) {
if (i <= r && z[i - l] < r - i + 1) {
z[i] = z[i - l];
} else {
z[i] = max(0, r - i + 1);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
}
if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}
return z;
}
long long sumScores(string s) {
long long ans = s.length();//注意这里初始化成字符串的长度,因为自身也算,这里被坑了一次
auto z = z_function(s);
for(auto k : z)ans += k;
return ans;
}
};
//Z函数教程:https://oi-wiki.org/string/z-func/
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)