2023.2.12LeetCode第332场周赛

6354. 找出数组的串联值

思路

双指针模拟，两个指针相遇的时候要特判

算法

class Solution {
public:long long findTheArrayConcVal(vector<int>& nums) {long long ans = 0;int i = 0, j = nums.size() - 1;while (i <= j) {if (i != j) {string s = to_string(nums[i]) + to_string(nums[j]);ans += stoll(s);} else {string s = to_string(nums[i]);ans += stoll(s);break;}i ++ , j -- ;}return ans;}
};

6355. 统计公平数对的数目

思路

计算在[lower, upper]之间满足条件的数目可以利用前缀和的思想转化为不超过upper和不超过lower-1的数量相减
遍历所有nums[j]，找到前面的满足条件的nums[i]的数量，需要先对数组排序后进行二分

算法

class Solution {
public:typedef long long ll;ll calc(vector<int> &a, ll x) {ll res = 0;int n = a.size();for (int i = 1; i < a.size(); i ++ ) {int l = 0, r = i - 1;while (l < r) {int mid = l + r + 1 >> 1;if (a[i] + a[mid] <= x) l = mid;else r = mid - 1;}if (a[i] + a[l] <= x)res += l + 1;}return res;}long long countFairPairs(vector<int>& a, int lower, int upper) {sort(a.begin(), a.end());return calc(a, upper) - calc(a, lower - 1);}
};

6356. 子字符串异或查询

思路

由于val ^ first == second，根据异或运算性质，val = first ^ second
即找到val的二进制在给定字符串中最先出现的位置
暴力算法是记录s的所有子串，o(n2)会超时
由于二进制长度不会超过32位，故记录时只用对每个起点枚举32位的长度
最后查找结果即可

算法

class Solution {
public:vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {vector<vector<int>> ans;unordered_map<string, int> mp;int n = s.size();for (int i = 0; i < n; i ++ )for (int j = i; j < n; j ++ ) {string t = s.substr(i, j - i + 1);if (j - i + 1 >= 32) break;if (!mp.count(t))mp[t] = i;}for (auto x : queries) {int t = x[0] ^ x[1];string a;while (t) {if (t & 1) a = '1' + a;else a = '0' + a;t >>= 1;}if (a.size() == 0) a = "0";if (mp.count(a)) ans.push_back({mp[a], mp[a] + (int)a.size() - 1});else ans.push_back({-1, -1});}return ans;}
};