《misc》

Posted on Edited on In , Views:

1. n sum问题

1.2 three sum

【题目】

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

Example 1:

1
2
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

【解析】

找到和为0的三个指针很简单。

先排序，然后设置一个窗口，指针i作为这个窗口的左端点，数组尾部作为窗口的右端点。在这个窗口中设置两个指针：向右移的指针lo——起始位置是窗口左端点（即i）+1，向左移的指针hi——起始位置是窗口右端点。每次i移动后（窗口向右缩小），判断这三个指针所在位置元素之和是否为0，为0则得到一组答案，大于0则令指针hi–，小于0则令指针lo++。

排序的另外一个好处是方便去重。每当i移动后，如果当前位置元素和上一位置元素相同，则直接i++， 这样就能避免选到相同的元素。（不光是i，lo和hi每次移动时也要进行这样的判断）

本题还有很多细节，在代码注释中会详述。

【ac代码】

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:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> re; 
        int lo, hi; 
        int length = nums.size();
        sort(nums.begin(), nums.end()); //先排序，方便后续处理
        for(int i = 0; i<length-2; i++) //因为一共有3个指针，i最多走到length-3
        {
            if(nums[i]>0) continue; 	//位置i的元素是最小的，如果它都大于零那么必然无解
            if(i>0&&nums[i]==nums[i-1]) continue; //去重
            lo = i+1, hi = length-1;	//窗口内的两个操作指针
            while(lo<hi)
            {
                int value = nums[lo]+nums[hi]+nums[i];
                if(value==0) //如果lo、hi、i上的元素之和为0，则它们就是一组答案
                {
                    re.push_back({nums[i], nums[lo], nums[hi]});
                    
                    //既然lo、hi、i位置元素和为0，那么现在仅仅改变一个指针的值是绝对不可能让它们的和再次为0，所以两个指针都变
                    lo++, hi--; 
                    
                    /*去重*/
                    while(lo<hi&&nums[lo]==nums[lo-1]) lo++;
                    while(lo<hi&&nums[hi]==nums[hi+1]) hi--;
                }
                else if(value>0) 
                {
                    hi--;
                    while(lo<hi&&nums[hi]==nums[hi+1]) hi--; //去重
                }
                else 
                {
                    lo++;
                    while(lo<hi&&nums[lo]==nums[lo-1]) lo++; //去重
                }
            }
        }
        return re;
    }
};

1.3 four sum

【题目】

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Notice that the solution set must not contain duplicate quadruplets.

【解析】

先对数组排序，然后定义一个窗口，左边界为i（不断向右步进），右边界为数组结尾。随着i不断移动，窗口不断缩小，在这个过程中对每一个新窗口进行完整的3sum，然后用3sum的结果加i位置元素判断是否等于target

【ac代码】

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
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> re;
        sort(nums.begin(), nums.end());
        int length = nums.size();
        int hi, lo;
        
        for(int i = 0;i<length-3;i++)
        {
            if(i>0&&nums[i]==nums[i-1]) continue; //去重
            
            /*3sum*/
            for(int j = i+1;j<length-2;j++) 
            {
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                lo = j+1;
                hi = length-1;
                
                while(lo<hi)
                {
                    int value = nums[i]+nums[j]+nums[lo]+nums[hi];
                    if(value==target) 
                    {
                        re.push_back({nums[i],nums[j],nums[lo],nums[hi]});
                        lo++;
                        hi--;
                        while(lo<hi&&nums[lo]==nums[lo-1]) lo++;
                        while(lo<hi&&nums[hi]==nums[hi+1]) hi--;
                    }
                    else if(value>target)
                    {
                        hi--;
                        while(lo<hi&&nums[hi]==nums[hi+1]) hi--;
                    }
                    else 
                    {
                        lo++;
                        while(lo<hi&&nums[lo]==nums[lo-1]) lo++;
                    }
                }
            }
        }
        return re;
    }
};

1.4 four sum Ⅱ

【题目】

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

