前面的话

到大三了才深刻意识到自己算法基础的薄弱，趁暑期有时间应该多做一些算法题。
写一个 c++小算法还不如大一的自己了。所以在这里分享一些。

更新了分类栏目。
争取每工作日做一道题。
POPIAPA，PIPOPA, POPIPAPAPIPOPA!

其他小知识

树状数组

树状数组-利用 lowbit 的特殊数组数据结构，有奇效

  • 前置知识 lowbit

    • lowbit 即一个 $n$ 的数用二进制表示，其最低位的为 1 以及其后的 0 组成的数。
    • $44=(101100){(2)}$，$lowbit((101100{(2)}))=(100)_{(2)}=4$
    • 怎么得到呢？
      • 将这个数取反，然后+1（这其实等价于取负），再和原来的数 与 就好了。
      • 可以论证，$lowbit(x)=x&(-x)$

  • 通过树状数组结构可以快速得到一个数组某个位置前面的数 （作为一个数，它前面的数是它的子节点）image.png|400

    • 注意：$t[x]$ 保存以 $x$ 为根的子树中叶节点的值的和。$t[4]=t[2]+t[3]+a[4]=a[1]+a[2]+a[3]+a[4]$

  • 观察进一步发现

    • 树状数组中，节点 $x$ 的父节点为 $x+lowbit(x)$， 查父操作
    • 单点修改
      • add 操作
      • 我们需要维护和结构，所以某一点更新，需要不断更新其父亲的和
1
2
3
4
5
int add(int x,int k)//将x点的值增加k
{
	for(int i=x;i<=n;i+=lowbit(i))
		t[i]+=k;
}
  • 关于另一个操作
    • 区间查询
      • ask 操作
      • 例如：我们需要查询前 7 项的区间和 sum[7]
      • 发现 sum[7]=t[7]+t[6]+t[4]
      • 又发现7-lowbit[7]=6, 6-lowbit[6]=4
      • 故
1
2
3
4
5
6
7
int ask(x){
	int sum = 0;
	for(int i=x;i;i-=lowbit(i)){
		sum+=t[i];
	}
	return sum;
}

附加一个应用冒泡排序交换次数

  • 思路：
    • 冒泡排序每交换一次都消除且仅消除一个逆序对
    • 只需要计算逆序对
    • 由于本题的数组是 $(1\dots n)$ 随机打乱，故即 $i<j,a_{i}>a_{j}即a_{i}>j$ 是逆序对
    • 如果能快速计算某 $j$ 之前的 $i$ 的大于 $a_{j}$ 的数量就好了
    • 如果我们每次将一个输入的 $a_{i}$ 插入到树状数组的 $a_{i}$ 位置并令其大小为 1，（调用 $add(a_{i},1)$）更新 $t[a_{i}]$ 的值，那么如果对于一个遍历到的 $j$，只需要调用 $ask(j)$，就可以知道树状数组前 $j$ 个元素的和。
    • 这个前缀和$sum$，表达的是满足 $i<j,a_{i}<a_{j}$ 的个数（$i<j$ 是由于遍历过程自然得到，$a_{i}$ 小于 $a_{j}$ 是因为我们这时候 ask(j)，所以 $a_{i}$ 能被查到全是在 $j$ 之前，所以 $a_{i}{<j}$，由于本题的数组分布是 (1..n)，所以自然 $a_{i}<a_{j}$）
    • 我们用 $j-sum$, 就得到了逆序对的个数。（不是逆序对的元素数完了，剩下的都是逆序对）
    • 把这个加总到 ans
    • 继续遍历
  • 返回结果。

应试八股

以个人名义稍稍强调一下答题规范，因为期中批卷感觉咱们班在答题上有点吃亏，我真诚希望咱班孩子期末能多捞点分： 首先助教批卷的注意力一般是：先看你会不会，然后看你有没有规范地说明这个问题，最后是检查一些易错的边界条件判断。所以强调几点我个人的建议：
1. 思路最好多写点以及规范一点。极少部分人题解写的太少，并且没有规范说明解题过程，对于没写的部分助教可能觉得你会，但是不可能假定你会而给满分。少部分人思路只写一句话或不写思路，全靠伪代码说明，这样其实就是逼着助教逐行思考代码逻辑，而写错伪代码的概率比写错思路要大很多，所以你懂的。当然在这种情况下建议你的伪代码最好规范且精简一点。
2. 伪代码可以精简一些：伪代码是用于在文字叙述不够清晰直观时的补充说明，规范化地交代解题思路以及关键步骤，如果思路就已经像伪代码那样严谨的情况下甚至可以不写。有些人详细到人肉 python 级别，其实没有必要而且不建议。
主要原因如下：
①太浪费时间；
②助教更关注你的算法逻辑而非代码级实现；
③多写多错。
3. 还有极少数人会把书上的算法重复实现一遍，没有必要，书上算法可以黑盒调用（比如说快速选择算法）。
4. 一定要把边界情况和关键细节考虑在内。有人不写伪代码，但是思路写得跟伪代码一样，把所有初始结束边界情况和实现细节考虑到了，一样是满分；有的写了一大页伪代码，没有写出来那些关键的细节怎么处理，一样会扣分。建议在书写过程中认真地考虑一下，如果不留意的话，最后很可能因为以为无关大雅的实现细节而失分。最后祝大家考试加油 (•̀ᴗ•́)و ̑̑

刷题

二进制相关

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

思路：
做排序，比如 nums=[-1,0,1,2,-1,-4] 也就是 [-4,-1,-1,0,1,2]
三元组满足

  • 先遍历找出最小的数, 调整数组做一个哈希，比如最小的数是 -4，则 hash[0]代表-4
  • 通过此可以将三元组转化为二元组
  • 但这又提醒我了：每次定一个数是谁，可以转化为二元组和问题。很方便使用双指针。因为两数之和越大，另一个数就越小，保证了遍历的高效性。
    • i 定位我们找二元组的范围，然后用双指针 l 和 r 从 i+1 和 n-1 出发，相向而行

附上代码：
（用 cmd+shift+v 才能实现纯文本复制，解决 ob 的代码格式问题）

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
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    bool checkZero(vector<int>& nums, int i, int j, int k) {
        return nums[i] + nums[j] + nums[k];
    }

    void pushInto(vector<int>& res, int i, int j, int k) {
        res.push_back(i);
        res.push_back(j);
        res.push_back(k);
    }

    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size(); // 修正：使用 size() 而不是 len()

        sort(nums.begin(), nums.end()); 

        for (int i = 0; i < n - 1; i++) { // 最后两个数都需要留出空间
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // 跳过重复的 i
            }

            int l = i + 1;
            int r = n - 1;

            if(l>n-1){ //超出了
                break;
            }
            while (l < r) { 
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    res.push_back({nums[i], nums[l], nums[r]});

                    // 跳过重复的 l 和 r
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;

                    l++;
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return res;
    }
};

