014. 字符串中的变位词
class Solution {
Map<Character,Integer> m1 =new HashMap<>();
Map<Character,Integer> m2 =new HashMap<>();
public boolean check(char c)
{
if(m1.containsKey(c)&&m1.get(c).equals(m2.get(c)))
return true;
return false;
}
public boolean checkInclusion(String s1, String s2) {
for(char c : s1.toCharArray())
{
m1.put(c,m1.getOrDefault(c,0)+1);
}
//判断m1与m2有多少种字符是相等的 最多26
for(int i=0,j=0,cnt=0;i<s2.length();i++)
{
//插入
char c=s2.charAt(i);
if(check(c))cnt--;//之前是相等的 现在多了一个所以不相等
m2.put(c,m2.getOrDefault(c,0)+1);
if(check(c))cnt++;//插完后相等了 所以 这个字符的数目 两者相同
if(i-j+1==s1.length()+1)
{
char d=s2.charAt(j);
if(check(d))cnt--;//减之前相同 所以滑动完不同了
m2.put(d,m2.getOrDefault(d,0)-1);
if(check(d))cnt++;
j++;
}
if(cnt==m1.size())return true;//s1所含字符数
}
return false;
}
}
015. 字符串中的所有变位词
class Solution {
Map <Character,Integer>mp=new HashMap<>();
Map <Character,Integer>ms=new HashMap<>();
boolean check(char c)
{
if(mp.containsKey(c)&&mp.get(c).equals(ms.get(c)))
return true;
return false;
}
public List<Integer> findAnagrams(String s, String p) {
List <Integer> ans =new ArrayList();
char [] cs= s.toCharArray();
char [] cp= p.toCharArray();
for(char c : cp)
{
mp.put(c,mp.getOrDefault(c,0)+1);
// System.out.println(mp.size());
}
int n=s.length(),m=p.length();
for(int i=0,j=0,cnt=0;i<n;i++)
{
if(check(cs[i]))cnt--;//添加一个 原本两表s[i]个数相同 变成不同
ms.put(cs[i],ms.getOrDefault(cs[i],0)+1);
if(check(cs[i]))cnt++;
if(i-j+1>m)
{
if(check(cs[j]))cnt--;
ms.put(cs[j],ms.get(cs[j])-1);
if(check(cs[j]))cnt++;
j++;
}
//System.out.println(cnt);
//System.out.println(mp.size());
if(cnt==mp.size())ans.add(j);
}
return ans;
}
}
016. 不含重复字符的最长子字符串
双指针
class Solution {
public int lengthOfLongestSubstring(String s) {
Map <Character,Integer >memo =new HashMap<>();
int ans=0;
char [] cs=s.toCharArray();
for(int i=0,j=0;i<cs.length;i++)
{
if(memo.containsKey(cs[i]))//发现重复了 移动j直到不重复
{
while(memo.get(cs[i])!=0)
{
memo.put(cs[j],memo.get(cs[j])-1);
j++;
}
}
memo.put(cs[i],memo.getOrDefault(cs[i],0)+1);
ans=Math.max(ans,i-j+1);
}
return ans;
}
}
018. 有效的回文
class Solution {
public boolean isPalindrome(String s) {
int n=s.length();
char []cs=new char [n];
int j=0;
for(int i=0;i<n;i++)
{
char c=s.charAt(i);
if((c>='a'&&c<='z'))cs[j++]=c;
else if((c>='A'&&c<='Z'))cs[j++]=(char)(c+32);
else if(c>='0'&&c<='9')cs[j++]=c;//数字
}
boolean flag=true;
for(int i=0;i<j;i++)
{
if(cs[i]!=cs[(j-1)-i])flag=false;
}
return flag;
}
}
019. 最多删除一个字符得到回文
找到两边第一处不同 跳过左边的 或右边的 再继续做 判断两次
class Solution {
public boolean validPalindrome(String s) {
int i=0,j=s.length()-1;
while(i<j&&s.charAt(i)==s.charAt(j))
{
i++;j--;
}
if(i>=j)return true;
boolean flag=false;
int I=i,J=j;
i++;
while(i<j&&s.charAt(i)==s.charAt(j))
{
i++;j--;
}
if(i>=j)return true;
i=I;j=J;
j--;
while(i<j&&s.charAt(i)==s.charAt(j))
{
i++;j--;
}
if(i>=j)return true;
return false;
}
}