【LeetCode 算法笔记】164. 破解闯关密码

问题描述

问题来源

闯关游戏需要破解一组密码，闯关组给出的有关密码的线索是：

• 一个拥有密码所有元素的非负整数数组 password
• 密码是 password 中所有元素拼接后得到的最小的一个数

请编写一个程序返回这个密码。

示例 1:
输入: password = [15, 8, 7]
输出: “1578”

示例 2:
输入: password = [0, 3, 30, 34, 5, 9]
输出: “03033459”

提示:
0 < password.length <= 100

说明:
输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

冒泡排序

本质上是给数组进行排序。定义好比较规则后，选择一种排序算法实现即可，这里实现了冒泡排序。
假设 $x$、$y$ 是数组 $nums$ 中的两个元素。则排序的判断规则如下所示：

• 如果拼接字符串 $x+y>y+x$，则 $x$ 大于 $y$，$y$ 应该排在 $x$ 前面，从而使拼接起来的数字尽可能的小。
• 反之，如果拼接字符串 $x+y<y+x$，则 $x$ 小于 $y$，$x$ 应该排在 $y$ 前面，从而使拼接起来的数字尽可能的小。

class Solution:def crackPassword(self, password: List[int]) -> str:n = len(password)str_password = list(map(str, password))for i in range(n-1,0,-1):for j in range(i):if str_password[j] + str_password[j+1] > str_password[j+1] + str_password[j]:str_password[j], str_password[j+1] = str_password[j+1], str_password[j]return ''.join(str_password)

冒泡排序的时间复杂度：$O(N^2)$
这里为了转化为字符串数组开辟了新的空间（一般情况下，标准的冒泡排序不需要额外空间），所以空间复杂度： $O(N)$

参考文献：
[1] 算法通关手册