LeetCode 100 -- Day2
1. 链表：160、206、234、21
（1）160 相交链表
class Solution(object):def getIntersectionNode(self, headA, headB):if not headA or not headB:return Nonelen1,len2 = 0,0a,b = headA,headBwhile a:a=a.nextlen1+=1while b:b=b.nextlen2+=1a,b = headA,headBif len1>=len2:for _ in range(len1-len2):a=a.nextelse:for _ in range(len2-len1):b=b.nextwhile a!=b:a=a.nextb=b.nextreturn a优化方案：
p = headAq = headBwhile p!=q:p=p.next if p else headBq=q.next if q else headAreturn p（2）206 反转链表
class Solution(object):def reverseList(self, head):if not head:returnstack=[]p=headwhile p:stack.append(p) p=p.next""" 栈顶元素是新的头节点 """head=stack.pop() p=headwhile stack:p.next=stack.pop()p=p.next""" 尾节点的next置空 """p.next=None return head迭代法：
pre=Nonep=headwhile p:q=p.nextp.next=prepre=pp=qreturn pre（3）234 回文链表
快慢指针寻找中点 + 反转后半部分链表
class Solution(object):def isPalindrome(self, head):""" 找到链表中点 """slow,fast = head,headwhile fast and fast.next:slow=slow.nextfast=fast.next.next""" 反转后半段链表 """reversed_head=Nonewhile slow:q=slow.nextslow.next=reversed_headreversed_head=slowslow=qwhile reversed_head:if head.val!=reversed_head.val:return Falsereversed_head=reversed_head.nexthead=head.nextreturn True（4）21 合并有序链表
创建一个哨兵节点（dummy node），它的next指向合并后链表的头节点
class Solution(object):def mergeTwoLists(self, list1, list2):dummy=ListNode(0)p=dummywhile list1 and list2:if list1.val<=list2.val:p.next=list1list1=list1.nextelse:p.next=list2list2=list2.nextp=p.nextif list1: p.next=list1if list2: p.next=list2return dummy.next2. 图：200、994
（1）200 岛屿数量
from collections import deque
class Solution(object):def numIslands(self, grid):m,n = len(grid),len(grid[0])directions=[(0,1),(0,-1),(1,0),(-1,0)]island=0for i in range(m):for j in range(n):## 是未发现的新陆地if grid[i][j]=='1': island+=1## 找当前陆地连接的其他陆地（整个连通分量）quene=deque()quene.append((i,j))grid[i][j]='0' ## 当前陆地已访问 → 变成水while quene:row,col = quene.popleft()for dr,dc in directions:next_row, next_col = row+dr, col+dc""" 上下左右四个方向如果是符合范围的陆地：## 1.标记已访问（不是新的岛屿，只是加入当前岛屿的陆地）## 2.入队（继续找连通分量）"""if 0<=next_row<m and 0<=next_col<n and grid[next_row][next_col]=='1':grid[next_row][next_col]='0'quene.append((next_row,next_col))return island（2）994 腐烂的橘子
from collections import deque
class Solution(object):def orangesRotting(self, grid):time=-1fresh=0quene=deque()m,n = len(grid),len(grid[0])directions=[(0,1),(0,-1),(1,0),(-1,0)]for i in range(m):for j in range(n):if grid[i][j]==1:fresh+=1elif grid[i][j]==2:quene.append((i,j))if fresh==0: return 0while quene:for _ in range(len(quene)):cur_row,cur_col = quene.popleft()for dr,dc in directions:next_row,next_col = cur_row+dr,cur_col+dcif 0<=next_row<m and 0<=next_col<n and grid[next_row][next_col]==1:fresh-=1grid[next_row][next_col]=2quene.append((next_row,next_col))time+=1return time if fresh==0 else -13. 贪心算法：55、45
（1）55 跳跃游戏
class Solution(object):def canJump(self, nums):max_reach=0for i,num in enumerate(nums):""" max_reach无法支撑走到位置i → 直接失败 """if i>max_reach: return False""" 如果当前位置跳跃达到的最远位置比当前max_reach远 → 更新max_reach """max_reach=max(max_reach, i+num)if max_reach>=len(nums)-1:return Truereturn True（2）55 跳跃游戏②
class Solution(object):def jump(self, nums):n=len(nums)step=0cur_end=0max_reach=0for i in range(n-1):max_reach = max(max_reach, i+nums[i])""" 当前位置到达目前最远处的边界:1.必须要往前跳step++2.最远边界更新为当前位置能到达的最远处max_reach """if i==cur_end:step+=1cur_end=max_reach""" 当前最远边界已超过给定位置(n-1)，说明跳到现在就已经ok了 """if cur_end>=n-1:breakreturn step贪心vs动规的一点心得：
（1）贪心：现在 → 未来，做出当前最优选择，不考虑后续的影响
def greedy():sort() # 通常需要先排序current = initial_state # 当前状态for item in items: # 单次遍历if can_make_decision(current, item):current = make_decision(current, item) # 做出局部最优决策return current（2）动规：未来 → 现在，通过目标反推当前，定义状态转移方程
def dp():memo = [0]*n # 状态存储（记忆化）dp[0] = base_case # 基础状态for i in range(1, n):for j in range(i): # 考虑所有可能的前驱状态# 状态转移方程（核心）dp[i] = max/min(dp[i], dp[j] + transition_cost) return dp[n-1] # 返回最终状态