【阿里云在线编程】 65.Alice的01串

清疚 2021-06-10 20:38 360阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 思路 ###

1.  首先要注意的一点，题目中没有要求字串必须去重，所以字串是可以重复的
2.  用暴力法肯定不合适，暴力法时间复杂度是 O(n2)
3.  其实字串的算法很简单，找出第1个1之前的0的数量和第k个1之后的0的数量就能算出的结果

比如  
输入：2  
“000010010100”  
记录好1的位置  
项目 | Value

<table> 
 <thead> 
  <tr> 
   <th>1的索引</th> 
   <th>距离上一个1之间的0的数量</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>0</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>2</td> 
  </tr> 
 </tbody> 
</table>

这个时候结果就是 （4 +1）x（2 + 1） + （2 + 1）x（1 + 1） + （1 + 1）x（2 + 1）

### code ###

package solution65;
    
    import java.util.HashSet;
    
    class Solution { 
        public long solution(int k, String s) { 
            if (s.indexOf('1') == -1) return (long) (1 + s.length()) * s.length() / 2;
            long res = 0;
            long[] count = new long[s.length() + 1];
            int p = 0; // count的索引
            long sum = 0; // 记录出现的0的个数
            for (int i = 0; i < s.length(); i++) { 
                if (s.charAt(i) == '0') { 
                    sum++;
                } else { 
                    count[p] = sum;
                    p++;
                    sum = 0;
                }
            }
            count[p] = sum;
            if (k == 0) { 
                for (int i = 0; i <= p; i++) { 
                    res += (1 + count[i]) * count[i] / 2;
                }
            } else { 
                for (int i = 0; i <= p - k; i++) { 
                    res += (count[i] + 1) * (count[i + k] + 1);
                }
            }
            return res;
        }
    }

[Link 1]: https://developer.aliyun.com/coding/65
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/ff385be10bba43ccb15b7ccb92dccd90.png