2419. 按位与最大的最长子数组

只需要注意一个事实：两个数做按位与，结果小于等于二者。
所以只需要找最长的包含最大数的序列。

  • 有个小细节要注意一下：你要找所有子序列中最长的由最大数组成的序列
  • 比如 55555 45555 555，最长的是 5555555(6:12)

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int len=nums.size();
        int m=*max_element(nums.begin(),nums.end());

        int res=0;
        for(int i=0;i<len;i++){
            int j=i;
            if(nums[i]==m){ // 如果是以最大值开始的序列
                while(j<len && nums[j]==m){
                    ++j;
                }
            }
            // 已经数完了当前的序列长度
            res=max(res,j-i);
            i=j;
        }
        return res;
    }
};

326. 3 的幂

2438. 二的幂数组中查询范围内的乘积

解答

image.png

这个题目，最关键的是二进制分解。
如何快速知道每个数由 2 的多少次幂相加得到？
——二进制表示，某 bit 为 1 就是需要加这个 bit 对应的数，为 0 则不加。

这里需要注意一点，根据离散数学知识，mod 的性质：对于我们运算得到的很大的数取模，等价于对于这个数的每一个因子（也就是 [left,right] 范围内的 2 的某次幂的数列）取模。

容易得到代码

Code

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 {
private:
    const int MOD = 1000000007;
public:

    int getAns(int left,int right,vector<int>& powers){
        int cur=1;
        for(int i=left;i<=right;i++){
            cur = static_cast<long long>(cur) * powers[i] % MOD;
        }
        return cur;
    }

    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        // use binary to express n
        vector<int> powers;
        vector<int> ans;
        int tmp=n;
        int bitnum=1;
        while(tmp){
            if(tmp%2){powers.push_back(bitnum);}
            bitnum*=2;
            tmp=tmp>>1;
        }

        for(int i=0;i<queries.size();i++){
            int res_i=getAns(queries[i][0],queries[i][1],powers);
            ans.push_back(res_i);
        }

        return ans;
    }
};

分析

  1. 试除法

判断一个数是不是 3 的次幂。
我们可以通过不断除这个数来看。

注意负数和 0 一定不是 3 的次幂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPowerOfThree(int n) {
        int tmp=n;
        while(tmp>1){
            if(tmp%3!=0){
                return false;
            }
            tmp/=3;
        }
        if(tmp<=0){
            return false;
        }
        return true;
    }
};
  1. 在本题 INT 范围内，有符号整数范围内最大的一个 3 的幂是 3^19=1,162,261,467

所以只要检查 n 是不是其约数

1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};

3495. 使数组元素都变为零的最少操作次数

给你一个二维数组 queries，其中 queries[i] 形式为 [l, r]。每个 queries[i] 表示了一个元素范围从 l 到 r （包括 l 和 r ）的整数数组 nums 。
在一次操作中，你可以：

  • 选择一个查询数组中的两个整数 a 和 b。
  • 将它们替换为 floor(a / 4) 和 floor(b / 4)。
    你的任务是确定对于每个查询，将数组中的所有元素都变为零的 最少 操作次数。返回所有查询结果的总和。

分析

原题详细解释可以看 link
这里容易看出位运算能方便做。

即，每个数 x 变为 0 的 最少操作次数，其实就是求 4^(cnt-1)<=x<=4^cnt-1 cnt 的个数

我们可以先数出 l 介于什么 cnt 的范围，借助位运算来推进。

Code

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
42
class Solution {
public:
    long long minOperations(vector<vector<int>>& queries) {
        int n = queries.size();
        long long ans=0;
        for (int i = 0; i < n; i++) {
            vector<int> query=queries[i];
            int l=query[0];
            int r= query[1];
            // 0-3 need 1
            // 4-15 need 2
            // 16-4^3-1 need 3
            long long mybase=4;
            long long cnt=1;
            long long sum=0;
            while(mybase <= l){
               cnt++;
               mybase<<=2;
            }
            // l need to do cnt times to get 0;
            
            while(mybase<=r){
                // mybase is 4^cnt, numbers from 4^(cnt-1) to 4^cnt-1 need divide 4 for cnt times to get to 0
                // so it's mybase-1 - l +1 , base -l
                // it's well defined. the first l is also fit this.
                sum+=(long long)(mybase-l)*cnt;
                l = mybase;
                mybase <<=2;
                cnt++;
                // cnt++;
            }

            // tail situation
            // now l<=r<mybase, we neet to count (r-l+1)*cnt
            sum+=(r-l+1)*cnt;
            ans+=(sum+1)/2;

        }
        return ans;

    }
};

可以优化为前缀和，用一个匿名函数 f 来进一步简化

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 minOperations(vector<vector<int>>& queries) {
        auto f = [](long long x) {
            if (x <= 0) return 0LL;
            long long base = 1, cnt = 1, sum = 0;
            while ((base << 2) - 1 <= x) {
                long long len = (base << 2) - base; // 区间长度
                sum += len * cnt;
                base <<= 2;
                cnt++;
            }
            sum += (x - base + 1) * cnt;
            return sum;
        };

        long long ans = 0;
        for (auto &q : queries) {
            long long l = q[0], r = q[1];
            long long total = f(r) - f(l - 1);
            ans += (total + 1) / 2;
        }
        return ans;
    }
};

图问题

3341. 到达最后一个房间的最短时间

说来惭愧, djikstra 都不熟练，找官方题解画虎的，大体类似。
稍后可以发一下 dijkstra 的笔记。

image.png

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public:
    // 建一个结构存每个点的状态
    struct State{
        int x;
        int y;
        int dis; // 到此点的最小距离
        State(int x, int y, int dis):x(x),y(y),dis(dis){};

        // 重载运算符变成最小堆
        bool operator < (const State &rth) const{
            return dis>rth.dis;
        }
    };

    // 保存方向：又做
    int dirs[4][2]={{1,0},{-1,0},{0,1},{0,-1}};    
    int minTimeToReach(vector<vector<int>>& moveTime) {
        int inf=INT_MAX;
        // 记录n和m
        int n=moveTime.size();
        int m=moveTime[0].size();
        // 保存距离变量
        vector<vector<int>> d(n,vector<int>(m,inf));
        // 保存是否visit
        vector<vector<int>> v(n,vector<int>(m,0));

        // 初始化起始点
        d[0][0]=0;
        priority_queue<State> pq;
        pq.push(State(0,0,0));

        while(pq.size()){
            State s=pq.top();
            pq.pop();
            // if s is visited， skip it 
            if(v[s.x][s.y]) continue;
            // 标记visited
            v[s.x][s.y]=1;

            // otherwise, visit neighbors of s. sue dirs
            
            for(int i=0;i<4;i++){
                // nx意味着neighbor x
                int nx=s.x+dirs[i][0];
                int ny=s.y+dirs[i][1];

                // 越界直接取消
                if(nx<0 || nx >=n||ny<0||ny>=m){
                    continue;
                }

                // 房间打开需要一个时间，到达也需要一个时间，取最大者是我们能出发到这个房间的最小时间
                int dist=max(moveTime[nx][ny],d[s.x][s.y])+1; //加上1 是到达nx,ny的时间
                
                if(dist<d[nx][ny]){
                    d[nx][ny]=dist;
                    // 更新heap
                    pq.push(State(nx,ny,d[nx][ny]));
                }
            }
        }
        
        return d[n-1][m-1];
    }
};

