devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Leecode——数据结构练习_"temp.insert(0,\"count\",0)"

作者：我家自动化 | 2024-03-15 17:39:27

赞

踩

"temp.insert(0,\"count\",0)"
 
一、二叉树
前序遍历、中序遍历、后序遍历:
1.前序遍历： 
  1.      def preorderTraversal(self, root: TreeNode) -> List[int]:
  2.         if root == None:
  3.             return []
  4.         # 分别记录遍历结果，存储栈
  5.         result, istack = [], []
  6.         while root != None or len(istack) != 0:
  7.             # 嵌套循环
  8.             while root != None:
  9.                 # 前序遍历，压入栈前先输出
  10.                 result.append(root.val)
  11.                 istack.append(root)
  12.                 root=root.left
  13.             # 栈弹出
  14.             root = istack[-1]
  15.             istack = istack[:-1]
  16.             root = root.right
  17.         return result

2.中序遍历：

  1.     def inorderTraversal(self, root: TreeNode) -> List[int]:
  2.         if root == None:
  3.             return []
  4.         # 分别记录遍历结果，存储栈
  5.         result, istack = [], []
  6.         while root != None or len(istack) != 0:
  7.             while root != None:
  8.                 istack.append(root)
  9.                 root = root.left
  10.             # 中序遍历，等左子树压入栈完毕，再从栈输出
  11.             cur = istack[-1]
  12.             result.append(cur.val)
  13.             istack = istack[:-1]
  14.             root = cur.right
  15.         return result

3.后序遍历：

  1.     def postorderTraversal(self, root: TreeNode) -> List[int]:
  2.         if root == None:
  3.             return []
  4.         # 分别记录遍历结果，存储栈，后序遍历必要的前一个输出节点记录
  5.         result, istack, lastnode = [], [], None
  6.         while root != None or len(istack) != 0:
  7.             while root != None:
  8.                 istack.append(root)
  9.                 root = root.left
  10.             # 左子树压入栈后，判断当前节点是否可输出
  11.             cur = istack[-1]
  12.             # 如果当前节点无右子树，或者右子树已经输出，则该点可输出
  13.             if cur.right == None or cur.right == lastnode:
  14.                 istack = istack[:-1]
  15.                 result.append(cur.val)
  16.                 lastnode = cur
  17.             # 否则继续将该点右子树入栈，再继续循环
  18.             else:
  19.                 root = cur.right
  20.         return result

深度搜索DFS，层次搜索BFS：

1.层次搜索/遍历 
  1.     def levelOrder(self, root: TreeNode) -> List[List[int]]:
  2.         if root == None:
  3.             return []
  4.         # 层序遍历，需要借助队列记录
  5.         result, iqueue = [], []
  6.         # 队列需要先入队
  7.         iqueue.append(root)
  8.         while len(iqueue) != 0:
  9.             # 遍历当前层之前，先记录该层的个数，以便队列边记录边遍历
  10.             l, temp = len(iqueue), []
  11.             for i in range(0, l):
  12.                 # 遍历时，依次取出和输出队中的点，并将子树入队
  13.                 cur = iqueue[0]
  14.                 iqueue = iqueue[1:]
  15.                 temp.append(cur.val)
  16.                 if cur.left != None:
  17.                     iqueue.append(cur.left)
  18.                 if cur.right != None:
  19.                     iqueue.append(cur.right)
  20.             result.append(temp)
  21.         return result

分治法：递归返回条件+分段处理+合并结果（快速排序、归并排序、二叉树）

1.简单分治法：用于计算二叉树的最大深度 
  1.     def maxDepth(self, root: TreeNode) -> int:
  2.         if root == None:
  3.             return 0
  4.         left = self.maxDepth(root.left)
  5.         right = self.maxDepth(root.right)
  6.         return left + 1 if left > right else right + 1

2.判断是否为平衡二叉树：

  1.     def isBalanced(self, root: TreeNode) -> bool:
  2.         if self.judge(root) == -1:
  3.             return False
  4.         else:
  5.             return True
  6.     def judge(self, root: TreeNode) -> int:
  7.         if root == None:
  8.             return 0
  9.         left = self.judge(root.left)
  10.         right = self.judge(root.right)
  11.         # 借助层数来记录是否平衡，如果为-1，则直接返回不平衡
  12.         if left == -1 or right == -1 or left - right > 1 or right - left > 1:
  13.             return -1
  14.         else:
  15.             return left + 1 if left > right else right + 1

