当前位置:网站首页>Day32 LeetCode
Day32 LeetCode
2022-07-31 03:06:00 【太阳在坠落】
1. 字符串中所有变位词
给定两个字符串 s 和 p,找到 s 中所有 p 的 变位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同,但排列不同的字符串。
分析:
使用滑动窗口,滑动窗口的大小为p的长度。先使用一个数组来记录p中字母出现的次数,然后统计滑动窗口内每个字母出现的次数,如果两数组相同则将开始的坐标进行记录。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int n = s.length(), m = p.length();
if (m > n) return res;
int[] count1 = new int[26];
int[] count2 = new int[26];
for (int i = 0; i < m; i++) {
count1[s.charAt(i)-'a']++;
count2[p.charAt(i)-'a']++;
}
if (Arrays.equals(count1, count2)) res.add(0);
for (int i = 0; i < n-m; i++) {
--count1[s.charAt(i)-'a'];
++count1[s.charAt(i+m)-'a'];
if (Arrays.equals(count1, count2)) res.add(i+1);
}
return res;
}
}
2. 不含重复字符的最长子字符串
给定一个字符串 s ,请你找出其中不含有重复字符的最长连续子字符串的长度。
分析:
利用哈希表和滑动窗口来实现。初始化left=right=0,先用right开始遍历字符串,如果哈希表中不存在当前字符则存入表中,长度加1;如果哈希表中存有当前字符则开始left++直到下标left的字符等于当前字符,然后再left++,存入当前字符到表中。
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.isEmpty()) return 0;
int ans = 1;
int start = 0;
Set<Character> set = new HashSet<>();
set.add(s.charAt(0));
for (int end = 1; end < s.length(); end++) {
if (set.contains(s.charAt(end))) {
while (s.charAt(start) != s.charAt(end)) {
set.remove(s.charAt(start));
start++;
}
set.remove(s.charAt(start));
start++;
set.add(s.charAt(end));
} else {
set.add(s.charAt(end));
ans = Math.max(ans, end - start + 1);
}
}
return ans;
}
}
3. 所含有所有字符的最短字符串
给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串,则返回空字符串 “” 。
如果 s 中存在多个符合条件的子字符串,返回任意一个。
注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
分析:
1.大小写字母都有,用1个数组ascii128个字符包含,比哈希快,也比2个26数组好写。
2.变量all统计有效字母个数是否达到结算条件(all==m说明t中字母全部匹配)。
3.结算前收缩左边界l去除多余字母,追求最小长度。
4.结算后收缩左边界l去除1个有效字母,找下一个能全部匹配的字符串
class Solution {
public String minWindow(String s, String t) {
int n=s.length(),m=t.length();
if(n<m)return "";
int[] ori=new int[128],cnt=new int[128];
for(int i=0;i<m;i++){
ori[(int)t.charAt(i)]++;
}
int l=0,r=0,c=-1,len=n+1,all=0;
while(r<n){
int p=(int)s.charAt(r);
if(cnt[p]<ori[p])all++;
cnt[p]++;
if(all==m){
int k=(int)s.charAt(l);
while(l<=r&&cnt[k]>ori[k]){
cnt[k]--;
l++;
k=(int)s.charAt(l);
}
if(r-l+1<len){
c=l;
len=r-l+1;
}
while(l<=r&&all==m){
k=(int)s.charAt(l);
if(cnt[k]==ori[k]){
all--;
}
cnt[k]--;
l++;
}
}
r++;
}
return len==n+1?"":s.substring(c,c+len);
}
}
4. 有效的回文
给定一个字符串 s ,验证 s 是否是 回文串 ,只考虑字母和数字字符,可以忽略字母的大小写。
本题中,将空字符串定义为有效的 回文串 。
分析:
双指针+判断是否为字母和数字字符。
class Solution {
public boolean isPalindrome(String s) {
s = s.toLowerCase();
int l = 0, r = s.length() - 1;
while (l < r) {
while (l < r && !check(s.charAt(l))) l++;
while (l < r && !check(s.charAt(r))) r--;
if (l < r && s.charAt(l) != s.charAt(r)) return false;
l++;
r--;
}
return true;
}
public boolean check(char c) {
//检测字符c是否为数字或字母
return 'a' <= c && c <= 'z' || '0' <= c && c <= '9';
}
}
5. 最多删除一个字符得到回文
给定一个非空字符串 s,请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
分析:
双指针,设定左右指针,将二者分别指向字符串的两边。依次比较左右指针对应的字符是否相等。
如果相等,继续比较剩下的字符。如果不相等,则分两种情况,只要有一种情况是回文字符串即可:
- 删除左边的 left 指针指向的元素,判断 s[left+1, right] 是否回文。
- 删除右边的 right 指针指向的元素,判断s[left, right-1] 是否回文。
class Solution {
public boolean validPalindrome(String s) {
for(int left = 0, right = s.length() - 1; left < right; left++, right--){
// 如果不相等,则分两种情况:删除左边的元素,或者右边的元素,再判断各自是否回文,满足一种即可。
if(s.charAt(left) != s.charAt(right))
return isPalindrome(s, left+1, right) || isPalindrome(s, left, right - 1);
}
return true;
}
// 判断字符串 s 的 [left, right] 是否回文
private boolean isPalindrome(String s, int left , int right){
while (left < right){
if (s.charAt(left++) != s.charAt(right--))
return false;
}
return true;
}
}
边栏推荐
- 华为分布式存储FusionStorage知识点总结【面试篇】
- 编译Hudi
- 【HCIP】ISIS
- 【Cocos Creator 3.5】缓动系统停止所有动画
- Mysql 45讲学习笔记(二十四)MYSQL主从一致
- [C language foundation] Solve C language error: expected ';', ',' or ')' before '&' token
- 解析小结—自用
- 10 权限介绍
- Discourse 自定义头部链接(Custom Header Links)
- CorelDRAW2022 streamlined Asia Pacific new features in detail
猜你喜欢
华为分布式存储FusionStorage知识点总结【面试篇】
Compile Hudi
什么是系统?
IIR滤波器和FIR滤波器
5. SAP ABAP OData 服务如何支持 $filter (过滤)操作
Mysql 45讲学习笔记(二十三)MYSQL怎么保证数据不丢
【异常】The field file exceeds its maximum permitted size of 1048576 bytes.
What is a distributed lock?Three ways of implementing distributed lock
Mysql 45讲学习笔记(二十四)MYSQL主从一致
YOLOV5学习笔记(二)——环境安装+运行+训练
随机推荐
CorelDRAW2022 streamlined Asia Pacific new features in detail
15、网站统计数据
跨专业考研难度大?“上岸”成功率低?这份实用攻略请收下!
Thesis framework of the opening report
SQL injection Less47 (error injection) and Less49 (time blind injection)
软件积累 -- 截图软件ScreenToGif
冒泡排序、选择排序、直接插入排序、二分法查找
Uninstallation of mysql5.7.37 under CentOS7 [perfect solution]
选好冒烟测试用例,为进入QA的制品包把好第一道关
4. Sensitive word filtering (prefix tree)
【Exception】The field file exceeds its maximum permitted size of 1048576 bytes.
【C语言】进制转换一般方法
Software accumulation -- Screenshot software ScreenToGif
Ambiguous method call.both
什么是分布式锁?实现分布式锁的三种方式
StringJoiner in detail
The whole process scheduling, MySQL and Sqoop
CloudCompare&PCL 计算两个点云之间的重叠度
11、Redis实现关注、取消关注以及关注和粉丝列表
Office automation case: how to automatically generate period data?