栈

679. 24 点游戏（计算器实现）

分析

本题的思路

  • 后缀表达式
    • 括号是人类用中缀表达式规避歧义的方式，对于机器，更有效的方法是借助栈思想的后缀表达式。
    • 机器不需要阅读括号。
    • 比如 2*3-1，中缀的话，可能是 2*(3-1)=4 或者 2*3-1=5
    • 如果用后缀表达式，就可以无括号的区分了。前者是 31-2*，后者是 23*1-
  • 回溯
    • 我们需要遍历 cards 的不同数字，并遍历所有运算符。
    • 在尝试某个运算符的“世界线”后，如果不合适，我们需要回溯回来。
    • 具体来说，我们每次取出两个数 l[i] 和 l[j] 作为运算，将运算结果 x 放回栈顶（这里用 vector 模拟栈），这相当于随机了后缀表达式的前两个数。
    • 回溯在这种设计下，即将 x 弹出栈。这样就回到了没有进行第一步运算的状态。接下来可以尝试其他运算符。

Code

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#define ADD 0
#define MULTIPLY 1
#define SUBTRACT 2
#define DIVIDE 3
class Solution {
private:
    static constexpr int TARGET = 24;
    static constexpr double EPSILON = 1e-6;

    bool myCal(vector<double> &l){
        if(l.empty()) return false;
        if(l.size() == 1){
            return fabs(l[0] - TARGET) < EPSILON;
        }

        // 枚举两个数
        for(int i=0;i<l.size();i++){
            for(int j=0;j<l.size();j++){
                if(i==j) continue;

                // 把剩余的数字放到 next
                vector<double> next;
                for(int k=0;k<l.size();k++){
                    if(k!=i && k!=j) next.push_back(l[k]);
                }

                // 遍历运算符
                for(int op=0;op<4;op++){
                    if(op==ADD){
                        next.push_back(l[i] + l[j]);
                    }
                    else if(op==SUBTRACT){
                        next.push_back(l[i] - l[j]);
                    }
                    else if(op==MULTIPLY){
                        next.push_back(l[i] * l[j]);
                    }
                    else if(op==DIVIDE){
                        if(fabs(l[j]) < EPSILON) continue; // 除数为0，跳过
                        next.push_back(l[i] / l[j]);
                    }

                    if(myCal(next)) return true;
                    next.pop_back();  // 回溯, 换别的运算符
                }
            }
        }
        return false;
    }

public:
    bool judgePoint24(vector<int>& cards) {
        vector<double> l;
        for(int num : cards) l.push_back(static_cast<double>(num));
        return myCal(l);
    }
};

84. 柱状图中最大的矩形（单调栈）

分析

image.png

遍历高 h 或遍历宽是两种思路，遍历 h 比较简单。

一旦确定 h，问题即找到这个 h 最靠左的下标 i 和最靠右的下标 j，使得 k in [i,j] 之间 heights[k] 不小于 h

用单调栈可以快速维护这个下标。

  • 单调栈中的元素是单调的，比如找最靠左的满足条件的下标，就可以从左往右遍历压栈，如果新元素小于等于栈顶元素则弹出，直到新元素大于栈顶元素。我们存这个下标。

    • 这个操作相当于高效利用每一次比较。作为单调栈维护的大小关系已经足够我们确定下标，就不用每次都从左往右比所有元素了。而这样最多比较次数仅仅是出栈进栈，不超过 1 次，是 $O(n)$ （平摊分析）

  • 这样，每到一个新元素，我们都找到了其左边第一个 小于 它的元素。确定它的下标以备后用，存储到 left[]

  • 同样的，我们找到 heights[] 中任意一个元素的右边第一个小于它的元素的下标，存储到 right[]

  • 由于面积计算的有效宽度，不包括第一个小于它的元素，所以我们的实际宽度 w=(right[i]-1)- (left[i]+1) +1 = (right[i]-left[i]-1)

  • 枚举每一个高度（这里实际是遍历了 heights 的元素，找到对应下标的 left 和 right），然后得到最大值。

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
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n =heights.size();
        stack<int> st;
        vector<int> left(n,-1);
        vector<int> right(n,n);

        for(int i=0;i<n;i++){
            // 出现了第一个比左侧小的
            while(!st.empty() && heights[i]<=heights[st.top()]){
                st.pop();
            }
            left[i] = (st.empty()? -1 : st.top());
            st.push(i);
        }

        st= stack<int>();
        for(int i=n-1;i>=0;i--){
            while(!st.empty() && heights[i]<=heights[st.top()]){
                st.pop();
            }
            right[i] = (st.empty()? n : st.top());
            st.push(i);
        }

        int res=0;
        for(int i=0;i<n;i++){
            // 注意我们的下标是向左（向右）第一个不满足的下标，实际计算面积要考虑满足的 是
            //(right[i]-1-(left[i]+1) +1 )=right[i]-left[i]-1
            res=max(res, (right[i]-left[i]-1) * heights[i] );
        }

        return res;
    }
};

排序应用

3446. 按对角线进行矩阵排序

3027. 人员站位的方案数 II

分析

题目如下

给你一个  n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。

我们定义 x 轴的正方向为 右 （x 轴递增的方向），x 轴的负方向为 左 （x 轴递减的方向）。类似的，我们定义 y 轴的正方向为 上 （y 轴递增的方向），y 轴的负方向为 下 （y 轴递减的方向）。

你需要安排这 n 个人的站位，这 n 个人中包括 Alice 和 Bob 。你需要确保每个点处 恰好 有 一个 人。同时，Alice 想跟 Bob 单独玩耍，所以 Alice 会以 Alice 的坐标为 左上角 ，Bob 的坐标为 右下角 建立一个矩形的围栏（注意，围栏可能 不 包含任何区域，也就是说围栏可能是一条线段）。如果围栏的 内部 或者 边缘 上有任何其他人，Alice 都会难过。

请你在确保 Alice 不会 难过的前提下，返回 Alice 和 Bob 可以选择的 点对 数目。

