LeetCode刷题 day26

1.包含所有三种字符的子字符串数目

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。
请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。

示例 1：
输入：s = “abcabc”
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 “abc”, “abca”, “abcab”, “abcabc”, “bca”, “bcab”, “bcabc”, “cab”, “cabc” 和 “abc” (相同字符串算多次)。

示例 2：
输入：s = “aaacb”
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 “aaacb”, “aacb” 和 “acb” 。

示例 3：
输入：s = “abc”
输出：1

思路
只要某子字符串包含abc三种字符，则以该字符串为前缀的字符串都包含abc，因此用双指针，分别指向字符串的左边界和后边界，分别统计a,b,c的个数，只要a,b,c个数均大于0，即可得到从该位置起始的字符串个数。

classSolution{publicintnumberOfSubstrings(Strings){//双指针做法，滑动窗口inta=0,b=0,c=0;intans=0;char[]cs=s.toCharArray();intn=s.length();for(inti=0,j=-1;j<n;){//先决定哪个指针动if(a!=0&&b!=0&&c!=0){//三个都不为0ans+=n-j;if(cs[i]=='a'){a--;}elseif(cs[i]=='b'){b--;}elseif(cs[i]=='c'){c--;}i++;}else{j++;if(j<n){if(cs[j]=='a'){a++;}elseif(cs[j]=='b'){b++;}elseif(cs[j]=='c'){c++;}}}}returnans;}}

时间复杂度：O ( n ) O(n)O(n)左右指针都从头到尾移动，且每循环一次移动一位，要么左指针动，要么右指针动，总的移动次数不超过2 n 2n2n
空间复杂度：O ( n ) O(n)O(n)如果这里不把字符串转化成字符数组，空间复杂度为O ( 1 ) O(1)O(1)

2. 只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：
输入：nums = [2,2,3,2]
输出：3

示例 2：
输入：nums = [0,1,0,1,0,1,99]
输出：99

思路
这里借鉴当一个元素出现两次时，通过异或运算能直接消除掉该元素，其实是逢二进一，二进制的定义，同样，这里是逢三进一，即以某一位二进制为例，若该二进制位上1出现三次时，变为0，那么我们可以用两个二进制位来表示

• (ab)=00表示出现(0,3,6,9,…)次1
• (ab)=01表示出现(1,4,7,10,…)次1
• (ab)=10表示出现(2,5,8,11,…)次1
  当要找到出现1次的某个数时，只要求出b即可，因为只有在出现1次时，b的二进制位才为1，出现三次时b的二进制位为0，相当于忽略了出现三次的元素。
  如果无法理解，可以看下面的例子，以[2,2,3,2]为例：
  2=(0010),3=(0011);
  a=(0000),b=(0000);
  第一个二进制上有1个1，因此(ab)=(01)
  第二个二进制位有四个1，因此(ab)=(01)
  第三个二进制位有0个1，因此(ab)=(00)
  第四个二进制位有0个1，因此(ab)=(00)
  合并得到(ab) = ((00)(00)(01)(01))
  将ab拆开后得到a=(0000),b=(0011)，b与数字3一致
  这里如何根据a,b以及num来计算新的a,b的值，可以参考如何根据真值表得到逻辑表达式的计算公式，只要求出真值表，直接套用公式即可。

classSolution{publicintsingleNumber(int[]nums){inta=0,b=0;for(intnum:nums){b=(b^num)&~a;a=(a^num)&~b;}returnb;}}

时间复杂度：O ( n ) O(n)O(n)
空间复杂度：O ( 1 ) O(1)O(1)