3.找出二叉树中最大路径和【hard】

  1.     def maxPathSum(self, root: TreeNode) -> int:
  2.         # 最大和：左/右子树最大和，左右子树加根节点的最大和
  3.         summax = self.find(root)
  4.         return summax[1]
  5.  
  6.     def find(self, root: TreeNode) -> List[int]:
  7.         if root == None:
  8.             return [0, float('-inf')]
  9.         # 分治
  10.         left = self.find(root.left)
  11.         right = self.find(root.right)
  12.         result = []
  13.         # 合并规整，先求单边值，再求最大和
  14.         if left[0] > right[0]:
  15.             result.append(max(left[0] + root.val, 0))
  16.         else:
  17.             result.append(max(right[0] + root.val, 0))
  18.         result.append(max(max(left[1], right[1]), (left[0] + right[0] + root.val)))
  19.         return result

4.找出二叉树的公共祖先

  1.     def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
  2.         if root == None:
  3.             return root
  4.         if root == p or root == q:
  5.             return root
  6.         # 分治
  7.         left = self.lowestCommonAncestor(root.left, p, q)
  8.         right = self.lowestCommonAncestor(root.right, p, q)
  9.         # 归并整合，返回为空则未找到，返回不为空则找到
  10.         if left != None and right != None:
  11.             return root
  12.         if left != None:
  13.             return left
  14.         if right != None:
  15.             return right
  16.         return None

BFS层次遍历：

1.锯齿形层次遍历： 
  1.     def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
  2.         if root == None:
  3.             return []
  4.         # 层次遍历需要借助队列顺序，锯齿形需要逆转标记
  5.         result, iqueue, iturn = [], [], True
  6.         iqueue.append(root)
  7.         while len(iqueue) > 0:
  8.             temp, l = [], len(iqueue)
  9.             for i in range(0, l):
  10.                 cur = iqueue[0]
  11.                 iqueue = iqueue[1:]
  12.                 if iturn:
  13.                     temp.append(cur.val)
  14.                 else:
  15.                     temp.insert(0, cur.val)
  16.                 if cur.left != None:
  17.                     iqueue.append(cur.left)
  18.                 if cur.right != None:
  19.                     iqueue.append(cur.right)
  20.             if iturn:
  21.                 iturn = False
  22.             else:
  23.                 iturn = True
  24.             result.append(temp)
  25.         return result

2.判定是否为有效二叉搜索树【medium】

  1.     def isValidBST(self, root: TreeNode) -> bool:
  2.         res = self.helper(root)
  3.         if res[0] == 0:
  4.             return False
  5.         else:
  6.             return True
  7.     def helper(self, root: TreeNode) -> List[int]:
  8.         # 结果记录，分别为0是否有效，1树的最大值，2树的最小值
  9.         if root == None:
  10.             return [1, float('-inf'), float('-inf')]
  11.         # 分治
  12.         left = self.helper(root.left)
  13.         right = self.helper(root.right)
  14.         # 整合：先判定无效情况
  15.         if left[0] == 0 or right[0] == 0:
  16.             return [0, float('-inf'), float('-inf')]
  17.         if left[1] != float('-inf') and left[1] >= root.val:
  18.             return [0, float('-inf'), float('-inf')]
  19.         if right[2] != float('-inf') and right[2] <= root.val:
  20.             return [0, float('-inf'), float('-inf')]
  21.         # 节点为有效时，节点最大值为右子树的最大值，最小值为左子树的最小值，否则最大最小值为本身
  22.         result = [1, root.val, root.val]
  23.         if right[1] != float('-inf'):
  24.             result[1] = right[1]
  25.         if left[2] != float('-inf'):
  26.             result[2] = left[2]
  27.         return result

3.二叉搜索树中插值：

  1.     def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
  2.         if root == None:
  3.             root = TreeNode()
  4.             root.val = val
  5.             return root
  6.         if root.val == val:
  7.             return root
  8.         elif val < root.val:
  9.             root.left = self.insertIntoBST(root.left, val)
  10.         else:
  11.             root.right = self.insertIntoBST(root.right, val)
  12.         return root

二、链表