注意，Alice 建立的围栏必须确保 Alice 的位置是矩形的左上角，Bob 的位置是矩形的右下角。比方说，以 (1, 1) ，(1, 3) ，(3, 1) 和 (3, 3) 为矩形的四个角，给定下图的两个输入，Alice 都不能建立围栏，原因如下：

  • 图一中，Alice 在 (3, 3) 且 Bob 在 (1, 1) ，Alice 的位置不是左上角且 Bob 的位置不是右下角。
  • 图二中，Alice 在 (1, 3) 且 Bob 在 (1, 1) ，Bob 的位置不是在围栏的右下角。

image.png

  • Let’ s translate this condition
    • Assume Alice’ s position is (x1,y1), and Bob’ s position is (x2,y2)
    • Alice is at left-up Bob is at right-down, and it conclude edge and inner space situation
    • So y1>=y2, x1<=x2
    • And no other points in [(x1,y1) to (x2,y2)]
      • no other points m, x1<xm<x2, AND y1<ym<y2
  • To easily check this condition, we can pre-sort, by x increasing y decreasing
    • we iterate the sorted points, as x1
      • then iterate x2 from index i+1, so the first condition is satisfied
    • y1>=y2:
      • we use a if-condition to do this
    • x1<xm<x2 AND y1<ym<y2
      • we iterate to j as point 2, we just make sure no one point y1<=ym<=y2, ym>y2 is impossible for we jump off y2>y1
      • so we only need to make sure ym<y1
        • we don’t need to iterate all points between [i+1,j-1]
        • We just need to maintain maxY to check ym<y1 in O(1) time.

Code

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
class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        std::sort(points.begin(), points.end(),
                  [](const vector<int>& a, const vector<int>& b) {
                      if (a[0] != b[0])
                          return a[0] < b[0]; // x 升序
                      return a[1] > b[1];     // y 降序
                  });

        // Alice is left-up: x1<=x2, y1>=y2
        // for x is sorted increasingly, we hold x1<=x2

        // and no others- condition
        // it means points whose index in [i+1,j-1], their yx must >y1 or <y2, so won't bother Alice and Bob
        // we maintain a max_Y as the maximum y indexd from i+1 to j-1. 
        int n = points.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int y1 = points[i][1];
            int max_Y = INT_MIN;
            for (int j = i + 1; j < n && max_Y < y1; j++) {
                int y2 = points[j][1];
                if(y2<=y1 && y2>max_Y){
                    max_Y=y2;
                    ans++;
                }
            }
        }
        return ans;
    }
};

分析

image.png

本题采用模拟就比较容易做
模拟需要考虑

  • 怎么取出对角线的元素？
  • 排序完，怎么放回去？

究其根本是 如何遍历对角线的问题

  • 对于左下的，可见其都从 j=0 开始，我们可按行遍历，且每次 j 增加都意味着 i 增加，即坐标为 (i+j,j), 且满足 i+j<n
    • 外层循环按行，i 循环
    • 内层从 j 开始
  • 右上的是对偶的。由于主对角线和左下规则一样，我们外层循环从 j=1 开始。

Code

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
class Solution {
public:
    vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
        int n= grid.size();
        for(int i=0;i<n;i++){
            vector<int> tmp;
            for(int j=0;i+j<n;j++){
                tmp.push_back(grid[i+j][j]);

            }
            sort(tmp.begin(),tmp.end(),greater<int>());

            for(int j=0;i+j<n;j++){
                grid[i+j][j]=tmp[j];
            }
        }

        // 右上角是反过来的，非递减，所以用默认less顺序
        for(int j=1;j<n;j++){
            vector<int> tmp;
            for(int i=0;i+j<n;i++){
                tmp.push_back(grid[i][i+j]);
            }

            sort(tmp.begin(),tmp.end(),less<int>());

            for(int i=0;i+j<n;i++){
                grid[i][i+j]=tmp[i];
            }
        }

        return grid;
    }
};

回溯

93. 复原 IP 地址

image.png

解析

这道题的最大思想就是 回溯
所谓回溯，就是记录你之前获得的答案，局部答案组成全局答案。

  • 为什么适用于 IP 地址呢？
    • ip 地址分为 4 块。所以前 i 块如果确定为合法，后面类似的操作就可以了。可以按 dfs 的思想来做。用 vector<int> segments 存储每一块的数字，最后再汇总。
    • 注意 dfs 中前导零处理完直接 return
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
private:
    const int SEG_CNT=4; //ip一共有四块

    vector<string> ans;
    vector<int> segments;// 存储每一个块的数字
public:


    /*
        string &s: 目标处理的字符串
        int seg_start: 当前块对应的index起始位置
        int seg_id: 当前块对应的第几个块。一共有四块
    */
    void dfs(string &s,int seg_start,int seg_id){
        // 做一些边界条件的判断
        // 如果遍历完了，且seg_id正好到4，就直接做。
        if(seg_start>=s.size()){
            string ipAddr;
            if(seg_id>=4){
                for(int i=0;i<SEG_CNT;++i){
                    ipAddr+=to_string(segments[i]);
                    if(i!=SEG_CNT-1) ipAddr+=".";
                }
                ans.push_back((ipAddr));
            }
          
            return;  
        }
        if(seg_id>=4) return;


        // 特殊的：如果当前为是0，由于不能含有前导0，所以直接确定当前seg_id是0，存储并继续dfs
        if(s.at(seg_start)=='0'){
            segments[seg_id]=0;
            dfs(s,seg_start+1,seg_id+1);
            // 当前循环结束，不需要遍历其他可能
            return;
        }

        // 其他情况，遍历每一种可能
        int tmp_addr = 0;
        for(int drift = 0; drift <= 3 && seg_start + drift <s.size(); ++drift){
            tmp_addr = tmp_addr * 10 + (s[seg_start + drift] - '0');
            if(tmp_addr > 0xFF) break;

            if(tmp_addr>0 && tmp_addr<=0xFF){
                segments[seg_id] = tmp_addr;
                dfs(s, seg_start + drift+1, seg_id + 1);
            }
            
        }
        
    }
    vector<string> restoreIpAddresses(string s) {
        segments.resize(SEG_CNT);
        dfs(s,0,0);
        return ans;
    }
};

模拟

