前言

💫你好，我是辰chen，本文旨在準(zhǔn)備考研復(fù)試或就業(yè)
💫文章題目大多來(lái)自于 leetcode，當(dāng)然也可能來(lái)自洛谷或其他刷題平臺(tái)
💫歡迎大家的關(guān)注，我的博客主要關(guān)注于考研408以及AIoT的內(nèi)容
🌟 僅給出C++版代碼

以下的幾個(gè)專欄是本人比較滿意的專欄(大部分專欄仍在持續(xù)更新)，歡迎大家的關(guān)注：

💥ACM-ICPC算法匯總【基礎(chǔ)篇】
💥ACM-ICPC算法匯總【提高篇】
💥AIoT(人工智能+物聯(lián)網(wǎng))
💥考研
💥CSP認(rèn)證考試歷年題解

驗(yàn)證外星語(yǔ)詞典

題目鏈接：驗(yàn)證外星語(yǔ)詞典

C++版AC代碼：

class Solution {
public:bool isAlienSorted(vector<string>& words, string order) {unordered_map<char, char> m;// 注意這里相當(dāng)于重新映射成 a b c d e f g ...for (int i = 0; i < order.size(); i ++ ) m[order[i]] = (char)(i + 'a'); int n = words.size();vector<string> tmp, exch;for (int i = 0; i < n; i ++ ) {string word = words[i], numstr;for (int j = 0; j < word.size(); j ++ ) numstr += m[word[j]];    // 將原字符串映射為按照外星語(yǔ)字典序映射的字符串,即可排序tmp.push_back(numstr), exch.push_back(numstr);  // 分別存到tmp(要排序),exch(對(duì)比串)中}sort(tmp.begin(), tmp.end());    // 對(duì)tmp進(jìn)行排序bool flag = true;for (int i = 0; i < n; i ++ ) if (tmp[i] != exch[i]) {     // 有變化即不是按照新字典序有序排列flag = false;break;}return flag;}
};

---

在長(zhǎng)度 2N 的數(shù)組中找出重復(fù) N 次的元素

題目鏈接：在長(zhǎng)度 2N 的數(shù)組中找出重復(fù) N 次的元素

C++版AC代碼：

class Solution {
public:int repeatedNTimes(vector<int>& nums) {unordered_map<int, int> m;int res;for (int i = 0; i < nums.size(); i ++ ) {m[nums[i]] ++;if (m[nums[i]] >= 2) { // 因?yàn)橛衝+1個(gè)不同的值,所以當(dāng)一個(gè)元素出現(xiàn)2次的時(shí)候就是目標(biāo)值res = nums[i];break;}}return res;}
};

---

找到小鎮(zhèn)的法官

題目鏈接：找到小鎮(zhèn)的法官

C++版AC代碼：

class Solution {
public:int findJudge(int n, vector<vector<int>>& trust) {if (trust.empty() && n == 1) return 1;int judge = -1;unordered_map<int, int> m1;unordered_map<int, bool> m2;for (int i = 0; i < trust.size(); i ++ ) {int fs = trust[i][0], sd = trust[i][1];m1[sd] ++, m2[fs] = false;      // 信任sd的人數(shù)+1, fs不可能是法官}for (auto i = m1.begin(); i != m1.end(); i ++ ) {int guy = i -> first, num = i -> second;if ((num == n - 1) && !m2.count(guy)) {judge = guy;break;}}return judge;}
};

---

查找共用字符

題目鏈接：查找共用字符

C++版AC代碼：

class Solution {
public:vector<string> commonChars(vector<string>& words) {unordered_map<char, int> m;     // 用來(lái)記錄共用字符,一開始把words[0]存進(jìn)去for (int i = 0; i < words[0].size(); i ++ ) m[words[0][i]] ++;for (int i = 0; i < words.size(); i ++ ) {string word = words[i];unordered_map<char, int> tmp;         // 存儲(chǔ)當(dāng)前字符串的信息,用來(lái)和m做對(duì)比for (int j = 0; j < word.size(); j ++ ) tmp[word[j]] ++;for (auto j = m.begin(); j != m.end(); j ++ ) {char s = j -> first;int cnt = j -> second;if (!tmp.count(s)) m[s] = 0;     // tmp中沒有這個(gè)字符,即不是共用字符,刪掉else m[s] = min(cnt, tmp[s]);    // 如果是共用字符則取出現(xiàn)次數(shù)為兩個(gè)串中的最小值}}vector<string> res;for (auto i = m.begin(); i != m.end(); i ++ ) {int cnt = i -> second;while (cnt -- ) res.push_back(string(1, i -> first));// string(1, c) : 把字符c變成字符串格式}return res;}
};

---

數(shù)組的相對(duì)排序

題目鏈接：數(shù)組的相對(duì)排序

C++版AC代碼：

class Solution {
public:vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {unordered_map<int, int> m;for (int i = 0; i < arr1.size(); i ++ ) m[arr1[i]] ++; vector<int> res, tmp; for (int i = 0; i < arr2.size(); i ++ ) {auto it = m.find(arr2[i]);int k = it -> second;while (k -- ) res.push_back(arr2[i]);   // 按照arr2中的順序把a(bǔ)rr1中的元素存入resit -> second = 0;                       // 標(biāo)記成已經(jīng)存儲(chǔ)好}for (auto i = m.begin(); i != m.end(); i ++ ) {  // 把a(bǔ)rr2中沒有的元素暫存到tmp中int k = i -> second;while (k -- ) tmp.push_back(i -> first);}sort(tmp.begin(), tmp.end());       // arr2中沒有的元素排序for (int i = 0; i < tmp.size(); i ++ ) res.push_back(tmp[i]);return res;}
};

---

分發(fā)餅干

題目鏈接：分發(fā)餅干

C++版AC代碼：

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end()), sort(s.begin(), s.end());int res = 0;for (int i = 0, j = 0; i < g.size() && j < s.size(); j ++ ) if (g[i] <= s[j]) i ++, res ++;return res;}
};

---

分發(fā)糖果

題目鏈接：分發(fā)糖果

C++版AC代碼：

class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();vector<int> v(n, 1);         // 開一個(gè)長(zhǎng)度為n的vector并附初值為1for (int i = 1; i < n; i ++ )     // 從頭往后遍歷if (ratings[i] > ratings[i - 1]) // 右邊比左邊大就讓右邊+1v[i] = v[i - 1] + 1;for (int i = n - 1; i > 0; i -- ) if (ratings[i] < ratings[i - 1])  // 左邊比右邊大且左邊的糖果數(shù)≤右邊的糖果數(shù)就更新+1v[i - 1] = max(v[i - 1], v[i] + 1);return accumulate(v.begin(), v.end(), 0);}
};

---

區(qū)間選點(diǎn)(AcWing)

題目鏈接：區(qū)間選點(diǎn)(AcWing)

C++版AC代碼：

#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;struct St{int l, r;bool operator < (const St w) const {      // 按照右端點(diǎn)進(jìn)行排序return r < w.r;}
}st[N];int main()
{int n;cin >> n;for (int i = 0; i < n; i ++ ) {int l, r;cin >> l >> r;st[i] = {l, r};}sort(st, st + n);int ed = -1e9 - 1, res = 0;for (int i = 0; i < n; i ++ ) {if (st[i].l > ed) {      // 新區(qū)間的左端點(diǎn)大于當(dāng)前區(qū)間的右端點(diǎn)，證明這是一個(gè)新的區(qū)間res ++;              // 區(qū)間數(shù) + 1ed = st[i].r;        // 更新為新的右端點(diǎn)}}cout << res;return 0;
}

---

最大不相交區(qū)間數(shù)量(AcWing)

題目鏈接：最大不相交區(qū)間數(shù)量(AcWing)

C++版AC代碼：

同上

#include <iostream>
#include <algorithm>
#include <cstdio>using namespace std;const int N = 100010;struct St {int l, r;bool operator < (const St w) const {return r < w.r;}
}st[N];int main()
{int n;cin >> n;for (int i = 0; i < n; i ++ ) {int l, r;cin >> l >> r;st[i] = {l, r};}sort(st, st + n);int res = 0, ed = -1e9 - 1;for (int i = 0; i < n; i ++ ) if (st[i].l > ed) {res ++;ed = st[i].r;}cout << res;return 0;
}

---

無(wú)重疊區(qū)間

題目鏈接：無(wú)重疊區(qū)間

C++版AC代碼：

class Solution {
public:// 問(wèn)題等價(jià)于求最多的無(wú)重疊區(qū)間// 貪心思路:按照右端點(diǎn)進(jìn)行排序,想要最多的無(wú)重疊區(qū)域,就是在不重疊的時(shí)候選擇最小的右端點(diǎn)static bool cmp(const vector<int> &a, const vector<int> &b) {return a[1] < b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);int res = 0, r = -5 * 1e4 - 1;for (int i = 0; i < intervals.size(); i ++ ) {int st = intervals[i][0], ed = intervals[i][1];if (st >= r) {    // 根據(jù)例子所述,區(qū)間是不包含兩個(gè)端點(diǎn)的,所以相等的時(shí)候也需要更新res ++;r = ed;}}return intervals.size() - res;}
};

---

關(guān)于重寫小于號(hào)

定義結(jié)構(gòu)體的寫法：

struct St {int l, r;bool operator < (const St w) const {return r < w.r;}
}st[N];// 調(diào)用無(wú)需傳入第三個(gè)參數(shù):
sort(st, st + n);

關(guān)于外部定義的寫法：

static bool cmp(const vector<int> &a, const vector<int> &b) {return a[1] < b[1];
}// 調(diào)用需要傳入第三個(gè)參數(shù):
sort(intervals.begin    (), intervals.end(), cmp);