当前位置:网站首页>Day32 LeetCode
Day32 LeetCode
2022-07-31 03:11:00 【the sun is falling】
1. All anagrams in the string
给定两个字符串 s 和 p,找到 s 中所有 p 的 变位词 的子串,返回这些子串的起始索引.不考虑答案输出的顺序.
变位词 指字母相同,但排列不同的字符串.
分析:
使用滑动窗口,滑动窗口的大小为p的长度.First use an array to recordp中字母出现的次数,Then count the number of occurrences of each letter in the sliding window,If the two arrays are the same, the starting coordinates will be recorded.
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 ,请你找出其中不含有重复字符的最长连续子字符串的长度.
分析:
It is implemented using hash table and sliding window.初始化left=right=0,先用right开始遍历字符串,If the current character does not exist in the hash table, it is stored in the table,长度加1;Start if the current character exists in the hash tableleft++直到下标leftis equal to the current character,然后再left++,Store the current character into the table.
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. The shortest string containing all characters
给定两个字符串 s 和 t .返回 s 中包含 t 的所有字符的最短子字符串.如果 s 中不存在符合条件的子字符串,则返回空字符串 “” .
如果 s 中存在多个符合条件的子字符串,返回任意一个.
注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量.
分析:
1.Both uppercase and lowercase letters,用1个数组ascii128个字符包含,比哈希快,也比2个26Arrays are easy to write.
2.变量allCheck whether the number of valid letters meets the settlement conditions(all==m说明tMatch all letters in).
3.Shrink the left border before settlementlRemove extra letters,Go for the minimum length.
4.Shrink the left border after settlementl去除1个有效字母,Find the next string that matches all
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 是否是 回文串 ,只考虑字母和数字字符,可以忽略字母的大小写.
本题中,将空字符串定义为有效的 回文串 .
分析:
双指针+Determines whether it is an alphanumeric character.
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;
}
}
边栏推荐
- Addition and Subtraction of Scores in LeetCode Medium Questions
- [Compilation principle] Design principle and implementation of recursive descent parsing
- 【编译原理】递归下降语法分析设计原理与实现
- 5. SAP ABAP OData 服务如何支持 $filter (过滤)操作
- 10. Redis implements likes (Set) and obtains the total number of likes
- 刚出道“一战成名”,安全、舒适一个不落
- Good place to download jar packages
- What is SQALE
- Project (5) - Small target detection tph-yolov5
- The whole process scheduling, MySQL and Sqoop
猜你喜欢
【异常】The field file exceeds its maximum permitted size of 1048576 bytes.
Mysql 45讲学习笔记(二十四)MYSQL主从一致
CorelDRAW2022 streamlined Asia Pacific new features in detail
Recursive query single table - single table tree structure - (self-use)
【C语言】三子棋(经典解法+一览图)
7年经验,功能测试工程师该如何一步步提升自己的能力呢?
Project (5) - Small target detection tph-yolov5
Multilingual settings of php website (IP address distinguishes domestic and foreign)
Graphical lower_bound & upper_bound
什么是系统?
随机推荐
Problems that need to be solved in distributed system architecture
[Dynamic programming] Maximum sum of consecutive subarrays
Recursive query single table - single table tree structure - (self-use)
web容器及IIS --- 中间件渗透方法1
Use of QML
接口测试关键技术
TCP详解(一)
10、Redis实现点赞(Set)和获取总点赞数
some of my own thoughts
点云DBSCAN聚类(MATLAB,非内置函数)
YOLOV5 study notes (3) - detailed explanation of network module
[Android] Room - Alternative to SQLite
[C language] Preprocessing operation
MP使用时的几个常见报错
els 方块向右移动边界判断、向下加速
分布式系统架构需要解决的问题
什么是系统?
自己的一些思考
QML的使用
递归查询单表-单表树结构-(自用)