这个类别，有一些是简单的模拟如[[#[3477. 水果成篮 II](https //leetcode. cn/problems/fruits-into-baskets-ii/description/? envType=daily-question&envId=2025-08-05)|水果成篮]]，也有一些是需要数学推导后比较简单的。由于很难归类于某种套路，也相对容易，列入此列表。

3195. 包含所有 1 的最小矩形面积 I

分析

给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形，并且满足 grid 中所有的 1 都在矩形的内部。

返回这个矩形可能的 最小 面积。

这个题目很简单：要包含所有 1，其实就是找最大的矩形边界。
找到 1 的坐标的左最小，右最大，上最小，下最大，就可以包含所有 1.

Code

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:
    int minimumArea(vector<vector<int>>& grid) {
        int lm=INT_MAX,rm=0,um=INT_MAX,dm=0;// left right up down
        int rows=grid.size();
        int cols=grid[0].size();
        for(int i=0;i<rows;++i){
            for(int j=0;j < cols; ++j){
                if(grid[i][j]&&j<lm){
                    lm=j;
                }
                if(grid[i][j]&&j>rm){
                    rm=j;
                }
                if(grid[i][j]&&i<um){
                    um=i;
                }
                if(grid[i][j]&&i>dm){
                    dm=i;
                }
            }
        }
        return (dm-um+1)*(rm-lm+1);
    }
};

3477. 水果成篮 II

分析

今天的只需要模拟题干意思就好了。没什么好思考的必要

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        vector<bool> isEmpty(baskets.size(),1);
        vector<bool> isPut(fruits.size(),0);
        for(int i=0;i<fruits.size();++i){
            for(int j=0;j<baskets.size();++j){
                if(baskets[j]>=fruits[i] && isEmpty[j]){
                    isEmpty[j]=false;
                    isPut[i]=true;
                    break;
                }
            }
        }
        int ans=0;
        for(int i=0;i<isPut.size();++i){
            if(!isPut[i]) ++ans;
        }
        return ans;
    }
};

2348. 全 0 子数组的数目

分析

先来看看题：

给你一个整数数组 `nums` ，返回全部为 `0` 的 **子数组** 数目。
**子数组** 是一个数组中一段连续非空元素组成的序列。
**示例 1：**

输入： nums = [1,3,0,0,2,0,0,4]
输出： 6
解释：
子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
不存在长度大于 2 的全 0 子数组，所以我们返回 6 。

这里的重要 insight 是认识到：子数组是连续的，每个全部为 0 的子数组的连续为 0 的最大长度一旦确定，这个局部的最大的子数组包含的符合条件的 0 子数组总数是确定的。

是一个简单的等差数列。

比如一个最大长度为 4 的，0 0 0 0，其中含有 4 个 0，3 个 00，2 个 000，1 个 0000，所以有 (1+4)*4/2=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
26
27
28
29
30
31
32
class Solution
{
public:
    long long zeroFilledSubarray(vector<int> &nums)
    {
        int size = nums.size();
        long long ans=0;
        for (long i = 0; i < size; i++)
        {
            if (nums[i] == 0)
            {
                long j = 0;
                for (j = i; j < size; j++)
                {
                    if (nums[j] != 0)
                    {
                        ans += (1+j-i) * (j-i) / 2;
                        break;
                    }
                }
                if (j == size)
                {
                    ans += (1+j-i) * (j-i) / 2;
                }

                i = j;
            }
        }

        return ans;
    }
};

36. 有效的数独

开学了，好几天没写了，还是要坚持呢

这次是一道数独检测题，考察哈希表的思想。——即你怎么快速确定每一位是否合乎数独规则？自然的想法是记录每一行、每一列、每一个九宫格的每种数字出现的个数。

如果使用 hash 表，我们可以免去复杂的遍历操作，而在 O（1） 时间内完成上述记录的更新和检查。
故引入三个数组

  • rows[9][9] 其中第一个 9 代表一共 9 行的情况，第二个 9 是 hash（由于本数独数字分布 1-9 ，直接数组做 hash 也很方便）
  • cols[9][9] 同理，记录的是列
  • subboxes[3][3][9] 记录的是九宫格。九宫格划分直接 i/3,j/3 即可。
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
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // create a hash map. it contains 1-9 numbers appear times cnt;
        int rows[9][9];
        int cols[9][9];
        int subboxes[3][3][9];

        memset(rows,0,sizeof(rows));
        memset(cols,0,sizeof(cols));
        memset(subboxes,0,sizeof(subboxes));

        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                char c=board[i][j];
                int num=0;
                if(c!='.'){
                    num=c-'0'-1;
                    ++rows[i][num];
                    ++cols[j][num];
                    ++subboxes[i/3][j/3][num];
                    if(rows[i][num]>1 
                        || cols[j][num]>1 
                        || subboxes[i/3][j/3] [num]>1
                    )return false;    
                }

              
                
            }
        }
        return true;

        
    }
};

6. Z 字形变换

分析

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

我们只要关心：每个字符在某行即可。用一个矩阵存储每一行的 string 是一个好方法。

Code

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
class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows ==1 ||s.size()<numRows){
            return s;
        }
        vector<string> rows(numRows);
        int curRow=0;
        int goingDown=true;

        for(char c:s){
            rows[curRow]+=c;
            // add char at some line;
            curRow+=goingDown?1:-1;
            // we don't actually care about the "space" in a line, we only care about the char in a row
            if(curRow==numRows-1 || curRow==0){
                goingDown=!goingDown;
            }
        }
        
        string ans;
        for(auto str:rows){
            ans+=str;
        }
        return ans;
    }
};

动态规划

3494. 酿造药水需要的最少总时间

给你两个长度分别为 n 和 m 的整数数组 skill 和 mana 。

在一个实验室里，有 n 个巫师，他们必须按顺序酿造 m 个药水。每个药水的法力值为 mana[j]，并且每个药水 必须 依次通过 所有 巫师处理，才能完成酿造。第 i 个巫师在第 j 个药水上处理需要的时间为 timeij = skill[i] * mana[j]。

由于酿造过程非常精细，药水在当前巫师完成工作后 必须 立即传递给下一个巫师并开始处理。（连续性）这意味着时间必须保持 同步，确保每个巫师在药水到达时 马上 开始工作。

返回酿造所有药水所需的 最短 总时间。

分析

本题最重要的一点，是确认每一轮酿造过程中，巫师酿造结束的 最早时间

  • 酿造 什么时候开始 并不清晰，反而思考酿造的结束。
  • 每一个人越早开始酿造，显然结束的越早。巫师 i 能开始酿造，一方面前一个人 i-1 酿造 j 药水结束，另一方面巫师 i 酿造完了 j-1 药水，从这个角度思考，每一轮的最优解 times[n-1][j] 是通过动态规划转移方程
    • times[i][j] = max(times[i][j-1], times[i-1][j]) + skill[i] * mana[j]
  • 得到的
    • 而 times[i-1][j] 的最优情况其实也取决于 times[n-1][j] 的真正结果，我们需要反向更新来得到。但是这只影响后续计算的 times[i][j-1], for larger j，本轮的 times[n-1][j] 结果是正确的。

