Add files via upload

linwt · web-flow · commit 21f92d2693a3 · 2019-05-31T22:55:26.000+08:00
diff --git a/leetcode2/1005.K 次取反后最大化的数组和.py b/leetcode2/1005.K 次取反后最大化的数组和.py
@@ -0,0 +1,8 @@
+# 每次将数组最小值取反替换
+class Solution(object):
+    def largestSumAfterKNegations(self, A, K):
+        for _ in range(K):
+            num = min(A)
+            i = A.index(num)
+            A[i] = -num
+        return sum(A)
diff --git a/leetcode2/1008.先序遍历构造二叉树.py b/leetcode2/1008.先序遍历构造二叉树.py
@@ -0,0 +1,15 @@
+# 列表第一个值构造为根结点，比根结点小的值作为左子树，比根结点大的值作为右子树，递归构造结点成二叉树
+class Solution(object):
+    def bstFromPreorder(self, preorder):
+        if not preorder:
+            return None
+        root = TreeNode(preorder[0])
+        left, right = [], []
+        for num in preorder[1:]:
+            if num < preorder[0]:
+                left.append(num)
+            else:
+                right.append(num)
+        root.left = self.bstFromPreorder(left)
+        root.right = self.bstFromPreorder(right)
+        return root
diff --git a/leetcode2/1021.删除最外层的括号.py b/leetcode2/1021.删除最外层的括号.py
@@ -0,0 +1,15 @@
+# 遍历记录左括号和右括号的个数，若相等则凑成一组
+class Solution(object):
+    def removeOuterParentheses(self, S):
+        l = r = 0
+        res = cur = ''
+        for s in S:
+            if s == '(':
+                l += 1
+            if s == ')':
+                r += 1
+            cur += s
+            if l == r:
+                res += cur[1:-1]
+                cur = ''
+        return res
diff --git a/leetcode2/1022.从根到叶的二进制数之和.py b/leetcode2/1022.从根到叶的二进制数之和.py
@@ -0,0 +1,19 @@
+# 深度优先搜索，得到所有路径表示的数字，最后转为十进制相加
+class Solution(object):
+    def sumRootToLeaf(self, root):
+        global res
+        res, sum = [], 0
+        self.dfs(root, '')
+        for i in res:
+            sum += int(i, 2)
+        return sum
+
+    def dfs(self, root, s):
+        if not root:
+            return ''
+        if not root.left and not root.right:
+            res.append(s + str(root.val))
+        if root.left:
+            self.dfs(root.left, s + str(root.val))
+        if root.right:
+            self.dfs(root.right, s + str(root.val))
diff --git a/leetcode2/1023.驼峰式匹配.py b/leetcode2/1023.驼峰式匹配.py
@@ -0,0 +1,20 @@
+class Solution(object):
+    def camelMatch(self, queries, pattern):
+        res = []
+        l = len(pattern)
+        for q in queries:
+            i = 0
+            flag = True
+            for char in q:
+                # 与模板字符匹配
+                if i < l and char == pattern[i]:
+                    i += 1
+                # 与模板字符不匹配，且为大写字母，则待查项与模式串不匹配
+                elif 'A' <= char <= 'Z':
+                    flag = False
+                    break
+            # 模板没有全部匹配
+            if i < l:
+                flag = False
+            res.append(flag)
+        return res
diff --git a/leetcode2/1024.视频拼接.py b/leetcode2/1024.视频拼接.py
@@ -0,0 +1,22 @@
+# 贪心，每一步都走可到范围内下一步最远的那一步
+class Solution(object):
+    def videoStitching(self, clips, T):
+        d = {}
+        for clip in clips:
+            # 用字典记录每个起点的最远终点
+            d[clip[0]] = max(d.get(clip[0], 0), clip[1])
+        res = 1
+        start = s = 0
+        end = e = reach = d.get(0, 0)
+        while reach < T:
+            # 在已有范围内搜寻可到最远距离
+            for cur in range(start + 1, end + 1):
+                if d.get(cur, 0) > reach:
+                    # 记录下一轮的起点和终点
+                    s, e, reach = cur, d[cur], d[cur]
+            # 本轮停留在原地
+            if s == start and e == end:
+                return -1
+            start, end = s, e
+            res += 1
+        return res
diff --git a/leetcode2/1025.除数博弈.py b/leetcode2/1025.除数博弈.py
@@ -0,0 +1,6 @@
+# 如果黑板上写的是奇数，那么下一个人改完之后肯定会变成偶数，因为奇数没有偶数因子并且奇数减去奇数差为偶数。
+# 谁先在黑板上写出3谁就赢了，因为3之后另外一个人只能写2，然后你再写1，另外一个人就没办法写了。
+# 所以如果想赢，必须让自己每次写完之后黑板上都是奇数，因为这样对方就只能写偶数，那么3肯定就会是我方写。
+class Solution(object):
+    def divisorGame(self, N):
+        return N % 2 == 0
diff --git a/leetcode2/1026.节点与其祖先之间的最大差值.py b/leetcode2/1026.节点与其祖先之间的最大差值.py
@@ -0,0 +1,14 @@
+# 递归时计算与当前祖先里面的最大值、最小值的差值，即可算出当前节点的最大差值
+# 而一颗树的祖先差值为左子树的祖先差值、右子树的祖先差值、当前节点的祖先差值三者里面的最大值
+class Solution(object):
+    def maxAncestorDiff(self, root):
+        return self.dfs(root, root.val, root.val)
+
+    def dfs(self, root, minVal, maxVal):
+        if not root:
+            return 0
+        val = root.val
+        root_res = max(abs(minVal - val), abs(maxVal - val))
+        left_res = self.dfs(root.left, min(val, minVal), max(val, maxVal))
+        right_res = self.dfs(root.right, min(val, minVal), max(val, maxVal))
+        return max(root_res, left_res, right_res)
diff --git a/leetcode2/1027.最长等差数列.py b/leetcode2/1027.最长等差数列.py
@@ -0,0 +1,31 @@
+# 暴力破解
+class Solution(object):
+    def longestArithSeqLength(self, A):
+        res = 0
+        for i in range(len(A)-2):
+            for j in range(i+1, len(A)-1):
+                count = 2
+                diff = A[j] - A[i]
+                cur = A[j] + diff
+                for k in range(j+1, len(A)):
+                    if A[k] == cur:
+                        count += 1
+                        cur += diff
+                res = max(res, count)
+        return res
+
+
+# 动态规划
+# dp[i][diff]表示以下标为i的元素结尾且公差为diff的等差子序列的最大长度
+# 由于使用数组内存开销太大而且公差可能是负数，所以选择使用字典来代替数组
+class Solution2(object):
+    def longestArithSeqLength(self, A):
+        n = len(A)
+        dp = [{} for _ in range(n)]
+        res = 2
+        for i in range(1, n):
+            for j in range(0, i):
+                diff = A[i] - A[j]
+                dp[i][diff] = dp[j].get(diff, 1) + 1
+                res = max(res, dp[i][diff])
+        return res
diff --git a/leetcode2/1028.从先序遍历还原二叉树.py b/leetcode2/1028.从先序遍历还原二叉树.py
@@ -0,0 +1,31 @@
+class Solution(object):
+    def recoverFromPreorder(self, S):
+        # 遍历字符串，记录结点值和对应层数
+        layer, num, queue = 0, '', []
+        for char in S:
+            if char == '-':
+                if num:
+                    queue.append((num, layer))
+                    num, layer = '', 0
+                layer += 1
+            else:
+                num += char
+        if num:
+            queue.append((num, layer))
+
+        head = TreeNode(None)
+        # 存放已还原的结点和层数
+        stack = [(head, -1)]
+        for num, layer in queue:
+            # 层数小于等于最后一个已还原结点时，弹出已还原结点直到其父节点
+            while layer <= stack[-1][1]:
+                stack.pop()
+            node = TreeNode(num)
+            parent = stack[-1][0]
+            stack.append((node, layer))
+            # 左孩子优先
+            if parent.left:
+                parent.right = node
+            else:
+                parent.left = node
+        return head.left
diff --git a/leetcode2/1033.移动石子直到连续.py b/leetcode2/1033.移动石子直到连续.py
@@ -0,0 +1,8 @@
+class Solution(object):
+    def numMovesStones(self, a, b, c):
+        a, b, c = sorted([a, b, c])
+        if a+1==b and b+1==c:
+            return [0, 0]
+        if a+1==b or a+2==b or b+1==c or b+2==c:
+            return [1, c-a-2]
+        return [2, c-a-2]
diff --git a/leetcode2/1034.边框着色.py b/leetcode2/1034.边框着色.py
@@ -0,0 +1,39 @@
+# 连通分量边界：与至少一个非连通分量相邻的连通分量，或网格的首尾行列
+class Solution(object):
+    def colorBorder(self, grid, r0, c0, color):
+        m = len(grid)
+        n = len(grid[0])
+        ret = [[0] * n for _ in range(m)]
+        vis = [[0] * n for _ in range(m)]
+        for i in range(m):
+            for j in range(n):
+                ret[i][j] = grid[i][j]
+        # 代表四个方向的分量
+        ds = ((0,1),(1,0),(0,-1),(-1,0))
+        t = grid[r0][c0]
+
+        def dfs(i, j):
+            # 判断当前网格是否已搜寻过
+            if not vis[i][j]:
+                vis[i][j] = True
+                edge = False
+                # 遍历四个方向的网格
+                for di, dj in ds:
+                    ni, nj = i+di, j+dj
+                    # 某个方向在网格内
+                    if 0<=ni<m and 0<=nj<n:
+                        # 值相等则为连通分量，递归
+                        if grid[ni][nj] == t:
+                            dfs(ni,nj)
+                        # 值不相等则当前网格是连通分量边界
+                        else:
+                            edge = True
+                    # 某个方向不在网格内，则当前网格是网格边界
+                    else:
+                        edge = True
+                # 遍历完四个方向后判断，若是边界则染色
+                if edge:
+                    ret[i][j] = color
+
+        dfs(r0, c0)
+        return ret
diff --git a/leetcode2/1035.不相交的线.py b/leetcode2/1035.不相交的线.py
@@ -0,0 +1,22 @@
+# 相当于寻找最长公共子串
+class Solution(object):
+    def maxUncrossedLines(self, A, B):
+        n, m = len(A), len(B)
+        dp = [[0]*(n+1) for _ in range(m+1)]
+        for i in range(m):
+            for j in range(n):
+                if A[j] == B[i]:
+                    dp[i+1][j+1] = dp[i][j] + 1
+                else:
+                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
+        return dp[-1][-1]
+
+#       2 5 1 2 5
+#
+#     0 0 0 0 0 0
+# 10  0 0 0 0 0 0
+# 5   0 0 1 1 1 1
+# 2   0 1 1 1 2 2
+# 1   0 1 1 2 2 2
+# 5   0 1 2 2 2 3
+# 2   0 1 2 2 3 3
diff --git a/leetcode2/1036.逃离大迷宫.py b/leetcode2/1036.逃离大迷宫.py
@@ -0,0 +1,29 @@
+class Solution(object):
+    def isEscapePossible(self, blocked, source, target):
+        ds = ((1,0), (0,1), (-1,0), (0,-1))
+        # 元组节省空间
+        blocks = set(map(tuple, blocked))
+        T = 999999
+
+        def not_circle(p):
+            cur = [p]
+            vis = set()
+            vis.add(tuple(p))
+            for _ in range(50):
+                next = list()
+                # 遍历当前可到达的方格
+                for i, j in cur:
+                    # 遍历每个方格四个方向的方格
+                    for di, dj in ds:
+                        ni, nj = i+di, j+dj
+                        # 方格在有效范围内，未访问过，且不在封锁列表中
+                        if 0<=ni<=T and 0<=nj<=T and (ni,nj) not in vis and (ni,nj) not in blocks:
+                            # 将该方格添加到下一可访问列表和已访问列表
+                            next.append((ni,nj))
+                            vis.add((ni,nj))
+                cur = next
+            # 判断50次遍历搜寻后当前是否还有可访问的方格，若没有则说明封闭
+            return bool(cur)
+
+        # 判断起点和终点是否连通
+        return not_circle(source) and not_circle(target)
