NO.44十六届蓝桥杯备战|顺序表习题|询问学号|寄包柜|移动零|颜色分类|合并两个有序数组|pair(C++)

P3156 【深基15.例1】询问学号 - 洛谷

直接⽤ vector 或者数组模拟即可

#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 10;
int n, m;
vector<int> a(N);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (m--)
    {
        int x; cin >> x;
        cout << a[x] << endl;
    }
    
    return 0;
}

P3613 【深基15.例2】寄包柜 - 洛谷

如果⽤⼆维数组来模拟，需要开$10^5\times 10^5$⼤⼩的数组，空间会超。但是格⼦的总数量是$10^7$ ，⽤数组模拟是完全够⽤的。因此可以⽤动态扩容的数组，创建$10^5$个vector来模拟

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
vector<int> a[N];
int n, q;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    while (q--)
    {
        int op, i, j, k;
        cin >> op >> i >> j;

        if (op == 1)
        {
            cin >> k;
            if (a[i].size() <= j)
            {
                a[i].resize(j + 1);
            }
            a[i][j] = k;
        }
        else
        {
            cout << a[i][j] << endl;
        }
        
    }
    
    return 0;
}

283. 移动零 - 力扣（LeetCode）

在本题中，我们可以⽤⼀个cur指针来扫描整个数组，另⼀个dest指针⽤来记录⾮零数序列的最后⼀个位置。根据cur在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。
在cur遍历期间，使[0, dest]的元素全部都是⾮零元素，[dest + 1, cur - 1]的元素全是零
cur：扫描数组
分类讨论：

1. 遇到0，直接cur++
2. 遇到非0，swap(dest+1，cur)，dest++，cur++
   

一开始dest=-1，cur=0
cur指向0，cur直接++

cur指向1，交换dest+1和cur，dest+1是0元素区间的第一个位置，cur是当前遍历的元素，cur+1是待遍历的区间

然后dest++，cur++

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for (int cur = 0, dest = -1; cur < nums.size(); cur++)
        {
            if (nums[cur])
            {
                swap(nums[++dest], nums[cur]);
            }
        }
    }
};

75. 颜色分类 - 力扣（LeetCode）

class Solution {
public:
    void sortColors(vector<int>& nums) {
        sort(nums.begin(), nums.end());
    }
};

定义三个指针
cur：扫描数组
left：标记的是0区间的最后一个元素
right：标记的是2区间的第一个元素

在cur 往后扫描的过程中，保证：

• [0, lef t]内的元素都是0 ；
• [lef t + 1, cur - 1] 内的元素都是1 ；
• [cur, right - 1] 内的元素是待定元素；
• [right, n]内的元素都是2 。
  

cur指向2，让right-1位置的元素和cur指向的元素交换，再right–
因为此时的cur是待扫描的数，所以cur不能动

此时cur碰到0，让left+1和cur的位置交换，left++，cur++

cur碰到2，与right-1位置交换，right–

当cur碰到1，cur++

直到cur与right相遇，遍历结束

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = -1, cur = 0, right = nums.size();
        while (cur < right)
        {
            if (nums[cur] == 0) swap(nums[++left], nums[cur++]);
            else if(nums[cur] == 1) cur++;
            else swap(nums[--right], nums[cur]);
        }
    }
};

88. 合并两个有序数组 - 力扣（LeetCode）

辅助数组
可以创建⼀个辅助数组，然后⽤两个指针分别指向两个数组。每次拿出⼀个较⼩的元素放在辅助数组中，直到把所有元素全部放在辅助数组中。最后把辅助数组的结果覆盖到nums1中

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> tmp(m + n);
        int cur = 0, cur1 = 0, cur2 = 0;
        while (cur1 < m && cur2 < n)
        {
            if (nums1[cur1] <= nums2[cur2]) tmp[cur++] = nums1[cur1++];
            else tmp[cur++] = nums2[cur2++];
        }
        while (cur1 < m) tmp[cur++] = nums1[cur1++];
        while (cur2 < n) tmp[cur++] = nums2[cur2++];
  
        for(int i = 0; i < n + m; i++) nums1[i] = tmp[i];
    }
};

原地合并，需要反着遍历
cur1定义为整个nums1数组最大的值，cur2定义为整个nums2数组最大的值，cur指向的是整个nums1数组m+n的最后一个元素的位置

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int cur1 = m - 1, cur2 = n - 1, cur = n + m - 1;
        while (cur1 >= 0 && cur2 >= 0)
        {
            if (nums1[cur1] >= nums2[cur2]) nums1[cur--] = nums1[cur1--];
            else nums1[cur--] = nums2[cur2--];
        }
        while (cur2 >= 0) nums1[cur--] = nums2[cur2--];
    }
};

pair

pair是C++标准库中的一个模板类，用于将两个值组合成一个单一的对象，通常用于存储键值对或返回多个值，有两个公有成员first和second，分别表示第一个值和第二个值

struct pair
{
	type first;
	type second;
};

使用的时候可以指定first和second的类型
指定的方式为pair<第一个关键字的类型，第二个关键字的类型>

pair<int, int> p1;
pair<long long, int> p2;
pair<string, int> p3;

不过，一般使用pair的时候，一般会typedef一下

typedef pair<int, int> PII;
PII p1;

typedef pair<long long, long long> PLL;
PLL p2;

UVA101 The Blocks Problem - 洛谷

move：a上方归位
pile：a及a上放在b上
onto：b上方归位，a及a上放在b上
over：a及a上放在b上
总结为2种操作：归位；移动

#include <bits/stdc++.h>
using namespace std;

const int N = 30;
typedef pair<int, int> PII;
int n;
vector<int> p[N];

PII find(int x)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < p[i].size(); j++)
        {
            if (p[i][j] == x)
            {
                return {i, j};
            }
        }
    }
}

void clean(int x, int y)
{
    for (int j = y + 1; j < p[x].size(); j++)
    {
        int t = p[x][j];
        p[t].push_back(t);
    }
    p[x].resize(y + 1);
}

void move(int x1, int y1, int x2)
{
    for (int j = y1; j < p[x1].size(); j++)
    {
        p[x2].push_back(p[x1][j]);        
    }
    p[x1].resize(y1);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    //初始化
    for (int i = 0; i < n; i++)
    {
        p[i].push_back(i);        
    }

    string op1, op2;
    int a, b;
    while (cin >> op1 >> a >> op2 >> b)
    {
        //查找a和b的位置
        PII pa = find(a);
        int x1 = pa.first, y1 = pa.second;
        PII pb = find(b);
        int x2 = pb.first, y2 = pb.second;

        if (x1 == x2) continue;
        
        if (op1 == "move")
        {
            clean(x1, y1);
        }
        if (op2 == "onto")
        {
            clean(x2, y2);
        }
        move(x1, y1, x2);
    }

    for (int i = 0; i < n; i++)
    {
        cout << i << ":";
        for (int j = 0; j < p[i].size(); j++)
        {
            cout << " " << p[i][j];        
        }
        cout << endl;
    }
    
    return 0;
}