我们用 cur_time 记录每一瓶药酿造结束，进入下一瓶药处理的时间刻。times[i] 记录每一轮迭代中，巫师 i 酿造结束的最早时间。

  • 可能 times[i] > cur_time 这意味着，我们需要等待。

  • 否则，times[i] <= cur_time，前一瓶药酿造完，我们可以立刻开始酿造。

  • 我们最初，对 times[i] 实际没有估计（表现为代码里为 0），这实际是假设我们在这一轮可以不连续的酿造。我们在完成酿造后，根据得到的结果，优化每一瓶药的酿造时间。

    • times[i] = times[i+1] - skill[i+1] * mana[j]

  • 然后我们接着考虑下一瓶药。

    • cur_time = max(cur_time, times[i]) + skill[i] * mana[j]
      • 这里的 times[i] 是完成第 j 个药所需要的时间，计算完 times[n-1] 之后，我们需要反向更新一下之前假设不连续导致的空隙。
      • 具体而言，每一轮计算出的 times[n-1][j] （虽然没有 [j]，但是这样可以更方便表示）是准确的。但是这瓶药在经手每一个巫师时，该巫师的结束时间是一个区间。
      • 我们通过 times[i] = times[i+1] - skill[i+1] * mana[j]，来得到结束时间的最大值，来尽量错配时间，达到 完全连续 的生产时间。
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
class Solution {
public:
    using ll = long long;
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size();
        int m = mana.size();
        vector<ll> times(n); 
        
        for(int j=0; j < m; j++){
            // cur_time: one iteration, our cost of time
            ll cur_time=0;
            // all the people before n-1 wizzar have done.
            for(int i = 0; i < n; i++){
                cur_time = max(cur_time, times[i]) + skill[i] * mana[j];
                // the first potion is all the time add up.
                // and we can use this potion's time to calculate the finish time time[i][j] for each wizzar i
            }
            // times[i] at the first loop is all 0;
            times[n-1] = cur_time;

            // update times[]
            for(int i = n-2; i>=0; i--){
                times[i]=times[i+1]-skill[i+1]*mana[j];
            }
        }
        return times[n-1];
    }
};

3363. 最多可收集的水果数目

image.png

考虑使用动态规划。

分析

几个小思考：

  • 由于每一位小朋友都会 恰好 移动 n-1 次，到达房间 (n-1,n-1)，所以第一个小朋友的路线固定为主对角线。
    • 不需要再考虑，最优解 >= 主对角线元素和
    • 做完这一步，将主对角线水果数量设置为 0。避免再走。
      • 设置为 0 是比较合适的。因为虽然不会逾越对角线，但是一定会用到 fruit[n-1][n-1]
  • 如果某小朋友逾越了主对角线，容易发现他无法在 n-1 步到达 (n-1,n-1)
    • 所以在最优解，其他两个小朋友分别在上三角和下三角活动
  • 考虑 DP
    • 以上三角小朋友为例
    • 用 dp1[i,j] 表达上三角小朋友在 (i,j) 格子处最大水果数
      • dp[0,n-1]=fruits[0][n-1]
      • dp[i,j]=max{dp[i-1,j-1],dp[i-1,j],dp[i-1,j+1]}+fruit[i,j]
        • if exists
    • 用 dp2[i,j] 表达下三角小朋友在 (i,j) 格子处最大水果数
      • dp[n-1,0]=fruits[n-1][0]
      • dp[i,j]=max{dp[i+1,j-1],dp[i,j-1],dp[i-1,j-1]}+fruit[i,j]
        • if exists

Code

开始写代码.

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
42
43
44
45
46
47
48
49
50
51
52
const int INF = 0x3f3f3f3f;
class Solution {
private:
    int n;

    int getMyMax1(int i, int j, const vector<vector<int>>& dp) {
        int m=dp[i-1][j];
        if(j-1>=0 && dp[i-1][j-1]>m){m=dp[i-1][j-1];}
        if(j+1<n && dp[i-1][j+1]>m){m=dp[i-1][j+1];}
        return m;
    }

    int getMyMax2(int i, int j, const vector<vector<int>>& dp) {
        int m=dp[i][j-1];
        if(i-1>=0&&dp[i-1][j-1]>m){m=dp[i-1][j-1];}
        if(i+1<n&&dp[i+1][j-1]>m){m=dp[i+1][j-1];}
        return m;
    }

public:
    int maxCollectedFruits(vector<vector<int>>& fruits) {
        n = fruits.size();
        int res = 0;

        // 主对角线
        for (int i = 0; i < n; ++i) {
            res += fruits[i][i];
            fruits[i][i]=0;
        }

        vector<vector<int>> dp1(n, vector<int>(n, -INF));
        dp1[0][n - 1] = fruits[0][n - 1];

        vector<vector<int>> dp2(n, vector<int>(n, -INF));
        dp2[n - 1][0] = fruits[n - 1][0];

        for (int i = 1; i < n; ++i) {
            for (int j = n - 1; j>=i; --j) {
                dp1[i][j] = getMyMax1(i, j, dp1) + fruits[i][j];
            }
        }

        for (int j = 1; j < n; ++j) {
            for (int i = n - 1 ; i >= j; --i) {
                dp2[i][j] = getMyMax2(i, j, dp2) + fruits[i][j];
            }
        }
        res+=dp2[n-1][n-1]+dp1[n-1][n-1];
        return res;
    }
};

贪心

2561. 重排水果

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 minCost(vector<int>& basket1, vector<int>& basket2) {
        int m = INT_MAX;
        unordered_map<int, int> frequency;
        // find the minimum element in both baskets and count the frequency of each element
        
        for (int x1 : basket1)
        {
            frequency[x1]++;
            m=min(m, x1);
        }
        for (int x2 : basket2) {
           frequency[x2]--;
           m=min(m, x2);
        }

        long long ans = 0;

        vector<int> to_be_swap; // 记录需要交换的元素
        // 交换是什么样的？比如basket 1 成本为4的有x个，basket 2 成本为4的有y个，应该保证多的那个交换(x-y)/2个。
        for (auto [k, c] : frequency)
        {
            if (c % 2 != 0) return -1; // If any element has an odd frequency,then can't divide into 2 basket, return -1
            for(int i = 0; i < abs(c/2); i++)
            {
                to_be_swap.push_back(k);
            }
        }

        // 将to_be_swap中的元素排序
        // 我们将成本较小的元素放在前面，这样可以最小化总成本，交换前一半即可。
        // 需要注意每个元素交换不一定只交换一次，可以以最小元素m为跳板交换两次达到效果。需要比较2m和每个元素的成本
        sort(to_be_swap.begin(), to_be_swap.end());
        for (int i = 0;i<to_be_swap.size()/2;i++)
        {
            ans += min(to_be_swap[i], 2 * m);
        }
        return ans;
    }
};

2598. 执行操作后的最大 MEX

