鱼C论坛

 找回密码
 立即注册
查看: 3169|回复: 26

[已解决]Python:每日一题 155(高额悬赏)

[复制链接]
发表于 2018-3-4 08:11:17 | 显示全部楼层 |阅读模式
20鱼币
题目:一个无序数组里有99个不重复正整数,范围从1到100,唯独缺少一个整数。如何找出这个缺失的整数?
(太简单,无提示)


                               
登录/注册后可看大图


题目扩展:一个无序数组里有若干个正整数,范围从1到100,其中99个整数都出现了偶数次,只有一个整数出现了奇数次(比如1,1,2,2,3,3,4,5,5),如何找到这个出现奇数次的整数?
(异或算法)


                               
登录/注册后可看大图


题目第二次扩展:一个无序数组里有若干个正整数,范围从1到100,其中98个整数都出现了偶数次,只有两个整数出现了奇数次(比如1,1,2,2,3,4,5,5),如何找到这个出现奇数次的整数?
(分治法)


                               
登录/注册后可看大图

最佳答案
2018-3-4 08:11:18
xuzu = [1,2,3,4,5,6,7,8]
for i in range(1,101):
    if i in xuzu:
        print('true')
    else:
            print(i)

最佳答案

查看完整内容

xuzu = [1,2,3,4,5,6,7,8] for i in range(1,101): if i in xuzu: print('true') else: print(i)

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 08:11:18 | 显示全部楼层    本楼为最佳答案   
xuzu = [1,2,3,4,5,6,7,8]
for i in range(1,101):
    if i in xuzu:
        print('true')
    else:
            print(i)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 09:55:13 | 显示全部楼层
本帖最后由 溯影 于 2018-3-4 10:36 编辑
  1. #题目一:
  2. list1 = []
  3. list2 = [22,44,11,55]#99个元素无序的列表

  4. for i in range(1,101):
  5.         list1.append(i)#生成1到100的数

  6. for each in list1:
  7.         if each not in list2:
  8.                 print(each)
  9.                 break
  10. #######################
  11. #扩展1:
  12. list1 = [1,1,2,2,3,3,4,4,5,5,5,6,6,6,6]
  13. result = 0
  14. for i in list1:
  15.         result  = result ^ i#零异或任何数是零

  16. print(result)
  17. 结果:5

  18. ***Repl Closed***
  19. ##################
  20. #扩展2
  21. def find_odd(list1):
  22.         result = 0
  23.         for each in list1:
  24.                 result = result ^ each#对所有的数进行异或

  25.         cnt = 0
  26.         temp = result
  27.         while temp&1 == 0:#得到最低一位二进制中1的位置
  28.                 temp = temp >> 1
  29.                 cnt = cnt + 1

  30.         a = 0
  31.         for each in list1:
  32.                 if (each>>cnt)&1!=0:#根据cnt的值进行分组
  33.                         a = a^each

  34.         return a,result ^ a



  35. if __name__ == '__main__':
  36.         list1 = [1,2,2,1,3,4,5,5,5,5]
  37.         (result1,result2) = find_odd(list1)
  38.         print(result1,result2)
  39. #结果:
  40. 3 4

  41. ***Repl Closed***
复制代码

评分

参与人数 1鱼币 +6 收起 理由
新手·ing + 6

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 10:06:34 | 显示全部楼层
第一个
  1. import random as r
  2. def find(x):
  3.     set1=x.copy()
  4.     for i in range(1,101):
  5.         x.add(i)
  6.         if set1!=x:
  7.             return i
  8. x=set(range(1,101))
  9. x.remove(r.randint(1,100))
  10. print(find(x))
复制代码

第二个,算是异或法吗
  1. import random as r
  2. def find2(x):
  3.     A=sorted(x)
  4.     print(A)
  5.     while 1:
  6.         if len(A)==1:
  7.             return A[0]
  8.         a=A.pop()
  9.         b=A.pop()
  10.         if a!=b:
  11.             return a
  12. L=list(range(1,101))*2
  13. L.pop(r.randint(0,199))
  14. print(find2(L))
复制代码

第三个容我没想明白如何应用到分治法,,分治法也是百度才看到

评分

