当前位置:网站首页>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;
}
}
边栏推荐
猜你喜欢
分布式与集群是什么 ? 区别是什么?
7年经验,功能测试工程师该如何一步步提升自己的能力呢?
SQL injection Less54 (limited number of SQL injection + union injection)
Local area network computer hardware information collection tool
什么是系统?
Discourse Custom Header Links
7. List of private messages
What is distributed and clustered?What is the difference?
STM32问题合集
Chapter 9 SVM实践
随机推荐
[Godot][GDScript] 二维洞穴地图随机生成
3.5 】 【 Cocos Creator slow operating system to stop all animations
YOLOV5学习笔记(三)——网络模块详解
共模电感的仿真应用来了,满满的干货送给大家
【编译原理】递归下降语法分析设计原理与实现
execsnoop tool
YOLOV5 study notes (3) - detailed explanation of network module
WebSocket Session is null
Installation of mysql5.7.37 under CentOS7 [perfect solution]
【HCIP】ISIS
Chapter 9 SVM实践
Modbus on AT32 MCUs
【异常】The field file exceeds its maximum permitted size of 1048576 bytes.
Detailed explanation of TCP (3)
CorelDRAW2022 streamlined Asia Pacific new features in detail
多线程下类对象的服务承诺探讨
解析小结—自用
False positives and false negatives in testing are equally worthy of repeated corrections
[Compilation principle] Lexical analysis program design principle and implementation
原子操作 CAS