LeetCode第 75 场双周赛题解

2220. 转换数字的最少位翻转次数

题目描述：给你两个整数\(a , b\)，每次可以翻转a的一个二进制位，问最少需要多少次才可以将a变成b。

思路：显然先将a , b异或之后统计异或后的数字的二进制位中1的个数。

时间复杂度：\(O(logn)\)

参考代码：

class Solution {
public:
    int minBitFlips(int start, int goal) {
        start ^= goal;
        int res = 0;
        for(int i = 30 ; i >= 0 ; --i) res += (start >> i) & 1;
        return res;
    }
};

2221. 数组的三角和

题目描述：给你一个长度为\(n - 1\)的数组\(nums\)，构造一个长度为\(n - 1\)的新数组\(a\)，满足\(a_i = nums_i + nums_{i + 1} \forall 1 \leq i < n\)。若递归构造，直到新数组的长度变为\(1\)，问这个最终的数组的值模10后的值是多少。

思路：根据题意模拟即可

时间复杂度：\(O(n^2)\)

参考代码：

class Solution {
public:
    int triangularSum(vector& nums) {
        int res = 0, n = nums.size();
        for(int i = n ; i >= 1 ; --i){
            for(int j = 0 ; j < i ; ++j){
                res += nums[j];
                if(j < i - 1) nums[j] = (nums[j] + nums[j + 1]) % 10;
            }
        }
        return nums[0];
    }
};

6035. 选择建筑的方案数

题目描述：给你一个二进制串，问你有多少长度为\(3\)的子串为101或者010。

思路：赛时思路参考了115. 不同的子序列

时间复杂度：\(O(n)\)

参考代码：

class Solution {
public:
    long long numberOfWays(string s) {
        int n = s.size();
        vector> f(n + 1 , vector(4 , 0));
        auto cal = [&](string t)->long long{
            int n = s.size(), m = t.size();
            for(int i = 0 ; i <= n ; ++i) f[i][0] = 1;
            for(int i = 1 ; i <= n ; ++i){
                char c = s[i - 1];
                for(int j = 1 ; j <= m ; ++j){
                    if(c == t[j - 1]) f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
                    else f[i][j] = f[i - 1][j];
                }
            }
            return f[n][m];
        };
        return cal("010") + cal("101");
    }
};

2223. 构造字符串的总得分和

题目描述：给你一个长度为\(n\)的字符串\(s\)，对于它的每一个后缀，其得分为该后缀与原串的最长公共前缀的长度，求\(s\)的得分。

思路：\(z\)函数的模板题目，注意\(z_0 = n\)，具体证明可以看z函数（扩展KMP）。

时间复杂度：\(O(n)\)

参考代码：

class Solution {
private:
public:
	long long sumScores(string s) {
		int n = s.size();
		vectorz(n, 0);
		auto zFuncation = [&](int len) {
			for (int i = 1, lr = 0, rs = 0; i < len; ++i) {
				if (i <= rs && z[i - lr] < rs - i + 1) z[i] = z[i - lr];
				else {
					z[i] = max(0, rs - i + 1);
					while (i + z[i] < len && s[z[i]] == s[i + z[i]]) ++z[i];
				}
				if (i + z[i] - 1 > rs) lr = i, rs = i + z[i] - 1;
			}
			return;
		};
		zFuncation(n);
		long long res = 0;
		for (auto& val : z) res += val;
        res += n;
		return res;
	}
};