剑指 Offer II 字符串

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;

    }
}
上一篇:HTTP 400 Bad Request问题的解决


下一篇:《Deep Learning for Computer Vision withPython》阅读笔记-StarterBundle(第11 - 12章)