给你一个下标从 0 开始的整数数组 nums 和一个整数 value 。
在一步操作中，你可以对 nums 中的任一元素加上或减去 value 。

  • 例如，如果 nums = [1,2,3] 且 value = 2 ，你可以选择 nums[0] 减去 value ，得到 nums = [-1,2,3] 。
    数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。
  • 例如，[-1,2,3] 的 MEX 是 0 ，而 [1,0,3] 的 MEX 是 2 。
    返回在执行上述操作 任意次 后，nums 的最大 MEX 。

分析

用同余的思想很好解决这个问题：

既然我们能对每一位加减 value 任意次，则实际加减任意次后的数组，和最初的数组在 mod value 意义下都是等价的。

那么，这时候找缺失的最小非负整数的最大值，我们可以这样：

  • 先数出一个 0 <= nums[i] < value 的 mod value 意义下，不同数字的频数。可以用哈希表构建
1
2
3
4
5
std::unordered_map<int,int> cnt;
        for(int i = 0;i < nums.size(); i++){
            // 建立同余组
            cnt[(nums[i] % value +value) % value]++; // 之所以这么做，为了让负数的模也>0
        }

然后，我们可以从 0 开始遍历 MEX
如果 MEX 模 value 在 cnt 中找不到，就说明无论怎么加减，都会缺失 MEX。
而如果能找到，我们将 cnt[MEX % value]--，以说明该数已经用过。
然后，我们递增 MEX。最初找到的无法匹配 cnt 中的，就是最小的非负整数。
而由于我们贪心的统计了所有数字的频数，涵盖了加减 value 任意次数的可能，保证之前的都已经用过，所以它是最大的 MEX。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int value) {
        // 由于每个数可以加减value任意次，我们要找缺失的最小非负整数，可以同余分组来解决。
        std::unordered_map<int, int> cnt;
        for (int i = 0; i < nums.size(); i++) {
            // 建立同余组
            cnt[(nums[i] % value + value) %
                value]++; // 之所以这么做，为了让负数的模也>0
        }
        int ans = 0;
        while (cnt[ans % value] > 0) {
            cnt[ans % value]--;
            ans++;
        }
        return ans;
    }
};

哈希

LCR 063. 单词替换

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
class Solution {
public:
    string replaceWords(vector<string>& dictionary, string sentence) {
        unordered_set<string> dict(dictionary.begin(), dictionary.end());
        stringstream ss(sentence);
        string word, ans;
        bool first = true;

        while (ss >> word) {
            string prefix;
            for (int j = 1; j <= word.size(); j++) {
                prefix = word.substr(0, j);
                if (dict.count(prefix)) {
                    word = prefix;
                    break;
                }
            }
            if (!first) ans.push_back(' ');
            ans += word;
            first = false;
        }

        return ans;
    }
};

Log Trick

这是一个利用特殊性质化简迭代的问题大类。

3097. 或值至少为 K 的最短子数组 II

分析

经典性质：

  • 按位或的序列是单调递增的
  • 如果按二进制表达位来思考按位或，相当于集合的取并
  • 我们每次对于一个 i，遍历小于 i 的 j，将每个 j 更新：加入这个新元素。
  • 如果 i=3, 则 j=0 存储了 nums[0] | nums[1] | nums[2] | nums[3], j=1 存储了 nums[1] | ... | nums[3], … j=2 存储了 nums[2] | nums[3]

在这个思路下，如果新的 nums[i] 我们发现其和 nums[j] 做 or，结果 nums[j] 没有变大，就说明 nums[i] 的二进制表示的 32bit 的集合是 nums[j] 表示的子集.
那么对于更靠前的 j，则结果也必然不会变化。我们可以直接 break 内层循环

发散

你不难想象，二进制提供了一些很好的性质。a & b 其实就是集合的交，a ^ b 可以看作集合的对称差。

好习惯

按位操作的优先级 低于 == 的优先级。所以你最好加一个括号!

Code

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
class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        // or: a | b >= a, or b
        int n=nums.size();
        int ret=INT_MAX;
        // 计算所有子数组的OR并记录下来
        for(int i=0;i<n;i++){
            int x=nums[i];
            if(x>=k) return 1;
            // we now calculate the j from i-1 to 0. update it as the ORs from j to i in original nums

            for(int j=i-1;j>=0 ;j--){
                if((nums[j] | x )== nums[j]){
                    break;
                }
                
                // nums[j] = OR all the nums[j+k], where j+k <i
                nums[j] |=x;
                if(nums[j]>=k){
                   // or is non-decrease.
                    ret= min(ret, i-j+1); 
                }
            }
        }
        return ret==INT_MAX? -1 : ret;
    }
};

3171. 找到按位或最接近 K 的子数组

分析

和 3097 同理。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int ret=INT_MAX;
        for(int i=0;i<nums.size();i++){
            int x=nums[i];
            ret=min(ret,abs(x-k));
            for(int j=i-1; j>=0;j--){
                if((nums[j] | x) == nums[j]){break;} 
                nums[j]|=x;
                ret=min(ret, abs(nums[j]-k));
            }
        }
        return ret;
    }
};

2411. 按位或最大的最小子数组长度

分析

这题要我们找的是从 i 出发的子数组，其按位或最大（指的是 [i,k], k in (i, n]） 的按位或），且长度最短。

我们外层循环迭代右边界，逐步更新 j。
我们知道，如果 (nums[j] | x) == nums[j], 说明新加入的元素 x = nums[i] 不会让原来的从 j 出发的子数组变的更大。在这个意义上，对于更小的 j 比如 j-1, j-2, ... 0，由于他们遵循 nums[0] 包含 nums[1] ... 包含 ...nums[j]，自然也不需要更新（不会变的更大！）

所以每次内层循环 ans[j] = i-j +1, 记录着最后一次变大的数值。

最后，当 i 迭代到 n，我们就得到了最终的全局视角的答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        int n=nums.size();
        vector<int> ans(n);
        // get the max or value

        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i];
            int j = i - 1;
            ans[i]=1;
            for (j = i - 1; j >= 0; j--) {
                // if x subset nums[j], then [0, i], cannot find larger or value
                if((nums[j] | x) == nums[j]){
                    break;
                }
                nums[j] |= x;

                ans[j] = i-j+1;
            }
        }
        return ans;
    }
};

视角 2: 找到“最远的 1”bit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 1);
        vector<int> last(30, -1);

        // 记录每个bit出现的最靠后的位置
        for(int i=n-1;i>=0;i--){
            for(int b=0;b<31;b++){
                if (nums[i] & 1<<b){
                    last[b]=i;
                }
            }

            int farthest = *max_element(last.begin(),last.end());
            // if farthest is -1, it means right has no any 1 bit. or is 0. shortest ans is 1
            ans[i]=farthest!=-1 ? farthest-i+1 : 1;
        }
        return ans;
    }
};

