牛客网：华为机试刷题记录

**华为机试刷题记录**

作为一名正在努力提升编程能力的程序员，我决定在牛客网上进行华为机试刷题。以下是我的刷题记录，包括部分代码示例和注释。

**第一题：最长公共子序列**

题目描述：给定两个字符串 `s1` 和 `s2`，找到它们的最长公共子序列（LCS）。

def longest_common_subsequence(s1, s2):
 m = len(s1) +1 n = len(s2) +1 # 创建一个二维数组来存储每个子问题的结果 dp = [[0] * n for _ in range(m)]
 # 初始化第一行和第一列 for i in range(1, m):
 dp[i][0] =0 for j in range(1, n):
 dp[0][j] =0 # 填充二维数组 for i in range(1, m):
 for j in range(1, n):
 if s1[i -1] == s2[j -1]:
 dp[i][j] = dp[i -1][j -1] +1 else:
 dp[i][j] = max(dp[i -1][j], dp[i][j -1])
 # 回溯找到LCS lcs = []
 i, j = m -1, n -1 while i >0 and j >0:
 if s1[i -1] == s2[j -1]:
 lcs.append(s1[i -1])
 i -=1 j -=1 elif dp[i -1][j] > dp[i][j -1]:
 i -=1 else:
 j -=1 return ''.join(reversed(lcs))

import networkx as nxdef minimum_spanning_tree(graph):
 # 使用Prim算法找到最小生成树 mst = nx.minimum_spanning_tree(graph)
 return mst.edges()

def sliding_window(arr, window_size):
 # 使用列表推导式生成所有可能的滑动窗口 windows = [arr[i:i + window_size] for i in range(len(arr) - window_size +1)]
 return windows

def binary_search(arr, target):
 # 使用二分查找算法找到目标值的索引 left, right =0, len(arr) -1 while left <= right:
 mid = (left + right) //2 if arr[mid] == target:
 return mid elif arr[mid] < target:
 left = mid +1 else:
 right = mid -1 return -1

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef is_palindrome(head):
 # 使用快慢指针找到链表的中点 slow, fast = head, head while fast and fast.next:
 slow = slow.next fast = fast.next.next # 将后半段反转 prev = None while slow:
 next_node = slow.next slow.next = prev prev = slow slow = next_node # 比较前后两半是否相等 p1, p2 = head, prev while p2:
 if p1.val != p2.val:
 return False p1 = p1.next p2 = p2.next return True