Python算法训练：collections.deque()的应用---“对称数”_对称数python

问题描述：

对称数是一个旋转180°后看起来一样的数，找到所有长度为n的对称数。

问题示例：

输入n=2，输出[“11”,“69”,“88”,“96”]

代码实现:

本例运用到了collections模块，并使用了模块中的deque

介绍一些collections.deque()：
deque 是双边队列（double-ended queue），具有队列和栈的性质（即两头都可以Push和Pop），在 list 的基础上增加了移动、旋转和增删等。

常用方法：

创建一个deque对象：

>>> d = collections.deque([])
>>> d
deque([])
1
2
3

d.append() 在最右边添加一个元素

>>> d.append("hello")
>>> d
deque(['hello'])
1
2
3

d.appendleft() 在最左边添加一个元素

>>> d.appendleft("Oh")
>>> d
deque(['Oh', 'hello'])
1
2
3

d.extend() 在最右边添加一个序列

>>> list = ["nice", "to","meet","you"]
>>> d.extend(list)
>>> d
deque(['Oh', 'hello', 'nice', 'to', 'meet', 'you'])
1
2
3
4

d.extendleft() 在最左边添加一个序列

>>> tuple = ("Oct",10,1)
>>> d.extendleft(tuple)
>>> d
deque([1, 10, 'Oct', 'Oh', 'hello', 'nice', 'to', 'meet', 'you'])   #注意添加后的顺序哦
1
2
3
4

d.pop() 将最右边的元素取出

>>> data = d.pop()
>>> data
'you'
>>> d
deque([1, 10, 'Oct', 'Oh', 'hello', 'nice', 'to', 'meet'])
1
2
3
4
5

d.popleft() 将最左边的元素取出

>>> data = d.popleft()
>>> data
1
>>> d
deque([10, 'Oct', 'Oh', 'hello', 'nice', 'to', 'meet'])
1
2
3
4
5

d.rotate(-2) 向左移动（旋转）两个位置（正数则向右移动（旋转））

>>> d.rotate(-2)
>>> d
deque(['Oh', 'hello', 'nice', 'to', 'meet', 10, 'Oct'])
1
2
3

d.count(num) # 队列中num的个数

deque(['Oh', 'hello', 'nice', 'to', 'meet', 10, 'Oct'])
>>> d.append(10)
>>> d
deque(['Oh', 'hello', 'nice', 'to', 'meet', 10, 'Oct', 10])
>>> d.count(10)
2
1
2
3
4
5
6

d.remove(‘to’) # 从队列中将’to’删除

>>> d.remove('to')
>>> d
deque(['Oh', 'hello', 'nice', 'meet', 10, 'Oct', 10])
1
2
3

d.reverse() # 将队列倒序

>>> d.reverse()
>>> d
deque([10, 'Oct', 10, 'meet', 'nice', 'hello', 'Oh'])
1
2
3

代码：

import collections
class Solution:
   def findSymmetryNumber(self,n):
      ROTATE = {}
      ROTATE["0"] = "0"
      ROTATE["1"] = "1"
      ROTATE["6"] = "9"
      ROTATE["9"] = "6"
      ROTATE["8"] = "8"
      dqueue = collections.deque()  #创建一个双边队列对象
      if n % 2 == 0:
         dqueue.append("")  #也是一个元素"",dqueue = deque([""])
      else:
         dqueue.append("0")
         dqueue.append("1")
         dqueue.append("8")
      result = []
      while dqueue:
            num = dqueue.popleft()
            if len(num) == n:
               result+=[num] if num[0] !="0" or n ==1 else []
            else:
               for key,val in ROTATE.items():
                  dqueue.append(key+num+val)
      return result

if __name__ == '__main__':
   n = int(input("请输入长度n："))
   temp = Solution()
   res = temp.findSymmetryNumber(n)
   print(res)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

输出：

请输入长度n：3
['101', '609', '906', '808', '111', '619', '916', '818', '181', '689', '986', '888']

请输入长度n：2
['11', '69', '96', '88']
1
2
3
4
5