Add files via upload

linwt · web-flow · commit 8bba6c5fc730 · 2019-10-07T21:11:33.000+08:00
diff --git a/leetcode2/1020.飞地的数量.py b/leetcode2/1020.飞地的数量.py
@@ -0,0 +1,22 @@
+# 从四条边上为 1 的位置向内搜索，将相连的 1 都改为 0,剩下的都是没有连接到边界的 1，计算1的个数所求数量
+class Solution(object):
+    def numEnclaves(self, A):
+        d = [(0, 1), (0, -1), (-1, 0), (1, 0)]
+        m, n = len(A), len(A[0])
+
+        def dfs(x, y):
+            A[x][y] = 0
+            for dx, dy in d:
+                nx, ny = x + dx, y + dy
+                if 0 <= nx < m and 0 <= ny < n and A[nx][ny] == 1:
+                    dfs(nx, ny)
+
+        for i in range(m):
+            for j in range(n):
+                if (i == 0 or i == m - 1 or j == 0 or j == n - 1) and A[i][j] == 1:
+                    dfs(i, j)
+
+        res = 0
+        for i in range(m):
+            res += sum(A[i])
+        return res
diff --git a/leetcode2/1079.活字印刷.py b/leetcode2/1079.活字印刷.py
@@ -0,0 +1,44 @@
+# 用集合存放所有可能的字符长度的全排列
+from itertools import permutations
+class Solution(object):
+    def numTilePossibilities(self, tiles):
+        res = set()
+        for item_len in range(1, len(tiles)+1):
+            for item in permutations(tiles, item_len):
+                res.add(item)
+        return len(res)
+
+
+# 回溯法，组合所有可能的字符串
+class Solution(object):
+    def numTilePossibilities(self, tiles):
+        res = set()
+
+        def genrate(output, tiles):
+            if output:
+                res.add(output)
+            for i in range(len(tiles)):
+                genrate(output + tiles[i], tiles[:i] + tiles[i+1:])
+
+        genrate('', tiles)
+        return len(res)
+
+
+# 回溯法，记录字母个数
+class Solution(object):
+    def numTilePossibilities(self, tiles):
+        def dfs(counter):
+            res = 0
+            for i in range(26):
+                if not counter[i]:
+                    continue
+                res += 1
+                counter[i] -= 1
+                res += dfs(counter)
+                counter[i] += 1
+            return res
+
+        counter = [0]*26
+        for i in tiles:
+            counter[ord(i) - ord('A')] += 1
+        return dfs(counter)
diff --git a/leetcode2/1080.根到叶路径上的不足节点.py b/leetcode2/1080.根到叶路径上的不足节点.py
@@ -0,0 +1,33 @@
+class TreeNode(object):
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+
+
+class Solution(object):
+    # 方法返回当前节点是否要删除
+    def dfs(self, node, sums, limit):
+        # 递归终止条件
+        if not node.left and not node.right:
+            return node.val + sums < limit
+        # 默认左右子树都需要删除，后面如果左右节点为空时才能处理
+        l_tree_del, r_tree_del = True, True
+        # 递归判断左右子树是否需要删除
+        if node.left:
+            l_tree_del = self.dfs(node.left, node.val + sums, limit)
+        if node.right:
+            r_tree_del = self.dfs(node.right, node.val + sums, limit)
+        # 需要删除则置位空
+        if l_tree_del:
+            node.left = None
+        if r_tree_del:
+            node.right = None
+        # 左右子树都需要删除时，当前节点就需要删除
+        return l_tree_del and r_tree_del
+
+    def sufficientSubset(self, root, limit):
+        root_del = self.dfs(root, 0, limit)
+        if root_del:
+            return None
+        return root
diff --git a/leetcode2/1123.最深叶节点的最近公共祖先.py b/leetcode2/1123.最深叶节点的最近公共祖先.py
@@ -0,0 +1,24 @@
+class TreeNode(object):
+    def __init__(self, x):
+        self.val = x
+        self.left = None
+        self.right = None
+
+
+# 深度优先搜索，从下往上计算深度，比较左右子树的深度，最近公共祖先的左右子树等高
+class Solution(object):
+    def lcaDeepestLeaves(self, root):
+        def dfs(root):
+            if not root:
+                return None, 0
+            l_node, l_depth = dfs(root.left)
+            r_node, r_depth = dfs(root.right)
+            if l_depth > r_depth:
+                return l_node, l_depth + 1
+            elif l_depth < r_depth:
+                return r_node, r_depth + 1
+            else:
+                return root, l_depth + 1
+
+        node, _ = dfs(root)
+        return node
