Python 程序重新排列字符串,使所有相同字符相距 d 距离

pythonserver side programmingprogramming更新于 2025/8/19 16:12:17

给定一个非空字符串 str 和一个整数 k,重新排列字符串,使相同字符彼此之间的距离至少为 k。

所有输入字符串均以小写字母给出。如果无法重新排列字符串,则返回一个空字符串""。

示例 1:

str = “tutorialspoint”, k = 3

答案:"tiotiotalnprsu"

相同字符之间至少相隔 3 个字符。

str = "aabbcc", k = 3

答案:"abcabc"

相同字符之间至少相隔 3 个字符。

示例 2

str = "aaabc", k = 3

答案:""

无法重新排列字符串。

示例 3:

str = "aaadbbcc", k = 2

答案:"abacabcd"

另一个可能的答案是:"abcabcda"

相同字符之间至少相隔 2 个字符。

示例

MAX = 128

# 用于存储字符 'char' 及其频率 'freq' 的结构
# 在输入字符串中
class charFreq(object):
   def __init__(self,char,freq):
      self.c = char
      self.f = freq

# 用于交换两个 charFreq 项的实用函数。
def swap(x, y):
   return y, x

# 实用函数
def toList(string):
   t = []
   for x in string:
      t.append(x)

   return t

# 实用函数
def toString(l):
   return ''.join(l)

# 实用函数,用于对存储在 freq[] 中的堆的节点 freq[i] 进行 maxheapify
def maxHeapify(freq, i, heap_size):
   l = i*2 + 1
   r = i*2 + 2
   largest = i
   if l < heap_size and freq[l].f > freq[i].f:
      largest = l
   如果 r < heap_size 和 freq[r].f > freq[largest].f:
      largest = r
   如果 largest != i:
      freq[i], freq[largest] = swap(freq[i], freq[largest])
      maxHeapify(freq, largest, heap_size)

# 一个实用函数,用于将数组 freq[] 转换为最大堆
def buildHeap(freq, n):
   i = (n - 1)//2
   while i >= 0:
      maxHeapify(freq, i, n)
      i-=1

# 一个实用函数,用于从最大堆中删除最大项或根
def extractMax(freq, heap_size):
   root = freq[0]
   if heap_size > 1:
      freq[0] = freq[heap_size-1]
      maxHeapify(freq, 0, heap_size-1)

return root

# 重新排列输入字符串"str"的主要函数,以便
# 两个相同的字符相距 d 距离
def rearrange(string, d):
   # 查找输入字符串的长度
   n = len(string)

   # 创建一个数组来存储 str[] 中的所有字符及其
   # 频率
   freq = []
   for x in range(MAX):
      freq.append(charFreq(0,0))

   m = 0

   # 遍历输入字符串并将所有
   # 字符的频率存储在 freq[] 数组中。
   for i in range(n):
      x = ord(string[i])

      # 如果此字符第一次出现,则增加 m
      if freq[x].c == 0:
         freq[x].c = chr(x)
         m+=1

      freq[x].f+=1
      string[i] = '\0'

   # 构建所有字符的最大堆
   buildHeap(freq, MAX)

   # 现在逐个从最大堆中提取所有不同的字符
   # 并将它们放回到 str[] 中,距离限制为 d
   for i in range(m):
      x = extractMax(freq, MAX-i)

      # 查找 str[] 中的第一个可用位置
      p = i
      while string[p] != '\0':
         p+=1

      # 在 p、p+d、p+2d、.. p+(f-1)d 处填充 x.c
      for k in range(x.f):

         # 如果索引超出大小,则字符串无法
         # 重新排列。
         if p + d*k >= n:
            print ("无法重新排列字符串。")
         return

      string[p + d*k] = x.c

   return toString(string)

string = "tutorialspoint"
print (rearrange(toList(string), 3) )

结果

tiotiotalnprsu

相关文章


有用资源