【解析】

这题比four sum Ⅰ简单，因为只需要算出数量而不需要返回具体下标。因为有多次查询所以优先考虑哈希表。所以先将A和B所有可能的和存入hashmap中，然后计算C和D所有可能的和的相反数，在hashmap中一一查找它们即可。

【ac代码】

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 fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        int count = 0;
        unordered_map<int, int> hashmap;
        /*将A和B的和存入hashmap中*/
        for(int i = 0;i<A.size();i++)
        {
            for(int j = 0;j<B.size();j++)
            {
                hashmap[A[i]+B[j]]++;
            }
        }
        /*在hashmap中查找C和D的和的相反数。注意可能存在多个和相同的情况，所以必须计算A+B的某个和的出现次数*/
        for(int i = 0;i<C.size();i++)
        {
            for(int j = 0;j<D.size();j++)
            {
                if(hashmap.count(-C[i]-D[j]))
                {
                    count+=hashmap[-C[i]-D[j]];
                }
            }
        }

        return count;
    }
};

2. 区间合并问题

2.1 用最少数量的箭引爆气球

【题目】

There are some spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter, and hence the x-coordinates of start and end of the diameter suffice. The start is always smaller than the end.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps traveling up infinitely.

Given an array points where points[i] = [xstart, xend], return the minimum number of arrows that must be shot to burst all balloons.

题意：给定一些区间，将所有具有公共重叠部分的区间分到一组，问最少有几组。

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4

Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2

Example 4:

Input: points = [[1,2]]
Output: 1

Example 5:

Input: points = [[2,3],[2,3]]
Output: 1

【解析】

先将所有区间按左侧端点排序，用curInterval记录当前区间组的公共部分。遍历所有区间，如果两个区间存在交集，就用curInterval记录它们的公共部分，如果两个区间不存在交集，说明我们已经找到一个最大的具有公共重叠部分的区间组了，将这次寻找记录到count中。遍历完所有区间后，count就是答案。

【ac代码】

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
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end()); //所有区间按照左端点排序
        int length = points.size();
        int shotCount = 0; //计数，有多少个区间组
        vector<int> curInterval; //当前区间组的公共重叠部分
        for(int i = 0;i<length;i++)
        {
            curInterval = points[i];
            while(i<length-1 && curInterval[1]>=points[i+1][0]) //如果当前区间和下一个区间重合
            {
                if(curInterval[1]>=points[i+1][1]) //如果当前区间包含下一个区间
                {
                    /*将当前区间更新为下一个区间*/
                    curInterval[0] = points[i+1][0];
                    curInterval[1] = points[i+1][1];
                }
                else //如果当前区间不包含下一个区间
                {
                    /*将当前区间更新为【当前区间和下一个区间的公共部分】*/
                    curInterval[0] = points[i+1][0];
                }
                i++;//继续测试下一个区间和当前区间是否重合
            }
            //printf("%d %d\n", curInterval[0],curInterval[1]); //查看每次成功找出的区间组的公共重叠部分
            shotCount++; //当前区间和下一个区间不重合了，现在我们找出了一个最大的具有公共重叠部分的区间组，将其记录
        }
        return shotCount;//最后答案就是最大的具有公共重叠部分的区间组的数量
    }
};

2.2 无重叠区间

【题目】

https://leetcode-cn.com/problems/non-overlapping-intervals/

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

【解析】

先按照左端点从小到大给所有区间排序，然后遍历所有区间：如果区间i的右端点大于区间i+1的右端点，说明两区间重叠，且i与之后所有区间重叠的概率比i+1大，因此剔除掉区间i；如果区间i的右端点大于区间i+1的左端点且小于区间i+1的右端点，说明两区间重叠，且i+1与之后所有区间重叠的概率比i大，因此剔除掉区间i+1；如果两区间不重叠，则无需剔除任一区间。

