骨骼 滇缅

刚刚结束的店面，面试官是美国小姐姐，超过了时间感觉最后她已经明显不耐烦了。。。
题目是给你个N（她给的是6

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ng>
补充一下，这道题就是里扣而司发，只有0 1 6 8 9 是能够混淆的数字

贴一下我的代码 基本完全套用 247 击败 70%

1. def strobogrammaticInRange(self, low, high):
   
2.         """
   
3.         :type low: str
   
4.         :type high: str
   
5.         :rtype: int
   
6.         """
   
7.         
   
8.         self.low, self.high = int(low), int(high)
   
9.         start, end = len(low), len(high)
   
10.         count = 0
    
11.         for i in range(start, end + 1):
    
12.             count += self.find_strong_grammactic(i, {})
    
13.         
    
14.         return count
    
15.    
    
16.     def find_strong_grammactic(self, n, memo):
    
17.         graph = {'0': '0', '1':'1', '6': '9', '8': '8', '9': '6'}
    
18.         count, arr = 0, self.find_S(n, graph, memo)
    
19.         for n in arr:
    
20.             if (n == "0" or n[0] != "0") and self.low <= int(n) <= self.high:
    
21.                 count += 1
    
22.         
    
23.         return count   
    
24.         
    
25.     def find_S(self, n, graph, memo):
    
26.         if n == 0:
    
27.             return []
    
28.         if n == 1:
    
29.             return ["0", "1", "8"]
    
30.         if n == 2:
    
31.             return ["00", "11", "88", "69", "96"]
    
32.         if n > 2:
    
33.             base = self.find_S(n - 2, graph, memo)
    
34.         
    
35.         res = self.get_all_combinations(base, graph)
    
36.         memo[n] = res
    
37.         return res
    
38.    
    
39.     def get_all_combinations(self, base, graph):
    
40.         res = []
    
41.         for a, b in graph.items():
    
42.             for st in base:
    
43.                 res.append(a + st + b)
    
44.         return res

复制代码

Alice_koi 发表于 2018-10-24 15:16
是输出不是剪掉，最后输出的是会被误判的数字

明白，那应该可以用DFS做，而且比248要简单一些，枚举各个位置上的数再判断就好……
那么复杂度应该是 5^(log10(N))=N^(log10(5))=N^0.7 这样？不知道面试官会不会接受这样的答案

LaSeineFirenze 发表于 2018-10-24 16:27
明白，那应该可以用DFS做，而且比248要简单一些，枚举各个位置上的数再判断就好……
那么复杂度应该是 5 ...

请问下那这道题目是不是就变成了求0，1，6，8，9的permutation呀？但是要在给定的0 到 N的范围内

谢谢分享！同求加米，很多看不了

609算不会看错的？

来自一亩三分地官方APP

LC二寺巴

LC二寺巴 zszszszs

儿四爸是要求倒过看一样的吧？大家有没有好的解法

比如659这样的，倒过来是看错还是不看错呢

0-9中 0，1，2，5，6，8，9是upside down后有效的数字，3，4，7是upside down后无效的数字，是不是可以理解为一个不含3，4，7的数字就是可以被看错的数字

补充内容 (2018-10-15 08:19):
还得去掉像69种倒过来看还是69的数字？

安晴晴 发表于 2018-10-15 06:22
儿四爸是要求倒过看一样的吧？大家有没有好的解法

248 不应该因为4不会混淆，只有0 1 6 8 9 是倒过来会被混淆的数字

EuniceYLiu 发表于 2018-10-15 08:17
0-9中 0，1，2，5，6，8，9是upside down后有效的数字，3，4，7是upside down后无效的数字，是不是可以理解 ...

我当时问过面试官，只有0 1 6 8 9 是会被混淆的