当前位置:网站首页>[summary of leetcode weekly competition] the 81st fortnight competition of leetcode (6.25)
[summary of leetcode weekly competition] the 81st fortnight competition of leetcode (6.25)
2022-07-05 14:27:00 【Let it beSun】
Weekly Links : competition - Power button (LeetCode)81 A fortnight game
subject 1 2315. Statistical asterisk
Ideas :
Direct traversal of simple topics , Use a variable to identify whether it is within the vertical line pair
Code :
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;
}
}
subject 2 Count the logarithm of points that cannot reach each other in an undirected graph
Ideas :
Union checking set , See 【 Algorithm notes 】 Focus on summary and collection _Let it beSun The blog of -CSDN Blog
Mainly find the size of each connected component
In limine TLE( Overtime ) The idea of : Calculate the size of each connected component directly by multiplication
for example :
At this time, the sizes of several connected components are {4,2,1} Now calculate ans = 4*2+4*1+2*1 = 14
But time complexity O(n^2) Overtime ;
Calculation method 1
So consider for each node , Computing node i The number of disconnected points , Because there is repetition in the calculation of each node , So the answer is to sum and divide by 2.
for(int i=0;i<n;i++){
ans += (long)(n-sz[find(i)]);
}
return ans/2;
Calculation method 2
You can consider the logarithm of all points n*(n-1)/2 , Subtract the number of nodes inside each connected component a*(a-1)/2
Code :
Corresponding calculation method 1 :
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;
}
}
Corresponding calculation method 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;
}
}
subject 3 2317. Maximum XOR and after operation
Ideas
It is to count whether each bit in this array appears 1, For all binary bits , As long as this bit appears in the array 1
, So this one in the answer is also 1
.
So the answer is the result of bitwise or of all numbers . Complexity O(n).
Code
Method 1 : Direct statistics
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;
}
}
Method 2 : Press bit or
public int maximumXOR(int[] nums) {
int ans = 0;
for (int num : nums) ans |= num;
return ans;
}
边栏推荐
- openGauss数据库源码解析系列文章—— 密态等值查询技术详解(下)
- 展现强大。这样手机就不会难前进
- Tiflash compiler oriented automatic vectorization acceleration
- 网上电子元器件采购商城:打破采购环节信息不对称难题,赋能企业高效协同管理
- SSL证书错误怎么办?浏览器常见SSL证书报错解决办法
- Assembly language
- Postgresql 13 安装
- Why do mechanical engineers I know complain about low wages?
- Online electronic component purchasing Mall: break the problem of information asymmetry in the purchasing process, and enable enterprises to effectively coordinate management
- How to choose the appropriate certificate brand when applying for code signing certificate?
猜你喜欢
为什么我认识的机械工程师都抱怨工资低?
直播预告|如何借助自动化工具落地DevOps(文末福利)
Thymeleaf th:classappend attribute append th:styleappend style append th:data- custom attribute
Pointer operation - C language
CYCA少儿形体礼仪 宁波市培训成果考核圆满落幕
日化用品行业智能供应链协同系统解决方案:数智化SCM供应链,为企业转型“加速度”
[learning notes] stage test 1
乌卡时代下,企业供应链管理体系的应对策略
Interpretation of tiflash source code (IV) | design and implementation analysis of tiflash DDL module
SaaS multi tenant solution for FMCG industry to build digital marketing competitiveness of the whole industry chain
随机推荐
C language -- structure and function
Shen Ziyu, nouveau Président de Meizu: M. Huang Zhang, fondateur de Meizu, agira comme conseiller stratégique pour les produits scientifiques et technologiques de Meizu
美国费城发生“安全事故” 2名警察遭枪杀
World Environment Day | Chow Tai Fook serves wholeheartedly to promote carbon reduction and environmental protection
ASP.NET大型外卖订餐系统源码 (PC版+手机版+商户版)
详解Vue适时清理keepalive缓存方案
Solution of commercial supply chain collaboration platform in household appliance industry: lean supply chain system management, boosting enterprise intelligent manufacturing upgrading
How to introduce devsecops into enterprises?
【leetcode周赛总结】LeetCode第 81 场双周赛(6.25)
Scenario based technology architecture process based on tidb - Theory
Thymeleaf 模板的创建与使用
Qingda KeYue rushes to the science and Innovation Board: the annual revenue is 200million, and it is proposed to raise 750million
Interpretation of tiflash source code (IV) | design and implementation analysis of tiflash DDL module
Sorter evolution of ticdc 6.0 principle
Pointer operation - C language
R Language ggplot2 Visualization: visualize linegraph, using Legend in Theme function. Paramètre de position emplacement de la légende personnalisée
注意!软件供应链安全挑战持续升级
mysql8.0JSON_CONTAINS的使用说明
TDengine 社区问题双周精选 | 第三期
R語言ggplot2可視化:可視化折線圖、使用theme函數中的legend.position參數自定義圖例的比特置