当前位置:实例文章 » 其他实例» [文章]牛客刷题总结11

牛客刷题总结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]

相关标签:
其他信息

其他资源

Top