[Leetcode][第5458题][JAVA][字符串的好分割数目][双指针][HashSet]

布满荆棘的人生 2023-03-01 13:35 5阅读 0赞

#### 【问题描述】5458. 字符串的好分割数目\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 双指针 ######

前面的搜索前面的个数和，后面的搜索后面的个数和  
**时间复杂度：O(N^2) 空间复杂度：O(1)**

class Solution { 
        /* 双指针做法， 前面的搜索前面的个数和，后面的搜索后面的个数和 */
         public int numSplits(String s) { 
             //rem1[i]用来记录前i个字符里面不同字符的个数
            int[] rem1=new int[s.length()];
             //s1[i]第i个字符是不是在前面出现过
            boolean[] s1=new boolean[26];
             //rem2[i]用来记录第i个字符后面不同字符的个数
            int[] rem2=new int[s.length()];
             //s2[i]第i个字符是不是在后面出现过
            boolean[] s2=new boolean[26];
             //给第一个和最后一个附上初始值
            rem1[0]=1;
            rem2[s.length()-1]=0;
            s1[s.charAt(0)-'a']=true;
            for(int i=1;i<s.length();i++){ 
                //如果没出现过，
                if(!s1[s.charAt(i)-'a']) { 
                    //前面不同的字符数+1
                    rem1[i]=rem1[i-1]+1;
                    //就把他标记出现
                    s1[s.charAt(i)-'a']=true;
                }
                else{ 
                    //如果出现过，不同字符的数量不变，直接用上一个的就行，这个字符不需要更改内容
                    rem1[i]=rem1[i-1];
                } 
                //与上面正好相反
                //后面是不是出现过……
                if(!s2[s.charAt(s.length()-i)-'a']){ 
                    rem2[s.length()-1-i]=rem2[s.length()-i]+1;
                    s2[s.charAt(s.length()-i)-'a']=true;
                }
                else{ 
                    rem2[s.length()-1-i]=rem2[s.length()-i];
                    
                }
            }
            int ans=0;
             //最后统计
            for(int i=0;i<s.length();i++){ 
                if(rem1[i]==rem2[i]) ans++;
            } 
    
            return ans;
        }
    }

###### 2. HashSet ######

正向扫描字符串,统计i位置处不同字符的个数  
反向扫描字符串,统计s.length()-i位置处不同字符的个数  
比较正反扫描结果,统计结果  
字符串 a a c a b a  
正向 1 1 2 2 3 1  
反向 3 3 3 2 2 1

**时间复杂度：O(N) 空间复杂度：O(1)**

public int numSplits(String s) { 
            int len = s.length();
            Set<Character> s1 = new HashSet<>();
            Set<Character> s2 = new HashSet<>();
            int[]count1 = new int[len];
            int[]count2 = new int[len];
    
            for(int i=0,j=len-1;i<len;i++,j--){ 
                char c1 = s.charAt(i);
                char c2 = s.charAt(j);
    
                if(!s1.contains(c1)){ 
                    s1.add(c1);
                }
                if(!s2.contains(c2)){ 
                    s2.add(c2);
                }
                count1[i] = s1.size();
                count2[j] = s2.size();
            }
            int count=0;
            for(int i =1 ;i<len;i++){ 
                if(count1[i-1]== count2[i]){ 
                    ++count;
                }
            }
            return count;
        }

#### 【总结】 ####

###### 1. 统计 HashSet 双指针思路 ######

###### 2.一开始只能想到暴力 能想到是好事 但是要多思考再动手 不然会超时 ######

参考链接：https://leetcode-cn.com/problems/number-of-good-ways-to-split-a-string/solution/javaer-fen-by-dui-fang-zheng-zai-jiang-hua-2/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230208/daddbfbdd89b431398cfa79cd21cd2f7.png