【ac代码】

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 MySort{ //一元谓词，按照区间的左端点排序
public:
    bool operator()(vector<int> vec1, vector<int> vec2){
        return vec1[0]<vec2[0];
    }    
};

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), MySort());
        int count = 0;
        int length = intervals.size();
        for(int i = 0;i<length-1;i++){
            //如果区间i的右端点大于区间i+1的右端点，说明两区间重叠，且i与之后所有区间重叠的概率比i+1大，因此剔除掉区间i
            if(intervals[i][1]>intervals[i+1][1]) count++; 
            
            //如果区间i的右端点大于区间i+1的左端点且小于区间i+1的右端点，说明两区间重叠，且i+1与之后所有区间重叠的概率比i大，因此剔除掉区间i+1
            else if(intervals[i][1]>intervals[i+1][0]){
                intervals[i+1][0] = intervals[i][0];
                intervals[i+1][1] = intervals[i][1];
                count++;
            }
        }
        return count;
    }
};

3. 二分查找

3.1 整数二分查找

整数二分的难点在于每次更新$mid = \frac{l+r}{2}$还是$mid = \frac{l+r+1}{2}$，因此最好把模板背下来，否则边界问题不好处理。

假定问题的值域为下面这个数轴，现在要通过二分法找到target

有两种选择：

  1. 当mid落在target左边，更新当前查找区间的左端点l = mid，否则更新右端点r = mid-1。这种方案每次更新mid的操作为mid = l+r+1>>1
  2. 当mid落在target右边，更新当前查找区间的右端点r = mid，否则更新左端点l = mid+1。这种方案每次更新mid的操作为mid = l+r>>1

这两种选择看似一样，当target只有一个时，它们的效果确实是相同的，但是当target有多个时，第1种会找到最后一个target，第2种会找到第一个target。

【例题】找出某一个数字在数组中出现的起始位置

