经过两轮的头脑爆炸,越是找不到解题思路了。用什么样的方式来答题,才能拿到 offer.这种感受就像是突然之间被电了一下。
① 两个栈实现队列
题目:用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
有两个栈stackA、stackB,A是入栈的,B是出栈的,入栈时,直接进入A即可,出栈时,先判断是否有元素,如果B没有元素,pop肯定报错,应该先将A中所有的元素压到B里面,再pop最上面一个元素,如果B中有就直接pop出,就可以,两个栈实现了先进后出,在一起又实现了队列的先进先出。
class Solution:
def __init__(self):
self.stackA = []
self.stackB = []
def push(self, node):
self.stackA.append(node)
def pop(self):
if self.stackB:
return self.stackB.pop()
elif not self.stackA:
return None
else:
while self.stackA:
self.stackB.append(self.stackA.pop())
return self.stackB.pop()
② 字符串的排列
题目:输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
依次取一个元素,然后依次和之前递归形成的所有子串组合,形成新的字符串。
class Solution:
def permutation(self, li):
# write code here
if not len(li):
return []
if len(li) == 1:
return list(li)
charList = list(li)
print(charList)
charList.sort()
pStr = []
for i in range(len(charList)):
if i > 0 and charList[i] == charList[i-1]:
continue
temp = self.permutation(''.join(charList[:i])+''.join(charList[i+1:]))
for j in temp:
pStr.append(charList[i]+j)
print(pStr)
return pStr