企业网站规划书范文,wordpress 知道创宇,徐州关键词优化平台,网站首页快速收录【问题描述】5458. 字符串的好分割数目[中等] 【解答思路】
1. 双指针
前面的搜索前面的个数和#xff0c;后面的搜索后面的个数和 时间复杂度#xff1a;O(N^2) 空间复杂度#xff1a;O(1)
class Solution {/*双指针做法#xff0c;前面的搜索前面的个数和#xff0c;…【问题描述】5458. 字符串的好分割数目[中等] 【解答思路】
1. 双指针
前面的搜索前面的个数和后面的搜索后面的个数和 时间复杂度O(N^2) 空间复杂度O(1)
class Solution {/*双指针做法前面的搜索前面的个数和后面的搜索后面的个数和*/public int numSplits(String s) {//rem1[i]用来记录前i个字符里面不同字符的个数int[] rem1new int[s.length()];//s1[i]第i个字符是不是在前面出现过boolean[] s1new boolean[26];//rem2[i]用来记录第i个字符后面不同字符的个数int[] rem2new int[s.length()];//s2[i]第i个字符是不是在后面出现过boolean[] s2new boolean[26];//给第一个和最后一个附上初始值rem1[0]1;rem2[s.length()-1]0;s1[s.charAt(0)-a]true;for(int i1;is.length();i){//如果没出现过if(!s1[s.charAt(i)-a]) {//前面不同的字符数1rem1[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 ans0;//最后统计for(int i0;is.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();SetCharacter s1 new HashSet();SetCharacter s2 new HashSet();int[]count1 new int[len];int[]count2 new int[len];for(int i0,jlen-1;ilen;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 count0;for(int i 1 ;ilen;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/