链表基本操作：
1.删除全部的重复元素 
  1.     def deleteDuplicates(self, head: ListNode) -> ListNode:
  2.         pre = ListNode()
  3.         pre.next = head
  4.         head, last = pre, float('inf')
  5.         # 删除重复的额外点，只需要一个指针滑动，判断当前点和下一点(如有)；
  6.         # 而删除全部重复点，则需要空指针领头，进行领头后续两个节点的判断(无两个节点则无需判断)。
  7.         while head.next != None and head.next.next != None:
  8.             if head.next.val == head.next.next.val:
  9.                 last = head.next.val
  10.                 while head.next != None and head.next.val == last:
  11.                     head.next = head.next.next
  12.             else:
  13.                 head = head.next
  14.         return pre.next

2.反转链表

  1.     def reverseList(self, head: ListNode) -> ListNode:
  2.         pre = ListNode()
  3.         pre.next = head
  4.         while head.next != None:
  5.             # 记录下一个节点
  6.             last = head.next
  7.             # 将当前节点next指向下一个节点的next
  8.             head.next = last.next
  9.             # 下一个节点next指向空指针next
  10.             last.next = pre.next
  11.             # 将空指针移动至最左
  12.             pre.next = last
  13.         return pre.next

3.将指定段落的链表反转【medium】

  1.     def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
  2.         if head == None or m == n:
  3.             return head
  4.         # 先进行小节点检索
  5.         point = ListNode()
  6.         point.next = head
  7.         head = point
  8.         count = 1
  9.         while count < m:
  10.             head = head.next
  11.             count += 1
  12.         pre, mid = head, head.next
  13.         head = head.next
  14.         last = head
  15.         # 用head作为原始遍历顺序指针，last记录移动的前一个结点
  16.         while count <= n and head != None:
  17.             # 将head指针的下一个记录，将当前节点的指针指向上一个节点
  18.             temp = head.next
  19.             head.next = last
  20.             # 移动上一个节点，并将head指针放在原来的下一个
  21.             last = head
  22.             head = temp
  23.             count += 1
  24.         pre.next = last
  25.         mid.next = head
  26.         return point.next

4.拼接两个有序链表

  1.     def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
  2.         # 将合并后的表新起一个空指针作为起点（表头）
  3.         result = ListNode()
  4.         point = result
  5.         while l1 != None and l2 != None:
  6.             if l1.val <= l2.val:
  7.                 point.next = l1
  8.                 l1 = l1.next
  9.             else:
  10.                 point.next = l2
  11.                 l2 = l2.next
  12.             point = point.next
  13.         if l1 != None:
  14.             point.next = l1
  15.         if l2 != None:
  16.             point.next = l2
  17.         return result.next

链表分隔与排序：

1.将链表根据值分隔为左小右大 
  1.     def partition(self, head: ListNode, x: int) -> ListNode:
  2.         # 需要用空指针作为原始起点的记录，用额外的表记录比x大的节点，再将结果并至指针末尾
  3.         result, pre = ListNode(), ListNode()
  4.         pre.next = head
  5.         bigger, head = result, pre
  6.         while head.next != None:
  7.             if head.next.val < x:
  8.                 head = head.next
  9.             else:
  10.                 # 将大值节点记录，移动指针，同时将大值节点链入额外记录链表中
  11.                 node = head.next
  12.                 head.next = node.next
  13.                 bigger.next = node
  14.                 bigger = bigger.next
  15.         bigger.next = None
  16.         head.next = result.next
  17.         return pre.next

2.归并排序【medium】

  1.     def sortList(self, head: ListNode) -> ListNode:
  2.         return self.mergeSort(head)
  3.     
  4.     def findMiddle(self, head: ListNode) -> ListNode:
  5.         # 用快慢指针来寻找中间节点
  6.         slow = head
  7.         fast = head.next
  8.         while fast != None and fast.next != None:
  9.             fast = fast.next.next
  10.             slow = slow.next
  11.         return slow
  12.     # 拼接两个有序链表
  13.     def mergeTwo(self, l1: ListNode, l2: ListNode) -> ListNode:
  14.         pre = ListNode()
  15.         point = pre
  16.         while l1 != None and l2 != None:
  17.             if l1.val < l2.val:
  18.                 point.next = l1
  19.                 l1 = l1.next
  20.             else:
  21.                 point.next = l2
  22.                 l2 = l2.next
  23.             point = point.next
  24.         if l1 != None:
  25.             point.next = l1
  26.         if l2 != None:
  27.             point.next = l2
  28.         return pre.next
  29.  
  30.     def mergeSort(self, head: ListNode) -> ListNode:
  31.         # 分治法要点1：递归返回确定，这里对至少2个节点排序，故而要有两个判断条件
  32.         if head == None or head.next == None:
  33.             return head
  34.         mid = self.findMiddle(head)
  35.         last = mid.next
  36.         mid.next = None
  37.         # 分治法要点2：分两部分递归，利用快慢指针找到中间节点
  38.         left = self.mergeSort(head)
  39.         right = self.mergeSort(last)
  40.        # 分治法要点3：归并整合两部分，用合并有序链表的方法
  41.         return self.mergeTwo(left, right)

