服务公司网站建设,公司起名查询,wordpress 自定义栏目 是什么,网站制作行业越来越难做文章目录 前言验证外星语词典在长度 2N 的数组中找出重复 N 次的元素找到小镇的法官查找共用字符数组的相对排序分发饼干分发糖果区间选点(AcWing)最大不相交区间数量(AcWing)无重叠区间关于重写小于号 前言 #x1f4ab;你好#xff0c;我是辰chen#xff0c;本文旨在准备考… 文章目录 前言验证外星语词典在长度 2N 的数组中找出重复 N 次的元素找到小镇的法官查找共用字符数组的相对排序分发饼干分发糖果区间选点(AcWing)最大不相交区间数量(AcWing)无重叠区间关于重写小于号 前言 你好我是辰chen本文旨在准备考研复试或就业 文章题目大多来自于 leetcode当然也可能来自洛谷或其他刷题平台 欢迎大家的关注我的博客主要关注于考研408以及AIoT的内容 仅给出C版代码 以下的几个专栏是本人比较满意的专栏(大部分专栏仍在持续更新)欢迎大家的关注 ACM-ICPC算法汇总【基础篇】 ACM-ICPC算法汇总【提高篇】 AIoT(人工智能物联网) 考研 CSP认证考试历年题解 验证外星语词典 题目链接验证外星语词典
C版AC代码
class Solution {
public:bool isAlienSorted(vectorstring words, string order) {unordered_mapchar, char m;// 注意这里相当于重新映射成 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();vectorstring 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]]; // 将原字符串映射为按照外星语字典序映射的字符串,即可排序tmp.push_back(numstr), exch.push_back(numstr); // 分别存到tmp(要排序),exch(对比串)中}sort(tmp.begin(), tmp.end()); // 对tmp进行排序bool flag true;for (int i 0; i n; i ) if (tmp[i] ! exch[i]) { // 有变化即不是按照新字典序有序排列flag false;break;}return flag;}
};在长度 2N 的数组中找出重复 N 次的元素 题目链接在长度 2N 的数组中找出重复 N 次的元素
C版AC代码
class Solution {
public:int repeatedNTimes(vectorint nums) {unordered_mapint, int m;int res;for (int i 0; i nums.size(); i ) {m[nums[i]] ;if (m[nums[i]] 2) { // 因为有n1个不同的值,所以当一个元素出现2次的时候就是目标值res nums[i];break;}}return res;}
};找到小镇的法官 题目链接找到小镇的法官
C版AC代码
class Solution {
public:int findJudge(int n, vectorvectorint trust) {if (trust.empty() n 1) return 1;int judge -1;unordered_mapint, int m1;unordered_mapint, 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的人数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:vectorstring commonChars(vectorstring words) {unordered_mapchar, int m; // 用来记录共用字符,一开始把words[0]存进去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_mapchar, int tmp; // 存储当前字符串的信息,用来和m做对比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中没有这个字符,即不是共用字符,删掉else m[s] min(cnt, tmp[s]); // 如果是共用字符则取出现次数为两个串中的最小值}}vectorstring 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;}
};数组的相对排序 题目链接数组的相对排序
C版AC代码
class Solution {
public:vectorint relativeSortArray(vectorint arr1, vectorint arr2) {unordered_mapint, int m;for (int i 0; i arr1.size(); i ) m[arr1[i]] ; vectorint 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中的顺序把arr1中的元素存入resit - second 0; // 标记成已经存储好}for (auto i m.begin(); i ! m.end(); i ) { // 把arr2中没有的元素暂存到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;}
};分发饼干 题目链接分发饼干
C版AC代码
class Solution {
public:int findContentChildren(vectorint g, vectorint 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;}
};分发糖果 题目链接分发糖果
C版AC代码
class Solution {
public:int candy(vectorint ratings) {int n ratings.size();vectorint v(n, 1); // 开一个长度为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]) // 左边比右边大且左边的糖果数≤右边的糖果数就更新1v[i - 1] max(v[i - 1], v[i] 1);return accumulate(v.begin(), v.end(), 0);}
};区间选点(AcWing) 题目链接区间选点(AcWing)
C版AC代码
#include cstdio
#include iostream
#include algorithmusing 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 ed -1e9 - 1, res 0;for (int i 0; i n; i ) {if (st[i].l ed) { // 新区间的左端点大于当前区间的右端点证明这是一个新的区间res ; // 区间数 1ed st[i].r; // 更新为新的右端点}}cout res;return 0;
}最大不相交区间数量(AcWing) 题目链接最大不相交区间数量(AcWing)
C版AC代码
同上
#include iostream
#include algorithm
#include cstdiousing 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;
}无重叠区间 题目链接无重叠区间
C版AC代码
class Solution {
public:// 问题等价于求最多的无重叠区间// 贪心思路:按照右端点进行排序,想要最多的无重叠区域,就是在不重叠的时候选择最小的右端点static bool cmp(const vectorint a, const vectorint b) {return a[1] b[1];}int eraseOverlapIntervals(vectorvectorint 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) { // 根据例子所述,区间是不包含两个端点的,所以相等的时候也需要更新res ;r ed;}}return intervals.size() - res;}
};关于重写小于号
定义结构体的写法
struct St {int l, r;bool operator (const St w) const {return r w.r;}
}st[N];// 调用无需传入第三个参数:
sort(st, st n);关于外部定义的写法
static bool cmp(const vectorint a, const vectorint b) {return a[1] b[1];
}// 调用需要传入第三个参数:
sort(intervals.begin (), intervals.end(), cmp);
