- 逆向思维（如链表反着排，树反着遍历，从逆向条件开始搜寻）
题目 medium
You are given two non-empty linked listsrepresenting two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
分析
一道非常简单的题目。由于题目已经将输入逆序（个位最前，十位其次，。。。），故不需要使用递归算法或栈结构，直接迭代数据即可。
每次计算相同的位，当两数之和大于9时需要进位，迭代全部位数即可。
技巧
由于涉及到两个链表的操作，设置一个头结点是非常方便的，可以统一的对链表进行操作。
官方solution
题解
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
dummy_head = ListNode(0) #哑的头结点
cur_l1, cur_l2, cur_res = l1, l2, dummy_head
carry = 0 #进位
while cur_l1 is not None or cur_l2 is not None or carry != 0:
x = cur_l1.val if cur_l1 else 0
y = cur_l2.val if cur_l2 else 0
sum_val = x + y + carry
carry = sum_val / 10
cur_res.next = ListNode(sum_val % 10)
cur_res = cur_res.next
if cur_l1 is not None: cur_l1 = cur_l1.next
if cur_l2 is not None: cur_l2 = cur_l2.next
return dummy_head.next题目 medium
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
分析
与第二题唯一不同点在于这道题的链表顺序是逆序的，因此不能直接遍历。在这道题中，由于两链表长度不一定相同，使用递归方法不方便控制。可采用栈来进行处理，将两链表分别存储到两个栈中，再遍历栈顶处理。
官方solution
题解
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
dummy_head = ListNode(0) #哑的头结点
p_stack, q_stack = [], [] #栈
while l1 is not None:
p_stack.append(l1.val)
l1 = l1.next
while l2 is not None:
q_stack.append(l2.val)
l2 = l2.next
carry = 0
while len(p_stack) or len(q_stack) or carry:
x = p_stack[-1] if len(p_stack) else 0
y = q_stack[-1] if len(q_stack) else 0
sum_val = x + y + carry
carry = sum_val // 10
cur_node = ListNode(sum_val % 10)
cur_node.next = dummy_head.next
dummy_head.next = cur_node
if len(p_stack): p_stack.pop()
if len(q_stack): q_stack.pop()
return dummy_head.next题目 medium
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
分析
由于是链式存储，且移动操作不会导致两段内部的顺序打乱，因此只需要找到链表打断的位置。也就是找到新链表的最后一个节点，和第一个节点，重置它们的next指针即可。
算法如下
- 计算链表长度
n和真实移动距离k % n - 找到新链表最后一个节点，它的next即为新链表的第一个节点（注意，这里的链表视作一个循环链表）。
- 重置二者指针。
class Solution(object):
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if head is None or head.next is None:
return head
original_last, new_last = head, head
length = 1
while original_last.next is not None:
length += 1
original_last = original_last.next
for i in range(length - (k % length) - 1):
new_last = new_last.next
original_last.next = head #do rotation
new_head = new_last.next if new_last.next else head
new_last.next = None
return new_head性能
题目 hard
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
分析
虽然被标为hard难度，但其实并不是太难。只是在多个不同区间上对链表进行reverse。需要注意的一点是，由于是链式存储，因此需要将各个reverse后的部分用指针连接起来。reverse可以采用迭代或递归两种方法求解。
算法如下
- 对每个区段的链表进行reverse，这里应该写成一个函数，并返回最后一个（新first）元素，用于进行链表连接。
- 对每个区段重复执行上述过程，并连接各个区段
class Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if head is None:
return None
new_head = self.sub_reverse_iteration(head,k)
last_tail, sub_head = head, head.next
while sub_head is not None:
new_sub_head = self.sub_reverse_iteration(sub_head,k)
last_tail.next = new_sub_head
last_tail, sub_head = sub_head, sub_head.next
return new_head
def sub_reverse_iteration(self,head,k):
"""
reverse given linked-list 'head' top-k elements, and return the new head node.
iterative version
"""
## Calculate the length of given list.
length = 0
p = head
while p is not None:
p = p.next
length += 1
if length < k or length == 1: # less than k or equal one, just return
return head
first, middle, last = head, head.next, head.next.next # last may be None
while middle is not None and k > 1: #start reverse, After that, middle is the new head and head is the new tail
middle.next = first
first = middle
middle = last
last = last.next if last else None
k -= 1
head.next = middle # for next function. just a temp pointer
return first另一种逆转链表算法
前文所述的链表逆转算法如图。
每次将first和middle逆置位置，由于middle指针指向first，因此需要保存last使之不被丢失。每次整个方框向前移动一个，直到middle为None为止。
另一种方法如下
在前面插入一个dummy head用于平凡化头节点，依次遍历节点，并将该节点(temp)插入尾节点后面。充分利用了链表随意插入的特性。
class Solution2(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if head is None or head.next is None or k < 2:
return head
dummy_head = ListNode(0)
dummy_head.next = head
head, tail, temp = dummy_head, dummy_head, None
count = 0
while tail is not None:
for count in range(k):
tail = tail.next
if tail is None:
break
else:
original_head = head.next
for count in range(k-1):
temp = head.next
head.next = temp.next
temp.next = tail.next
tail.next = temp
tail = original_head
head = original_head
return dummy_head.next题目 hard
Merge k sorted linked lists and return it as one sorted list.
分析
有多种方法可以解此题目，其中一种是依次比对k个链表的第一个元素的大小，并取其中最小的元素。
技巧
使用优先队列或堆来每次获取最小的元素
算法如下
from Queue import PriorityQueue
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
dummy_head = ListNode(0)
cur_head = dummy_head
nodes_pq = PriorityQueue()
for head in lists:
if head:
nodes_pq.put((head.val, head))
while nodes_pq.qsize() > 0:
node = nodes_pq.get()[1]
cur_head.next = node
cur_head = cur_head.next
node = node.next
if node: nodes_pq.put((node.val,node))
return dummy_head.next官方solution 在官方Solution中列举了四种解法。包括采用数组排序，两两merge链表，以及分治法merge链表
- 构造dummy head是平凡化头节点的有力方式，可以较好地简化算法。
- 链表的精髓即在于链式的存储，可以非常方便的更改结构
- 逆置链表的一个有力方式是依次把元素插在尾节点后面。
- 当需要按顺序取元素时，使用一个优先队列或者堆是一种好的方法
- 当需要对K个任务执行相似的操作时，两两依次是一种方式，而分治法则格外适合优化这种情况。
题目 hard
Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3}
return [3,2,1].
分析
需标识访问栈的次数
官方solution 在官方solution中，使用了一种不同的思路。与本解不同，官方solution中，同时使用一个指针和栈来进行状态存储，指针指向现在访问的节点，而栈则是历史信息，该解法更加符合递归式的工作流程，可以以一个通用的框架来书写三种遍历方式。本解法则完全依赖栈来提供全部信息
技巧（重要）
- 针对后序遍历时，反过来输出，即左右中变为中右左
- 用指针指向当前状态，用栈来保存旧状态的表达力可能更强。
题解
def postorder(tree):
node_s, traversal = [], []
while tree is not None:
node_s.append((tree,0))
tree = tree.left
while len(node_s) > 0:
n, tag = node_s.pop()
if tag == 0:
node_s.append((n,1))
if n.right:
n = n.right
while n is not None:
node_s.append((n,0))
n = n.left
else:
traversal.append(n.val)
return traversal迭代式先序遍历
先序遍历中，先访问当前节点，再访问左子树，最后访问右子树。使用一个栈来保存将要访问的节点，先将右儿子入栈，再将左儿子入栈，每次出栈时先访问它，再执行儿子入栈操作。
def preorder(tree):
node_s, traversal = [tree], []
while len(node_s) > 0:
n = node_s.pop()
traversal.append(n.val)
if n.right: node_s.append(n.right)
if n.left: node_s.append(n.left)
return traversal迭代式中序遍历
中序遍历中，先访问左子树，再访问当前节点，最后访问右子树。因此先将根节点及其所有左子树入栈。然后依次出栈，访问之，并将右儿子入栈。入栈右儿子时，将其所有左子树入栈。这样做使得可以区分顺序。
def inorder(tree):
node_s, traversal = [], []
while tree is not None:
node_s.append(tree)
tree = tree.left
while len(node_s): #Start travesal
n = node_s.pop()
traversal.append(n.val)
if n.right:
n = n.right
while n is not None:
node_s.append(n)
n = n.left
return traversal题目 easy
Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
分析
由于是BST，因此中序遍历可以获得递增序列。该题只需要逆转中序遍历每个节点，加上比该节点大的量即可。
算法如下
'''
Recursive
'''
class Solution(object):
def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
self.greater_sum = 0
self.core(root)
return root
def core(self,root):
if root is None:
return None
else:
self.core(root.right)
root.val += self.greater_sum
self.greater_sum = root.val
self.core(root.left)
return
'''
Iterative
'''
class Solution2(object):
def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
nodes_s = []
greater_sum = 0
curr = root
while len(nodes_s) or curr:
if curr:
nodes_s.append(curr)
curr = curr.right
else:
curr = nodes_s.pop()
curr.val += greater_sum
greater_sum = curr.val
curr = curr.left
return root题目 middle
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
分析
两种解法：
- 按照BST的定义，左子树的最大值< val < 右子树最小值。递归求解。后序遍历
- 一个合法的BST，其中序遍历的序列应当是递增的，利用此性质，中序遍历该树，实时判断序列是否递增。
技巧
利用好BST的性质
算法如下
class Solution1 (object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
self.is_valid = True
self.valid(root)
return self.is_valid
def valid(self,root):
if not root:
return None, None
left_min, left_max = self.valid(root.left)
right_min, right_max = self.valid(root.right)
legal_min, legal_max = root.val, root.val
if root.left:
if left_max >= root.val:
self.is_valid = False
legal_min = left_min
if root.right:
if right_min <= root.val:
self.is_valid = False
legal_max = right_max
return legal_min, legal_max
Solution2
'''递归式'''
class Solution2(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
self.pre = None
return self.valid(root)
def valid(self,root):
if root:
if not self.valid(root.left):
return False
if self.pre is not None and self.pre >= root.val:
return False
self.pre = root.val
if not self.valid(root.right):
return False
return True
'''迭代式'''
class Solution3(object):
'''iterative'''
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
nodes_q = []
curr, pre = root, None
while len(nodes_q) or curr:
if curr:
nodes_q.append(curr)
curr = curr.left
else:
curr = nodes_q.pop()
if pre and pre.val >= curr.val:
return False
pre = curr
curr = curr.right
return True题目 middle
Given a complete binary tree, count the number of nodes.
分析
两种解法：
- 后序遍历二叉树，遍历过程中记录二叉树最大深度，并找叶子节点，记录叶子结点数目。当找到叶子节点的深度小于最大深度时停止遍历。计算得到完全二叉树的节点个数。 时间复杂度O(N)
- 二分法。首先判断该树是否为满二叉树，即是否满足以下公式$$height(left_tree)=height(right_tree)$$
若该树为满二叉树，则直接计算节点个数。否则递归的分别两个子树。
NodeCount = 1 + NodeCount(left) + NodeCount(right)
时间复杂度为$O((\log N)^2)$
算法如下
class Solution(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.max_depth = 0
self.leaf_count = 0
self.count(root,0)
return 2 ** self.max_depth + self.leaf_count - 1
def count(self,root,depth):
if root:
if self.count(root.left,depth+1):
return True
if self.count(root.right,depth+1):
return True
if not root.left and not root.right: #leaf
if depth < self.max_depth:
return True
self.leaf_count += 1
self.max_depth = depth
class Solution2(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
l, r = root, root
lh, rh = 0, 0
while l is not None:
lh += 1
l = l.left
while r is not None:
rh += 1
r = r.right
if lh == rh:
return 2 ** lh - 1
return 1 + self.countNodes(root.left) + self.countNodes(root.right)题目 middle
Given a binary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level).
Given binary tree [3,9,20,null,null,15,7],
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
分析
- 层次遍历二叉树，使用一个队列来记录将要访问的节点。每次访问一个节点，将其左右孩子入队。由于题目要求，入队时需要保存该节点所处的depth。
- 另一个思路不需要保存depth，而是记录下当前节点的个数（队列长度），并在遍历队列时做一个内层循环，访问全部当前层的节点。例如，首先将root入队，然后循环取出1个元素，将其2个孩子队列，然后循环取出2个元素，将其最多4个孩子入队。。。一次内层循环将访问全部一层节点。
算法如下
from collections import deque
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
nodes_q, traversal = deque(), []
if root: nodes_q.append((root,0))
max_depth = -1
while nodes_q:
curr, depth = nodes_q.popleft()
if depth > max_depth:
max_depth = depth
traversal.append([])
traversal[depth].append(curr.val)
if curr.left: nodes_q.append((curr.left,depth+1))
if curr.right: nodes_q.append((curr.right,depth+1))
return traversal题目 easy
Given a binary tree, return the bottom-up level order traversal of its nodes values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree [3,9,20,null,null,15,7],
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
分析
该题只需要反向上一题的结果列表即可。在此不列出程序源码
题目 middle
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
分析
该题的遍历顺序是先序遍历，难点在于需要原地改变结构，且连接均位于右子树上。设置一个全局量为当前最后一个节点，然后将访问的节点连接在这个节点的右节点上。
算法如下
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
if not root:
return
self.curr = root
right = root.right
if root.left:
self.curr.right = root.left
self.flatten(root.left)
root.left = None
if right:
self.curr.right = right
self.flatten(right)题目 easy
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
分析
审题很重要！！ 这道题目要求的是从根节点到叶子节点。用递归易解此题。是叶子节点时，判断是否sum值等于该节点值，否则向左右节点传递这一Path
算法如下
class Solution(object):
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
if not root:
return False
if not root.left and not root.right and sum == root.val:
return True
if self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val):
return True
return False题目 hard
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
分析
注意审题，除path最顶点外，path上的点都只能选择一个孩子前进。
这道题目可以采用后序遍历的方法来做。保持一个全局量用于保存已经出现过的最大的路径和。然后再确定是否值要向上传递。显而易见，若该节点所在的路径（从下往上）可得到的最大加和小于零，那这条路径是没有必要向上传递的，因此只往上传递0。
需要注意的点是，路径上不能形成分叉树，，而最大值计算的却可以，故当前最大加和计算的是left+right+curr，而向上传递的只能是left+curr，right+curr和0中的最大值。
算法如下
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.max_sum = None
self.maxPathSumRecursive(root)
return self.max_sum
def maxPathSumRecursive(self,root):
if not root: return 0
left = self.maxPathSumRecursive(root.left)
right = self.maxPaumRecursive(root.right)
if self.max_sum is None:
self.max_sum = left + right + root.val
self.max_sum = max(self.max_sum, left + right + root.val)
return max(0, root.val + max(left,right))性能
- 善于利用性质，如BST的中序遍历是一个递增序列。
- 考虑使用二分法
题目 middle
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
Input:
[[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.
分析
使用并查集解此题即可
算法如下
class Solution(object):
def hasPathSum(self, root, sum):
"""
:type M: List[List[int]]
:rtype: int
"""
count, ufs, rank = len(M), list(range(len(M))), [0 for i in range(len(M))]
for i in range(count):
for j in range(i+1, count):
if M[i][j]:
# do union
i_p, j_p = i, j
while ufs[i_p] != i_p: i_p = ufs[i_p]
while ufs[j_p] != j_p: j_p = ufs[j_p]
ufs[i_p] = j_p
# do compress(not the standard, directly point to j_p)
i_t, j_t = i, j
while ufs[i_t] != i_t: i_t, ufs[i_t] = ufs[i_t], j_p
while ufs[j_t] != j_t: j_t, ufs[j_t] = ufs[j_t], j_p
return sum(idx == parent for idx, parent in enumerate(ufs))题目 middle
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110
11010
11000
00000
Answer: 1
分析
使用DFS解此题较为方便，也可使用并查集。思路类似
算法如下
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
self.visited = [[0 for j in range(len(grid[0]))] for i in range(len(grid))]
self.grid = grid
count = 0
for x in range(len(grid)):
for y in range(len(grid[0])):
if self.grid[x][y] == '1' and not self.visited[x][y]:
count += 1
self.dfs(x, y)
print(self.visited)
return count
def dfs(self, x, y):
dx, dy = (0, 0, -1, 1), (-1, 1, 0, 0)
for d in range(4):
tx, ty = x + dx[d], y + dy[d]
if 0 <= tx < len(self.grid) and 0 <= ty < len(self.grid[0]):
if self.grid[tx][ty] == '1' and not self.visited[tx][ty]:
self.visited[tx][ty] = 1
self.dfs(tx, ty)题目 middle
Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
分析
该题可使用并查集解，没有围绕的事实上就是处于边界的O，找到这些边界O及其连接的O即可。同样的，可使用DFS或BFS解
技巧
逆向思考。既然找没有围绕的更容易，就应该从边界开始找，而不是最后找到来判断是否在边界！！！
算法如下
class UFS:
'''
Path compress and connect by rank
'''
def __init__(self, size):
self.ufs = [i for i in range(size)]
self.rank = [0 for i in range(size)]
def find(self, x):
# find ancestor and do path compressing
px = self.ufs[x]
while px != self.ufs[px]:
px = self.ufs[px]
tx = x
while tx != px:
tx, self.ufs[tx] = self.ufs[tx], px
return px
def connect(self, x, y):
px = self.find(x)
py = self.find(y)
if px != py:
if self.rank[px] > self.rank[py]:
self.ufs[py] = px
else:
self.ufs[px] = py
if self.rank[px] == self.rank[py]:
self.rank[py] += 1
def isConnected(self, x, y):
return self.find(x) == self.find(y)
class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not board:
return
xmax, ymax = len(board[0]), len(board)
ufs = UFS(ymax * xmax + 1)
dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)
for y in range(ymax):
for x in range(xmax):
if board[y][x] == 'O':
for d in range(4):
ty, tx = y + dy[d], x + dx[d]
if ty < 0 or ty >= ymax or tx < 0 or tx >= xmax:
try:
ufs.connect(y * xmax + x, ymax * xmax)
except:
return
break
elif board[ty][tx] == 'O':
ufs.connect(y * xmax + x, ty * ymax + tx)
# do Draw
for y in range(ymax):
new_string = []
for x in range(xmax):
if board[y][x] == 'O' and not ufs.isConnected(y * xmax + x, ymax * xmax):
new_string.append('X')
else:
new_string.append(board[y][x])
board[y] = "".join(new_string)题目 middle
In this problem, a tree is an undirected graph that is connected and has no cycles.
The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.
Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v.
Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
1
/ \
2 - 3
分析
当出现环路时，即为多余边。使用并查集解此题
算法如下
class Solution(object):
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
ufs = list(range(len(edges)))
for (x, y) in edges:
px, py = ufs[x-1], ufs[y-1]
while px != ufs[px]: px = ufs[px]
while py != ufs[py]: py = ufs[py]
if px == py:
return (x,y)
ufs[px] = py
tx, ty = x-1, y-1
while ufs[tx] != py: ufs[tx], tx = py, ufs[tx]
while ufs[ty] != py: ufs[ty], ty = py, ufs[ty] 性能
- 逆向思维很重要！！
- 并查集是一种高效判别归属的数据结构