字符串 - 《算法学习》

1.Leetcode 409 : 最长回文串
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

class Solution {
    //统计每个字符的个数
    // public int longestPalindrome(String s) {
    //  int count[] = new int [128]; 
    //  for(char c:s.toCharArray()){
    //      count[c]++;
    //  }
    //  int len =0;
    //  boolean flag = false;
    //  for(int i=0;i<count.length;i++){
    //      if(count[i]>0&&count[i]%2==0)len=len+count[i];
    //      else if(count[i]%2!=0) {
    //          len=len+(count[i]-1);
    //          flag = true;
    //          }
    //  }
    //  return  flag ? len+1 : len;
    // }
    //空间优化 
    // public int longestPalindrome(String s){
    //  int count [] = new int [52];
    //  for(char c: s.toCharArray()){
    //      if(c>='a'&& c<='z') count[c-'a']++;
    //      if(c>='A'&& c<='Z') count[c-'A'+26]++;
    //  }
    //  int len =0;
    //  boolean flag =false;
    //  for(int i=0;i<count.length;i++){
    //      if(count[i]>0&&count[i]%2==0) len+=count[i];
    //      else if(count[i]%2!=0){
    //          flag =true;
    //          len+=(count[i]-1);
    //      } 
    //  }
    //  return flag ? len+1 :len;
    // }
    //hashMap hashSet 实现
    public int longestPalindrome(String s){
        HashMap<Character,Integer> map = new HashMap<>();
        //使用hashMap统计字符个数
        for(char c:s.toCharArray()){
            map.put(c,map.getOrDefault(c,0)+1);
        }
        int len = 0;
        boolean flag= false;
      for(Character set :map.keySet()){
          int count = map.get(set);
          if(count>0&&count%2==0)len += count;
          else if(count%2!=0) {
              flag = true;
              len+=(count-1);
              }
      }
     return flag ? len+1: len;
    }
}

2.Leetcode 205:同构字符串:
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

class Solution {
    //采用第三方替代
    // public boolean isIsomorphic(String s, String t) {
    //  if(s.length()!=t.length()) return false;
    //  String []arr1= s.split("");
    //  String []arr2= t.split("");
    //  return helper(arr1).equals(helper(arr2));
    // }
    // public String helper(String arr[]){
    //     StringBuilder sb= new StringBuilder();
    //     HashMap<String,Integer>map = new HashMap<>();
    //     for(int i=0;i<arr.length;i++){
    //         if(map.containsKey(arr[i])){
    //         sb.append(map.get(arr[i]));
    //     }else{
    //         sb.append(i);
    //          map.put(arr[i],i);
    //     }
    //     }
    //     return sb.toString();
    // }
    public boolean isIsomorphic(String s, String t){
        if(t.length()!=s.length()) return false;
        String []arr1= s.split("");
        String []arr2= t.split("");
        return helper(arr1,arr2)&& helper(arr2,arr1);
    }
    public boolean helper(String arr1[],String arr2[]){
        HashMap<String,String> map = new HashMap<>();
        for(int i=0;i<arr1.length;i++){
            if(map.containsKey(arr1[i])){
                if(!map.get(arr1[i]).equals(arr2[i])) return false;
            }else{
                map.put(arr1[i],arr2[i]);
            }
        }
        return true;
    }
}

3.Leetcode 290:单词规律：
给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

class Solution {
    // public boolean wordPattern(String pattern, String str) {
    // //采用HashMap
    //  String arr[]  = str.split(" ");
    //  if(pattern.length()!=arr.length)  return false;
    //  HashMap<Character,String> map = new HashMap<>();
    //  for(int i=0;i<arr.length;i++){
    //      char c = pattern.charAt(i);
    //     if(map.containsKey(c)){
    //         if(!map.get(c).equals(arr[i])) return false;
    //     }
    //     else{
    //       if(map.containsValue(arr[i])) return false;
    //     }
    //     map.put(c,arr[i]);
    //  }
    //  return true;
    // }
    //换一种思路：就是pattern和str满足一一对应的关系
    public boolean wordPattern(String pattern, String str){
        String arr1[] = str.split(" ");
        String arr2[] = pattern.split("");
        if(arr1.length!=pattern.length()) return false;
        return helper(arr1,arr2)&&helper(arr2,arr1);
    }
    public boolean helper(String arr1[],String arr2[]){
        HashMap<String,String> map = new HashMap<>();
        for(int i=0;i<arr1.length;i++){
          if(map.containsKey(arr1[i])){
             if(!map.get(arr1[i]).equals(arr2[i])) return false;
          }else{
              map.put(arr1[i],arr2[i]);
          }
        }
        return true;
    }
}
public boolean wordPattern(String pattern, String str) {
    String[] array1 = str.split(" ");
    if (array1.length != pattern.length()) {
        return false;
    }
    char[] array2 = pattern.toCharArray();
    HashMap<String, Integer> map1 = new HashMap<>();
    HashMap<Character, Integer> map2 = new HashMap<>();
    for (int i = 0; i < array1.length; i++) {
        String c1 = array1[i];
        char c2 = array2[i];
        // 当前的映射值是否相同
        int a = map1.getOrDefault(c1, -1);
        int b = map2.getOrDefault(c2, -1);
        if (a != b) {
            return false;
        } else { 
            map1.put(c1, i);
            map2.put(c2, i); 
        }
    }
    return true;
}

