# 每个特定长度的二进制子串中应至少包含一个 ‘1’ 字符。

go评论59阅读模式

Each substring of a certian length of a binary substring should have at least one '1' character

# 问题

``````public static int minimumMoves(String s, int d) {
int n = s.length();

int i = 0, answer = 0;
while (i < n) {
boolean hasOne = false;
int j = i;
while (j < n && j < i + d) {
if (s.charAt(j) == '1') {
hasOne = true;
break;
}
j++;
}
if (!hasOne) {
i += d;
} else {
i++;
}
}
}
``````

You have been given a binary string containing only the characters '1' and '0'.

Calculate how many characters of the string need to be changed in order to make the binary string such that each of its substrings of at least a certain length contains at least one "1" character.

I came to think of the following idea but it fails for many testcases:

``````public static int minimumMoves(String s, int d) {
int n = s.length();

while(i&lt;n)
{
boolean hasOne = false;
int j=i;
while(j&lt;n &amp;&amp; j&lt;i+d)
{
if(s.charAt(j) == &#39;1&#39;)
{
hasOne = true;
break;
}
j++;
}
if(!hasOne) {
i += d;
}
else i++;
}
}
``````

Also my algorithm runs on O(|s|<sup>2</sup>) time. Can anyone suggest ideas on O(|s|) time?

# 答案1

return s.split("(?<=" + String.valueOf(d) + "})").stream().filter(str -> str.contains("1")).count()

Just throwing off an idea:

``````return s.split(&quot;(?&lt;=\\G.{&quot; + String.valueof(d) + &quot;})&quot;).stream().filter(str -&gt; str.contains(&quot;1&quot;)).count()
``````

# 答案2

``````public static int minimumMoves(String s, int d) {
int n = s.length();
int count = 0, answer = 0;

for(int i=0; i<d; i++)
{
if(s.charAt(i) == '1') count++;
}

if(count == 0) {
count++;
dq.removeLast();
}

int i=d;

while(i<n)
{
if(dq.getFirst() == '1') count--;
dq.removeFirst();

if(s.charAt(i) == '1') count++;

if(count == 0)
{
dq.removeLast();
count++;
}
i++;
}

}
``````

I used the sliding window technique and Deque to solve this. This is my accepted solution:

``````public static int minimumMoves(String s, int d) {
int n = s.length();
int count = 0, answer = 0;

for(int i=0; i&lt;d; i++)
{
if(s.charAt(i) == &#39;1&#39;) count++;
}

if(count == 0) {
count++;
dq.removeLast();
}

int i=d;

while(i&lt;n)
{
if(dq.getFirst() == &#39;1&#39;) count--;
dq.removeFirst();

if(s.charAt(i) == &#39;1&#39;) count++;

if(count == 0)
{
dq.removeLast();
count++;
}
i++;
}

}
``````

# 答案3

``````public static int minimumMoves(String s, int d) {
int n = s.length();
int[] count = new int[n+1];
int res = 0;
for (int i = 1; i <= d; i++) {
if (s.charAt(i-1) == '1') count[i] = count[i-1] + 1;
else count[i] = count[i-1];
}

if (count[d] == 0) {
res++;
count[d] = 1;
}

for (int i = d+1; i <= n; i++) {
if (s.charAt(i-1) == '0') {
count[i] = count[i-1];
int ones = count[i] - count[i-d];
if (ones == 0) {
count[i] = count[i-1] + 1;
res++;
}
} else {
count[i] = count[i-1] + 1;
}
}

return res;
}
``````

You just need to use a sliding window and a count of 1s so far at each index. Use a sliding window of `d` and if you don't see any ones so far, update the last index of that window with `1` and increment the result.

Code below:

``````public static int minimumMoves(String s, int d) {
int n = s.length();
int[] count = new int[n+1];
int res = 0;
for ( int i = 1; i &lt;= d; i++ ) {
if ( s.charAt(i-1) == &#39;1&#39;) count[i] = count[i-1]+1;
else count[i] = count[i-1];
}
if ( count[d] == 0 ) {
res++;
count[d] = 1;
}
for ( int i = d+1; i &lt;= n; i++ ) {
if ( s.charAt(i-1) == &#39;0&#39; ) {
count[i] = count[i-1];
int ones = count[i] - count[i-d];
if ( ones == 0 ) {
count[i] = count[i-1] + 1;
res++;
}
} else {
count[i] = count[i-1] + 1;
}
}
return res;
}
``````

# 答案4

``````public static int minimumMoves(String s, int d) {
int result = 0;
int runLength = 0;
for(char c: s.toCharArray()) {
if (c == '0') {
runLength += 1;
if (runLength == d) { // 我们需要中断这个连续的零
result += 1;
runLength = 0;
}
} else {
runLength = 0;
}
}
return result;
}
``````

You just need to break ensure there is no run of `d` zeros.

``````public static int minimumMoves(String s, int d) {
int result = 0;
int runLength = 0;
for(char c: s.toCharArray()) {
if (c == &#39;0&#39;) {
runLength += 1;
if (runLength == d) { // we need to break this run
result += 1;
runLength = 0;
}
} else {
runLength = 0;
}
}
return result;
}
``````

# 答案5

``````public static int minimumMoves(String s, int d)
{
char[] a = s.toCharArray();

// 总可能的变化次数（不计尾部）
if(a.length < d)
return 0;
int t = (int) a.length / d;

// 总可能的变化次数（计尾部）
// int t = (int) Math.ceil((double) a.length / (double) d);

for(int i = 0; i < a.length; i++)
{
if(a[i] == '1')
{
t--;
// 计算下一个子字符串的起始索引
i = (i / d + 1) * d - 1;
}
}

return t;
}
``````

Thought of another implementation you can do for this by working from the maximum possible changes (assumes at start that all values are '0' in String), reduce it when it finds a '1' value, and then jump to the next substring start. This allows it to run in `O(n)` and `Ω(n/m)` (n = String length, m = Substring length).

``````  public static int minimumMoves(String s, int d)
{
char[] a = s.toCharArray();
//Total possible changes (not counting tail)
if(a.length &lt; d)
return 0;
int t = (int) a.length / d;
//Total possible changes (counting tail)
//int t = (int) Math.ceil((double) a.length / (double) d);
for(int i = 0; i &lt; a.length; i++)
{
if(a[i] == &#39;1&#39;)
{
t--;
//Calculate index for start of next substring
i = (i / d + 1) * d - 1;
}
}
return t;
}
``````

• 本文由 发表于 2020年7月30日 21:07:11
• 转载请务必保留本文链接：https://go.coder-hub.com/63173854.html
• algorithm
• arrays
• java
• string

go 53

go 54

go 55

go 51