做网站的价格 外贸,网站后端开发,wordpress 头条采集,自动点击器文章目录 前言等价多米诺骨牌对的数量拼写单词“气球” 的最大数量独一无二的出现次数找出井字棋的获胜者种花问题用最少数量的箭引爆气球划分字母区间最小数字游戏 前言 #x1f4ab;你好#xff0c;我是辰chen#xff0c;本文旨在准备考研复试或就业 #x1f4ab;文章题目… 文章目录 前言等价多米诺骨牌对的数量拼写单词“气球” 的最大数量独一无二的出现次数找出井字棋的获胜者种花问题用最少数量的箭引爆气球划分字母区间最小数字游戏 前言 你好我是辰chen本文旨在准备考研复试或就业 文章题目大多来自于 leetcode当然也可能来自洛谷或其他刷题平台 欢迎大家的关注我的博客主要关注于考研408以及AIoT的内容 仅给出C版代码 以下的几个专栏是本人比较满意的专栏(大部分专栏仍在持续更新)欢迎大家的关注 ACM-ICPC算法汇总【基础篇】 ACM-ICPC算法汇总【提高篇】 AIoT(人工智能物联网) 考研 CSP认证考试历年题解 等价多米诺骨牌对的数量 题目链接等价多米诺骨牌对的数量
C版AC代码
class Solution {
public:int numEquivDominoPairs(vectorvectorint dominoes) {unordered_mapint, int m;for (int i 0; i dominoes.size(); i ) {int d dominoes[i][0], u dominoes[i][1]; if (d u) swap(d, u); // 不管是0°还是180°都统一映射成一个数m[d * 10 u] ;}int res 0;for (auto i m.begin(); i ! m.end(); i ) {int n i - second;res (n - 1) * n / 2; // 组合数学问题}return res;}
};C版AC代码
关于组合数学那里其实可以再多一部思考 C n 2 n ∗ ( n − 1 ) / 2 C_n^2 n*(n-1)/2 Cn2n∗(n−1)/2 n ∗ ( n − 1 ) / 2 1 2 . . . n − 1 n*(n-1)/2 12...n-1 n∗(n−1)/212...n−1因此可以边统计边计算
class Solution {
public:int numEquivDominoPairs(vectorvectorint dominoes) {unordered_mapint, int m;int res 0;for (int i 0; i dominoes.size(); i ) {int d dominoes[i][0], u dominoes[i][1];if (d u) swap(d, u);int k d * 10 u;res m[k], m[k] ; // 边统计边计算}return res;}
};拼写单词 题目链接拼写单词
C版AC代码
class Solution {
public:int countCharacters(vectorstring words, string chars) {unordered_mapchar, int m;for (int i 0; i chars.size(); i ) m[chars[i]] ;int res 0;for (int i 0; i words.size(); i ) {string word words[i];unordered_mapchar, int tmp;for (int j 0; j word.size(); j ) tmp[word[j]] ;bool flag true;for (auto j tmp.begin(); j ! tmp.end(); j ) {char c j - first;if (tmp[c] m[c]) {flag false;break;}}if (flag) res word.size();}return res;}
};“气球” 的最大数量 题目链接“气球” 的最大数量
C版AC代码
主要学习一下多个值取 min 的语法
return min({x1, x2, x3, x4, x5});class Solution {
public:int maxNumberOfBalloons(string text) {unordered_mapchar, int m;for (int i 0; i text.size(); i ) m[text[i]] ;return min({m[b], m[a], m[l] / 2, m[o] / 2, m[n]});}
};独一无二的出现次数 题目链接独一无二的出现次数
C版AC代码
class Solution {
public:bool uniqueOccurrences(vectorint arr) {unordered_mapint, int m1; // 第一个映射,统计每个数出现的次数for (int i 0; i arr.size(); i ) m1[arr[i]] ;unordered_mapint, int m2; // 第二个映射,统计出现的次数的次数for (auto i m1.begin(); i ! m1.end(); i ) {int cnt i - second;m2[cnt] ;}bool flag true;for (auto i m2.begin(); i ! m2.end(); i ) if (i - second ! 1) {flag false;break;}return flag;}
};找出井字棋的获胜者 题目链接找出井字棋的获胜者
C版AC代码
class Solution {
public:int a[3][3];string tictactoe(vectorvectorint moves) {int win 0;for (int i 0; i moves.size(); i ) {int x moves[i][0], y moves[i][1];if ((i 1) % 2) a[x][y] 1;else a[x][y] 2;}for (int i 0; i 3; i ) { // 横着或者竖着连成一直线if (a[i][0] a[i][1] a[i][1] a[i][2]) {win a[i][0];break;}else if (a[0][i] a[1][i] a[1][i] a[2][i]) {win a[0][i];break;}}if (a[0][0] a[1][1] a[1][1] a[2][2]) win a[0][0]; // 主对角线if (a[0][2] a[1][1] a[1][1] a[2][0]) win a[0][2]; // 副对角线if (win 1) return A;else if (win 2) return B;else if (win 0 moves.size() 9) return Draw;else return Pending;}
};种花问题 题目链接种花问题
C版AC代码
class Solution {
public:bool canPlaceFlowers(vectorint flowerbed, int n) {int cnt 0, m flowerbed.size();if (m 1 !flowerbed[0]) return true; // 特判只有一朵花if (m 2 !flowerbed[0] !flowerbed[1]) { // 特判第一个结点flowerbed[0] 1;cnt ;}for (int i 1; i m - 1; i ) if (!flowerbed[i] !flowerbed[i - 1] !flowerbed[i 1]) { // 统计中间结点flowerbed[i] 1;cnt ;}if (m 2 !flowerbed[m - 2] !flowerbed[m - 1]) { // 特判最后一个结点flowerbed[m - 1] 1;cnt ;}return cnt n;}
};C版AC代码
改进上述代码其实由于边界条件分成了三部分进行了处理我们可以在 vector 的头和尾各添加一个 0这样就可以规避边界处理
class Solution {
public:bool canPlaceFlowers(vectorint flowerbed, int n) {int cnt 0, m flowerbed.size();flowerbed.insert(flowerbed.begin(), 0);flowerbed.push_back(0);// 注意此时 flowered.size() m 2 ,flowerbed[m]才是未拓展前的最后一个元素for (int i 1; i m; i ) if (!flowerbed[i] !flowerbed[i - 1] !flowerbed[i 1]) { // 统计中间结点flowerbed[i] 1;cnt ;}return cnt n;}
};用最少数量的箭引爆气球 题目链接用最少数量的箭引爆气球
C版AC代码
class Solution {
public:int min(int a, int b) {return a b ? b : a;}/* 贪心:维护右端点,如果新加入的元素的左端点当前维护的右端点,res ;同时更新右端点为新加入元素的右端点如果新加入的元素的左端点≤当前维护的右端点,证明可以使用同一根箭引爆新气球则更新一下右端点的值为当前区间的右端点与新加入元素右端点的最小值*/int findMinArrowShots(vectorvectorint points) {sort(points.begin(), points.end()); // 按照左端点进行排序int res 0;long long ed -1e10; for (int i 0; i points.size(); i ) {int l points[i][0], r points[i][1];if (l ed) {res ;ed r;}else ed min(ed, r);}return res;}
};划分字母区间 题目链接划分字母区间
C版AC代码
class Solution {
public:vectorint partitionLabels(string s) {unordered_mapchar, int last;for (int i 0; i s.size(); i ) last[s[i]] i; // 记录字母最后一次出现的位置vectorint res;for (int i 0; i s.size(); i ) {int r i; // 记录划分区间的最右边for (int j i; j s.size(); j ) {r max(r, last[s[j]]); // 如果当前遍历的字母不是最后一个该字母,更新r为最大值if (j r) { // j 遍历到了划分点,即代表该段的字母不会出现在之后的段res.push_back(r - i 1);i j;break;}}}return res;}
};最小数字游戏 题目链接最小数字游戏
C版AC代码
class Solution {
public:vectorint numberGame(vectorint nums) {sort(nums.begin(), nums.end());vectorint res;for (int i 0; i nums.size(); i 2 ) {int alice nums[i], bob nums[i 1];res.push_back(bob), res.push_back(alice);}if (res.size() nums.size()) res.push_back(nums[nums.size() - 1]);return res;}
};
