牛客刷题总结9

**牛客刷题总结9**

本文是对牛客刷题系列的第九篇总结。我们将讨论一些常见的算法问题，包括链表、栈、队列、树等数据结构，以及一些经典的算法题目。

### 一. 链表链表是一种线性数据结构，它由一系列的节点组成，每个节点包含一个值和一个指向下一个节点的引用。链表是动态分配内存的，因此它比数组更适合用于需要频繁插入或删除元素的情况。

####1. 链表反转反转链表的目的是将原来的链表中的元素顺序颠倒过来。例如，原来的链表为 `1 ->2 ->3`, 反转后变成 `3 ->2 ->1`。

class Node:
 def __init__(self, value):
 self.value = value self.next = Nonedef reverse_linked_list(head):
 prev = None current = head while current is not None:
 next_node = current.next current.next = prev prev = current current = next_node return prev

####2. 链表求中间结点求链表的中间结点是指找到链表中间的结点。例如，原来的链表为 `1 ->2 ->3 ->4`, 中间结点为 `2`。

def find_middle_node(head):
 slow = head fast = head while fast is not None and fast.next is not None:
 slow = slow.next fast = fast.next.next return slow

### 二. 栈栈是一种后进先出的数据结构，它遵循 LIFO（Last In First Out）原则。栈的元素可以通过 push 和 pop 操作添加和删除。

####1. 栈实现栈的基本操作包括 push、pop、peek 等。

class Stack:
 def __init__(self):
 self.items = []

 def push(self, item):
 self.items.append(item)

 def pop(self):
 return self.items.pop()

 def peek(self):
 return self.items[-1]

####2. 栈求最大值栈求最大值是指在栈中找到最大元素的位置。

def find_max_value(stack):
 max_value = float('-inf')
 for item in stack.items:
 if item > max_value:
 max_value = item return max_value

### 三. 队列队列是一种先进先出的数据结构，它遵循 FIFO（First In First Out）原则。队列的元素可以通过 enqueue 和 dequeue 操作添加和删除。

####1. 队列实现队列的基本操作包括 enqueue、dequeue 等。

class Queue:
 def __init__(self):
 self.items = []

 def enqueue(self, item):
 self.items.append(item)

 def dequeue(self):
 return self.items.pop(0)

####2. 队列求最大值队列求最大值是指在队列中找到最大元素的位置。

def find_max_value(queue):
 max_value = float('-inf')
 for item in queue.items:
 if item > max_value:
 max_value = item return max_value

### 四. 树树是一种非线性数据结构，它由一系列的节点组成，每个节点包含一个值和零到多个子节点。

####1. 二叉树二叉树是指每个节点最多有两个子节点的树。二叉树可以分为两类：满二叉树和完全二叉树。

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Nonedef is_full_binary_tree(root):
 if root is None:
 return True if root.left is None and root.right is None:
 return True if (root.left is not None and root.right is None) or (root.left is None and root.right is not None):
 return False return is_full_binary_tree(root.left) and is_full_binary_tree(root.right)

####2. 二叉树求高度二叉树求高度是指找到二叉树中最长路径的长度。

def find_height(root):
 if root is None:
 return0 return max(find_height(root.left), find_height(root.right)) +1

### 五. 经典算法题目####1. 最大子序列和最大子序列和是指在一串数字中找到最长的连续子序列，其元素之和最大。

def max_subarray_sum(arr):
 if len(arr) ==0:
 return0 current_max = arr[0]
 overall_max = arr[0]
 for i in range(1, len(arr)):
 current_max = max(arr[i], current_max + arr[i])
 overall_max = max(current_max, overall_max)
 return overall_max

####2. 最长公共子序列最长公共子序列是指在两串数字中找到最长的连续子序列，其元素相同。

def longest_common_subsequence(str1, str2):
 m = len(str1)
 n = len(str2)
 dp = [[0] * (n +1) for _ in range(m +1)]
 for i in range(1, m +1):
 for j in range(1, n +1):
 if str1[i -1] == str2[j -1]:
 dp[i][j] = dp[i -1][j -1] +1 else:
 dp[i][j] = max(dp[i -1][j], dp[i][j -1])
 return dp[m][n]

本文总结了链表、栈、队列、树等数据结构，以及一些经典的算法题目。这些知识将有助于你更好地理解和解决问题。