牛客刷题总结11
发布人:shili8
发布时间:2025-01-21 08:48
阅读次数:0
**牛客刷题总结11**
本文总结了我在牛客网上刷题的经历,涵盖了从初级到高级题目的解决方案和思考过程。希望通过这篇文章,可以帮助更多的人提高编程能力和问题解析技巧。
**一、初级题目**
初级题目通常涉及基本数据结构(如链表、栈、队列等)和算法(如排序、查找等)的应用。在牛客网上,初级题目的难度相对较低,但仍然需要仔细思考和分析。
###1.1 链表相关题目* **反转链表**
class ListNode: def __init__(self, x): self.val = x self.next = Nonedef reverseList(head): prev = None while head: next_node = head.next # 将下一个节点暂存 head.next = prev # 反转当前节点的next指针 prev = head # 移动prev指针 head = next_node # 移动head指针 return prev
* **合并两个有序链表**
def mergeTwoLists(l1, l2): dummy = ListNode(0) current = dummy while l1 and l2: if l1.val < l2.val: current.next = l1 l1 = l1.next else: current.next = l2 l2 = l2.next current = current.next # 如果l1或l2中有剩余的节点,直接将其接到结果链表后面 if l1: current.next = l1 elif l2: current.next = l2 return dummy.next
###1.2 算法相关题目* **查找第一个出现的指定数字**
def findNthDigit(n): if n < 10: return n index, count =0,9 while True: total = count * (index +1) *9 if total >= n: break n -= total count +=9 index +=1 num = int(str(index +1) + str(n // (count * (index +1)))) return num
* **最长公共子序列**
def longestCommonSubsequence(text1, text2): m, n = len(text1), len(text2) dp = [[0] * (n +1) for _ in range(m +1)] for i in range(1, m +1): for j in range(1, n +1): if text1[i -1] == text2[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]
**二、中级题目**
中级题目通常涉及更复杂的数据结构(如树、图等)和算法(如动态规划、贪婪算法等)的应用。在牛客网上,中级题目的难度相对较高,但仍然需要仔细思考和分析。
###2.1 树相关题目* **二叉树的最大深度**
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nonedef maxDepth(root): if not root: return0 left_depth = maxDepth(root.left) right_depth = maxDepth(root.right) return max(left_depth, right_depth) +1
* **二叉树的中序遍历**
def inorderTraversal(root): res = [] if root: res += inorderTraversal(root.left) res.append(root.val) res += inorderTraversal(root.right) return res
###2.2 图相关题目* **最短路径**
from collections import dequedef shortestPathBinaryMatrix(grid): if grid[0][0] ==1 or grid[-1][-1] ==1: return -1 rows, cols = len(grid), len(grid[0]) directions = [(0,1), (0, -1), (1,0), (-1,0), (1,1), (-1, -1), (1, -1), (-1,1)] queue = deque([(0,0,1)]) visited = {(0,0)} while queue: x, y, step = queue.popleft() if x == rows -1 and y == cols -1: return step for dx, dy in directions: nx, ny = x + dx, y + dy if (0 <= nx < rows) and (0 <= ny < cols) and grid[nx][ny] ==0 and (nx, ny) not in visited: queue.append((nx, ny, step +1)) visited.add((nx, ny)) return -1
**三、高级题目**
高级题目通常涉及更复杂的数据结构(如并查集、线段树等)和算法(如分治算法、随机化算法等)的应用。在牛客网上,高级题目的难度相对最高,但仍然需要仔细思考和分析。
###3.1 并查集相关题目* **并查集**
class UnionFind: def __init__(self, n): self.parent = list(range(n)) def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x != root_y: self.parent[root_x] = root_y
* **最小生成树**
import heapqdef findMinHeightTrees(n, edges): if n ==1: return [0] graph = [[] for _ in range(n)] for u, v in edges: graph[u].append(v) graph[v].append(u) while n >2: leaves = [] for i in range(n): if len(graph[i]) ==1: leaves.append(i) for leaf in leaves: neighbor = graph[leaf][0] graph[neighbor].remove(leaf) graph[leaf] = [] n -= len(leaves) return leaves
###3.2 分治算法相关题目* **分治算法**
def mergeSort(arr): if len(arr) <=1: return arr mid = len(arr) //2 left_half = mergeSort(arr[:mid]) right_half = mergeSort(arr[mid:]) return merge(left_half, right_half) def merge(left, right): merged = [] left_index =0 right_index =0 while left_index < len(left) and right_index < len(right): if left[left_index] <= right[right_index]: merged.append(left[left_index]) left_index +=1 else: merged.append(right[right_index]) right_index +=1 merged.extend(left[left_index:]) merged.extend(right[right_index:]) return merged
* **线段树**
class SegmentTree: def __init__(self, arr): self.n = len(arr) self.tree = [0] * (4 * self.n) self.build_tree(arr,1,0, self.n -1) def build_tree(self, arr, node, start, end): if start == end: self.tree[node] = arr[start] return mid = (start + end) //2 self.build_tree(arr,2 * node, start, mid) self.build_tree(arr,2 * node +1, mid +1, end) self.tree[node] = max(self.tree[2 * node], self.tree[2 * node +1]) def query(self, left, right): return self.query_tree(1,0, self.n -1, left, right) def query_tree(self, node, start, end, left, right): if start > right or end < left: return float('-inf') if start >= left and end <= right: return self.tree[node]