当前位置:网站首页>【leetcode周赛总结】LeetCode第 81 场双周赛(6.25)
【leetcode周赛总结】LeetCode第 81 场双周赛(6.25)
2022-07-05 14:21:00 【Let it beSun】
题目1 2315. 统计星号
思路:
简单题目直接遍历,用一个变量标识是否在竖线对之内
代码:
class Solution {
public int countAsterisks(String s) {
int count = 0;
int d = 0;
for(char c:s.toCharArray()){
if(d==1){
if(c=='|'){
d = 0;
}
}else{
if(c=='|'){
d = 1;
}
if(c=='*'){
count++;
}
}
}
return count;
}
}
题目2 统计无向图中无法互相到达点对数
思路:
并查集,并查集的参考模板见【算法笔记】重点总结并查集_Let it beSun的博客-CSDN博客
主要求每个连通分量的大小
一开始TLE(超时)的思路:求出每个连通分量的大小之后直接用乘法计算
例如:
此时几个联通分量的大小分别为{4,2,1}此时计算 ans = 4*2+4*1+2*1 = 14
但是时间复杂度O(n^2)超时;
计算方法一
所以考虑对于每一个节点,计算节点i不联通的点对数,因为每一个节点分别计算存在重复,所以答案就是求和再除以2。
for(int i=0;i<n;i++){
ans += (long)(n-sz[find(i)]);
}
return ans/2;
计算方法二
可以考虑对于所有的点对数 n*(n-1)/2 ,减去各个联通分量内部的节点对数 a*(a-1)/2
代码:
对应计算方法一:
class Solution {
int[] f = new int[100005];
int[] sz = new int[100005];
public int find(int x){
if(f[x]==x) return x;
return f[x] = find(f[x]);
}
public void unite(int x,int y){
int fx = find(x);
int fy = find(y);
if(fx!=fy){
f[fx] = fy;
sz[fy] += sz[fx];
sz[fx] = 0;
}
}
public long countPairs(int n, int[][] edges) {
for(int i=0;i<n;i++){
f[i] = i;
sz[i] = 1;
}
long ans = 0;
for(int i=0;i<edges.length;i++){
int a = edges[i][0];
int b = edges[i][1];
unite(a,b);
}
for(int i=0;i<n;i++){
ans += (long)(n-sz[find(i)]);
}
return ans/2;
}
}
对应计算方法二:
class Solution {
int[] f = new int[100005];
int[] sz = new int[100005];
public int find(int x){
if(f[x]==-1) return x;
return f[x] = find(f[x]);
}
public void unite(int x,int y){
int fx = find(x);
int fy = find(y);
if(fx!=fy){
f[fx] = fy;
sz[fy] += sz[fx];
sz[fx] = 0;
}
}
public long countPairs(int n, int[][] edges) {
for(int i=0;i<n;i++){
f[i] = -1;
sz[i] = 1;
}
long ans = 0;
for(int i=0;i<edges.length;i++){
int a = edges[i][0];
int b = edges[i][1];
unite(a,b);
}
for(int i=0;i<n;i++){
if(f[i]==-1){
ans += (long)sz[i]*(sz[i]-1)/2;
}
}
return (long)n*(n-1)/2-ans;
}
}
题目3 2317. 操作后的最大异或和
思路
就是统计这个数组中每一位是否出现1,对于所有二进制位,只要这一位在数组中出现过 1
,那么答案里这一位也是 1
。
因此答案就是所有数按位或的结果。复杂度 O(n)。
代码
方法一:直接统计
class Solution {
public int maximumXOR(int[] nums) {
int[] bit = new int[32];
for(int i=0;i<32;i++){
for(int num:nums){
if( ((num>>i)&1) == 1){
bit[i]++;
break;
}
}
}
int res = 0;
int t = 1;
for(int i=0;i<32;i++){
if(i!=0){
t = t*2;
}
res += bit[i]==0?0:t;
}
return res;
}
}
方法二:按位或
public int maximumXOR(int[] nums) {
int ans = 0;
for (int num : nums) ans |= num;
return ans;
}
边栏推荐
- How to introduce devsecops into enterprises?
- 如何将 DevSecOps 引入企业?
- Online electronic component purchasing Mall: break the problem of information asymmetry in the purchasing process, and enable enterprises to effectively coordinate management
- Principle and performance analysis of lepton lossless compression
- 怎么叫一手一机的功能方式
- TiFlash 面向编译器的自动向量化加速
- 一网打尽异步神器CompletableFuture
- R language uses the polR function of mass package to build an ordered multi classification logistic regression model, and uses the coef function to obtain the log odds ratio corresponding to each vari
- Matrix chain multiplication dynamic programming example
- 网上电子元器件采购商城:打破采购环节信息不对称难题,赋能企业高效协同管理
猜你喜欢
Sorter evolution of ticdc 6.0 principle
【学习笔记】阶段测试1
循环不变式
为什么我认识的机械工程师都抱怨工资低?
Tidb DM alarm DM_ sync_ process_ exists_ with_ Error troubleshooting
魅族新任董事長沈子瑜:創始人黃章先生將作為魅族科技產品戰略顧問
Chow Tai Fook fulfills the "centenary commitment" and sincerely serves to promote green environmental protection
How to protect user privacy without password authentication?
分享 12 个最常用的正则表达式,能解决你大部分问题
日化用品行业智能供应链协同系统解决方案:数智化SCM供应链,为企业转型“加速度”
随机推荐
3W原则[通俗易懂]
Enjoy what you want. Zhichuang future
LeetCode_ 3 (longest substring without repeated characters)
R language dplyr package select function, group_ By function, mutate function and cumsum function calculate the cumulative value of the specified numerical variable in the dataframe grouping data and
Redis如何实现多可用区?
Mysql database installation tutorial under Linux
【学习笔记】阶段测试1
Google eventbus usage details
Total amount analysis accounting method and potential method - allocation analysis
Tdengine biweekly selection of community issues | phase III
After the microservice project is deployed, static resources and files uploaded to upload cannot be accessed. Solution
魅族新任董事长沈子瑜:创始人黄章先生将作为魅族科技产品战略顾问
Chow Tai Fook fulfills the "centenary commitment" and sincerely serves to promote green environmental protection
PHP - fatal error: allowed memory size of 314572800 bytes exhausted
PMP考试20天能通过吗?
TiFlash 面向编译器的自动向量化加速
3W principle [easy to understand]
CYCA少儿形体礼仪 宁波市培训成果考核圆满落幕
Principle and performance analysis of lepton lossless compression
POI set the data format of the column (valid)