题目描述:
LeetCode 753. Cracking the Safe
There is a box protected by a password. The password is n
digits, where each letter can be one of the first k
digits 0, 1, ..., k-1
.
You can keep inputting the password, the password will automatically be matched against the last n
digits entered.
For example, assuming the password is "345"
, I can open it when I type "012345"
, but I enter a total of 6 digits.
Please return any string of minimum length that is guaranteed to open the box after the entire string is inputted.
Example 1:
Input: n = 1, k = 2 Output: "01" Note: "10" will be accepted too.
Example 2:
Input: n = 2, k = 2 Output: "00110" Note: "01100", "10011", "11001" will be accepted too.
Note:
n
will be in the range[1, 4]
.k
will be in the range[1, 10]
.k^n
will be at most4096
.
题目大意:
一个密码锁,其预设密码为n位,当输入一个字符串的后n位与预设密码相同时即可开启。
假设密码的每一位数字范围为0 ~ k-1,求长度最小的输入密码串,使得密码锁一定可以开启。
解题思路:
构造答案
初始令输入密码串ans = '0' * (n - 1),visits记录输入串已经出现过的所有密码组合 从k - 1到0倒序枚举字符y,使得ans的后n位没有在visits中出现过 若找到这样的c,则将ans的后n位加入visits,并令ans += y
Python代码:
class Solution(object):
def crackSafe(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
ans = "0" * (n - 1)
visits = set()
for x in range(k ** n):
current = ans[-n+1:] if n > 1 else ''
for y in range(k - 1, -1, -1):
if current + str(y) not in visits:
visits.add(current + str(y))
ans += str(y)
break
return ans
上述解法的正确性我也不会证明,o(╯□╰)o,但是枚举了所有的测试用例,结果均正确
测试Python代码:
import collections
so = Solution()
for n in range(1, 5):
for k in range(1, 11):
if k ** n > 4096: continue
ans = so.crackSafe(n, k)
vset = set(ans[x : x + n] for x in range(len(ans) - n + 1))
print 'k =', k, ' n =', n
print len(ans), len(vset), sorted(collections.Counter(ans).items()), '\n'
本文链接:http://bookshadow.com/weblog/2017/12/24/leetcode-cracking-the-safe/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。
隔壁老汪 发布于 2018年1月16日 12:20 #
楼主的代码和 简介,我的是C++写的,用的是dfs,比你的长很多。。。惭愧。
我隐约感觉这个题目应该是某种数学里循环置换群,我用英语搜了很多资料,找不到。。。
Zhiming Qin 发布于 2018年7月20日 04:01 #
如果用图论来考虑这个问题:把每种可能的key想成一个顶点,那么任意一个顶点与其他的n-1个顶点连接。这个问题就变成图论里的货郎担问题。不确定。