参与人数 1鱼币 +6 收起 理由
新手·ing + 6

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 10:43:53 | 显示全部楼层
  1. #1
  2. x = [1,2,3,5,6,7,8,9,10]
  3. for i in range(1,11):
  4.     if i in x:
  5.         continue
  6.     else:
  7.         print('1.',i)
  8. #2
  9. print('2.',end = ' ')
  10. y = [1,1,2,2,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10]
  11. for each in range(1,11):
  12.     i = 0
  13.     for num in y:
  14.         if num ^ each == 0:  #异或
  15.             i += 1
  16.     if i % 2 == 1:
  17.         print(each)
  18. #3
  19. print('3.',end = ' ')
  20. z = [1,1,2,2,3,3,3,4,4,5,5,6,6,6,6,7,8,8,9,9,10,10]
  21. for each in range(1,11):
  22.     i = 0
  23.     for num in z:
  24.         if num ^ each == 0:  #异或
  25.             i += 1
  26.     if i % 2 == 1:
  27.         print(each,end = ' ')
复制代码

运算结果:
  1. 1. 4
  2. 2. 3
  3. 3. 3 7
复制代码

分冶法我不知道是啥

评分

参与人数 1鱼币 +6 收起 理由
新手·ing + 6

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 11:15:41 | 显示全部楼层
纯属好奇,把第一问用了四种方式写了下并进行效率对比(在Jupyter Notebook中通过):
  1. %%capture time_results
  2. import random

  3. n = 10000
  4. popu = list(range(1, n + 1))
  5. samp = random.sample(popu, n - 1)


  6. def missing_1(samp, popu):
  7.     temp = popu.copy()
  8.     [temp.remove(s) for s in samp]
  9.     return temp[0]


  10. def missing_2(samp, popu):
  11.     d = dict.fromkeys(popu)
  12.     for s in samp:
  13.         d[s] = 1
  14.     for k, v in d.items():
  15.         if v is None:
  16.             return k


  17. def missing_3(samp, popu):
  18.     d = dict.fromkeys(popu)
  19.     for s in samp:
  20.         d.pop(s)
  21.     return list(d.keys())[0]


  22. def missing_4(samp, popu):
  23.     for each in popu:
  24.         if each not in samp:
  25.             return each


  26. funs = [missing_1, missing_2, missing_3, missing_4]
  27. for f in funs:
  28.     print(f(samp, popu))
  29.     %timeit f(samp, popu)
复制代码
  1. import re

  2. time_res = time_results.stdout
  3. time_lst = re.findall(r'\d*(?:\.\d+)? [m|u]s', time_res)
  4. print('\n'.join('%s: %s' % (f.__name__, t) for f, t in zip(funs, time_lst)))
复制代码

输出:
  1. missing_1: 378 ms
  2. missing_2: 1.15 ms
  3. missing_3: 1.86 ms
  4. missing_4: 495 ms
复制代码

说明散列表还是最快的.

评分

参与人数 1鱼币 +6 收起 理由
新手·ing + 6

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 11:58:47 | 显示全部楼层
本帖最后由 °蓝鲤歌蓝 于 2018-3-4 14:17 编辑

第一问:
  1. def Num1(list1):
  2.     sum1 = sum(range(101))
  3.     sum2 = sum(list1)
  4.     return sum1 - sum2
复制代码


第二问:
  1. def Num2(list2):
  2.     result  = 0
  3.     for each in list2:
  4.         result = result^each
  5.     return result
复制代码


第三问:
  1. def Num3(list3):
  2.     list3.sort()
  3.     for i in range(1, len(list3), 2):
  4.         if list3[i] != list3[i-1]:
  5.             result1 = list3[i-1]
  6.             k = i
  7.             break

  8.     result2 = 0
  9.     for each in list3[k:]:
  10.         result2 = result2^each

  11.     return [result1, result2]
复制代码

评分

参与人数 1鱼币 +6 收起 理由
新手·ing + 6

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 13:48:14 | 显示全部楼层

学到了= =
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 13:59:43 | 显示全部楼层
  1. print(a = {i for i in range(100)}-b)
复制代码

  1. import collections
  2. a = collections.Counter()
  3. b=[1,1,2,2,3,4,5,5]
  4. for i in b:
  5.     a[i] += 1
  6. for i in a.items():
  7.     if i[1] %2 != 0:
  8.         print(i[0])
复制代码

评分

参与人数 1鱼币 +6 收起 理由
新手·ing + 6

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 14:13:15 | 显示全部楼层

其实,Num2的sort()可以不用
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 14:16:47 | 显示全部楼层
本帖最后由 pillar 于 2018-3-4 14:17 编辑

def Daily_practice_155():
“第一问”
    list1 = list(range(1,101))
    list2 = list1.remove(66)
    for i in range(1,101):
        if i not in list1:
            print(i)
           
