Add files via upload

linwt · web-flow · commit b9f62f7727e6 · 2019-10-07T21:10:59.000+08:00
diff --git a/leetcode/060.第k个排列.py b/leetcode/060.第k个排列.py
@@ -0,0 +1,39 @@
+# 回溯法，先算出全部全排列，再取第k个
+class Solution(object):
+    def getPermutation(self, n, k):
+        def gen(output, nums):
+            if not nums:
+                res.append(output)
+            for i in range(len(nums)):
+                gen(output + str(nums[i]), nums[:i] + nums[i+1:])
+
+        res = []
+        nums = [i for i in range(1, n+1)]
+        gen('', nums)
+        return res[k-1]
+
+
+# 找规律，一位一位地组合数字
+import math
+class Solution(object):
+    def getPermutation(self, n, k):
+        nums = [str(i) for i in range(1, n+1)]
+        res = ''
+        n -= 1
+        while n >= 0:
+            # n个数，以每一位数字开头有(n-1)!个排列
+            fac_n = math.factorial(n)
+
+            # 确定n个数中第k个排列的第一位数的位置，向上取整再减1，该行等于以下四行
+            loc = math.ceil(k / fac_n) - 1
+            # if k % fac_n:
+            #     loc = k // fac_n
+            # else:
+            #     loc = k // fac_n - 1
+
+            res += nums[loc]
+            nums.pop(loc)
+            # 确定了前一位数后，k减去前面已排除的多个(n-1)!全排列
+            k %= fac_n
+            n -= 1
+        return res
diff --git a/leetcode/223.矩形面积.py b/leetcode/223.矩形面积.py
@@ -0,0 +1,10 @@
+class Solution(object):
+    def computeArea(self, A, B, C, D, E, F, G, H):
+        # 两个矩形的面积
+        a = (C-A) * (D-B)
+        b = (G-E) * (H-F)
+        # 重叠部分的面积
+        x = max(0, min(C, G) - max(A, E))
+        y = max(0, min(D, H) - max(B, F))
+        area = a+b-x*y
+        return area
diff --git a/leetcode/390.消除游戏.py b/leetcode/390.消除游戏.py
@@ -0,0 +1,18 @@
+# 按题目说明解法
+class Solution(object):
+    def lastRemaining(self, n):
+        nums = [i+1 for i in range(n)]
+        res = []
+        while len(nums) > 1:
+            for i in range(1, len(nums), 2):
+                res.append(nums[i])
+            nums, res = res[::-1], []
+        return nums[0]
+
+
+# 找规律，如果输入a输出b，则输入2a输出2*（a-b+1）
+class Solution(object):
+    def lastRemaining(self, n):
+        if n == 1:
+            return 1
+        return 2 * (n/2 - self.lastRemaining(n/2) + 1)
diff --git a/leetcode/395.至少有K个重复字符的最长子串.py b/leetcode/395.至少有K个重复字符的最长子串.py
@@ -0,0 +1,13 @@
+# 分治法
+class Solution(object):
+    def longestSubstring(self, s, k):
+        if not s:
+            return 0
+        # 遍历字符串去重后的字符
+        for c in set(s):
+            # 如果字符个数少于k
+            if s.count(c) < k:
+                # 按照该字符拆分字符串，再递归求出拆分后的字串中最长的字串
+                return max(self.longestSubstring(t, k) for t in s.split(c))
+        # 每个字符的个数都大于等于k，则返回字符串的长度
+        return len(s)
diff --git a/leetcode/419.甲板上的战舰.py b/leetcode/419.甲板上的战舰.py
@@ -0,0 +1,11 @@
+# 遍历时如果为'X'，并且其左边和上边不为'X'，则个数加1
+class Solution(object):
+    def countBattleships(self, board):
+        res = 0
+        for i in range(len(board)):
+            for j in range(len(board[0])):
+                if board[i][j] == 'X':
+                    if (i > 0 and board[i-1][j] == 'X') or (j > 0 and board[i][j-1] == 'X'):
+                        continue
+                    res += 1
+        return res
diff --git a/leetcode/473.火柴拼正方形.py b/leetcode/473.火柴拼正方形.py
@@ -0,0 +1,39 @@
+# 递归，贪心，深度优先，剪枝
+# 每次尝试把每根火柴拼到4条边，全部拼完则可以组成正方形
+class Solution(object):
+    def makesquare(self, nums):
+        # 不能组成正方形的情况：1.火柴总长度不是4的倍数  2.火柴数少于4  3.最长的火柴大于目标边长
+        sums = sum(nums)
+        if sums % 4 or len(nums) < 4:
+            return False
+        # 贪心，先排序可以节约回溯的次数
+        nums.sort(reverse=True)
+        side_len = sums / 4
+        if nums[0] > side_len:
+            return False
+
+        def dfs(i, sides):
+            """
+            深度优先遍历
+            :param i: 当前访问的火柴的位置
+            :param sides: 当前4条边的长度
+            :return:
+            """
+            # 递归终止条件，火柴全部拼完
+            if i == len(nums):
+                return True
+            # 尝试把火柴拼到4条边中
+            for j in range(4):
+                # 当前边长加上新的火柴后长度小于等于目标边长。当前边长与前一边长相等时可跳过，以为如果前一边长失败，当前边长也会失败
+                if sides[j] + nums[i] <= side_len and (j == 0 or sides[j] != sides[j - 1]):
+                    # 放入当前火柴
+                    sides[j] += nums[i]
+                    # 放入下一根火柴
+                    if dfs(i + 1, sides):
+                        return True
+                    # 放入失败，取出火柴准备放入下一条边
+                    sides[j] -= nums[i]
+            # 四条边都不能放火柴，回溯
+            return False
+        # 初始化边并从0开始放入
+        return dfs(0, [0, 0, 0, 0])
diff --git a/leetcode/695.岛屿的最大面积.py b/leetcode/695.岛屿的最大面积.py
@@ -0,0 +1,18 @@
+class Solution(object):
+    def maxAreaOfIsland(self, grid):
+        m, n, maxArea = len(grid), len(grid[0]), 0
+
+        # 获取岛屿面积
+        def getArea(grid, x, y):
+            # 符合条件的土地，将其置0，并累加四个方向的土地，得到岛屿的面积
+            if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
+                grid[x][y] = 0
+                return 1 + getArea(grid, x + 1, y) + getArea(grid, x - 1, y) + getArea(grid, x, y + 1) + getArea(grid, x, y - 1)
+            return 0
+
+        # 遍历每个位置，得到每个位置上的面积并更新最大面积
+        for i in range(m):
+            for j in range(n):
+                area = getArea(grid, i, j)
+                maxArea = area if area > maxArea else maxArea
+        return maxArea
diff --git a/leetcode/733.图像渲染.py b/leetcode/733.图像渲染.py
@@ -0,0 +1,19 @@
+class Solution(object):
+    def floodFill(self, image, sr, sc, newColor):
+        d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
+        m, n, oldColor = len(image), len(image[0]), image[sr][sc]
+
+        # 新值等于就值则返回原图像，避免无限搜索
+        if newColor == oldColor:
+            return image
+
+        # 将符合条件的位置赋新值，再搜索该位置的四个方向是否符合
+        def dfs(x, y):
+            image[x][y] = newColor
+            for dx, dy in d:
+                nx, ny = x + dx, y + dy
+                if 0 <= nx < m and 0 <= ny < n and image[nx][ny] == oldColor:
+                    dfs(nx, ny)
+
+        dfs(sr, sc)
+        return image