这个思路比较明确：每个 bit 为 1 出现的最靠后的那一个，就是能让

蓝桥杯 2622 和与乘积

题面

给定一个数列 A = (a1, a2, · · · , an)，问有多少个区间 [L, R] 满足区间内元素的乘积等于他们的和，即 aL · aL+1 · · · aR = aL + aL+1 + · · · + aR。

输入格式

输入第一行包含一个整数 n，表示数列的长度。
第二行包含 n 个整数，依次表示数列中的数 a1, a2, · · · , an。

输出格式

输出仅一行，包含一个整数表示满足如上条件的区间的个数。

思路

如果元素都是 >1 的，容易知道乘法的增长速度远大于加法。

解读

可严格证明：如果 [L, R] 满足 sum_lr < product_lr, 则 [L, R+k], for some k, 都 sum_lk < product_lk

但是本题有 1 元素，我们单独处理。把 >1 的元素单挑出来。记录其下标。这样可以减少溢出

怎么处理 1 元素呢？

1 元素有个有趣的性质：在序列和 sum_ij、序列乘积 product_ij 中，有且仅有 1 元素加入序列， sum_ij 可以单调增加 1 而 product_ij 不变。
这给了一个 insight，我们可以计算 int dis = product_ij - sum_ij, 即 product 高于 sum 的部分，并提前计算好每个非 1 的元素，向左有多少连续的 1 (L1_Count)，向右则是 R1_Count

  • 计算连续的 1 的数量可以考虑用动态规划，在 O(n) 内完成。
  • 如果左右两边的 1 的总数不够弥补 dis，则可以直接 break，因为此段以 i 开头的序列无法通过左右 +1 来构成答案。
  • 如果可以，则利用滑动窗口确定滑动的边界。右边的 1 最多用 r = min(rones, dis) 个，左边的最多用 l=min(lones, dis) 个，总体来说方案数是滑动的，l + r - dis +1 个
    • 代码中用的是一个更严谨的方法。通过左边用多少个 ：k，来构造不等式来说的。道理是一样的。
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <cstring> // For memset, though std::vector is preferred
#define endl "\n"

using namespace std;

// N 应该略大于最大可能的元素数量
const int N_MAX = 200005;

// a 数组为原始数据数组
int a[N_MAX];
// sum 数组记录前缀和数组 (使用 long long 防止溢出，尽管元素值较小)
long long sum[N_MAX];

// b 数组为 a 中值不为 1 的元素所构成的数组
int b[N_MAX];
// id[i] 表示在 b 数组中下标为 i 的元素原始下标 (在 a 数组中的下标)
int id[N_MAX];

// L1[i] 存储紧邻 i 左侧的连续 '1' 的数量
int L1_count[N_MAX];
// R1[i] 存储紧邻 i 右侧的连续 '1' 的数量
int R1_count[N_MAX];

int n;
long long ans = 0;
int blen = 0;

void solve() {
    // 1. 输入和预处理前缀和
    if (!(cin >> n)) return;
    ans += n; // 每个单独元素 (i=j) 都是一个答案 (因为 a[i] == a[i])

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];

        if (a[i] != 1) {
            // 把不为 1 的元素放到 b 数组中去
            b[++blen] = a[i];
            id[blen] = i; // 记录原始的下标
        }
    }
    
    // 2. 预处理 L1_count 和 R1_count
    // L1_count[i]: 紧邻 a[i] 左侧连续 '1' 的数量
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) {
            // 如果 a[i] 是 1, 它的左边连续 1 的数量是它左边那个元素的数量 + 1
            L1_count[i] = L1_count[i - 1] + 1;
        } else {
            // 如果 a[i] 不是 1, 紧邻其左侧的 1 数量为 0
            L1_count[i] = 0;
        }
    }
    
    // R1_count[i]: 紧邻 a[i] 右侧连续 '1' 的数量
    for (int i = n; i >= 1; i--) {
        if (a[i] == 1) {
            // 如果 a[i] 是 1, 它的右边连续 1 的数量是它右边那个元素的数量 + 1
            R1_count[i] = R1_count[i + 1] + 1;
        } else {
            // 如果 a[i] 不是 1, 紧邻其右侧的 1 数量为 0
            R1_count[i] = 0;
        }
    }

    // 3. 遍历由非 '1' 元素构成的子数组 B[i...j]
    for (int i = 1; i <= blen; i++) {
        long long current_multi = 1;
        int idx1 = id[i]; // 左起点的原始下标

        for (int j = i; j <= blen; j++) {
            // 计算 B[i...j] 的乘积
            current_multi *= b[j];

            // 剪枝: 乘积增长过快，直接大于所有元素的最大和，后续不可能再相等
            if (current_multi > sum[n]) {
                break;
            }
            
            // 跳过 i=j (单独一个元素的子数组已在 ans+=n 中计算)
            if (i == j) continue;

            int idx2 = id[j]; // 右边界限点的原始下标

            // 计算 A[idx1...idx2] 的实际和
            long long current_sum = sum[idx2] - sum[idx1 - 1];

            // dis 是我们需要通过两侧 '1' 元素弥补的差值
            long long dis = current_multi - current_sum;

            if (dis < 0) {
                // 和大于乘积，且数组元素都 >= 1，随着 j 增大，乘积会增长更快，dis 可能会变大
                continue;
            }

            // 计算方案数
            // 需要 Dis 个 '1'，左侧有 X 个可用，右侧有 Y 个可用

            // 注意：我们取的是 idx1 左边紧邻的 1 块，和 idx2 右边紧邻的 1 块
            long long X = L1_count[idx1 - 1]; // idx1 左边紧邻的 1 块数量
            long long Y = R1_count[idx2 + 1]; // idx2 右边紧邻的 1 块数量
            
            if (X + Y < dis) {
                // 两侧 '1' 的总数不够所需差值，条件不可能成立
                continue;
            } else {
                // 有足够的 '1' 来弥补差值 Dis
                
                // k 是从左侧 X 个 '1' 中选取的数量
                // k 必须满足:
                // 1. 0 <= k <= X
                // 2. 0 <= Dis - k <= Y  => Dis - Y <= k <= Dis
                
                // k 的下限 (L_bound)
                long long L_bound = max(0LL, dis - Y);
                // k 的上限 (R_bound)
                long long R_bound = min(X, dis);
                // 实际是一个滑动窗口
                
                // 方案数 = R_bound - L_bound + 1
                // 必须保证 R_bound >= L_bound
                if (R_bound >= L_bound) {
                    ans += R_bound - L_bound + 1;
                }
            }
        }
    }

    cout << ans << endl;
}

int main() {
    // 提高 I/O 效率
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}