如何在字符串中找到1s和0s的最大交替子序列 [英] How to find largest alternating subsequence of 1s and 0s in a string

问题描述

在仅包含1s和0s的字符串中查找最大的交替1和0子序列。然后找到最大子序列的起始索引



1101011最长交替的示例从索引1到5的子序列长度是5。



我尝试过：



尝试通过比较连续元素并且如果它们不相等来检查当前长度与最大尺寸

Find largest alternating 1s and 0s subsequence in a string containing only 1s and 0s.also find the starting index for the largest subsequence

Example for 1101011 rhe longest alternating subsequence length is 5 from index 1 to 5.

What I have tried:

Tried doing it by comparing consecutive elements and if they are not equal checking current length with max size

int findSubArray(int arr[], int n) 
{
int sum = 0;
int maxsize = -1, startindex = 0;
int endindex = 0;

int j = 0;
for (int i = 0; i < n - 1; i++) 
{
    if (arr[i] != arr[i+1] && maxsize < i - j + 1) 
    {
        maxsize = i - j + 1;
        startindex = j;
    } else {
        j = i;
    }
}

endindex = startindex+maxsize-1;
if (maxsize == -1)
    System.out.println("No such subarray");
else
    System.out.println(startindex+" to "+endindex);

return maxsize;
}

int [] ia = {1,1,0,1,0,1,1}

findSubArray（ia，7）;

返回：5并打印0到4



问题是虽然这打印正确的长度，即5，索引不正确。理想的输出应该是1到5.



为了纠正这个问题，如果我做j = i + 1，那么整个匹配就可以进行折腾，我得到了索引为0到0.



上述代码中的错误是什么？另外，替代方法的任何伪代码都有帮助吗？

int [] ia = {1, 1, 0, 1, 0, 1, 1}
findSubArray (ia, 7);
Returns: 5 and prints 0 to 4

The problem is that although this prints the length correctly which is 5, the indexes are incorrect. Ideal output should be 1 to 5.

To rectify this, if I do j = i + 1, then the whole matching goes for a toss and I get the indexes as 0 to 0.

What is the mistake in the above code? Also, any pseudocode for alternative approach would help?

推荐答案

我会写：

I would write:

static int findSubArray(int arr[])
{
  int max_size = -1, start_index = 0;
  int end_index = 0;
  int start_sequence=0;
  boolean in_sequence = false;

  int n = arr.length;

  for (int i = 0; i < n - 1; i++)
  {
    if ( in_sequence )
    {
      if ( arr[i] == arr[i+1])
      {
        in_sequence = false;
        if ( i - start_sequence >= max_size)
        {
          max_size = i -start_sequence + 1;
          start_index = start_sequence;
        }
      }
    }
    else
    {
      if ( arr[i] != arr[i+1] )
      {
        in_sequence = true;
        start_sequence = i;
      }
    }
  }
  if ( in_sequence )
  {
    if ( n - start_sequence > max_size)
    {
      max_size = n -start_sequence;
      start_index = start_sequence;
    }
  }

  end_index = start_index + max_size - 1;
  if (max_size == -1)
    System.out.println("No such subarray");
  else
    System.out.println(start_index + " to " + end_index);

  return max_size;
}

当你不理解你的代码在做什么时，答案是调试器。

这一行看起来很可疑

When you don't understand what you code is doing, the answer is debugger.
this line look suspicious

if (arr[i] != arr[i+1] && maxsize < i - j + 1)

它无法正确查找第二个序列in：

it prevent from finding the second sequence correctly in:

int [] ia = {1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1}

有一个工具可以让你看到你的代码在做什么，它的名字是调试器。它也是一个很好的学习工具，因为它向你展示了现实，你可以看到哪种期望与现实相符。

当你不明白你的代码在做什么或为什么它做它做的时候，答案就是答案是调试器。

使用调试器查看代码正在执行的操作。只需设置断点并查看代码执行情况，调试器允许您逐行执行第1行并在执行时检查变量。



调试器 - 维基百科，免费的百科全书 [ ^ ]



掌握Visual Studio 2010中的调试 - 初学者指南 [ ^ ]

使用Visual Studio 2010进行基本调试 - YouTube [ ^ ]

HTTP：//docs.or acle.com/javase/7/docs/technotes/tools/windows/jdb.html [ ^ ]

https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html [ ^ ]

调试器在这里向您展示您的代码正在做什么，您的任务是与它应该做什么进行比较。

调试器中没有魔法，它没有发现错误，它只是帮助你到。当代码没有达到预期的效果时，你就会接近一个错误。

There is a tool that allow you to see what your code is doing, its name is debugger. It is also a great learning tool because it show you reality and you can see which expectation match reality.
When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]
http://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html[^]
https://www.jetbrains.com/idea/help/debugging-your-first-java-application.html[^]
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.

这篇关于如何在字符串中找到1s和0s的最大交替子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！