“第三问”
    list3 = list(range(1,101))
    list4 = list(range(1,101))
    list4.remove(100)
    list4.remove(8)
    list5 = list3+list4
    list6 = sorted(list5)
    print(list6)
    length = len(list6)
    print(list6[length-2])
    print(list6[length-1])
    for i in range(1,length-1):
#        print(list6)
        if list6[i-1] != list6 and list6[i+1] != list6:
            print(list6)
    if list6[0] != list6[1]:
        print(list6[0])
#        elif list6[length-2] != list6[length-1]:
#            print(list6[length-1])
    if list6[length-2] != list6[length-1]:
        print(list6[length-1])
            
Daily_practice_155()  
第二问可以可用跟第三问一样的方法写出来。

评分

参与人数 1鱼币 +6 收起 理由
新手·ing + 6

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 14:17:26 | 显示全部楼层
塔利班 发表于 2018-3-4 14:13
其实,Num2的sort()可以不用

是的,其实是想Num3的时候加错了的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 15:21:36 | 显示全部楼层
学习后改进如下,一就不发了,好的在别人那里
  1. def Num2(list2):
  2.     result  = 0
  3.     for each in list2:
  4.         result = result^each
  5.     return result
复制代码

  1. def Num3(list3):
  2.     list3.sort()
  3.     res1=res2=0
  4.     for i in list3:
  5.         res1^=i
  6.     for i in list3:
  7.         res2^=i
  8.         if res2==res1:
  9.             return i^res1,i
复制代码

评分

参与人数 1鱼币 +6 收起 理由
新手·ing + 6

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 15:29:43 | 显示全部楼层
本帖最后由 天圆突破 于 2018-3-4 16:27 编辑

重新排了一下格式

  1. import random as r
  2. #制作随机的试验数据用来验证结果
  3. #问题1试验数据制作
  4. a = [i for i in range(1,101)]
  5. tempa = r.randint(1,100)
  6. a.remove(tempa)
  7. r.shuffle(a)
  8. #问题2试验数据制作
  9. b = [i for i in range(1, 101)]*2
  10. tempb = r.randint(1, 100)
  11. b.remove(tempb)
  12. r.shuffle(b)
  13. #问题3试验数据制作
  14. c = [i for i in range(1, 101)]*2
  15. tempc1 = r.randint(1, 100)
  16. tempc2 = r.randint(1, 100)
  17. while tempc2 == tempc1:
  18.     tempc2 = r.randint(1, 100)
  19. c.remove(tempc1)
  20. c.remove(tempc2)
  21. r.shuffle(c)

  22. #打印试验数据,用来验证后面的计算结果
  23. #打印问题1试验数据:
  24. print('%s %s %s'%('*'*50, '试验数据', '*'*50))
  25. print('问题1')
  26. print(a)
  27. print('被剔除的数据为:%d'%tempa)
  28. #打印问题2试验数据:
  29. print('问题二')
  30. print(b)
  31. print('出现次数为奇数的数据为:%d'%tempb)
  32. #打印问题3试验数据:
  33. print( '问题三')
  34. print(c)
  35. print('出现次数为奇数的数据为:%d和%d'%(tempc1, tempc2))
  36. print('%s %s %s'%('*'*50, '计算结果', '*'*50))








  37. #上面都是用来生成试验数据,下面才是计算过程:





  38. #问题1:
  39. a.sort()
  40. for i, k in enumerate(a, 1):
  41.     if i != k:
  42.         print('问题1:\n计算缺失的数据是%d' % (i))
  43.         break
  44. else:print('问题1:\n计算缺失的数据是100')

  45. #问题2:
  46. b.sort();b.insert(0, None);b.append(None)
  47. for k in range(1, len(b)-1):
  48.     if b[k] != b[k-1] and b[k] != b[k+1]:
  49.         break
  50. print('问题2:\n计算出现次数为奇数的数据是%d'%b[k])

  51. #问题3
  52. c.sort();c.insert(0, None);c.append(None)
  53. lst = list()
  54. for k in range(1, len(c)-1):
  55.         if c[k] != c[k-1] and c[k] != c[k+1]:
  56.             lst.append(c[k])
  57. print('问题3:\n计算出现次数为奇数的两个数据是:',lst)

复制代码

评分

参与人数 1鱼币 +6 收起 理由
新手·ing + 6

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 17:09:53 | 显示全部楼层
大硕硕 发表于 2018-3-4 10:43
运算结果:

分冶法我不知道是啥

这个第三问其实有局限,对于 z = [0,1,1,2,2,3,4]形式的列表,  应该不能正确找到那两个数。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 17:49:11 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2018-3-4 17:50 编辑

