【問題描述】5458. 字符串的好分割數(shù)目[中等]

【解答思路】

1. 雙指針

前面的搜索前面的個數(shù)和，后面的搜索后面的個數(shù)和
時間復(fù)雜度：O(N^2) 空間復(fù)雜度：O(1)

class Solution {/*雙指針做法，前面的搜索前面的個數(shù)和，后面的搜索后面的個數(shù)和*/public int numSplits(String s) {//rem1[i]用來記錄前i個字符里面不同字符的個數(shù)int[] rem1=new int[s.length()];//s1[i]第i個字符是不是在前面出現(xiàn)過boolean[] s1=new boolean[26];//rem2[i]用來記錄第i個字符后面不同字符的個數(shù)int[] rem2=new int[s.length()];//s2[i]第i個字符是不是在后面出現(xiàn)過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++){//如果沒出現(xiàn)過，if(!s1[s.charAt(i)-'a']) {//前面不同的字符數(shù)+1rem1[i]=rem1[i-1]+1;//就把他標(biāo)記出現(xiàn)s1[s.charAt(i)-'a']=true;}else{//如果出現(xiàn)過，不同字符的數(shù)量不變，直接用上一個的就行，這個字符不需要更改內(nèi)容rem1[i]=rem1[i-1];} //與上面正好相反//后面是不是出現(xiàn)過……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;//最后統(tǒng)計for(int i=0;i<s.length();i++){if(rem1[i]==rem2[i]) ans++;} return ans;} }

2. HashSet

正向掃描字符串,統(tǒng)計i位置處不同字符的個數(shù)
反向掃描字符串,統(tǒng)計s.length()-i位置處不同字符的個數(shù)
比較正反掃描結(jié)果,統(tǒng)計結(jié)果
字符串 a a c a b a
正向 1 1 2 2 3 1
反向 3 3 3 2 2 1

時間復(fù)雜度：O(N) 空間復(fù)雜度：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;}

【總結(jié)】

1. 統(tǒng)計 HashSet 雙指針?biāo)悸?/h6>

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/

總結(jié)

以上是生活随笔為你收集整理的[Leetcode][第5458题][JAVA][字符串的好分割数目][双指针][HashSet]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。