PDD
最長公共子序列
1143-最長公共子序列
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:"""二維動態規劃"""m, n = len(text1), len(text2)# dp = [[0]* (n+1)] * (m+1) 這種寫法錯誤，m+1行會共享存儲dp = [[0] * (n + 1) for _ in range(m + 1)]print('dp2', len(dp), len(dp[0]))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] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])return dp[-1][-1]
島嶼數量
200-島嶼數量
class Solution:def numIslands(self, grid: List[List[str]]) -> int:"""遇到1，深度優先搜索（遞歸遍歷上下左右 類比二叉樹），搜索到后置為0 防止再次搜索"""def dfs(grid, i, j):if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == '0':returngrid[i][j] = '0'dfs(grid, i-1, j)dfs(grid, i, j-1)dfs(grid, i, j+1)dfs(grid, i+1, j)cnt = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == '1':dfs(grid, i, j)cnt += 1return cntx的平方根
69-x的平方根
class Solution:def mySqrt(self, x: int) -> int:"""二分查找"""left, right = 0, xwhile left <= right:mid = (left + right) // 2if mid * mid <= x:left = mid + 1else:right = mid - 1else:mid = (left + right) // 2return mid
智譜
氣溫變化趨勢
LCP 61. 氣溫變化趨勢
class Solution:def temperatureTrend(self, temperatureA: List[int], temperatureB: List[int]) -> int:def trans(t1, t2):"""獲取趨勢"""if t2 > t1:return '+'elif t2 == t1:return '0'else:return '-'occ_cnt, max_occ = 0, 0for i in range(1, len(temperatureA)):if trans(temperatureA[i-1], temperatureA[i]) == trans(temperatureB[i-1], temperatureB[i]):occ_cnt += 1else:max_occ = max(max_occ, occ_cnt)occ_cnt = 0max_occ = max(max_occ, occ_cnt)return max_occ
數組創建二叉樹
from typing import List, Optionalclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef array_to_btree(arr: List[Optional[int]], index: int = 0) -> Optional[TreeNode]:"""遞歸地將數組轉換為二叉樹。:param arr: 包含樹節點值的列表，其中 None 代表空節點。:param index: 當前索引，默認從0開始。:return: 二叉樹的根節點。"""if index >= len(arr):return Noneroot = TreeNode(arr[index])root.left = array_to_btree(arr, 2 * index + 1)root.right = array_to_btree(arr, 2 * index + 2)return rootdef preorder_traversal(root: Optional[TreeNode]):"""前序遍歷二叉樹"""if root:print(root.val, end=" ")preorder_traversal(root.left)preorder_traversal(root.right)# 示例數組，表示按層序遍歷的二叉樹
arr = [1, 2, 3, 4, 5, 6, 7]
tree_root = array_to_btree(arr)
print("前序遍歷結果:")
preorder_traversal(tree_root)# 棧
def array_to_btree(arr: List[Optional[int]]) -> Optional[TreeNode]:"""使用棧將數組轉換為二叉樹。:param arr: 包含樹節點值的列表，其中 None 代表空節點。:return: 二叉樹的根節點。"""if not arr:return Noneroot = TreeNode(arr[0])stack = [(root, 0)]while stack:node, index = stack.pop()left_index, right_index = 2 * index + 1, 2 * index + 2if left_index < len(arr) and arr[left_index] is not None:node.left = TreeNode(arr[left_index])stack.append((node.left, left_index))if right_index < len(arr) and arr[right_index] is not None:node.right = TreeNode(arr[right_index])stack.append((node.right, right_index))return root
蝦皮
多頭自注意力
import torch
import torch.nn as nnclass MultiHeadSelfAttention(nn.Module):def __init__(self, embed_dim, num_heads, dropout=0.1):super(MultiHeadSelfAttention, self).__init__()assert embed_dim % num_heads == 0, "Embedding dimension must be divisible by number of heads"self.num_heads = num_headsself.head_dim = embed_dim // num_headsself.scale = self.head_dim ** 0.5# Linear layers for query, key, and valueself.qkv = nn.Linear(embed_dim, embed_dim * 3)self.out = nn.Linear(embed_dim, embed_dim)self.dropout = nn.Dropout(dropout)def forward(self, x):batch_size, seq_len, embed_dim = x.size()# Generate Q, K, V from inputqkv = self.qkv(x) # (batch_size, seq_len, embed_dim * 3)qkv = qkv.view(batch_size, seq_len, 3, self.num_heads, self.head_dim)q, k, v = qkv.permute(2, 0, 3, 1, 4) # (3, batch_size, num_heads, seq_len, head_dim)# Scaled dot-product attentionscores = torch.matmul(q, k.transpose(-2, -1)) / self.scale # (batch_size, num_heads, seq_len, seq_len)attn = torch.softmax(scores, dim=-1)attn = self.dropout(attn)out = torch.matmul(attn, v) # (batch_size, num_heads, seq_len, head_dim)out = out.permute(0, 2, 1, 3).contiguous() # (batch_size, seq_len, num_heads, head_dim)out = out.view(batch_size, seq_len, -1) # (batch_size, seq_len, embed_dim)# Final linear projectionout = self.out(out)return out# 示例
batch_size = 2
seq_len = 4
embed_dim = 32
num_heads = 4x = torch.randn(batch_size, seq_len, embed_dim)
attention = MultiHeadSelfAttention(embed_dim, num_heads)
output = attention(x)print("Input shape:", x.shape)
print("Output shape:", output.shape)
