时间戳

首页 > 解决方案 > 给定一个由 0 和 1 组成的圆形字符串，求最小编号。将所有 1 放在一起的相邻掉期

string - 给定一个由 0 和 1 组成的圆形字符串，求最小编号。将所有 1 放在一起的相邻掉期

问题描述

如果给定一个循环（意味着您可以用 sizeOfString-1 交换 0）字符串 1 和 0，那么显示将所有 1 组合在一起所需的相邻交换的最小数量的好算法是什么。1 不需要在字符串中的任何特定位置分组。他们只需要在任何提供最小数量的相邻交换的地方分组。

例如，如果字符串看起来像这样......

011010110001

相邻交换的最小数量为 6，因为您将执行以下交换：

交换索引 0 和 11，得到：111010110000

交换索引 3 和 4，得到：111100110000

交换索引 5 和 6，得到：111101010000

交换索引 4 和 5，得到：111110010000

交换索引 6 和 7，得到：111110100000

交换索引 5 和 6，得到：111111000000

任何人都有一个很好的算法来找到任何 1 和 0 字符串的最小相邻交换数？

标签： stringalgorithmsorting

解决方案

找到一个好的起点，将所有具有相同价值的东西移向该集群。

注意：Python 有点生疏，没有设置为在 atm 测试它（现在通常与 Ruby 一起使用），但应该非常接近有效的 python，如果不是有效的。

def longest_cluster_ending_indexes(array)
  # Scan the array to find the end index of the longest cluster of the same value
  index = 0
  check = array[start]
  best_index = 0
  most_count = 1
  count = 1
  for item in array[1:-1]:
    index += 1
    if item == check:
      count += 1
      if count > most_count:
        best_index = index
        most_count = count
      else:
        check = item
        count = 1
   return (best_index - most_count, best_index)

last_seen_left,last_seen_right = longest_cluster_ending_index(array)
check = array[last_seen_right]
index_left = start_left = last_seen_left
index_right = start_right = last_seen_right
swaps = 0
while true:
  index_left -= 1
  if array[index_left] == check
    diff = (index_left - last_seen_left) - 1
    swaps += diff
    last_seen_left -= 1

  if array[index_right] == check
    diff = (index_right - last_seen_right) - 1
    swaps += diff
    last_seen_right += 1

  break if index_left % len(array) == start_right # Went around the array
  break if index_right % len(array) == start_left # Went around the array

我们想找到一个最长的运行，并在运行结束时开始。这可以防止出现以下情况：10000000000000011101如果您从 index 开始，就会给出不正确的结果0。相反，最好从大组零中的最后一个 0 开始。在这种情况下，您只需要在下一个零上进行一次交换即可将其向后移动。

性能是O(N)，其中N是 1 和 0 的总数。

例子： 111000111000

在这里，我们有 4 次相同大小的运行。算法应确定索引 2 是最佳起点（第一组的结尾）。它将扫描，找到第二组并将它们一个接一个地移动。掉期为 3 + 3 + 3 = 9。

111100011000 3 swaps. index 7 - index 3 - 1 = 3 swaps (right side)
111110001000 3 swaps. index 8 - index 4 - 1 = 3 swaps (right side)
111111000000 3 swaps. index 9 - index 5 - 1 = 3 swaps (right side)

11101100001
11101100001 # Second to last is starting index
11111000001 # index 3 and index 6, cost is 2 swaps (from the left side)

嗯，这提出了一个很好的观点，必须调整算法以从最佳集群进行双向搜索（而不是仅仅向右），虽然现在它确实做了大约 2 倍的严格需要的工作（它可能会在中途结束阵列的另一侧，循环）。

01001001100 => left start = 2 (moving left), right start = 3 (moving right)
10000101100 => Swap left and right (cost = 1 + 1 = 2 swaps)
00000011101 => Swap left and right (cost = 1 + 1 = 2 swaps)
00000011110 => One more swap
So 5 swaps.

011010110001 => Left start at 8, right start and the last index
111011100000 => 2 swaps and 1 swap = 3 swaps
011111100000 => 3 swaps
6 swaps

推荐阅读