java - 更改数组中的位

Question

我有一个位数组。位将根据以下标准打开和关闭:1. 如果 bit 的左位和右位为 1，否则为 0。2. 边界条件(最左边和最右边的位只取决于一位。即要么在它的左边，要么在它的右边。

此数组将根据以下条件处理 m 次。

我写了下面的代码，其中 A 是原始数组，subsiquent 是要处理的数组。但这会给我 O(nm)，其中 n 是长度，m 是我想要执行该过程的次数。请建议我一些替代解决方案，以便我可以降低我的复杂性。

for(int k = 0;k < m;k++){
  for(int l = 0;l < n;k++){
    if(l == 0){
      if(A[l+1]==1)
        subsiquent[l]=1;
      else
        subsiquent[l]=0;
      //** is there a } missing here?
      else if(l==n){
        if(A[l-1]==1)
          subsiquent[l]=1;
        else
          subsiquent[l]=0;                        
      } else {
        if(A[l+1]==1 && A[l-1]==1 ){
          subsiquent[l]=1;
        }else{
          subsiquent[l]=0;
        }
      } 
    //** or is there a } missing here?      
  }

  A = subsiquent;
}

Answer 1

一些要看的东西:

• 如果你的 last p first 或 p last bits 为 0，它们将始终保持为 0，bit p+1 (resp. p-1) 也将始终为 0。因此，您可以对此添加检查，并减少 l 循环的开始/结束(并将 p+1 数字更改为 0)
• 同理，如果第p位(和最后p位)为1，则p-1位为1，第p位为0
• 如果你有全 0 或全 1，则不需要再更改
• 可以在你的数组中间做同样的事情(中间有5个零？下次会有7个。五个1？中间的三个会保持1)，但不确定是否容易整合(只有当你说 1000 个相同的位是否值得我认为处理它)
• 如果你不以全 0 或全 1 结束，你将交替出现 0 和 1。因此你还可以检查你是否交替出现 0 和 1，并且对剩余的 m 取模 2，你可以预测结果

编辑:当然在我的四肢示例中使用 p>=2

编辑:您可以将数组表示为 int 数组中相似位数的数量 + 记住第一位000111101100110101 将表示为 [0]3412221111(从零开始，然后是 3 个零，然后是 4 个一，然后是 1 个零，然后是 2 个一，等等)

我没有检查全部，但您可以推断出规则，只需最少的步骤就可以很容易地从一个步骤转到另一个步骤。 (有很多情况，我让你找。你只需要从左往右走，记住你是从0和1切换，但是迭代的时候可能要修改/减少右边的数字，或者插入数字。链接列表将非常适合这里)

例如，步骤将是:

000111101100110101  [0]3-4-1-2-2-2-1-1-1-1      
000011010000001010  [0]4-2-1-1-6-1-1-1-1
000000100000000101  [0]6-1-8-1-1-1
000000000000000010  [0]16-1-1
000000000000000001  [0]17-1
000000000000000000  [0]18