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

huangapple go评论39阅读模式
英文:

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) {
            answer++;
            i += d;
        } else {
            i++;
        }
    }
    return answer;
}

希望这能帮助到您。

英文:

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();
        
        int i=0, answer = 0;
        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) {
                answer++;
                i += d;
            }
            else i++;
        }
        return answer;
}

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

答案1

得分: 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

得分: 0

我使用滑动窗口技巧和双端队列来解决这个问题。这是我的已接受解决方案:

public static int minimumMoves(String s, int d) {
    int n = s.length();
    Deque<Character> dq = new LinkedList<>();
    int count = 0, answer = 0;
    
    for(int i=0; i<d; i++)
    {
        if(s.charAt(i) == '1') count++;
        dq.addLast(s.charAt(i));
    }
    
    if(count == 0) {
        answer++;
        count++;
        dq.removeLast();
        dq.addLast('1');
    }
    
    int i=d;
    
    while(i<n)
    {
        if(dq.getFirst() == '1') count--;
        dq.removeFirst();
        
        if(s.charAt(i) == '1') count++;
        dq.addLast(s.charAt(i));
        
        if(count == 0)
        {
            answer++;
            dq.removeLast();
            dq.addLast('1');
            count++;
        }
        i++;
    }
    
    return answer;
    
}
英文:

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();
    Deque&lt;Character&gt; dq = new LinkedList&lt;&gt;();
    int count = 0, answer = 0;
    
    for(int i=0; i&lt;d; i++)
    {
        if(s.charAt(i) == &#39;1&#39;) count++;
        dq.addLast(s.charAt(i));
    }
    
    if(count == 0) {
        answer++;
        count++;
        dq.removeLast();
        dq.addLast(&#39;1&#39;);
    }
    
    int i=d;
    
    while(i&lt;n)
    {
        if(dq.getFirst() == &#39;1&#39;) count--;
        dq.removeFirst();
        
        if(s.charAt(i) == &#39;1&#39;) count++;
        dq.addLast(s.charAt(i));
        
        if(count == 0)
        {
            answer++;
            dq.removeLast();
            dq.addLast(&#39;1&#39;);
            count++;
        }
        i++;
    }
    
    return answer;
    
}

答案3

得分: 0

你只需要使用一个滑动窗口和每个索引处到目前为止的1的计数。使用一个大小为 d 的滑动窗口,如果你在窗口中没有看到任何1,就将该窗口的最后一个索引更新为 1 并增加结果。

以下是代码:

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

得分: 0

您只需确保没有连续的d个零。

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

得分: 0

以下是翻译好的代码部分:

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;
}

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

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定