T1 合并两个二维数组 - 求和法

思路1

哈希表

使用哈希表合并两个数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        map<int,int> m;
      
        for(auto &p:nums1) m[p[0]]+=p[1];
        for(auto &p:nums2) m[p[0]]+=p[1];
      
        vector<vector<int> > ret;
        for(auto &p:m) ret.push_back({p.first,p.second});
        
        return ret;
    }
};

思路2归并

$T:O(m + n)$ 没有额外空间

T2 6365. 将整数减少到零需要的最少操作数

思路1

位运算

寻找末尾连续的1

如果连续的1大于2, 我们进行一步操作,将所有的1 合并为一个1;

如果末尾只有一个1, 我们直接一步操作减去最后的一个1;

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
class Solution {
public:
    int minOperations(int n) {
        int i = n;
        int ret = 0;
        while(i)
        {
            //去除末尾0
            while(i && !(i & 1)) i = i >> 1;
            
            int t = i;
            int s = 0;
            while(t & 1)
            {
                t = t >> 1;
                s++;
            }
            if(s >= 2)
            {
                ret++;
                t = t | 1;
            }
            else
                ret++;
            i = t;
        }
        
        return ret;
    }
};

思路2

DFS

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int dfs(int cnt, int n)
{
    int t = n & (-n);
    if(n - t == 0) return cnt + 1;
    return min(dfs(cnt+1, n - t), dfs(cnt + 1, n + t));
}
    int minOperations(int n) {
        return dfs(0,n);
    }
};

T3 6364. 无平方子集计数

状态压缩DP