【MIX】算法题解(20200703)

题目列表

LC 250. 统计同值子树LC 25. K个一组翻转链表LC1499. 满足不等式的最大值LC 1143. 最长公共子序列LC 71. 简化路径LC 72. 编辑距离

LC 250. 统计同值子树

题目链接 本题为树递归问题, 分析树结构可以发现, 叶子节点是同值子树, 非叶子节点如果左右子树均为同值子树, 那么该节点也是同值子树, 设计一个bool类型返回值, 参数为节点和父节点值的函数进行DFS求解. 算法时间复杂度为$\mathcal{O}(n)$，空间复杂度为$\mathcal{O}(1)$.

class Solution: def countUnivalSubtrees(self, root: TreeNode) -> int: ans=0 def dfs(node, pv): if node: lans, rans=dfs(node.left, node.val), dfs(node.right, node.val) nonlocal ans if lans and rans: ans+=1 return node.val==pv else: return False else: return True dfs(root, float('-inf')) return ans

LC 25. K个一组翻转链表

题目链接 按照节点的顺序, 每次翻转$k$个节点, 对剩余节点不足$k$个时进行special judge, 属于链表细节操作题. 建立虚拟头结点dummy，每次翻转k个节点，并将当前指针向前移动k位，在翻转函数revNode(node, k)中，先探测k位， 如果遇到空节点，说明待翻转节点不足k个，直接return. 记录待翻转的最末节点NK和其后节点NKP，进行顺序翻转，返回节点N1. 算法时间复杂度为$\mathcal{O}(n)$，空间复杂度为$\mathcal{O}(1)$.

class Solution: def reverseKGroup(self, head: ListNode, k: int) -> ListNode: if not head or k<=1: return head dummy=ListNode(-1) dummy.next=head prev=dummy def revNode(prev, k): cur, N1=prev, prev.next for i in range(k): # 向前探测k个节点 cur=cur.next if not cur: return cur NK, NKP, p=cur, cur.next, prev cur=p.next while cur != NKP: # 依次翻转k个节点 pnext=cur.next cur.next=p p=cur cur=pnext prev.next=p N1.next=NKP return N1 while prev: prev = revNode(prev, k) return dummy.next

LC1499. 满足不等式的最大值

题目链接 对目标方程展开得到 $$y_i+y_j+|x_i-x_j|=y_i+y_j+x_j-x_i=(x_j+y_j)+(y_i-x_i)$$ 其中满足$i<j$, 因此可以考虑使用单调队列/优先队列/堆求解，对于固定的点$(x_j,y_j)$，需要找到满足$x_j-x_i\le k$的最大$y_i-x_i$的点，对点的$y_i-x_i$属性维持最大值. 算法时间复杂度$\mathcal{O}(n)$, 空间复杂度$\mathcal{O}(n)$(需要维护一个双端队列)

class Solution: def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int: q, ans=[], float('-inf') if not k: return 0 q.append((points[0][0], points[0][1]-points[0][0])) for i in range(1, len(points)): pt=points[i] while q and pt[0]-q[0][0]>k: q.pop(0) if q: ans=max(ans, pt[0]+pt[1]+q[0][1]) while q and pt[1]-pt[0]>=q[-1][1]: q.pop(-1) # 出现的早, 值还小, 离开单调队列 q.append((pt[0], pt[1]-pt[0])) return ans

LC 1143. 最长公共子序列

题目链接 动态规划问题，关键是找到状态转移方程. 定义$f[i][j]$表示text1的前$i$个字符和text2的前$j$个字符匹配，可以推导出转移方程如下 $$\begin{array}{rl}& f[i][j]=f[i-1][j-1]+1text1[i-1]==text2[j-1]\\ & f[i][j]=\max (f[i][j-1],f[i-1][j],f[i-1][j-1])O.W.\end{array}$$

class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: n, m= len(text1), len(text2) f = [[0 for _ in range(m+1)] for _ in range(1+n)] for j in range(1, m+1): for i in range(1, n+1): if text1[i-1]==text2[j-1]: f[i][j]=f[i-1][j-1]+1 else: f[i][j]=max(f[i-1][j], f[i][j-1], f[i-1][j-1]) return f[n][m]

LC 71. 简化路径

题目链接 本题主要使用辅助栈, 对字符路径进行拆分后按照相应的规则进行求解 算法时间复杂度$\mathcal{O}(n)$, 空间复杂度$\mathcal{O}(n)$(需要维护一个栈)

class Solution: def simplifyPath(self, path: str) -> str: st = [] for e in path.split('/'): if e and e!='.' and e!='..': st.append(e) elif st and e=='..': st.pop(-1) return '/'+'/'.join(st)

LC 72. 编辑距离

题目链接 本题是DP问题中的经典题型，主要考虑初始状态的定义和状态转移方程. 定义$f[i][j]$表示word1的前$i$个字符和word2的前$j$个字符的编辑距离，考虑到添加，删除，替换三种状态对应到状态转移方程中 $$\begin{array}{r}f[i][j]=\min (f[i-1][j],f[i][j-1],f[i-1][j-1])+1\end{array}$$ 如果出现word1[i]==word2[j]，则更新$f[i][j]$ $$\begin{array}{r}f[i][j]=\min (f[i-1][j-1],f[i][j])\end{array}$$ 在初始化时，前0个字符和前$i$个字符的编辑距离为$i$，因此有 $$\begin{array}{rl}& f[0][i]=i,i=1,2,\dots ,n\\ & f[j][0]=j,j=1,2,\dots ,m\end{array}$$

class Solution: def minDistance(self, word1: str, word2: str) -> int: n, m= len(word1), len(word2) f=[[0 for _ in range(m+1)] for _ in range(n+1)] for i in range(1, n+1): f[i][0]=i for i in range(1, m+1): f[0][i]=i for i in range(1, n+1): for j in range(1, m+1): f[i][j]=min(f[i-1][j], f[i][j-1], f[i-1][j-1])+1 if word1[i-1]==word2[j-1]: f[i][j]=min(f[i][j], f[i-1][j-1]) return f[n][m]