建设部的网站,朝阳凌源网站建设,中国品牌网官网查询,顺德大良做网站文章目录1. 比赛结果2. 题目1. LeetCode 5511. 二进制矩阵中的特殊位置 easy2. LeetCode 5512. 统计不开心的朋友 medium3. LeetCode 5513. 连接所有点的最小费用 medium4. LeetCode 5514. 检查字符串是否可以通过排序子字符串得到另一个字符串 hard1. 比赛结果
做出来3题。继…
文章目录1. 比赛结果2. 题目1. LeetCode 5511. 二进制矩阵中的特殊位置 easy2. LeetCode 5512. 统计不开心的朋友 medium3. LeetCode 5513. 连接所有点的最小费用 medium4. LeetCode 5514. 检查字符串是否可以通过排序子字符串得到另一个字符串 hard1. 比赛结果
做出来3题。继续加油
全国排名 733 / 449116.3%全球排名 2140 / 1329116.1%
2. 题目
1. LeetCode 5511. 二进制矩阵中的特殊位置 easy
题目链接
给你一个大小为 rows x cols 的矩阵 mat其中 mat[i][j] 是 0 或 1请返回 矩阵 mat 中特殊位置的数目 。
特殊位置 定义如果 mat[i][j] 1 并且第 i 行和第 j 列中的所有其他元素均为 0行和列的下标均 从 0 开始 则位置 (i, j) 被称为特殊位置。
示例 1
输入mat [[1,0,0],[0,0,1],[1,0,0]]
输出1
解释(1,2) 是一个特殊位置
因为 mat[1][2] 1 且所处的行和列上所有其他元素都是 0示例 2
输入mat [[1,0,0],[0,1,0],[0,0,1]]
输出3
解释(0,0), (1,1) 和 (2,2) 都是特殊位置示例 3
输入mat [[0,0,0,1],[1,0,0,0],[0,1,1,0],[0,0,0,0]]
输出2示例 4
输入mat [[0,0,0,0,0],[1,0,0,0,0],[0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]
输出3提示
rows mat.length
cols mat[i].length
1 rows, cols 100
mat[i][j] 是 0 或 1解题
先计算出每行每列 1的个数再次遍历矩阵数字为1且行列1的个数均为1
class Solution {
public:int numSpecial(vectorvectorint mat) {int m mat.size(), n mat[0].size();int c 0, i, j;vectorint ct1(m, 0), ct2(n,0);for(i 0; i m; i){c 0;for(j 0 ; j n; j){if(mat[i][j]1)c;}ct1[i] c;}for(j 0; j n; j){c 0;for(i 0 ; i m; i){if(mat[i][j]1)c;}ct2[j] c;}c 0;for(int i 0; i m; i){if(ct1[i] ! 1)continue;for(int j 0 ; j n; j){if(mat[i][j] ct2[j]1)c;}}return c;}
};48 ms 13.1 MB
2. LeetCode 5512. 统计不开心的朋友 medium
题目链接
给你一份 n 位朋友的亲近程度列表其中 n 总是 偶数 。
对每位朋友 ipreferences[i] 包含一份 按亲近程度从高到低排列 的朋友列表。 换句话说排在列表前面的朋友与 i 的亲近程度比排在列表后面的朋友更高。 每个列表中的朋友均以 0 到 n-1 之间的整数表示。
所有的朋友被分成几对配对情况以列表 pairs 给出其中 pairs[i] [xi, yi] 表示 xi 与 yi 配对且 yi 与 xi 配对。
但是这样的配对情况可能会是其中部分朋友感到不开心。 在 x 与 y 配对 且 u 与 v 配对的情况下如果同时满足下述两个条件x 就会不开心
x 与 u 的亲近程度胜过 x 与 y且u 与 x 的亲近程度胜过 u 与 v
返回 不开心的朋友的数目 。
示例 1
输入n 4,
preferences [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]],
pairs [[0, 1], [2, 3]]
输出2
解释
朋友 1 不开心因为
- 1 与 0 配对但 1 与 3 的亲近程度比 1 与 0 高且
- 3 与 1 的亲近程度比 3 与 2 高。
朋友 3 不开心因为
- 3 与 2 配对但 3 与 1 的亲近程度比 3 与 2 高且
- 1 与 3 的亲近程度比 1 与 0 高。
朋友 0 和 2 都是开心的。示例 2
输入n 2, preferences [[1], [0]], pairs [[1, 0]]
输出0
解释朋友 0 和 1 都开心。示例 3
输入n 4,
preferences [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]],
pairs [[1, 3], [0, 2]]
输出4提示
2 n 500
n 是偶数
preferences.length n
preferences[i].length n - 1
0 preferences[i][j] n - 1
preferences[i] 不包含 i
preferences[i] 中的所有值都是独一无二的
pairs.length n/2
pairs[i].length 2
xi ! yi
0 xi, yi n - 1
每位朋友都 恰好 被包含在一对中解题
先预处理出每个人的列表里的关系值大小 rela然后按题意模拟
class Solution {
public:int unhappyFriends(int n, vectorvectorint preferences, vectorvectorint pairs) {vectorvectorint g(n);for(auto p : pairs)// pair 转化为无向图{g[p[0]].push_back(p[1]);g[p[1]].push_back(p[0]);}vectorvectorint rela(n,vectorint(n, 0));//关系数值for(int i 0, val; i n; i){val n;for(int id : preferences[i])rela[i][id] val--;//关系值递减}int x,y,u,v,i;vectorint unhappy(n, 0);for(x 0, y; x n; x)//遍历每个人{y g[x][0], u, v;for(i 0; i n-1; i){if(preferences[x][i] y)break;u preferences[x][i];//y前面的人条件1v g[u][0];// u , v 配对的人if(rela[u][x] rela[u][v])//条件2unhappy[x] 1;}}return accumulate(unhappy.begin(), unhappy.end(),0);}
};144 ms 26.2 MB
3. LeetCode 5513. 连接所有点的最小费用 medium
题目链接
给你一个points 数组表示 2D 平面上的一些点其中 points[i] [xi, yi] 。
连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 |xi - xj| |yi - yj| 其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。 只有任意两点之间 有且仅有 一条简单路径时才认为所有点都已连接。
示例 1 输入points [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出20
解释
我们可以按照上图所示连接所有点得到最小总费用总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。示例 2
输入points [[3,12],[-2,5],[-4,1]]
输出18示例 3
输入points [[0,0],[1,1],[1,0],[-1,1]]
输出4示例 4
输入points [[-1000000,-1000000],[1000000,1000000]]
输出4000000示例 5
输入points [[0,0]]
输出0提示
1 points.length 1000
-106 xi, yi 106
所有点 (xi, yi) 两两不同。解题
类似题目LeetCode 1135. 最低成本联通所有城市最小生成树排序并查集
prim算法vis标记点把该点相连的边全部加入优先队列取出最小的边边的另一端点的所有边加入队列
struct cmp
{bool operator()(const pairint,int a, const pairint,int b) const{return a.second b.second;//小顶堆, 距离小的优先}
};
class Solution {
public:int minCostConnectPoints(vectorvectorint points) {int n points.size();if(n 1) return 0;vectorbool vis(n, false);vectorvectorpairint,int edges(n,vectorpairint,int());for(int i 0, j, d; i n; i){for(j i1; j n; j){d abs(points[i][0]-points[j][0])abs(points[i][1]-points[j][1]);edges[i].push_back({j,d});edges[j].push_back({i,d});}}priority_queuepairint,int, vectorpairint,int, cmp q;int to, distance, total 0, edge_num 0;vis[0] true;for(auto e : edges[0])q.push(e); while(!q.empty()){to q.top().first;distance q.top().second;q.pop();if(!vis[to]){vis[to] true;total distance;edge_num;if(edge_num n-1)return total;for(auto e : edges[to])q.push(e); }}return -1;}
};1288 ms 162.2 MB
kruskal 算法对所有的边排序短的优先用并查集检查边的两个端点是否属于一个集合不属于的话加入边合并两个端点
class dsu{
public:vectorint f;dsu(int n){f.resize(n);for (int i 0; i n; i)f[i] i;}void merge(int a, int b){int fa find(a), fb find(b);f[fa] fb;}int find(int a){if(a f[a])return a;return f[a] find(f[a]);}
};
struct edge{int d;int p1, p2;edge(int dis, int a, int b){d dis, p1 a, p2 b;}
};
class Solution {
public:int minCostConnectPoints(vectorvectorint points) {int n points.size();if(n 1) return 0;dsu u(n);vectoredge e(n*(n-1)/2, edge(0,0,0));for(int i 0, k 0, j, d; i n; i){for(j i1; j n; j){d abs(points[i][0]-points[j][0])abs(points[i][1]-points[j][1]);e[k] edge(d,i,j);}}sort(e.begin(), e.end(),[](auto a, auto b){return a.d b.d;});int N n-1, p1, p2, d, ans 0, f1, f2;for(int i 0; i e.size(); i){p1 e[i].p1, p2 e[i].p2;d e[i].d;f1 u.find(p1), f2 u.find(p2);if(f1 f2)continue;ans d;u.f[f1] f2;if(--N 0)break;}return ans;}
};1184 ms 31.6 MB
4. LeetCode 5514. 检查字符串是否可以通过排序子字符串得到另一个字符串 hard
题目链接
给你两个字符串 s 和 t 请你通过若干次以下操作将字符串 s 转化成字符串 t
选择 s 中一个 非空 子字符串并将它包含的字符就地 升序 排序。
比方说对下划线所示的子字符串进行操作可以由 “1423 4” 得到 “12344” 。
如果可以将字符串 s 变成 t 返回 true 。否则返回 false 。
一个 子字符串 定义为一个字符串中连续的若干字符。
示例 1
输入s 84532, t 34852
输出true
解释你可以按以下操作将 s 转变为 t
84532 从下标 2 到下标 3- 84352
84352 从下标 0 到下标 2 - 34852示例 2
输入s 34521, t 23415
输出true
解释你可以按以下操作将 s 转变为 t
34521 - 23451
23451 - 23415示例 3
输入s 12345, t 12435
输出false示例 4
输入s 1, t 2
输出false提示
s.length t.length
1 s.length 105
s 和 t 都只包含数字字符即 0 到 9 。解题
参考zerotrac2 大佬的题解
class Solution {
public:bool isTransformable(string s, string t) {int n s.size();vectorqueueint pos(10);for(int i 0; i n; i) pos[s[i]-0].push(i);for(int i 0; i n; i){if(pos[t[i]-0].empty())return false;//字符内容对不上for(int d 0; d t[i]-0; d){if(!pos[d].empty() pos[d].front() pos[t[i]-0].front())//前面有数字比我小的升序不可能做到return false;}pos[t[i]-0].pop();}return true;}
};168 ms 16.9 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