只写了附加题的解答,对于附加题1和2都适用。
  1. def func(lst):
  2.     return set(i for i in lst if lst.count(i)%2)
  3. print(func([1,1,2,2,3,4,5,5]))
复制代码

评分

参与人数 1鱼币 +6 收起 理由
新手·ing + 6

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 19:40:41 | 显示全部楼层
  1. #第一题
  2. #生成99个不重复正整数
  3. import random
  4. list1 = list(range(1, 101))
  5. random.shuffle(list1)
  6. list1.pop()

  7. #使用集合的方法
  8. set1 = set(range(1, 101))
  9. set2 = set(list1)
  10. list2 = list(set1 - set2)
  11. print(list2[0])

  12. #第三题
  13. list1 = list(range(1, 101)) + list(range(1, 101)) +[7, 21, 21, 21]
  14. random.shuffle(list1)
  15. list2 = []
  16. for i in list1:
  17.     if i in list2:
  18.         list2.remove(i)
  19.     else:
  20.         list2.append(i)
  21. print(list2)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 20:00:56 | 显示全部楼层
题目:
  1. import random
  2. list1 = random.sample(range(1, 101), 99)
  3. list2 = [i for i in range(1, 101)]
  4. for j in list2:
  5.     if j not in list1:
  6.         print(j)
复制代码

扩展一、二(对异或法和分治法不了解,自己瞎写的):
  1. def classification(lis):
  2.     lis.sort()
  3.     lst = []
  4.     while len(lis) > 0:
  5.         num = lis.count(lis[0])
  6.         lst.append([lis[0],num])
  7.         temp = lis[0]
  8.         while temp in lis:
  9.             lis.remove(temp)
  10.     return lst
  11. list1 = [1, 1, 2, 2, 3, 3, 4, 5, 5]
  12. list2 = [1, 1, 2, 2, 3, 4, 5, 5]
  13. result1 = classification(list1)
  14. result2 = classification(list2)
  15. def count(l):
  16.     lst = []
  17.     lis = [i for i in range(1, 100, 2)]
  18.     for i in l:
  19.         if i[1] in lis:
  20.             lst.append(i[0])
  21.     return lst
  22. final1 = count(result1)
  23. final2 = count(result2)
  24. print(final1, final2)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-8 22:13:55 | 显示全部楼层
a=[int(i) for i in input('请输入正整数,并且用,号分开,找出出现了奇次数的数').split(',')]
c=[]
for b in a:
    if a.count(b) not in range(2,100,2):
        if b not in c:
            c.append(b)
print(c)
        
   
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-9 11:02:32 | 显示全部楼层
好题目,又学到了东西,虽然不知道自己写得方法对不对,结果应该是对的。

  1. import random
  2. from functools import reduce

  3. l1 = list(range(1, 101))
  4. random.shuffle(l1)              # 随机乱序
  5. d1 = random.randint(1, 100)
  6. t1 = l1[d1]                     
  7. print("弹出:%d" % t1)         
  8. l1.pop(d1)                      # 弹出第d1个数字,现在要找出这个数字

  9. for i in range(1, 101):
  10.     if i not in l1:
  11.         print("缺少的整数是:%d" % i)

  12. # 扩展一
  13. l2 = list(range(1, 101))
  14. random.shuffle(l2)              # 随机乱序
  15. l3 = l1 + l2                    

  16. d2 = reduce(lambda x, y: x ^ y, l3)     
  17. print("出现奇数次的一个数字是:%d" % d2)


  18. # 扩展二
  19. tmp = random.randint(1, 100)
  20. t2 = l2[tmp]
  21. print("弹出第二个数字:%d" % t2)     
  22. l2.pop(tmp)

  23. l4 = l1*2 + l2*2 + [t1, t2]     
  24. l4.sort()                     
  25. len4 = len(l4)                  

  26. i, k = 0, 0
  27. two = []
  28. while i < (len4-2):
  29.     for i in range(k, len4, 2):
  30.         d3 = reduce(lambda x, y: x ^ y, l4[i:i+2])
  31.         if d3:
  32.             two.append(l4[i])
  33.             k = i + 1
  34.             break

  35. if two:
  36.     print("出现奇数次的两个数字是:%d 和 %d" % (two[0], two[1]))
  37. else:
  38.     print("没有数字出现奇数次!")       # 由于列表中弹出的数字是随机的,因此可能弹出同一个数字,导致生成的l4中没有符合条件的数
复制代码


结果:
弹出:44
缺少的整数是:44
出现奇数次的一个数字是:44
弹出第二个数字:16
出现奇数次的两个数字是:16 和 44
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 12:58

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表