面试中翻车的一道题 求教

hello_world_AI 发表于 2020-12-24 22:09
含7的数字：
1. 个位数出现： 7,17,27,37,...,107,117,...
2. 十位数出现：70,71,72,7 ...

直接这么搜的话和brute force差不多吧

backtouzhaogong 发表于 2020-12-24 22:13
how about delete 7 from your dictionary? like, pretending it does not exist.
T ...

make sense，感觉也是个好办法

python得话 列表推导式建一个list  然后两个list 求差集不就好了?
差集（set_1 - set_2，或set_1.difference(set_2)）运算与更新为差集（set_1.difference_uptate(set_2)）运算的时间复杂度并不相同：前者是将在set_1中，但不在set_2中的元素添加到新的集合中，因此时间复杂度为O(len(set_1))。
后者是将在set_2中的元素从set_1中移除，因此时间复杂度为O(len(set_2))。

可不可以这样：第一遍删去所有最低位是7的数字，从7开始，每次index加9（删去之后）将17，27，...，4997都删掉；第二遍删去所有次低位是7的数字，从70开始删去9个数（77已经删去了），index加81（相当于9进制），将170-179，270-279，...，4970-4979删掉；第三遍删去百位是7的数字，从700开始删去81个数……以此类推，这样只需要访问每个需要被删的数字一次。

补充内容 (2020-12-25 02:58):
如果有O(1)的general方法从index i 开始删去m个连续数字，那么总的复杂的远低于O(N)

按照楼上有人说的，一个for循环搞定，时间复杂度O(n)。
因为最大到5000，我们只需要判断个位，十位，百位是不是7就好了
for i in range(1, 5001):
    if i%10 != 7 and (i//10)%10 != 7 and (i//100)%10 != 7: #分别判断个位、十位、百位。 O(1).
           add i to the result
return result
update:
刚才的回复没有看清楼主的意思，上面的复杂度还是O(n * average length of all numbers)。
下面提供个更优化的解法，利用while loop。
i = 1
while i <= n:
    factor = 1
    if i % 10 == 7: #个位是7，只加1
        i += 1
    elif (i//10) % 10 == 7: #十位是7，可以加10，跳过10个数字
        i += 10
    elif (i//100) % 10 == 7: #百位是7，加100，跳过100个数字
        i += 100
    else:
        add i to the result
        i += 1
return result

写一个function check int a，while a！= 0 if a%10 == 7 return false； break ；a//=10
然后 遍历一遍list。不知道时间复杂度是不是O（n）这个可以嘛

1. import time
   
2. def filter1(n):
   
3.         res = []
   
4.         count = 0
   
5.         start = time.time()
   
6.         for i in range(1, n+1):
   
7.                 j = i
   
8.                 while j>0:
   
9.                         count += 1
   
10.                         if j%10 == 7:
    
11.                                 break
    
12.                         j //= 10
    
13.                 else:
    
14.                         res.append(i)
    
15.         return res, count, time.time()-start
    
16. 
    
17. def filter2(n):
    
18.         res = [0]
    
19.         digit = 1
    
20.         count = 0
    
21.         start = time.time()
    
22.         while True:
    
23.                 temp = []
    
24.                 for i in [1,2,3,4,5,6,8,9]:
    
25.                         for j in res:
    
26.                                 num = i*digit + j
    
27.                                 count += 1
    
28.                                 if num > n:
    
29.                                         return res[1:] + temp, count, time.time()-start
    
30.                                 temp.append(num)
    
31.                 res += temp
    
32.                 digit *= 10
    
33. 
    
34. test_n = 5000
    
35. res1, count1, time1 = filter1(test_n)
    
36. res2, count2, time2 = filter2(test_n)
    
37. print(res1 == res2)
    
38. print(count1, time1)
    
39. print(count2, time2)
    

复制代码

第一种方法是O(N * average len of numbers)， 第二种方法是O(N)的。中间插入了一些count, time之类的是为了直观的比较一下二者的计算复杂度的区别。根据测试，如果n=5000的话，第一种方法大概要计算16000次，第二种方法只用计算3600次。
思路的话前面的答主都说了，就是假装7这个数字不存在，然后from bottom to up生成所有的数。
具体为什么这两种方法会有差异，前者是从1到N生成数字，然后对于每个数字都要花O(len of number)的复杂度去验证是否满足要求。后者是假装7不存在去生成数字，每个生成出来的数字肯定不存在7，所以不用检验，所以复杂度只有O(N)

你好！
不好意思，看了你这道题，我第一时间想到的是，把数字转换成字符，然后判断一下是否含有7，然后再输出没有7的，转换成数字。所以写出来的是这样的。我用python运行出来好像没问题，不知道对不对？谢谢。

import re
def delete_seven(x):
    ls=[]
    for item in x:
        item=str(item)
        if bool(re.search("7",item))==False:
            item=int(item)
            ls.append(item)   
    return ls
        
delete_seven(range(1,5000,1))

1. return [ i for i in range(5000) if '7' not in str(i) ]

复制代码