Python程序：构建没有两个相邻数字相同的最小数字

假设我们有一个字符串 s，其中包含四个可能的字符“1”，“2”，“3”和“？”。我们可以将“1”，“2”和“3”中的任意一个放置在“？”的位置。我们需要找到可以构建的最小可能的数字，使得没有两个相邻的数字相同。

因此，如果输入类似于 s = "2??3?"，则输出将为 21231

为了解决这个问题，我们将遵循以下步骤：

  • i := 0
  • s := s 中元素的列表
  • 如果 s 的大小 < 2，则
    • 如果 s[i] 等于 "？"，则
      • 返回 "1"
  • 当 i < s 的大小 时，执行以下操作：
    • 如果 s[i] 等于 "？"，则
      • 如果 i 等于 0，则
        • 当 s[i + 1] 不等于 "1" 时，s[i] := "1"，否则 s[i] := "2"
      • 否则，当 i > 0 且 i <= s 的大小 - 2 时，
        • 如果 s[i - 1] 等于 "1"，则
          • 如果 s[i + 1] 等于 "2"，则
            • s[i] := "3"
          • 否则，
            • s[i] := "2"
        • 否则，当 s[i - 1] 等于 "2" 时，
          • 如果 s[i + 1] 等于 "2"，则
            • s[i] := "3"
          • 否则，
            • s[i] := "1"
        • 否则，当 s[i - 1] 等于 "3" 时，
          • 如果 s[i + 1] 等于 "2"，则
            • s[i] := "2"
          • 否则，
            • s[i] := "1"
      • 否则，
        • 当 s[i - 1] 不等于 "1" 时，s[i] := "1"，否则 s[i] := "2"
    • i := i + 1
  • 将 s 中的项连接成字符串并返回

示例

让我们看看以下实现以更好地理解：

def solve(s):
   i = 0
   s = list(s)
   if len(s) < 2:
      if s[i] == "?":
         return "1"
   while i < len(s):
      if s[i] == "?":
         if i == 0:
            s[i] = "1" if s[i + 1] != "1" else "2"
         elif i > 0 and i <= len(s) - 2:
            if s[i - 1] == "1":
               if s[i + 1] == "2":
                  s[i] = "3"
               else:
                  s[i] = "2"
            elif s[i - 1] == "2":
               if s[i + 1] == "1":
                  s[i] = "3"
               else:
                  s[i] = "1"
            elif s[i - 1] == "3":
               if s[i + 1] == "1":
                  s[i] = "2"
               else:
                  s[i] = "1"
         else:
            s[i] = "1" if s[i - 1] != "1" else "2"
      i += 1
   return "".join(s)

s = "2??3?"
print(solve(s))

输入

"2??3?"

输出

21231

更新于: 2021年10月14日

281 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告