深色模式
LCR 164-破解闯关密码
题目参考： LCR 164-破解闯关密码
题目描述
闯关游戏需要破解一组密码，闯关组给出的有关密码的线索是：
一个拥有密码所有元素的非负整数数组 password
密码是 password 中所有元素拼接后得到的最小的一个数
请编写一个程序返回这个密码。示例 1:
输入: password = [15, 8, 7]
输出: "1578"示例 2:
输入: password = [0, 3, 30, 34, 5, 9]
输出: "03033459"提示:
0 < password.length <= 100说明:
输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0题目分析
题目中密码是最小的字符串，大体操作则需要将数组中最小的数字字符排到前面就行，得出结果。思路正确，实际真的这么简单吗？
当你以为这道题目只是简单字符串比较问题，你就调入陷阱里面去了。比如示例二中的 3 和 30 比较，字符串比较肯定是 330, 实际上正确答案是 303, 因此当两个字符串长度不相等時，还要比较后续内容，这就复杂了，举个例子
py
a = 323 323 323 4
b = 323 333 323
c = 323如果 c 跟 a 进行比较，需要比较 4 轮，c 需要跟 a 中的 323, 323, 323, 4 进行比较， 在第 4 轮比较中，分出结果
如果 c 跟 b 进行比较，只需要比较两轮就能分出结果，分别是 a 跟 323, 333 进行比较，得出结果
这道题目中排序思路没有问题，可以使用 选择排序 处理，每次都从剩余列表中选出最小的数据放到相应的位置。问题的关键是比较两个数字所代表的字符串的大小。
排序代码如下，没有特别的地方
py
class Solution(object):
def crackPassword(self, password):
"""
:type password: List[int]
:rtype: str
"""
length = len(password)
for i in range(length):
p = i
str1 = str(password[i])
for j in range(i+1, length):
str2 = str(password[j])
if self.isLessThan(str2, str1):
p = j
str1 = str2
if p != i:
password[i], password[p] = password[p], password[i]
return ''.join([str(x) for x in password])下面是比较算法，循环比较，知道分出结果
- 每一轮比较中选取相同位数进行比较，这里取两个字符串长度最小值 minlen, 如果能分出结果，则返回
- 如果两个字符串不剩余字符串，则已经分出结果，两个字符串相等
- 如果两个字符串长度不等，则将短的字符串和唱的剩余字符串进行比较，直到分出结果
py
def isLessThan(self, str1, str2):
len1 = len(str1)
len2 = len(str2)
minlen = min(len1, len2)
for i in range(minlen):
if str1[i] != str2[i]:
return str1[i] < str2[i]
if len1 == len2:
return False
if len1 <len2:
return self.isLessThan(str1, str2[minlen:])
return self.isLessThan(str1[minlen:], str2)复杂度分析：
- 时间复杂度：
- 空间复杂度：
比较算法复杂度
- 时间复杂度：
- 空间复杂度：
优化方案
参考Leetcode题解: 官方题解
核心思想是： 如果两个字符串 x, y, 需要分出排序结果，最终只有两种可能 xy 和 yx，因此只需要将字符串比较转化为比较 xy 和 yx 即可。
py
def isLessThan(self, str1, str2):
return str1 + str2 < str2 + str1非常佩服这种方案，比我的那个方案简介太多，比较算法复杂度分析：
- 时间复杂度
- 空间复杂度：