leetcode83周赛
创始人
2024-05-09 00:46:43
0

前言:

周赛两题选手,有点意思

830.较大分组的位置

思路:wa了三发,对边界了解的不够清楚
可以有一个小小的优化,时间复杂度O(n)

// arr.add(start);
//arr.add(i-1);
//res.add(arr);
res.add(Arrays.asList(start,i - 1));
class Solution {public List> largeGroupPositions(String s) {char[] chars = s.toCharArray();List> res = new ArrayList<>();int start = 0;int step = 1;if(s.length() <3) return res;for(int i = 1;i < chars.length;i++){if(chars[i] != chars[start]){if(i - start >= 3 ){List arr = new ArrayList<>();arr.add(start);arr.add(i-1);res.add(arr);}start = i;   }if(i == chars.length -1 && i - start >=2){List arr = new ArrayList<>();arr.add(start);arr.add(i);res.add(arr);}   }return res;}
}

831.隐藏个人信息

思路

单纯的模拟,熟悉javaAPI操作

class Solution {public String maskPII(String s) {//1、判断他是电子邮件if(s.indexOf("@") != -1){StringBuffer buffer = new StringBuffer();String[] str_arr = s.split("@");String name_str = str_arr[0].toLowerCase();buffer.append(name_str.charAt(0));buffer.append("*****");buffer.append(name_str.charAt(name_str.length() - 1));String domain_str = str_arr[1].toLowerCase();buffer.append("@").append(domain_str);return buffer.toString();}else{//数字 char[] chars = s.toCharArray();StringBuffer buffer = new StringBuffer();for(int i = 0;i < chars.length;i ++){if(chars[i] >= '0' && chars[i] <= '9'){buffer.append(chars[i]);}}String phone = buffer.toString();StringBuffer buffer1 = new StringBuffer();if(phone.length()==10){buffer1.append("***-***-").append(phone.substring(phone.length()-4));}else if(phone.length()==11){buffer1.append("+*-***-***-").append(phone.substring(phone.length()-4));}else if(phone.length()==12){buffer1.append("+**-***-***-").append(phone.substring(phone.length()-4));}else if(phone.length()==13){buffer1.append("+***-***-***-").append(phone.substring(phone.length()-4));}else{System.out.println("数字长度不符合");}return buffer1.toString();}// return "";}
}

829. 连续整数求和
题目:
给定一个正整数 n,返回 连续正整数满足所有数字之和为 n 的组数 。

示例 1:

输入: n = 5
输出: 2
解释: 5 = 2 + 3,共有两组连续整数([5],[2,3])求和后为 5。

思路
打死我都想不出来

有1个: x = x
有2个: x + (x+1) = 2x + 1
有3个: x + (x+1) + (x+2) = 3a + 3
有4个: x + (x+1) + (x+2) + (x+3) = 4x + 6
有5个: x + (x+1) + (x+2) + (x+3) + (x+4) = 5x + 10 … 当分解成连续的a个数字时, 有a个: x + (x+1) + … + (x+a-1) = ax + b 其中b总是相较于上一个b增加了(a-1), 可在迭代中维护b
因为x必须是正整数,所以只有当 (n - b) / a 可以整出时,说明n可以分解为联系的a个正整数,且第一个正整数就是(n - b) / a
容易知道随着个数a的不断增加,第一位数字x是不断减少的,当x小于等于0的时候,不管怎么增加a都不会得到有效的x了,因此迭代可以终止。

代码

class Solution {// x = x// x+(x+1) = 2x+1// x+(x+1)+(x+2) = 3x+3// ax+bpublic int consecutiveNumbersSum(int n) {int res = 0;int b = 0;int a = 1;while((n-b)/a > 0){if((n-b)%a==0) res += 1;b += a;a++;}return res;}
}

思路

为什么要用乘法定理呐?
刚开始,我对于这个字符的贡献值为什么是(curIndex - lastIndex) * (nextIndex - curIndex) 没有理解。
那么结合这个图的话,那就是A对于子串BCADEF的贡献值为 3 * 4 = 12。
这里是对应了包含A的总共有12种不同的连续子串。
BCA 、BCAD、BCADE、BCADEF、CA、CAD、CADE、CADEF、A、AD、ADE、ADEF

在这里插入图片描述

class Solution {public int uniqueLetterString(String s) {Map> map = new HashMap<>();for(int i = 0;i < s.length();i++){if(!map.containsKey(s.charAt(i))){map.put(s.charAt(i),new ArrayList<>());}map.get(s.charAt(i)).add(i);}int res = 0;for(Map.Entry> entry:map.entrySet()){List arr =  entry.getValue();int head = -1;int tail = -1;// 使用乘法定理for(int i = 0;i < arr.size();i++){tail = (i < arr.size() - 1) ? arr.get(i + 1): s.length();res += (arr.get(i) - head) * (tail - arr.get(i));head = arr.get(i);} }return res;}
}

参考文章

统计子串中唯一的字符

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播,要解决的几个问题是:1&...
Windows10添加群晖磁盘... 在使用群晖NAS时,我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章,在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
Fluent中创建监测点 1 概述某些仿真问题,需要创建监测点,用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装(Wind... 前言:刚换了一台电脑,里面所有东西都需要重新配置,习惯了所...
MFC文件操作  MFC提供了一个文件操作的基类CFile,这个类提供了一个没有缓存的二进制格式的磁盘...
有效的括号 一、题目 给定一个只包括 '(',')','{','}'...
【Ctfer训练计划】——(三... 作者名:Demo不是emo  主页面链接:主页传送门 创作初心ÿ...