共计 6189 个字符，预计需要花费 16 分钟才能阅读完成。
- 排序实现
有一组“+”和“-”符号，要求将“+”排到右边，“-”排到左边，写出具体的实现办法。
答:
如果让 + 等于 0，- 等于 1 不就是排序了么
from collections import deque from timeit import Timer s = “++++++—-+++—-” # 办法一 def func1(): new_s = s.replace(“+”, “0”).replace(“-“, “1”) result = “”.join(sorted(new_s)).replace(“0”, “+”).replace(“1”, “-“) return result # 办法二 def func2(): q = deque() left = q.appendleft right = q.append for i in s: if i == “+”: left(“+”) elif i == “-“: right(“-“) # 办法三 def func3(): data = list(s) start_index = 0 end_index = 0 count = len(s) while start_index + end_index < count: if data[start_index] == ‘-‘: data[start_index], data[count – end_index – 1] = data[count – end_index – 1], data[start_index] end_index += 1 else : start_index += 1 return “”.join(data) if name == ‘__main__’: timer1 = Timer(“func1()”, “from main import func1″) print(“func1”, timer1.timeit(1000000)) timer2 = Timer(“func2()”, “from main import func2″) print(“func2”, timer2.timeit(1000000)) timer3 = Timer(“func3()”, “from main import func3″) print(“func3”, timer3.timeit(1000000)) # 1000000 测试后果 # func1 1.39003764 # func2 1.593012875 # func3 3.3487415590000005 # func1 的形式最优，其次是 func2
- 单链表反转
答:
单链表反转
class Node: def init__(self, val=None): self.val = val self.next = None class SingleLinkList: def __init__(self, head=None): “”” 链表的头部 ””” self._head = head def add(self, val:int): “”” 给链表增加元素 :param val: 传过来的数字 :return: “”” # 创立一个节点 node = Node(val) if self._head is None: self._head = node else : cur = self._head while cur.next is not None: cur = cur.next # 挪动游标 cur.next = node # 如果 next 前面没了证实以及到最初一个节点了 def traversal(self): if self._head is None: return else : cur = self._head while cur is not None: print(cur.val) cur = cur.next def size(self): “”” 获取链表的大小 :return: “”” count = 0 if self._head is None: return count else : cur = self._head while cur is not None: count += 1 cur = cur.next return count def reverse(self): “”” 单链表反转 思路: 让 cur.next 先断开即指向 none，指向设定 pre 游标指向断开的元素，而后 cur.next 指向断开的元素，再把开始 self._head 再最初一个元素的时候. :return: “”” if self._head is None or self.size() == 1: return else : pre = None cur = self._head while cur is not None: post = cur.next cur.next = pre pre = cur cur = post self._head = pre # 逆向后的头节点 if __name == ‘__main__’: single_link = SingleLinkList() single_link.add(3) single_link.add(5) single_link.add(6) single_link.add(7) single_link.add(8) print(“ 对链表进行遍历 ”) single_link.traversal() print(f”size:{single_link.size()}”) print(“ 对链表进行逆向操作之后 ”) single_link.reverse() single_link.traversal()
- 穿插链表求交点
答:
Definition for singly-linked list. class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def getIntersectionNode(self, headA, headB): “”” :tye head1, head1: ListNode :rtye: ListNode “”” if headA is not None and headB is not None: cur1, cur2 = headA, headB while cur1 != cur2: cur1 = cur1.next if cur1 is not None else headA cur2 = cur2.next if cur2 is not None else headB return cur1
cur1、cur2，2 个指针的初始地位是链表 headA、headB 头结点，cur1、cur2 两个指针始终往后遍历。直到 cur1 指针走到链表的开端，而后 cur1 指向 headB；直到 cur2 指针走到链表的开端，而后 cur2 指向 headA；而后再持续遍历。
每次 cur1、cur2 指向 None，则将 cur1、cur2 别离指向 headB、headA。循环的次数越多，cur1、cur2 的间隔越靠近，直到 cur1 等于 cur2。则是两个链表的相交点。
- 用队列实现栈 ww
答:
上面代码别离应用 1 个队列和 2 个队列实现了栈。
from queue import Queue # 应用 2 个队列实现 class MyStack: def init__(self): “”” Initialize your data structure here. “”” # q1 作为进栈出栈，q2 作为中转站 self.q1 = Queue() self.q2 = Queue() def push(self, x): “”” Push element x onto stack. :type x: int :rtype: void “”” self.q1.put(x) def pop(self): “”” Removes the element on top of the stack and returns that element. :rtype: int “”” while self.q1.qsize() > 1: self.q2.put(self.q1.get()) # 将 q1 中除尾元素外的所有元素转到 q2 中 if self.q1.qsize() == 1: res = self.q1.get() # 弹出 q1 的最初一个元素 self.q1, self.q2 = self.q2, self.q1 # 替换 q1,q2 return res def top(self): “”” Get the top element. :rtype: int “”” while self.q1.qsize() > 1: self.q2.put(self.q1.get()) # 将 q1 中除尾元素外的所有元素转到 q2 中 if self.q1.qsize() == 1: res = self.q1.get() # 弹出 q1 的最初一个元素 self.q2.put(res) # 与 pop 惟一不同的是须要将 q1 最初一个元素保留到 q2 中 self.q1, self.q2 = self.q2, self.q1 # 替换 q1,q2 return res def empty(self): “”” Returns whether the stack is empty. :rtype: bool “”” return not bool(self.q1.qsize() + self.q2.qsize()) # 为空返回 True，不为空返回 False # 应用 1 个队列实现 class MyStack2(object): def __init__(self): “”” Initialize your data structure here. “”” self.sq1 = Queue() def push(self, x): “”” Push element x onto stack. :type x: int :rtype: void “”” self.sq1.put(x) def pop(self): “”” Removes the element on top of the stack and returns that element. :rtype: int “”” count = self.sq1.qsize() if count == 0: return False while count > 1: x = self.sq1.get() self.sq1.put(x) count -= 1 return self.sq1.get() def top(self): “”” Get the top element. :rtype: int “”” count = self.sq1.qsize() if count == 0: return False while count: x = self.sq1.get() self.sq1.put(x) count -= 1 return x def empty(self): “”” Returns whether the stack is empty. :rtype: bool “”” return self.sq1.empty() if __name == ‘__main__’: obj = MyStack2() obj.push(1) obj.push(3) obj.push(4) print(obj.pop()) print(obj.pop()) print(obj.pop()) print(obj.empty())
- 找出数据流的中位数
答:
对于一个升序排序的数组，中位数为左半局部的最大值，右半局部的最小值，而左右两局部能够是无需的，只有保障左半局部的数均小于右半局部即可。因而，左右两半局部别离可用最大堆、最小堆实现。
如果有奇数个数，则中位数放在左半局部；如果有偶数个数，则取左半局部的最大值、左边局部的最小值之平均值。分两种状况探讨:
当目前有偶数个数字时，数字先插入最小堆，而后抉择最小堆的最小值插入最大堆 (第一个数字插入左半局部的最小堆）。当目前有奇数个数字时，数字先插入最大堆，而后抉择最大堆的最大值插入最小堆。
最大堆: 根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。
最小堆: 根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。
–– coding:utf-8 –– from heapq import * class Solution: def init__(self): self.maxheap = [] self.minheap = [] def Insert(self, num): if (len(self.maxheap) + len(self.minheap)) & 0x1: # 总数为奇数插入最大堆 if len(self.minheap) > 0: if num > self.minheap[0]: # 大于最小堆里的元素 heappush(self.minheap, num) # 新数据插入最小堆 heappush(self.maxheap, -self.minheap[0]) # 最小堆中的最小插入最大堆 heappop(self.minheap) else : heappush(self.maxheap, -num) else : heappush(self.maxheap, -num) else : # 总数为偶数 插入最小堆 if len(self.maxheap) > 0: # 小于最大堆里的元素 if num < -self.maxheap[0]: heappush(self.maxheap, -num) # 新数据插入最大堆 heappush(self.minheap, -self.maxheap[0]) # 最大堆中的最大元素插入最小堆 heappop(self.maxheap) else : heappush(self.minheap, num) else : heappush(self.minheap, num) def GetMedian(self, n=None): if (len(self.maxheap) + len(self.minheap)) & 0x1: mid = self.minheap[0] else : mid = (self.minheap[0] – self.maxheap[0]) / 2.0 return mid if __name == ‘__main__’: s = Solution() s.Insert(1) s.Insert(2) s.Insert(3) s.Insert(4) print(s.GetMedian())
- 二叉搜寻树中第 K 小的元素
答:
二叉搜寻树 (BinarySearchTree)，又名二叉排序树 (BinarySortTree)。二叉搜寻树是具备有以下性质的二叉树:
若左子树不为空，则左子树上所有节点的值均小于或等于它的根节点的值。
若右子树不为空，则右子树上所有节点的值均大于或等于它的根节点的值。
左、右子树也别离为二叉搜寻树。二叉搜寻树依照中序遍历的程序打印进去正好就是排序好的程序。所以对其遍历一个节点就进行计数，计数达到 k 的时候就完结。
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: count = 0 nodeVal = 0 def kthSmallest(self, root, k): “”” :type root: TreeNode :type k: int :rtype: int “”” self.dfs(root, k) return self.nodeVal def dfs(self, node, k): if node != None: self.dfs(node.left, k) self.count = self.count + 1 if self.count == k: self.nodeVal = node.val # 将该节点的左右子树置为 None, 来完结递归，缩小工夫复杂度 node.left = None node.right = None self.dfs(node.right, k)
更多 Python 编程常见面试题，咱们后续持续分享，敬请关注。