Leetcode 3.无重复字符的最长子串(连续)

// class Solution {
//     //第一种采用hashSet和滑动窗口实现
//     public int lengthOfLongestSubstring(String s) {
//         HashSet<Character> set = new HashSet<>();
//         int ans =0;
//         char c[] = s.toCharArray();
//         int rk =0;
  //删除直到没有重复字符
//         for(int i=0;i<c.length;i++){
//           if(i>0){
//               set.remove(c[i-1]);
//           }
//           while(rk<c.length && !set.contains(c[rk])){
//               set.add(c[rk]);
//               rk++;
//           }
//           ans= Math.max(ans,rk-i);
//         }
//         return ans;
//     }

// }

//方法2 ：采用HashMap 散列表实现 
// class Solution {
//   public int lengthOfLongestSubstring(String s){
//    HashMap<Character,Integer> map = new HashMap<>();
//    int ans =0; 


//    int left=0;
//     char[]c =s.toCharArray();
//     for(int i=0;i<c.length;i++){
//         if(map.containsKey(c[i])){
//           left = Math.max(map.get(c[i])+1,left);//记录第一个重复字符的右边第一个字符作为新的串的
//         }
//         map.put(c[i],i);
//         ans= Math.max(ans,i-left+1);

//         }
//         return ans;
//         }

// }
//方法三采用队列 和第一种方法思路相同
class Solution {
  public int lengthOfLongestSubstring(String s){
      Queue<Character> queue = new LinkedList<>();
      int ans =0;
      for(char c:s.toCharArray()){
          while(queue.contains(c)){
              queue.poll();
          }
          queue.add(c);
          ans=Math.max(ans,queue.size());
      }
      return ans;
  }
}

Leetcode 49 :字母异味词分组

// class Solution {
//     //先排序 HashMap 字符串数组不能转化为字符串，应该先将字符串转化为字符数组，然后采用
//     //valueOf将字符数组转化为字符串
//     public List<List<String>> groupAnagrams(String[] strs) {
//      HashMap<String,List<String>> map = new HashMap<>();

//      for(int i=0;i<strs.length;i++){
//          char str[]=strs[i].toCharArray();
//          Arrays.sort(str);
//          String key = String.valueOf(str);
//          if(!map.containsKey(key)) map.put(key,new ArrayList<>());
//          map.get(key).add(strs[i]);
//      } 
//      return new ArrayList<>(map.values());
//     }
//  }







 //按计数类
class Solution {
    public List<List<String>> groupAnagrams(String[] strs){
        if(strs.length==0) return new ArrayList<>();
        int count [] = new int [26];
        HashMap<String,List> map = new HashMap<>();
        for(String s:strs){
            Arrays.fill(count,0);
            for(char c: s.toCharArray()) count[c-'a']++;
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<26;i++){
                sb.append("#");
                sb.append(count[i]);
            }
            String key = sb.toString();
          if(!map.containsKey(key)) map.put(key,new ArrayList<>());
           map.get(key).add(s);
        }
        return new ArrayList(map.values());
    }
}

字符串排序

