一、詢問學號

題?來源：洛?

題?鏈接：P3156 【深基15.例1】詢問學號 - 洛谷

難度系數：★

1. 題目描述

2. 算法原理

直接? vector 或者數組模擬即可。

3. 參考代碼

#include <iostream>
#include <vector>using namespace std;const int N = 2e6 + 10;int n, m;
vector<int> a(N);int main()
{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】寄包柜 - 洛谷

難度系數：★

1. 題目描述

2. 算法原理

解法1：創建二維數組（空間復雜度過高）

解法2：使用vector——vector<int> a[N]

注意：

• vector<int> a[N]?定義了一個包含?N?個?vector<int>?對象的數組。（類似二維數組）
• vector<int> a(N)?定義了一個?vector<int>?對象?a，并將其初始化為包含?N?個元素，這些元素的初始值默認為 0（對于?int?類型）。

3. 參考代碼

#include <iostream>
#include <vector>using namespace std;const int N = 1e5 + 10;int n, q;
vector<int> a[N]; // 創建 N 個柜子int main()
{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）

難度系數：★

1. 題目描述?

2. 算法原理

利用雙指針

類?數組分兩塊的算法思想，這?是將數組分成三塊，那么我們可以再添加?個指針，實現數組分三 塊。

設數組??為 n ，定義三個指針 left, cur,right :

• left ：?來標記 0 序列的末尾，因此初始化為 -1 ；
• cur?來掃描數組，初始化為 0 ；?
• right ：?來標記 2 序列的起始位置，因此初始化為 n? 。

在往后掃描的過程中，保證：

• [0, left] 內的元素都是 0 ；
• [left + 1,cur ? 1]內的元素都是 1 ;?
• [cur, right ? 1] 內的元素是待定元素;
• [right, n]?內的元素都是 2 。

3. 參考代碼

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

四、顏?分類

題?來源：?扣?

題?鏈接：75. 顏色分類 - 力扣（LeetCode）

難度系數：★

1. 題目描述

2. 算法原理

類?數組分兩塊的算法思想，這?是將數組分成三塊，那么我們可以再添加?個指針，實現數組分三 塊。

設數組??為 ，定義三個指針left, cur,right :

• left：?來標記 序列的末尾，因此初始化為 ；
• cur：?來掃描數組，初始化為 ；
• right：?來標記 序列的起始位置，因此初始化為 。

在 往后掃描的過程中，保證：

• [0, left]?內的元素都是 ；
• [left + 1,cur ? 1]?內的元素都是 ；
• [cur, right ? 1]?內的元素是待定元素；
• [right, n]?內的元素都是 。

??

?

3. 參考代碼

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

五、合并兩個有序數組

題?來源：?扣

題?鏈接：88. 合并兩個有序數組 - 力扣（LeetCode）

難度系數：★

1. 題目描述

2. 算法原理

解法?：利?輔助數組（需要學會，歸并排序的核?步驟）

可以創建?個輔助數組，然后?兩個指針分別指向兩個數組。每次拿出?個較?的元素放在輔助數組 中，直到把所有元素全部放在輔助數組中。最后把輔助數組的結果覆蓋到?nums1 中。

解法?：原地修改（本題的最優解）

與解法?的核?思想是?樣的。

由于第?個數組的空間本來就是 n+m 個，所以我們可以直接把最終結果放在 nums1 中。 nums1 中。為了不 覆蓋未遍歷到的元素，定義兩個指針指向兩個數組的末尾，從后往前掃描。每次拿出較?的元素也是 從后往前放在 nums1 的后?，直到把所有元素全部放在 nums1 中。

注意：從前往后遍歷會出現覆蓋的情況

3. 參考代碼

//解法一
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];}
};//解法二
class Solution 
{
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {// 解法二：原地合并int cur1 = m - 1, cur2 = n - 1, cur = m + n - 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--];}
};

六、The Blocks Problem

題?來源：洛?

題?鏈接：UVA101 The Blocks Problem - 洛谷

難度系數：★★

2. 算法原理

本質是?個模擬題，可以??vector?來模擬，注意細節問題。

3. 參考代碼

#include <iostream>
#include <vector>using namespace std;const int N = 30;
typedef pair<int, int> PII;int n;
vector<int> p[N]; // 創建 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)
{// 把 [x, 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)
{// 把 [x1, y1] 及其以上的木塊放在 x2 上面for(int j = y1; j < p[x1].size(); j++){p[x2].push_back(p[x1][j]);}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){// 查找 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") // 把 a 上方歸位{clean(x1, y1);}if(op2 == "onto") // 把 b 上方歸位{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;
}