Add files via upload

linwt · web-flow · commit 928806ff1146 · 2018-11-28T18:52:03.000+08:00
diff --git a/leetcode/007.反转整数.py b/leetcode/007.反转整数.py
@@ -0,0 +1,13 @@
+# 直接判断正负两种情况
+class Solution(object):
+    def reverse(self, x):
+        x = -int(str(x)[::-1][:-1]) if x<0 else int(str(x)[::-1])
+        return x if abs(x)<0x7FFFFFFF else 0
+        # return x if -2**31<=x<=2**31-1 else 0
+
+# 标记正负两种情况
+class Solution(object):
+    def reverse(self, x):
+        sign = 1 if x>0 else -1
+        x = sign * int(str(abs(x))[::-1])
+        return x if abs(x)<0x7FFFFFFF else 0
diff --git a/leetcode/669.修剪二叉搜索树.py b/leetcode/669.修剪二叉搜索树.py
@@ -0,0 +1,15 @@
+# 从根节点开始，若根节点在给定范围左侧，那么他和他的左子树完全裁剪；
+# 若根节点在给定范围右侧，那么他和他的右子树完全裁剪；
+# 若根节点在给定范围内，不用裁剪，按照递归分别推出他左右子树的裁剪结果。
+class Solution(object):
+    def trimBST(self, root, L, R):
+        if not root:
+            return
+        elif root.val < L:
+            return self.trimBST(root.right, L, R)
+        elif root.val > R:
+            return self.trimBST(root.left, L, R)
+        else:
+            root.left = self.trimBST(root.left, L, R)
+            root.right = self.trimBST(root.right, L, R)
+        return root
diff --git a/leetcode/671.二叉树中第二小的节点.py b/leetcode/671.二叉树中第二小的节点.py
@@ -0,0 +1,15 @@
+# 由题可知，根结点是最小的结点，则左右子树中节点值不等于根节点值的所有节点中，值最小的即为第二小的值
+class Solution(object):
+    def findSecondMinimumValue(self, root):
+        if not root or not root.left:
+            return -1
+        return self.find(root, root.val)
+
+    def find(self, root, minVal):
+        if not root.left:
+            return -1 if root.val == minVal else root.val
+        leftMin = self.find(root.left, minVal)
+        rightMin = self.find(root.right, minVal)
+        if leftMin == -1 or rightMin == -1:
+            return max(leftMin, rightMin)
+        return min(leftMin, rightMin)
diff --git a/leetcode/684.冗余连接.py b/leetcode/684.冗余连接.py
@@ -0,0 +1,18 @@
+# 寻根，当一条边让数组内构成循环，则删除该边
+class Solution(object):
+    def findRedundantConnection(self, edges):
+        tree = [-1] * (len(edges) + 1)
+        for edge in edges:
+            a = self.findRoot(edge[0], tree)
+            b = self.findRoot(edge[1], tree)
+            if a != b:
+                tree[a] = b
+            else:
+                return edge
+
+    def findRoot(self, x, tree):
+        if tree[x] == -1:
+            return x
+        root = self.findRoot(tree[x], tree)
+        tree[x] = root
+        return root
diff --git a/leetcode/685.冗余连接II.py b/leetcode/685.冗余连接II.py
@@ -0,0 +1,33 @@
+class Solution(object):
+    def findRedundantDirectedConnection(self, edges):
+        def find(x, tree):
+            if tree[x] == -1:
+                return x
+            root = find(tree[x], tree)
+            tree[x] = root
+            return root
+
+        # 用 count 来计数不合法的边
+        count = 0
+        res = []
+        tree = [-1] * (len(edges)+1)
+        # 第一轮查找不合法的边（正序）
+        for parent, child in edges:
+            # child已经有parent 或 child的parent的parent（或者一直往上找）就是 child 本身
+            if tree[child] != -1 or find(parent, tree) == child:
+                res = [parent, child]
+                count += 1
+            else:
+                tree[child] = parent
+        # 如果只有一条不合法的边，直接返回
+        if count == 1:
+            return res
+
+        # 要求返回最后一条边，重置 tree 并开始第二轮查找（逆序）
+        tree = [-1] * (len(edges)+1)
+        for parent, child in edges[::-1]:
+            if tree[child] != -1 or find(parent, tree) == child:
+                return [parent, child]
+            else:
+                tree[child] = parent
+        return res
diff --git a/leetcode/687.最长同值路径.py b/leetcode/687.最长同值路径.py
@@ -0,0 +1,21 @@
+class Solution(object):
+
+    def __init__(self):
+        self.maxLen = 0
+
+    def longestUnivaluePath(self, root):
+        if not root:
+            return 0
+        self.getMaxLen(root, root.val)
+        return self.maxLen
+
+    # 由左右最长同值路径相加
+    def getMaxLen(self, root, val):
+        if not root:
+            return 0
+        left = self.getMaxLen(root.left, root.val)
+        right = self.getMaxLen(root.right, root.val)
+        self.maxLen = max(self.maxLen, left + right)
+        if root.val == val:
+            return max(left, right) + 1
+        return 0
diff --git a/leetcode/700.二叉搜索树中的搜索.py b/leetcode/700.二叉搜索树中的搜索.py
@@ -0,0 +1,11 @@
+# 左边结点都比根结点小，右边结点都比根结点大
+class Solution(object):
+    def searchBST(self, root, val):
+        if not root:
+            return
+        if root.val == val:
+            return root
+        elif root.val > val:
+            return self.searchBST(root.left, val)
+        else:
+            return self.searchBST(root.right, val)
diff --git a/leetcode/701.二叉搜索树中的插入操作.py b/leetcode/701.二叉搜索树中的插入操作.py
@@ -0,0 +1,23 @@
+class Solution(object):
+    def insertIntoBST(self, root, val):
+        if not root:
+            return TreeNode(val)
+        if val < root.val:
+            root.left = self.insertIntoBST(root.left, val)
+        if val > root.val:
+            root.right = self.insertIntoBST(root.right, val)
+        return root
+
+################## 递归思路 #################
+# 方法作用极简化：先判断无结点和1个结点的情况
+# 方法作用描述：参数给一个根和值，将该值的结点插入到根的左右孩子，然后返回插入后的根结点
+# 递归：由于左右孩子有同样需求，给定值结点部分使用递归得到插入后的根结点，将返回结果赋给根结点的左右孩子
+class Solution(object):
+    def insertIntoBST(self, root, val):
+        if not root:
+            return TreeNode(val)
+        if val < root.val:
+            root.left = TreeNode(val)
+        if val > root.val:
+            root.right = TreeNode(val)
+        return root
diff --git a/leetcode/707.设计链表.py b/leetcode/707.设计链表.py
@@ -0,0 +1,29 @@
+# 用数组模拟
+class MyLinkedList(object):
+
+    def __init__(self):
+        self.arr = []
+
+    def get(self, index):
+        if index > len(self.arr)-1 or index < 0:
+            return -1
+        return self.arr[index]
+
+    def addAtHead(self, val):
+        self.arr.insert(0, val)
+
+    def addAtTail(self, val):
+        self.arr.append(val)
+
+    def addAtIndex(self, index, val):
+        if index == len(self.arr):
+            self.arr.append(val)
+        elif index > len(self.arr) or index < 0:
+            return
+        else:
+            self.arr.insert(index, val)
+
+    def deleteAtIndex(self, index):
+        if index > len(self.arr)-1 or index < 0:
+            return
+        self.arr.pop(index)
diff --git a/leetcode/725.分隔链表.py b/leetcode/725.分隔链表.py
@@ -0,0 +1,25 @@
+class Solution(object):
+    def splitListToParts(self, root, k):
+        # 计算链表长度
+        count = 0
+        head = root
+        while head:
+            count += 1
+            head = head.next
+
+        # nums代表每组的长度，rem代表前面几组可以再加1个结点
+        nums = count/k
+        rem = count%k
+        res = []
+        for _ in range(k):
+            head = h = ListNode(0)
+            for _ in range(nums):
+                head.next = ListNode(root.val)
+                head = head.next
+                root = root.next
+            if rem:
+                head.next = ListNode(root.val)
+                root = root.next
+                rem -= 1
+            res.append(h.next)
+        return res
diff --git a/leetcode/814.二叉树剪枝.py b/leetcode/814.二叉树剪枝.py
@@ -0,0 +1,21 @@
+class Solution(object):
+    def pruneTree(self, root):
+        if not root:
+            return
+        root.left = self.pruneTree(root.left)
+        root.right = self.pruneTree(root.right)
+        if not root.left and not root.right and root.val == 0:
+            return
+        return root
+
+################## 递归思路 #################
+# 方法作用极简化：先判断无结点和1个结点的情况
+# 方法作用描述：参数给一个结点，如果结点为0则返回空，即剪掉该结点，否则返回该结点
+# 递归：由于左右孩子有同样需求，使用递归，然后将返回结果赋给根结点的左右孩子
+class Solution(object):
+    def pruneTree(self, root):
+        if not root:
+            return
+        if root.val == 0:
+            return
+        return root
diff --git a/leetcode/817.链表组件.py b/leetcode/817.链表组件.py
@@ -0,0 +1,10 @@
+# 将G的元素放入Set，遍历head，若遇到一个元素在Set中并且下一个元素为空或者不在Set中，则将组件个数加1
+class Solution(object):
+    def numComponents(self, head, G):
+        count = 0
+        g = set(G)
+        while head:
+            if head.val in g and (not head.next or head.next.val not in g):
+                count += 1
+            head = head.next
+        return count
diff --git a/leetcode/834.树中距离之和.py b/leetcode/834.树中距离之和.py
@@ -0,0 +1,31 @@
+class Solution(object):
+    def sumOfDistancesInTree(self, N, edges):
+        d = collections.defaultdict(set)
+        for s,t in edges:
+            d[s].add(t)
+            d[t].add(s)
+
+        count = [1]*N
+        res = [0]*N
+
+        # 计算孩子到根的距离
+        def dfs(root, vis):
+            vis.add(root)
+            for i in d[root]:
+                if i not in vis:
+                    dfs(i, vis)
+                    # res[i]是用i作为根，所有孩子到i的距离之和
+                    count[root] += count[i]
+                    res[root] += res[i] + count[i]
+
+        # 计算根到孩子的距离
+        def dfs2(root, vis):
+            vis.add(root)
+            for i in d[root]:
+                if i not in vis:
+                    res[i] = res[root] - count[i] + N-count[i]
+                    dfs2(i, vis)
+
+        dfs(0, set())
+        dfs2(0, set())
+        return res
diff --git a/leetcode/863.二叉树中所有距离为K的结点.py b/leetcode/863.二叉树中所有距离为K的结点.py
@@ -0,0 +1,22 @@
+class Solution(object):
+    def distanceK(self, root, target, K):
+        # 字典的值类型是列表
+        con = collections.defaultdict(list)
+
+        def connect(parent, child):
+            if parent and child:
+                con[parent.val].append(child.val)
+                con[child.val].append(parent.val)
+            if child.left:
+                connect(child, child.left)
+            if child.right:
+                connect(child, child.right)
+
+        connect(None, root)
+        res = [target.val]
+        visited = set(res)
+        for _ in range(K):
+            res = [y for x in res for y in con[x] if y not in visited]
+            # 合并
+            visited |= set(res)
+        return res
diff --git a/leetcode/865.具有所有最深结点的最小子树.py b/leetcode/865.具有所有最深结点的最小子树.py
@@ -0,0 +1,15 @@
+class Solution(object):
+    def subtreeWithAllDeepest(self, root):
+        # 判断左右子树深度是否相同，若相同则根结点为所求
+        res = self.depth(root.left) - self.depth(root.right)
+        if res == 0:
+            return root
+        elif res > 0:
+            return self.subtreeWithAllDeepest(root.left)
+        else:
+            return self.subtreeWithAllDeepest(root.right)
+    # 求树的深度
+    def depth(self, root):
+        if not root:
+            return 0
+        return 1 + max(self.depth(root.left), self.depth(root.right))
diff --git a/leetcode/872.叶子相似的树.py b/leetcode/872.叶子相似的树.py
@@ -0,0 +1,12 @@
+# 获取叶值序列进行比较
+class Solution(object):
+    def leafSimilar(self, root1, root2):
+        def findLeaf(root):
+            if not root:
+                return []
+            if not root.left and not root.right:
+                return [root.val]
+            return findLeaf(root.left) + findLeaf(root.right)
+
+        return findLeaf(root1) == findLeaf(root2)
+
diff --git a/leetcode/876.链表的中间结点.py b/leetcode/876.链表的中间结点.py
@@ -0,0 +1,17 @@
+# 方法一：用数组存放结点值，返回中间结点后面的值
+class Solution(object):
+    def middleNode(self, head):
+        res = []
+        while head:
+            res.append(head.val)
+            head = head.next
+        return res[len(res)/2:]
+
+# 方法二：快的比慢的快一倍，当快的到底时，慢的刚好在中间
+class Solution(object):
+    def middleNode(self, head):
+        fast = slow = head
+        while fast and fast.next:
+            slow = slow.next
+            fast = fast.next.next
+        return slow
diff --git a/leetcode/889.根据前序和后序遍历构造二叉树.py b/leetcode/889.根据前序和后序遍历构造二叉树.py
@@ -0,0 +1,19 @@
+# 前序遍历的第一个元素，后续遍历的最后一个元素，是根节点
+# 从前序看 2 是左树的根节点，我们需要知道左树的长度，从后序找到2的位置，则4，5，2 是整个左树
+class Solution(object):
+    def constructFromPrePost(self, pre, post):
+        root = TreeNode(pre[0])
+        pre = pre[1:]
+        post = post[:-1]
+        len_left = 0
+        for i in post:
+            if i == pre[0]:
+                len_left += 1
+                break
+            else:
+                len_left += 1
+        if len_left > 0:
+            root.left = self.constructFromPrePost(pre[:len_left], post[:len_left])
+        if len(pre) - len_left > 0:
+            root.right = self.constructFromPrePost(pre[len_left:], post[len_left:])
+        return root
diff --git a/leetcode/894.所有可能的满二叉树.py b/leetcode/894.所有可能的满二叉树.py
diff --git a/leetcode/897.递增顺序查找树.py b/leetcode/897.递增顺序查找树.py