public class Test {
    public static void main(String[] args) {
        String[] str = new String[3];
        input(str);
        print(str);
        sort(str);
        print(str);
    }
    //输入函数
    public static void input(String[] str) {
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入三个字符串:");
        for(int i=0;i<str.length;i++) {
            str[i] = sc.nextLine();
        }
        sc.close();
    }
    //输出函数
    public static void print(String[] str) {
        for(int i=0;i<str.length;i++) {
            System.out.print(str[i]+" ");
        }
        System.out.println();
    }
    //排序函数
    public static void sort(String[] str) {
        for(int i=0;i<str.length-1;i++) {
            for(int j=i+1;j<str.length;j++) {
                if(str[i].compareTo(str[j])<0)
                    swap(str,i,j);
            }
        }
    }
    //归并排序
    public static void mergeSort(String str[],int lo,int hi){
        if(hi<=lo) return ;
        int mid = lo+(hi-lo)/2;
        mergeSort(str,lo,mid);
        mergeSort(str,mid+1,hi);
        merge(str,lo,mid,hi);
    }
    public static void merge(String str[],int lo,int mid,int hi){
        int i=lo;
        int j= mid+1;
        String aux[] = new  String [str.length];
        for(int k=lo;k<=hi;k++){
            aux[k] = str[k];
        }
        for(int k=lo;k<=hi;k++){
            if(i>mid) str[k] = aux[j++];
            else if(j>hi) str[k] = aux[i++];
            else if(aux[i].compareTo(aux[j])>0) str[k] = aux[i++];
            else str[k] = aux[j++];
        }
    }
 //快速排序：
    public static  void quickSort(String str[],int lo,int hi){
        if(hi<=lo) return ;
        int j= partition(str,lo,hi);
        quickSort(str,lo,j-1);
        quickSort(str,j+1,hi);
    }
    public static int partition(String str[],int lo,int hi){
        int i= lo;
        int j= hi+1;
        String v= str[lo];
        while(true){
            while(v.compareTo(str[++i])<0&&i<hi);
                while (v.compareTo(str[--j])>0&&j>0);
            if(i>=j)break;
            swap(str,i,j);

        }
        swap(str,lo,j);
        return j;
    }

    //交换函数
    public static void swap(String[] str,int i,int j) {
        String s=str[i];
        str[i]=str[j];
        str[j]=s;
    }
    //交换函数
    public static void swap(String[] str,int i,int j) {
        String s=str[i];
        str[i]=str[j];
        str[j]=s;
    }

}

字符串查找KMP算法

 public static  void main(String args[]){
        String str[] = new String[2];
     Scanner sc = new Scanner(System.in);
     for(int i=0;i<2;i++){
         str[i] = sc.nextLine();
     }
     sc.close();
        System.out.println(indexOf(str[0],str[1]));
    }
    public static int[] getNext(char[] p) {
        // 已知next[j] = k,利用递归的思想求出next[j+1]的值
        // 如果已知next[j] = k,如何求出next[j+1]呢?具体算法如下:
        // 1. 如果p[j] = p[k], 则next[j+1] = next[k] + 1;
        // 2. 如果p[j] != p[k], 则令k=next[k],如果此时p[j]==p[k],则next[j+1]=k+1,
        // 如果不相等,则继续递归前缀索引,令 k=next[k],继续判断,直至k=-1(即k=next[0])或者p[j]=p[k]为止
        int pLen = p.length;
        int[] next = new int[pLen];
        int k = -1;
        int j = 0;
        next[0] = -1; // next数组中next[0]为-1
        while (j < pLen - 1) {
            if (k == -1 || p[j] == p[k]) {
                k++;
                j++;
                // 修改next数组求法
                if (p[j] != p[k]) {
                    next[j] = k;// KMPStringMatcher中只有这一行
                } else {
                    // 不能出现p[j] = p[next[j]],所以如果出现这种情况则继续递归,如 k = next[k],
                    // k = next[[next[k]]
                    next[j] = next[k];
                }
            } else {
                k = next[k];
            }
        }
        return next;
    }

    public static int indexOf(String source, String pattern) {
        int i = 0, j = 0;
        char[] src = source.toCharArray();
        char[] ptn = pattern.toCharArray();
        int sLen = src.length;
        int pLen = ptn.length;
        int[] next = getNext(ptn);
        while (i < sLen && j < pLen) {
            // 如果j = -1,或者当前字符匹配成功(src[i] = ptn[j]),都让i++,j++
            if (j == -1 || src[i] == ptn[j]) {
                i++;
                j++;
            } else {
                // 如果j!=-1且当前字符匹配失败,则令i不变,j=next[j],即让pattern模式串右移j-next[j]个单位
                j = next[j];
            }
        }
        if (j == pLen)
            return i - j;
        return -1;
    }