3.将链表按照1, n, 2, n-1, 3, n-2, ..., 的顺序排列

  1.     def reorderList(self, head: ListNode) -> None:
  2.         # 思路：从中间破开链表，反转后链，再合并
  3.         if head == None or head.next == None:
  4.             return head
  5.         mid = self.findMiddle(head)
  6.         last = self.reverseList(mid.next)
  7.         mid.next = None
  8.         head = self.mergeTwo(head, last)
  9.  
  10.     def findMiddle(self, head: ListNode) -> ListNode:
  11.         slow, fast = head, head.next
  12.         while fast != None and fast.next != None:
  13.             fast = fast.next.next
  14.             slow = slow.next
  15.         return slow
  16.     
  17.     def reverseList(self, head: ListNode) -> ListNode:
  18.         pre = ListNode()
  19.         pre.next = head
  20.         while head.next != None:
  21.             last = head.next
  22.             head.next = last.next
  23.             last.next = pre.next
  24.             pre.next = last
  25.         return pre.next
  26.     
  27.     def mergeTwo(self, left: ListNode, right: ListNode) -> ListNode:
  28.         pre, isleft = ListNode(), True
  29.         point = pre
  30.         while left != None and right != None:
  31.             if isleft:
  32.                 point.next = left
  33.                 left = left.next
  34.                 isleft = False
  35.             else:
  36.                 point.next = right
  37.                 right = right.next
  38.                 isleft = True
  39.             point = point.next
  40.         if left != None:
  41.             point.next = left
  42.         if right != None:
  43.             point.next = right
  44.         return pre.next

环状链表：

1.判断链表是否有环 
  1.     def hasCycle(self, head: ListNode) -> bool:
  2.         if head == None:
  3.             return False
  4.         # 快指针用head表示，相交时当前点即为交汇点；
  5.         # 如用head.next表示，则相交点为下一个点
  6.         slow, fast = head, head.next
  7.         # 仅需判断快指针
  8.         while fast != None and fast.next != None:
  9.             if slow == fast:
  10.                 return True
  11.             slow = slow.next
  12.             fast = fast.next.next
  13.         return False

2.找出带环链表的入环点    

  1.     def detectCycle(self, head: ListNode) -> ListNode:
  2.         if head == None:
  3.             return head
  4.         # 相交点时，快慢指针分别走过a+b,a+n(b+c),c表示环剩下的长度;
  5.         # 得2(a+b)=a+n(b+c),即a=c+(n-1)(b+c),表示a的长度为n-1圈的环+c;
  6.         # 而慢指针继续走c即可回到入环点，再经过n-1圈仍然在入环点;
  7.         slow, fast = head, head.next
  8.         while fast != None and fast.next != None:
  9.             if fast == slow:
  10.                 fast = head
  11.                 # 因为一开始fast=head.next，此时slow.next才是真当前点
  12.                 slow = slow.next
  13.                 while fast != slow:
  14.                     fast = fast.next
  15.                     slow = slow.next
  16.                 return slow
  17.             fast = fast.next.next
  18.             slow = slow.next
  19.         return None

回文链表：