即给定一个数组，里面所有相同的数都必定连续出现。

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
​```c++
#include<iostream>
using namespace std;
const int N = 100010;
int q[N];
int n,m; //用户输入的数组长度和查询次数


int FindFirst(int value) //找到数组中该元素出现的第一个位置，找不到返回-1
{ //要找到target第一次出现的位置，就要选择第2种方案
    int l = 0, r = n-1;
    int mid = 0;
    while(l<r)
    {
        mid = l+r >> 1; 
        if(q[mid]>=value) r = mid; 
        else l = mid + 1;
    }
    if(q[l]!=value) return -1;
    return l;
}

int FindLast(int value) //找到数组中该元素出现的最后一个位置，找不到返回-1
{  //要找到target最后一次出现的位置，就要选择第1种方案
    int l = 0, r = n-1;
    int mid = 0;
    while(l<r)
    {
        mid = l+r+1 >> 1;
        if(q[mid]<=value) l = mid;
        else r = mid - 1;
    }
    if(q[l]!=value) return -1;
    return l;
}


int main()
{

    scanf("%d%d",&n,&m);
    for(int i = 0;i<n;i++) scanf("%d",&q[i]);
    
    int a = 0;
    while(m--) //m次询问
    {
        scanf("%d",&a);
        printf("%d %d\n", FindFirst(a), FindLast(a));
    }
    return 0;
}

3.2 浮点数二分查找

不像整数二分需要考虑边界情况，不需要加1减1操作，因此相对简单，mid落在target哪边，就令当前查找区间哪边的端点更新为mid即可。

【例题】求数的三次方根

数的范围-1w~+1w，结果保留6位小数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;

double find(double value)
{
    double l = -1e4, r = 1e4;
    double mid = 0;
    while(r-l>0.0000001)
    {
        mid = (l+r)/2;
        if(mid*mid*mid < value) l = mid; //mid落在value左侧时将查找区间左侧端点l更新为mid
        else r = mid;
    }
    return l;
}

int main()
{
    double a = 0;
    scanf("%lf", &a);
    printf("%.6lf", find(a));
    return 0;
}

4. 离散化

模板

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
vector<int> alls; // 离散化处理数组，现在里面存储了原数组中所有【有意义】的值的【下标】
sort(alls.begin(), alls.end()); // 将所有下标排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复下标
int a[原数组中有意义元素个数]; //离散化数组

/* 将原数组下标x映射到离散化数组的下标（若有重复，则返回第一个）*/
int find(int x) 
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r; // 映射到0, 1, 2, ...n
}

/*现在可以利用find函数构造离散化数组了。原数组中【下标间距可能很大】的所有元素按照它们的相对
位置被存放到离散化数组a的a[0],a[1],a[2]...中。*/
for(int i = 0;i<离散化处理数组.size();i++) 
    {
        int x = find(离散化处理数组[i]);//根据元素在原数组中的下标找到它在离散化数组中的下标
    	a[x] = 原数组[离散化处理数组[i]]; //原数组无法用数组表示，因此这一句只是逻辑上的
    }

4.1 典型应用：求长度巨大数组的区间和

题目：给定一个无限长的数轴，开始时所有坐标上的值都是0，现在进行n次操作，每次将位置x上的数加上c，接下来进行m次询问，每次询问求出数轴上【数l】和【数r】之间所有数的和。
数据范围：

−10^9≤x≤10^9,
1≤n,m≤10^5,
−10^9≤l≤r≤10^9,
−10000≤c≤10000

题目要求数轴的长度无限，因此我们不可能直接用数组存储每一个数。不过观察n和m的数据范围就会发现，实际上我们总共只会对数轴上10^5个数进行操作（只会进行m次询问），而且题目要求对区间范围的计算只需关注两个数【相对位置】，这种情况下就可以使用离散化来求解。

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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;

int n, m; //一共对数组元素进行n次加操作，之后询问m次子区间和
int a[N], s[N]; //a为离散化数组，s为用来算子区间和的前缀和数组

vector<int> alls; //离散化处理数组
vector<PII> add, query; //【加操作数组】和【询问数组】


//找到元素x在离散化数组中的下标。这是离散化的核心，它提供了从元素（原数组的值）到相对位置（原数组的下标）的映射关系，当然，在离散化之前要先将原数组排序+去重
int find(int x)
{
    int l = 0, r = alls.size()-1; //注意一定是alls.size()-1，而不是n-1，因为还要把每次询问的两端点加入到离散化处理数组中
    while(l<r)
    {
        int mid = l+r>>1;
        if(alls[mid]>=x) r=mid;
        else l = mid+1;
    }
    return l+1; //因为之后要使用前缀和处理，因此使让下标从1开始
}

int main()
{
    cin>>n>>m;
    
    int x,c;
    for(int i = 0;i<n;i++)
    {
        cin>>x>>c;
        add.push_back({x,c}); //存储待执行的加操作
        alls.push_back(x); //将每个被加元素的下标存入离散化处理数组
    }
    
    int l, r;
    for(int i = 0;i<m;i++)
    {
        cin>>l>>r;
        query.push_back({l,r}); //存储待询问子区间和操作
        
        /*每次被询问的子区间的左右端点也必须离散化（想想为什么?）*/
        alls.push_back(l);
        alls.push_back(r);
    }
    
    /*离散化数组处理*/
    sort(alls.begin(), alls.end());  //排序
    alls.erase(unique(alls.begin(), alls.end()), alls.end()); //去重
    
    
    /*执行加操作*/
    for(int i = 0;i<add.size();i++) 
    {
        int x = find(add[i].first);//根据元素在原数组中的位置找到它在离散化数组中的位置
        a[x] += add[i].second; //在离散化数组中对该元素进行加操作
    }
    
    /*多次询问子区间和，用前缀和解决*/
    for(int i = 1;i<=alls.size();i++) s[i] = s[i-1]+a[i]; 
    
    for(int i = 0;i<query.size();i++)
    {
        int l = find(query[i].first), r = find(query[i].second); //注意左右两个端点都要先转化为离散化数组下标后才能使用
        cout<< s[r]-s[l-1]<<endl;
    }
    return 0;
}