vector的使用 点击传送

文章目录

• 1.寄包柜（vector数组）
• 2. 移动零（数组分块思想）
• 3. 颜色分类(数组分三块)
• 4. 合并两个有序数组(辅助数组)
• 5. The Blocks Problem（模拟）

1.寄包柜（vector数组）

https://www.luogu.com.cn/problem/P3613

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

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

int n,q;
const int N = 1e5+10;
vector<int> a[N];//重点部分

int main()
{
    cin>>n>>q;
    while(q--)
    {
        int i,j,k,op;
        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;
}

2. 移动零（数组分块思想）

https://leetcode.cn/problems/move-zeroes/description/

这道题目是非常经典的 数组分块思想 而我们这道题就是通过某些条件 将数组分成非0和0两块。在本题中，我们可以⽤⼀个 i 指针来扫描整个数组，另⼀个 cur 指针⽤来记录⾮零数序列的最后⼀个位置。根据 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。

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

3. 颜色分类(数组分三块)

https://leetcode.cn/problems/sort-colors/description/

类⽐数组分两块的算法思想，这⾥是将数组分成三块，那么我们可以再添加⼀个指针，实现数组分三块。

class Solution {
public:
    void sortColors(vector<int>& nums) 
    {
        for(int left= -1,right = nums.size(),i=0;i<right;)//注意正确的终止条件是i<right
        {
            if(nums[i]==0)
            {
                swap(nums[left+1],nums[i]);
                left++;
                i++;
            }
            else if(nums[i]==2)
            {
                swap(nums[right-1],nums[i]);
                right--;
            }
            else
             i++;
        }
    }
};

4. 合并两个有序数组(辅助数组)

https://leetcode.cn/problems/merge-sorted-array/description/

解法⼀：利⽤辅助数组（需要学会，归并排序的核⼼步骤）
可以创建⼀个辅助数组，然后⽤两个指针分别指向两个数组。每次拿出⼀个较⼩的元素放在辅助数组中，直到把所有元素全部放在辅助数组中。最后把辅助数组的结果覆盖到 nums1 中。

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

       while(cur2<n)
       nums[cur++]=nums2[cur2++];

       nums1=nums;

    }
};

解法⼆：原地修改（本题的最优解）
与解法⼀的核⼼思想是⼀样的。由于第⼀个数组的空间本来就是 n+m 个，所以我们可以直接把最终结果放在 nums1 中。为了不覆盖未遍历到的元素，定义两个指针指向两个数组的末尾，从后往前扫描。每次拿出较⼤的元素也是从后往前放在 nums1 的后⾯，直到把所有元素全部放在 nums1 中。

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

     while(cur2>=0 )
     nums1[cur--]=nums2[cur2--];
    }
};

5. The Blocks Problem（模拟）

https://www.luogu.com.cn/problem/UVA101#ide

本质就是利用合理的容器对问题进行模拟。
我们可以创建一个vector数组来帮助我们完成该操作。
通过一个pair 来帮助我们记录木块的具体位置。

#include<iostream>
#include <vector>
using namespace std;
const int N = 30;
vector<int> p[N];
int n;
typedef pair<int,int> PII;

   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};
         }
    }
  }
       return {1,1};
}

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

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

int main()
{
    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)
    {
        //对ab位置进行定位，利用pair分别代表横纵坐标。
        PII pa=find(a);
        PII pb=find(b);
        int x1=pa.first,y1=pa.second,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;
}