1.判断回文链表 
  1.     def isPalindrome(self, head: ListNode) -> bool:
  2.         if head == None or head.next == None:
  3.             return True
  4.         # 思路：与前面置换插入排序类似，采用中点截断、反转后链、再比较的做法。
  5.         slow, fast = head, head.next
  6.         while fast != None and fast.next != None:
  7.             slow = slow.next
  8.             fast = fast.next.next
  9.         last = self.reverseList(slow.next)    
  10.         slow.next = None 
  11.         while last != None and head != None:
  12.             if last.val != head.val:
  13.                 return False
  14.             last, head = last.next, head.next
  15.         return True  
  16.  
  17.     def reverseList(self, head: ListNode) -> ListNode:
  18.         if head == None:
  19.             return head
  20.         pre = ListNode()
  21.         # 切记，在反转链表时，空指针不需要head辅助
  22.         pre.next = head
  23.         while head.next != None:
  24.             node = head.next
  25.             head.next = node.next
  26.             node.next = pre.next
  27.             pre.next = node
  28.         return pre.next

2.深拷贝链表【medium】

  1.    def copyRandomList(self, head: 'Node') -> 'Node':
  2.         if head == None:
  3.             return head
  4.         point = head
  5.         while point != None:
  6.             node = Node(point.val, point.next)
  7.             point.next = node
  8.             point = node.next
  9.         point = head
  10.         # 很精妙，采用判断前一个节点为非空，来操作空节点
  11.         while point != None:     
  12.             if point.random != None:
  13.                 point.next.random = point.random.next
  14.             point = point.next.next
  15.             # 原做法
  16.             # node = point.random
  17.             # if node != None:
  18.             #     point.random = node.next
  19.             # if point.next != None:
  20.             #     point = point.next.next
  21.             # else:
  22.             #     point = point.next
  23.         point = head.next
  24.         while head != None and head.next != None:
  25.             # 很精妙，采用指针穿线的方法
  26.             node = head.next
  27.             head.next = head.next.next
  28.             head = node
  29.         return point    

三、栈和队列

栈
1.最小栈 
  1. class MinStack:
  2.     def __init__(self,):
  3.         self.istack = []
  4.         self.minstack = []
  5.         # 采用辅助栈做法，记录每个位置的最小值
  6.     
  7.     def push(self, x: int) -> None:
  8.         self.istack.append(x)
  9.         if len(self.minstack) != 0 and self.minstack[-1] < x:
  10.             temp = self.minstack[-1]
  11.             self.minstack.append(temp)
  12.         else:
  13.             self.minstack.append(x)
  14.  
  15.     def pop(self) -> None:
  16.         if len(self.istack) == 0:
  17.             return
  18.         self.istack = self.istack[:-1]
  19.         self.minstack = self.minstack[:-1]
  20.  
  21.     def top(self) -> int:
  22.         if len(self.istack) == 0:
  23.             return 0
  24.         return self.istack[-1]
  25.  
  26.     def getMin(self) -> int:
  27.         if len(self.istack) == 0:
  28.             return float('inf')
  29.         return self.minstack[-1]

2.利用栈进行逆波兰表达式求解

  1. class Solution:
  2.     def evalRPN(self, tokens: List[str]) -> int:
  3.         if len(tokens) == 0:
  4.             return 0
  5.         istack = []
  6.         for i in range(0, len(tokens)):
  7.             # 关键：会有二位数，因此先判断是否符号，并且是符号还要判断是否有已有两个值在栈中
  8.             if tokens[i] not in ["+", "-", "*", "/"]:
  9.                 istack.append(int(tokens[i]))
  10.             elif len(istack) < 2:
  11.                 break
  12.             else:
  13.                 a, b = istack[-2], istack[-1]
  14.                 istack = istack[:-2]
  15.                 if tokens[i] == "+":
  16.                     istack.append(a + b)
  17.                 elif tokens[i] == "-":
  18.                     istack.append(a - b)
  19.                 elif tokens[i] == "*":
  20.                     istack.append(a * b)
  21.                 elif tokens[i] == "/":
  22.                     istack.append(int(a / b))
  23.                 else:
  24.                     pass
  25.         if len(istack) == 1:
  26.             return istack[0]
  27.         else:
  28.             return 0

3.字符串解码

  1.     def decodeString(self, s: str) -> str:
  2.         istack = []
  3.         for i in range(0, len(s)):
  4.             if s[i] == ']':
  5.                 # 找字符串
  6.                 temp = []
  7.                 while len(istack) > 0 and istack[-1] != '[':
  8.                     temp.insert(0, istack[-1])
  9.                     istack = istack[:-1]
  10.                 istack = istack[:-1]
  11.                 # 找数字
  12.                 number = 1
  13.                 ilen = len(istack)
  14.                 while ilen >= number and istack[ilen - number] in ['0','1','2','3','4','5','6','7','8','9']:
  15.                     number += 1
  16.                 # 数字范围：[len - i + 1, len - 1]
  17.                 res = int(''.join(istack[ilen - number + 1:]))
  18.                 istack = istack[:ilen - number + 1]
  19.                 # 复制
  20.                 for i in range(0, res):
  21.                     istack.extend(temp)
  22.             else:
  23.                 istack.append(s[i])
  24.         return ''.join(istack)

