T1 6354. 找出数组的串联值

求整数的位数

除以10的次数就是整数的位数

双指针

左右指针同时向中间移动

奇数特殊处理

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    long long findTheArrayConcVal(vector<int>& nums) {
        int i = 0;
        int j = nums.size() - 1;
        long long t = 0;
        while(i < j)
        {
            long long y = nums[j];
            long long x = nums[i];
          
          	// 求y的位数
            while(y)
            {
                x *= 10;
                y /= 10;
            }
            t += x + nums[j];
            i++;
            j--;
        }
        if(i == j) t += nums[j];
        return t;
    }
};

T2 6355. 统计公平数对的数目

典型两数之和做法

排序之后

先枚举第一个数,再寻找第二个数

二分

根据上下边界去寻找第二个数的范围, 相减获得数位的值

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long ret = 0;
        for(int i = 0; i < n; i++)
        {
            int t = upper - nums[i];
            
            int l = i + 1, r = n - 1;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(nums[mid] <= t) l = mid;
                else r = mid - 1;
            }
            
            int up = l;
            
            t = lower - nums[i];
            l = i + 1, r = n - 1;
            
            while(l < r)
            {
                int mid = l + r >> 1;
                if(nums[mid] >= t) r = mid;
                else l = mid + 1;
            }
            int lo = r;
            
            if(up < n && nums[i] + nums[up] <= upper && nums[i] + nums[lo] >= lower)
            {
                ret += up - lo + 1;
            }
        }
        
        return ret;
        
    }
};

C++内置二分库函数

1
2
lower_bound
upper_bound

T3 子字符串异或查询

哈希表

哈希标记录每一个子串的值

位运算

^ 运算规则, 等式变形

每增加一位左移一位并且加上下位的值,并记录在哈希表中, 答案返回哈希表的值

二进制

数据范围和二进制的转换2^30 > 10^9

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
        unordered_map<int, pair<int,int> > hash;
        int n = s.size();

        for(int i = 0; i < n; i++)
        {
            int x = 0;
            for(int j = i; j < n && j < i + 30; j++)
            {
                // x = (x * 2) + (s[j] - '0');
                x = x << 1 | (s[j] & 1);
                if(hash.find(x) == hash.end() || hash[x].second - hash[x].first > j - i)
                    hash[x] = {i,j};
            }
        }

        vector<vector<int>> ret;

        for(auto &q:queries)
        {
            // val ^ first = second
            // val ^ first ^ first = second ^ first
            // val = second ^ first
            int val = q[1] ^ q[0];
            if(hash.find(val) == hash.end()) ret.push_back({-1,-1});
            else ret.push_back({hash[val].first,hash[val].second});
        }

        return ret;
    }
};
1
'1' -> ASCII: 49 = (110001)2

T4 6357. 最少得分子序列