C++刷题实战（Array)

2D Array - DS

思路：不断求和比较更新最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int hourglassSum(vector<vector<int>> arr) {
    
    int sumMax=arr[0][0]+arr[0][1]+arr[0][2]
            +arr[1][1]
            +arr[2][0]+arr[2][1]+arr[2][2];;
    int lNum=arr.size();
    int vNum=arr[0].size();

    for(int i=0;i<lNum-2;++i){
        for(int j=0;j<vNum-2;++j){
            int tem=arr[i][j]+arr[i][j+1]+arr[i][j+2]
            +arr[i+1][j+1]
            +arr[i+2][j]+arr[i+2][j+1]+arr[i+2][j+2];
            if(tem>sumMax){
                sumMax=tem;
            }
        }
    }
    return sumMax;

}

vector operator[]

Arrays: Left Rotation

思路：先计算出实际偏移值，因为左移5次是一个循环，然后根据偏移值构建新的int数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> rotLeft(vector<int> a, int d) {
    int aSize=a.size();
    int usefulRotationTime=d%aSize;
    vector<int> b(aSize,0);
    for(int i=0;i<aSize;i++){
        if(i-usefulRotationTime<0){
            b[i-usefulRotationTime+aSize]=a[i];
        }else{
            b[i-usefulRotationTime]=a[i];

        }
    }
    return b;
}

New Year Chaos

思路：只需要计算本来应该在前面但跑到后面的个数。

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
void minimumBribes(vector<int> q) {
    int n = A.size();
    int cnt = 0;
    for(int i = n - 1; i >= 0; i--)
    {
        if(A[i] != (i + 1))
        {
            if(((i - 1) >= 0) && A[i - 1] == (i + 1))
            {
                cnt++;
                swap(A[i], A[i-1]);
            }
            else if(((i - 2) >= 0) && A[i - 2] == (i + 1))
            {
                cnt += 2;
                A[i - 2] = A[i - 1];
                A[i - 1] = A[i];
                A[i] = i + 1;
            }
            else
            {
                printf("Too chaotic\n");
                return;
            }
        }      
    }
    printf("%d\n",cnt);
    return;
}

Minimum Swaps 2

思路1：从第一位开始：如果该位不是他本身（不在正确的位置上）就找到他本身并交换，以此类推。有时候会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void swap(vector<int>& arr,int x,int y){
    int tem=arr[x];
    arr[x]=arr[y];
    arr[y]=tem;
}
// Complete the minimumSwaps function below.
int minimumSwaps(vector<int> arr) {
    
    int count =0;
    for(int i=0;i<arr.size();++i){
        if(arr[i]!=i+1){
            for(int j=i;j<arr.size();++j){
                if(arr[j]==i+1){
                    swap(arr,i,j);
                    count++;
                    break;
                }
            }
        }       
    }
    return count;

}

思路2：将问题图形化，利用闭环，寻找闭环节点数

https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/

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
int minSwaps(int arr[], int n) 
{ 
    // Create an array of pairs where first 
    // element is array element and second element 
    // is position of first element 
    pair<int, int> arrPos[n]; 
    for (int i = 0; i < n; i++) 
    { 
        arrPos[i].first = arr[i]; 
        arrPos[i].second = i; 
    } 
  
    // Sort the array by array element values to 
    // get right position of every element as second 
    // element of pair. 
    sort(arrPos, arrPos + n); 
  
    // To keep track of visited elements. Initialize 
    // all elements as not visited or false. 
    vector<bool> vis(n, false); 
  
    // Initialize result 
    int ans = 0; 
  
    // Traverse array elements 
    for (int i = 0; i < n; i++) 
    { 
        // already swapped and corrected or 
        // already present at correct pos 
        if (vis[i] || arrPos[i].second == i) 
            continue; 
  
        // find out the number of  node in 
        // this cycle and add in ans 
        int cycle_size = 0; 
        int j = i; 
        while (!vis[j]) 
        { 
            vis[j] = 1; 
  
            // move to next node 
            j = arrPos[j].second; 
            cycle_size++; 
        } 
  
        // Update answer by adding current cycle.  
        if (cycle_size > 0) 
        { 
            ans += (cycle_size - 1); 
        } 
    } 
  
    // Return result 
    return ans; 
} 
  
// Driver program to test the above function 
int main() 
{ 
    int arr[] = {1, 5, 4, 3, 2}; 
    int n = (sizeof(arr) / sizeof(int)); 
    cout << minSwaps(arr, n); 
    return 0; 
}

Array Manipulation

硬算：超时

1
2
3
4
5
6
7
8
9
10
11
long arrayManipulation(int n, vector<vector<int>> queries) {
    vector<long> indexs(n,0);
    for(auto& q : queries){
        for(int i=q[0]-1;i<=q[1]-1;++i){
            indexs[i]=indexs[i]+q[2];
        }
    }
    long it = *max_element(std::begin(indexs), std::end(indexs)); 
    return it;

}

用差分数组： 对于序列a{}，取a[i]-a[i-1]为其差分数组b[i]的值，可以发现，a[i]=∑bj（1≤j≤i）

https://www.cnblogs.com/COLIN-LIGHTNING/p/8436624.html

1.定义：

对于已知有n个元素的离线数列d，我们可以建立记录它每项与前一项差值的差分数组f：显然，f[1]=d[1]-0=d[1];对于整数i∈[2,n]，我们让f[i]=d[i]-d[i-1]。

2.简单性质：

(1)计算数列各项的值：观察d[2]=f[1]+f[2]=d[1]+d[2]-d[1]=d[2]可知，数列第i项的值是可以用差分数组的前i项的和计算的，即d[i]=f[i]的前缀和。
(2)计算数列每一项的前缀和：第i项的前缀和即为数列前i项的和，那么推导可知
img
即可用差分数组求出数列前缀和；

3.用途：

(1)快速处理区间加减操作：

假如现在对数列中区间[L,R]上的数加上x，我们通过性质(1)知道，第一个受影响的差分数组中的元素为f[L],即令f[L]+=x，那么后面数列元素在计算过程中都会加上x；最后一个受影响的差分数组中的元素为f[R],所以令f[R+1]-=x，即可保证不会影响到R以后数列元素的计算。这样我们不必对区间内每一个数进行处理，只需处理两个差分后的数即可；

(2)询问区间和问题：

由性质(2)我们可以计算出数列各项的前缀和数组sum各项的值；那么显然，区间[L,R]的和即为ans=sum[R]-sum[L-1];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long arrayManipulation(int n, vector<vector<int>> queries) {
    vector<long> cf(n+1,0);//构建下标从1到n+1的N长的差分数组
    for(auto& q : queries){
        cf[q[0]]+=q[2];//根据差分数组性质
        if(q[1]+1<=n)
        cf[q[1]+1]-=q[2];
    }

    long x=0;
    long max=0;
    for(int i=1;i<=n;i++){
        x+=cf[i];//根据差分数组性质每加一位就是取最终list中后一位的值，记录最大值
        if(max<x) max=x;
    }
    return max;

}

若将(x，y)区间整体加val，我们就可以对差分数组的b[x]加val，b[y+1]减val。

差分数组