4.克隆图

  1.     def cloneGraph(self, node: 'Node') -> 'Node':
  2.         # 关键点:用visited记录新建的节点，以连接
  3.         visited = {}
  4.         return self.cloneg(node, visited)
  5.  
  6.     def cloneg(self, node: 'Node', visited: dict) -> 'Node':
  7.         if node == None:
  8.             return node  
  9.         # visited中能找到新建节点，则直接返回节点
  10.         if visited.get(node) != None:
  11.             return visited[node]
  12.         newnode = Node(node.val, [])
  13.         visited[node] = newnode
  14.         for n in range(0, len(node.neighbors)):
  15.             newnode.neighbors.append(self.cloneg(node.neighbors[n], visited))
  16.         return newnode

5.小岛数量【medium】

  1.     def numIslands(self, grid: List[List[str]]) -> int:
  2.         count = 0
  3.         # 按数组顺序扫描
  4.         for i in range(0, len(grid)):
  5.             for j in range(0, len(grid[0])):
  6.                 if grid[i][j] == "1" and self.dfs(grid, i, j) >= 1:
  7.                     count += 1
  8.         return count
  9.  
  10.     def dfs(self, grid: List[List[str]], i: int, j: int) -> int:
  11.         if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
  12.             return 0
  13.         if grid[i][j] == "1":
  14.             grid[i][j] = "0"
  15.             # 将grid列表传入函数与（对象一样）属于引用传递，访问后改值相当于列表自带访问记录功能
  16.             return self.dfs(grid, i-1, j) + self.dfs(grid, i, j-1) +\
  17.                 self.dfs(grid, i+1, j) + self.dfs(grid, i, j+1) + 1
  18.         return 0

6.求条状图中的最大矩形面积【单调栈hard】

  1.     def largestRectangleArea(self, heights: List[int]) -> int:
  2.         # 1.采用宽度法，选取左右点固定区间，直接取高度，O(n2)
  3.         # 2.采用高度法，对于每根柱子求取最大宽度
  4.         # 固定高度，求宽度，即找左右侧：
  5.         # 左侧比当前高度低的第一根柱子;右侧比当前高度低的第一根柱子
  6.         res, istack = 0, []
  7.         # 在矩形中加入左右哨兵以求宽度
  8.         heights = [0] + heights + [0]
  9.         for i in range(len(heights)):
  10.             # 每次入栈，必须保证矩形高度为递增的
  11.             while istack and heights[istack[-1]] > heights[i]:
  12.                 last= istack.pop()
  13.                 res = max(res, heights[last]*(i - 1 - istack[-1]))
  14.             istack.append(i)
  15.         return res

队列

1.用栈实现队列 
  1. class MyQueue:
  2.     def __init__(self):
  3.         self.prestack = []
  4.         self.poststack = []
  5.  
  6.     def push(self, x: int) -> None:
  7.         while len(self.poststack) != 0:
  8.             self.prestack.append(self.poststack.pop())
  9.         self.prestack.append(x)
  10.  
  11.     def pop(self) -> int:
  12.         while self.prestack:
  13.             self.poststack.append(self.prestack.pop())
  14.         if self.poststack:
  15.             return self.poststack.pop()
  16.         return -1
  17.  
  18.  
  19.     def peek(self) -> int:
  20.         while self.prestack:
  21.             self.poststack.append(self.prestack.pop())
  22.         if self.poststack:
  23.             return self.poststack[-1]
  24.         return -1        
  25.  
  26.     def empty(self) -> bool:
  27.         if not self.prestack and not self.poststack:
  28.             return True
  29.         return False

2.二叉树层次遍历

