精华内容
下载资源
问答
  • 数据结构常考题

    2014-03-24 16:49:45
    数据结构常考题可以看看,着这问题是比较容易考到的,自己复习用得到
  • python web后端数据结构 1.常见的数据结构链表、队列、栈、二叉树、堆 2.使用内置结构实现高级数据结构,比如内置的 list/deque实现栈 3.Leetcode 或者 《剑指offer》上的常见题 二、数据结构之链表 链表有...
    一、常考题型

    python web后端常考数据结构
    1.常见的数据结构链表、队列、栈、二叉树、堆
    2.使用内置结构实现高级数据结构,比如内置的 list/deque实现栈
    3.Leetcode 或者 《剑指offer》上的常见题

    二、常考数据结构之链表

    链表有单链表、双链表、循环双端链表
    1.如何使用 python来表示链表结构
    2.实现链表常见操作,比如插入节点,反转链表,合并多个链表等
    3.Leetcode练习常见链表题目

    下面是 leetcode206号题 反转链表

    # 定义单链表
    class ListNode:
    	def __init__(self, x):
    		self.val = x
    		self.next = None
    
    class Solution:
    	def reverseList(self, head):
    		"""
    		:type head: ListNode
    		:rtype: ListNode
    		"""
    		pre = None
    		cur = head
    		while cur:
    			next_node = cur.next
    			cur.next = pre
    			pre = cur
    			cur = next_node
    		return pre
    		
    
    三、常考数据结构之队列

    队列(queue)是先进先出结构

    1.如何使用python实现队列?
    2.实现队列的 appendpop操作,如何做到先进先出
    3.使用 pythonlist或者 collections.deque实现队列

    代码示例:

    from collections import deque
    
    class Queue:
    	def __init__(self):
    		self.items = deque()
    
    	def append(self, val):
    		return self.items.append(val)
    
    	def pop(self):
    		return self.items.popleft()
    
    	def empty(self):
    		return len(self.items) == 0
    
    def test_queue():
    	q = Queue()
    	q.append(0)
    	q.append(1)
    	q.append(2)
    	
    	print(q.pop())
    	print(q.pop())
    	print(q.pop())
    
    test_queue()		
    

    运行结果:
    在这里插入图片描述

    四、常考数据结构之栈

    栈(stack)是后进先出结构
    1.如何使用python实现栈?
    2.实现栈的 pushpop 操作,如何做到后进先出
    3.同样可以用 python list或者 collections.deque实现栈

    代码示例:

    class Stack:
        def __init__(self):
            self.items = deque()
    
        def push(self, val):
            return self.items.append(val)
    
        def pop(self):
            return self.items.pop()
    
        def empty(self):
            return len(self.items) == 0
    
    def test_stack():
        q = Stack()
        q.push(0)
        q.push(1)
        q.push(2)
        print(q.pop())
        print(q.pop())
        print(q.pop())
    
    test_stack()
    

    借助内置的数据结构非常容易实现一个栈(Stack),后入先出

    一个常考问题:如何用两个栈实现队列?

    参考链接:Python剑指offer之两个栈实现一个队列-两个队列实现一个栈

    class Queue_By_Stack:
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
    
        def append(self, val):
            self.stack1.append(val)
    
        def pop(self):
            if self.stack2 == []:
                if self.stack1 == []:
                    return None
                else:
                    for i in range(len(self.stack1)):
                        self.stack2.append(self.stack1.pop())
            return self.stack2.pop()
    

    如何实现获取最小值的栈MinStack
    参考链接Python实现"最小栈"的两种方法

    代码示例:

    class MinStack:
    
        def __init__(self):
            """
            initialize your data structure here.
            """
            self.stack = []
            self.min_stack = []
    
    
        def push(self, val: int) -> None:
            if not self.min_stack or self.min_stack[-1] >= val:
                self.min_stack.append(val)
            self.stack.append(val)
    
        def pop(self) -> None:
            if self.min_stack[-1] == self.stack[-1]:
                del self.min_stack[-1]
            self.stack.pop()
    
        def top(self) -> int:
            return self.stack[-1]
    
    
        def getMin(self) -> int:
            return self.min_stack[-1]
    
    五、常考数据结构之字典与集合

    Python dict/set 底层都是哈希表
    1.哈希表的实现原理,底层其实就是一个数组
    2.根据哈希函数快速定位一个元素,平均查找O(1),非常快
    3.不断加入元素会引起哈希表重新开辟空间,拷贝之前元素到新数组

    六、哈希表如何解决冲突

    链接法和开放寻址法
    1.元素 key 冲突之后使用一个链表填充相同 key的元素
    2.开放寻址法是冲突之后根据一种方式(二次探查)寻找下一个可用的槽
    3.cpython使用的二次探查

    七、常考数据结构之二叉树

    先序、中序、后序遍历
    1.先(根)序:先处理要,之后是左子树,然后是右子树
    2.中(根)序:先处理左子树,然后是根,然后是右子树
    3.后(根)序:先处理左子树,然后是右子树,最后是根

    八、树的遍历方式

    先序遍历,其实很简单,递归代码里先处理根就好了
    中序遍历,调整下把print(subtree.data)放中间就好啦
    后序遍历,调整下把print(subtree.data)放最后

    class BinTreeNode:
    	def __init__(self, data, left=None, right=None):
    		self.data, self.left, self.right = data, left, right
    
    
    class BinTree:
    	def __init__(self, root=None):
    		self.root = root
    
    	def preorde_trav(self, subtree):
    		""" 先(根)序遍历 """
    		if subtree is not None:
    			print(subtree.data)   # 递归函数里先处理根
    			self.preorder_trav(subtree.left)   # 递归处理左子树
    			self.preorder_trav(subtree.right)  # 递归处理右子树
    
    	def inorder_trav(self, subtree):
    		""" 中(根)序遍历 """
    		if subtree is not None:
    			self.preorder_trav(subtree.left)
    			print(subtree.data)   # 中序遍历放到中间就好啦
    			self.preorder_trav(subtree.right)
    			
    	 def lastorder_trav(self, subtree):
    		""" 后(根)序遍历 """
    		if subtree is not None:
    			self.preorder_trav(subtree.left)			
    			self.preorder_trav(subtree.right)
    			print(subtree.data)   # 后序遍历放到最后
    
    九、常考数据结构之堆

    堆其实是完全二叉树,有最堆和最小堆
    1.最大堆:对于每个非叶子节点 VV的值都比它的两个孩子大
    2.最大堆支持每次 pop操作获取最大的元素,最小堆获取最小元素
    3.常见问题:用堆来完成 topk 问题,从海量数字中寻找最大的 k

    代码示例:

    import heapq
    
    class TopK:
        """
        获取大量元素 topk 大个元素,固定内存
        思路:
        1.先放入元素前 k 个建立一个最小堆
        2.迭代剩余元素:
            如果当前元素小于堆顶元素,跳过该元素(肯定不是前 k 大)
            否则替换堆顶元素为当前元素,并重新堆
        """
    
        def __init__(self, iterable, k):
            self.min_heap = []
            self.capacity = k
            self.iterable = iterable
    
        def push(self, val):
            if len(self.min_heap) >= self.capacity:
                min_val = self.min_heap[0]
                if val < min_val:  # 当然你可以直接  if val > min_val 操作,这里我只是显示指出跳过个元素
                    pass
                else:
                    heapq.heapreplace(self.min_heap, val)  # 返回并且 pop 堆顶最小值,推入新的 val 值并调整堆
            else:
                heapq.heappush(self.min_heap, val)  # 前面 k 个元素直接放入 min_heap
    
        def get_topk(self):
            for val in self.iterable:
                self.push(val)
            return self.min_heap
    
    
    def test():
        import random
        i = list(range(1000))  # 这里可以是一个可迭代元素,节省内存
        random.shuffle(i)
        _ = TopK(i, 10)
        print(_.get_topk())
    
    test()
    
    展开全文
  • 2.常考题:删除一个链表节点 3.常考题:合并两个有序链表 # leetcode第237号题目:删除一个链表节点 class Solution: def deleteNode(self, node): next_node = node.next after_next_node = node.next.next ...
    一、链表

    链表涉及到指针操作较为复杂,容易出错,经常用用考题
    1.熟悉链表的定义和常见操作
    2.常考题:删除一个链表节点
    3.常考题:合并两个有序链表

    # leetcode第237号题目:删除一个链表节点
    class Solution:
    	def deleteNode(self, node):
    		next_node = node.next
    		after_next_node = node.next.next
    		node.val = next_node.val
    		node.next = after_next_node
    

    下图分析:
    在这里插入图片描述

    # leetcode第21号题目:合并两个有序链表
    class ListNode:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next
    class Solution:
        def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
            root = ListNode(None)
            cur = root
            while l1 and l2:
                if l1.val < l2.val:
                    node = ListNode(l1.val)
                    l1 = l1.next
                else:
                    node = ListNode(l2.val)
                    l2 = l2.next
                cur.next = node
                cur = node 
    
            # l1 或者 l2 可能还有剩余的值
            cur.next = l1 or l2
            return root.next
    
    二、多写多练

    打开相关的题目,多做一些练习
    1.一般可能一次很难写对
    2.尝试自己先思考,先按照自己的方式编写代码,提交后发现问题
    3.如果实在没有思路或者想参考别人的思路可以搜题解

    展开全文
  • 2.常考题:二叉树的镜像(反转二叉树) 3.常考题:如何层序遍历二叉树(广度优先) # leetcode 第226号题:反转二叉树 class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = ...
    一、二叉树

    二叉树涉及到递归和指针操作,常结合递归考察
    1.二叉树的操作很多可以用递归的方式解决,不了解递归会比较吃力
    2.常考题:二叉树的镜像(反转二叉树)
    3.常考题:如何层序遍历二叉树(广度优先)

    # leetcode 第226号题:反转二叉树
    class TreeNode:
    	def __init__(self, x):
    		self.val = x
    		self.left = None
    		self.right = None
    
    class Solution:
    	def invertTree(self, root):
    		if root:
    			root.left, root.right = root.right, root.left
    			self.invertTree(root.left)
    			self.invertTree(root.right)
    		return root		
    

    图示分析:
    在这里插入图片描述

    # leetcode 第106号题目:层序遍历二叉树(广度优先)
    class TreeNode:
    	def __init__(self, x):
    		self.val = x
    		self.left = None
    		self.right = None
    
    	def levelOrder(self, root):
    		if not root:
    			return []
    		
    		res = []
    		cur_nodes = [root]
    		next_nodes = []
    		res.append([i.val for i in cur_nodes])
    		while cur_nodes or next_nodes:
    			for node in cur_nodes:
    				if node.left:
    					next_nodes.append(node.left)
    				if node.right:
    					next_nodes.append(node.right)
    			if next_nodes:
    				res.append(
    					[i.val for i in next_nodes]
    				)
    	
    			cur_nodes = next_nodes
    			next_nodes = []
    		return res
    				
    

    图示分析:
    在这里插入图片描述
    二叉树变形题:输出左右视角的二叉树结果

    展开全文
  • 堆的常考题基本围绕在合并多个有序(数组/链表);TopK问题 1.理解堆的概念,堆是完全二叉树,有最大堆和最小堆 2.全使用python内置的 heapq模块实现堆的操作 3.常考题:合并K个有序链表 leetcode merge-k-sorted-...
    一、堆

    堆的常考题基本围绕在合并多个有序(数组/链表);TopK问题
    1.理解堆的概念,堆是完全二叉树,有最大堆和最小堆
    2.全使用python内置的 heapq模块实现堆的操作
    3.常考题:合并K个有序链表 leetcode merge-k-sorted-list

    # leetcode 第23号题目: 合并K个升序链表
    from heapq import heapify, heappop
    
    class ListNode:
    	def __init__(self, val=0, next=None):
    		self.val = val
    		self.next = next
    
    class Solution:
    	def mergKLists(self, lists):
    		# 读取所有节点值
    		h = []
    		for node in lists:
    			while node:
    				h.append(node.val)
    				node = node.next
    
    		if not h:   # h 为空时,返回 None,不然会报错
    			return None
    		# 构造一个最小堆
    		heapify(h)   # 转换成最小堆
    
    		# 构造链表
    		root = ListNode(heappop(h))
    		cur_node = root
    		while h:
    			next_node = ListNode(heappop(h))
    			cur_node.next = next_node
    			cur_node = next_node
    		return root
    
    展开全文
  • 一、你使用过哪些常用内置算法和数据结构 仔细回想一下你用过哪些内置的算法数据结构? 1.sorted 2.dict/list/set/tuple… 3.问题:想的不全或者压根没了解和使用过 数据结构/算法 语言内置 内置库 线性结构...
  • 2.常考题:用栈实现队列 3.leetcode implement-queue-using-stacks 用栈实现队列图示分析: 代码实现: # leetcode 第232号 用栈实现队列 from collections import deque class Stack: def __init__(self): ...
  • 我们经典的排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 算法复杂度如下图: 下面我们一一来总结...

空空如也

空空如也

1 2 3 4 5
收藏数 88
精华内容 35
关键字:

数据结构常考题

数据结构 订阅