骨骼 滇缅

wangyxwyx 发表于 2018-10-13 06:08
LC二寺巴 zszszszs

对对对，就是这个题，Thanks

那是不是可以先构造出0到N之间只由0,1,6,9,8构成的数字，再判断每个数是不是回文的，就像贰肆捌要求的那样， 把这些数减掉就好了？
感觉当场写这个DFS有点难欸……

LaSeineFirenze 发表于 2018-10-24 15:09
那是不是可以先构造出0到N之间只由0,1,6,9,8构成的数字，再判断每个数是不是回文的，就像贰肆捌要求的那样 ...

是输出不是剪掉，最后输出的是会被误判的数字

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

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

和儿丝吧不一样。6倒过来是9，符合这题要求，不符合儿丝吧

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

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

现在电面都考hard题了吗 = =

youtube一个老师讲解的视频  那个老师还让大家不用太准备这道题，说面试一般不会出现， 楼主的运气真的不大好。。

想问一下楼主 面试官是直接问你248的吗。
还是说先做了247 再做的248
248在247的基础上比较简单。
求一个permutation 然后去掉不在range内的数。

贴一下我的代码 基本完全套用 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

复制代码