3.0-1矩阵，找非0位置到0的距离【medium】 
  1.     def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
  2.         # 根据广度优先搜索，从外部向内包围
  3.         if not matrix:
  4.             return matrix
  5.         row, col = len(matrix), len(matrix[0])
  6.         iqueue = []
  7.         for i in range(row):
  8.             for j in range(col):
  9.                 # 从外包围，先将外围入队
  10.                 if matrix[i][j] == 0:
  11.                     iqueue.append([i,j])
  12.                 # 直接用值（-1）区分需要修改的点
  13.                 else:
  14.                     matrix[i][j] = -1
  15.         while len(iqueue) != 0:
  16.             point_i, point_j = iqueue[0][0], iqueue[0][1]
  17.             iqueue = iqueue[1:]
  18.             newpoint = [[point_i-1, point_j], [point_i+1, point_j], [point_i, point_j-1], [point_i, point_j+1]]
  19.             for n in newpoint:
  20.                 ii, jj = n[0], n[1]
  21.                 # 修改过的点为下一层入队点
  22.                 if ii >= 0 and ii < row and jj >= 0 and jj < col and matrix[ii][jj] == -1:
  23.                     matrix[ii][jj] = matrix[point_i][point_j] + 1
  24.                     iqueue.append([ii, jj])
  25.         return matrix

 

四、二进制（位运算）【https://blog.csdn.net/holmofy/article/details/79360859】

6个位运算符【&  |  ^  ~  <<  >>】
  • &（0清零，1保留）：取指定位；判断奇偶 (a&1)==0或a&(-a)==0；
  • |（有1则1，0保留）：改值（用1）
  • ^（同0异1，满足结合律、自反性）：反转指定位；
  • ~
从数组中找出只出现1次的数字：
1.2次中找1次：【异或】 
  1.     def singleNumber(self, nums: List[int]) -> int:
  2.         res = 0
  3.         for n in nums:
  4.             res = res ^ n
  5.         return res

2.3次中找1次：【异或、与、非的组合】

  1.     def singleNumber(self, nums: List[int]) -> int:
  2.         once, twice = 0, 0
  3.         # n,once,twice 
  4.         # 0 0 0 
  5.         # 0 1 0 
  6.         # 0 0 1
  7.         # 1 0 0
  8.         # 1 1 0 
  9.         # 1 0 1
  10.         # 对于n=1而言，3个1最终仍使once=0，实现3个数的位运算保证 
  11.         for n in nums:
  12.             once = once ^ n & ~twice 
  13.             twice = twice ^ n & ~once
  14.         return once

3.2次中找2个1次：

  1.     def singleNumber(self, nums: List[int]) -> List[int]:
  2.         # 1.求x和y的异或值。
  3.         # 2.求这个异或值最右位的1
  4.         # 3.找出x和y中是谁造成了这个最右位的1，以分离x和y
  5.         res = 0
  6.         for n in nums:
  7.             res ^= n
  8.         # res = x ^ y
  9.         # 取最右一位的1：res&(~res + 1)、res&(-res)、res&(res-1)^res
  10.         lastbit = (res&(res-1))^res
  11.         x = 0
  12.         for n in nums:
  13.             if n & lastbit != 0:
  14.                 x ^= n
  15.         return [x, res^x]

计算二进制：

1.计算二进制中1的个数：

  1.     def hammingWeight(self, n: int) -> int:
  2.         count = 0
  3.         while n != 0:
  4.             # 获取最后一位判断
  5.             if n & (-n) == 1:
  6.                 count += 1
  7.             n = n >> 1
  8.         return count

2.反转32位无符号整数二进制

  1.     def reverseBits(self, n: int) -> int:
  2.         res = 0
  3.         for i in range(32):
  4.             res = res << 1 
  5.             # 获取最后一位判断
  6.             if n & 1 == 1:
  7.                 res += 1
  8.             n = n >> 1
  9.         return res 

3.求区间数二进制的与值

  1.     def rangeBitwiseAnd(self, m: int, n: int) -> int:
  2.         # 因为相邻的两个数必有1~2位不相同的位置，可以找规律：
  3.         # 100100
  4.         # 100101
  5.         # 100110
  6.         # 100111
  7.         # 101000
  8.         # 因为m与n的相同前缀后分别为0，1（SSS0XXX,SSS1XXX）
  9.         # 通过m与n的不断舍取得到相同前缀即可
  10.         count = 0
  11.         while m != n:
  12.             m = m >> 1
  13.             n = n >> 1
  14.             count += 1
  15.         # 得到相同前缀，将末尾0补足
  16.         return m << count

 

 
 
 
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/243319
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号