algorithm002 · GeekUniversity · Aug 5, 2019 · Jun 24, 2019 · Jun 24, 2019 · Jun 25, 2019
diff --git a/Week_03/id_3/dfs/LeetCode_127_3_v2.py b/Week_03/id_3/dfs/LeetCode_127_3_v2.py
@@ -22,9 +22,7 @@ def ladderLength(self, begin, end, word_list) -> int:
         begin_queue = [begin]
         end_queue = [end]
 
-        while True:
-            if not begin_queue and not end_queue:
-                return 0
+        while begin_queue or end_queue:
             if count % 2 == 0:
                 queue = begin_queue
                 cur_set, target_set = begin_set, end_set
@@ -56,6 +54,6 @@ def ladderLength(self, begin, end, word_list) -> int:
 
 
 s = Solution()
-# print(s.ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))
-# print(s.ladderLength("hit", "cog", ["hot", "dot", "dog", "lot"]))
+print(s.ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))
+print(s.ladderLength("hit", "cog", ["hot", "dot", "dog", "lot"]))
 print(s.ladderLength("hot", "dog", ["hot", "dog"]))
diff --git a/Week_04/id_3/backtracking/LeetCode_46_3_v1.py b/Week_04/id_3/backtracking/LeetCode_46_3_v1.py
@@ -0,0 +1,31 @@
+"""
+全排列 O(n^n) 似乎没啥悬念
+====== 但是我居然没通过
+两点问题
+1 递归的退出条件不能忘了return
+2 set在迭代到时候要小心插入和删除，还是list复制一份更为稳妥
+"""
+
+
+class Solution:
+    def permute(self, nums):
+        results = []
+        if not nums:
+            return results
+        self.recursion([], set(nums), results)
+        return results
+
+    def recursion(self, curr, num_set, results):
+        if len(num_set) == 0:
+            results.append(curr)
+            return
+
+        for n in list(num_set):
+            num_set.remove(n)
+            self.recursion(curr + [n], num_set, results)
+            num_set.add(n)
+
+
+s = Solution()
+print(s.permute([1, 2, 3]))
+print(s.permute([6, 2, -1, 8]))
diff --git a/Week_04/id_3/backtracking/LeetCode_51_3.py b/Week_04/id_3/backtracking/LeetCode_51_3.py
@@ -0,0 +1,45 @@
+"""
+最原始回溯解决n皇后方法
+每一行判断是否可行，对角线方向用set可以简易实现
+"""
+
+
+class Solution:
+    def solveNQueens(self, n):
+        results = []
+        if n == 0:
+            return []
+        self.recursion(n, [], [0]*n, set(), set(), results)
+        return results
+
+    def recursion(self, n, curr, dis_col, dis_pie, dis_na, results):
+        row = len(curr) - 1
+        if n == (row + 1):
+            results.append(curr)
+            return
+        for i in range(n):
+            if dis_col[i] == 1:
+                continue
+            pie = i + row
+            if pie in dis_pie:
+                continue
+            na = i - row
+            if na in dis_na:
+                continue
+
+            line = ['.'] * n
+            line[i] = 'Q'
+
+            dis_col[i] = 1
+            dis_pie.add(pie)
+            dis_na.add(na)
+
+            self.recursion(n, curr + [''.join(line)], dis_col, dis_pie, dis_na, results)
+
+            dis_col[i] = 0
+            dis_pie.remove(pie)
+            dis_na.remove(na)
+
+
+s = Solution()
+print(s.solveNQueens(4))
diff --git a/Week_04/id_3/backtracking/LeetCode_77_3_v1.py b/Week_04/id_3/backtracking/LeetCode_77_3_v1.py
@@ -0,0 +1,25 @@
+"""
+全组合 避免重复元素出现
+使用下标过滤掉已经组合过的是一个常用的技巧
+"""
+
+
+class Solution:
+    def combine(self, n, k):
+        results = []
+        if n == 0:
+            return results
+        self.recursion([], 1, n+1, k, results)
+        return results
+
+    def recursion(self, curr, index, n, k, results):
+        if len(curr) == k:
+            results.append(curr)
+            return
+
+        for i in range(index, n):
+            self.recursion(curr + [i], i + 1, n, k, results)
+
+
+s = Solution()
+print(s.combine(4, 2))
diff --git a/Week_04/id_3/backtracking/LeetCode_784_3_v1.py b/Week_04/id_3/backtracking/LeetCode_784_3_v1.py
@@ -0,0 +1,25 @@
+class Solution:
+    def letterCasePermutation(self, ss):
+        results = []
+        if not ss:
+            return results
+        self.recursion(ss, 0, [], results)
+        return results
+
+    def recursion(self, ss, i, curr_arr, results):
+        if i == len(ss):
+            results.append(''.join(curr_arr))
+            return
+
+        c = ss[i]
+        self.recursion(ss, i + 1, curr_arr + [c], results)
+        if c.isupper():
+            self.recursion(ss, i + 1, curr_arr + [c.lower()], results)
+        elif c.islower():
+            self.recursion(ss, i + 1, curr_arr + [c.upper()], results)
+
+
+s = Solution()
+print(s.letterCasePermutation('a1b2'))
+print(s.letterCasePermutation('3z4'))
+print(s.letterCasePermutation('12345'))
diff --git a/Week_04/id_3/backtracking/LeetCode_784_3_v2.py b/Week_04/id_3/backtracking/LeetCode_784_3_v2.py
@@ -0,0 +1,28 @@
+"""
+尝试非递归解决
+"""
+
+
+class Solution:
+    def letterCasePermutation(self, ss):
+        if not ss:
+            return []
+
+        results = ['']
+        for c in ss:
+            _results = []
+            for r in results:
+                if c.islower() or c.isupper():
+                    _results.append(r + c.upper())
+                    _results.append(r + c.lower())
+                else:
+                    _results.append(r + c)
+
+            results = _results
+        return results
+
+
+s = Solution()
+print(s.letterCasePermutation('a1b2'))
+print(s.letterCasePermutation('3z4'))
+print(s.letterCasePermutation('12345'))
diff --git a/Week_04/id_3/backtracking/LeetCode_78_3_v1.py b/Week_04/id_3/backtracking/LeetCode_78_3_v1.py
@@ -0,0 +1,23 @@
+"""
+经典全组合
+"""
+
+
+class Solution:
+    def subsets(self, nums):
+        results = []
+        if not nums:
+            return results
+        self.recursion([], nums, results)
+        return results
+
+    def recursion(self, cur, nums, results):
+        results.append(cur)
+        if not nums:
+            return
+        for i in range(len(nums)):
+            self.recursion(cur + [nums[i]], nums[i+1:], results)
+
+
+s = Solution()
+print(s.subsets([1, 2, 3]))
diff --git a/Week_04/id_3/backtracking/LeetCode_78_3_v2.py b/Week_04/id_3/backtracking/LeetCode_78_3_v2.py
@@ -0,0 +1,17 @@
+"""
+经典全组合 直接调用库函数 其实为了点进去看看他的实现代码
+"""
+import itertools
+
+
+class Solution:
+    def subsets(self, nums):
+        results = []
+        for i in range(len(nums) + 1):
+            for r in itertools.combinations(nums, i):
+                results.append(list(r))
+        return results
+
+
+s = Solution()
+print(s.subsets([1, 2, 3]))
diff --git a/Week_04/id_3/backtracking/LeetCode_78_3_v3.py b/Week_04/id_3/backtracking/LeetCode_78_3_v3.py
@@ -0,0 +1,19 @@
+"""
+经典全组合 非递归
+"""
+import itertools
+
+
+class Solution:
+    def subsets(self, nums):
+        results = [[]]
+        for n in nums:
+            _results = []
+            for pn in results:
+                _results.append(pn + [n])
+            results += _results
+        return results
+
+
+s = Solution()
+print(s.subsets([1, 2, 3]))
diff --git a/Week_04/id_3/division/LeetCode_169_3_v1.py b/Week_04/id_3/division/LeetCode_169_3_v1.py
@@ -0,0 +1,65 @@
+"""
+既然是分治专题的，那么估计用hash的玩法是没啥意义了
+看答案 分治有点儿勉强 算是学习个思路吧
+O(nlogn)
+
+似乎分治总会比暴力要好，只要从n^2变成nlogn，如果找不到最优的O(n)，那么先用nlogn也不错。
+"""
+
+
+class Solution:
+    def majorityElement(self, nums):
+        if not nums:
+            return None
+        # return self._division1(nums)
+        return self._division2(nums, 0, len(nums) - 1)
+
+    def _division1(self, nums):
+        if len(nums) == 1:
+            return nums[0]
+
+        mid = len(nums) // 2
+        left = self._division1(nums[:mid])
+        right = self._division1(nums[mid:])
+        if left == right:
+            return left
+
+        lc = 0
+        rc = 0
+        for n in nums:
+            if n == left:
+                lc += 1
+                continue
+            if n == right:
+                rc += 1
+                continue
+        return left if lc > rc else right
+
+    def _division2(self, nums, low, high):
+        if low == high:
+            return nums[low]
+
+        mid = low + (high-low)//2
+        left = self._division2(nums, low, mid)
+        right = self._division2(nums, mid+1, high)
+
+        if left == right:
+            return left
+
+        lc = 0
+        rc = 0
+        for i in range(low, high+1):
+            n = nums[i]
+            if left == n:
+                lc += 1
+                continue
+            if right == n:
+                rc += 1
+                continue
+
+        return left if lc > rc else right
+
+
+s = Solution()
+# print(s.majorityElement([2, 2, 1, 1, 1, 2, 2]))
+print(s.majorityElement([3, 3, 4]))
diff --git a/Week_04/id_3/division/LeetCode_169_3_v2.py b/Week_04/id_3/division/LeetCode_169_3_v2.py
@@ -0,0 +1,23 @@
+"""
+似乎是最优解 时间O(n) 空间O(1)
+投票法
+假设一个数是众数 在遍历过程中遇到该数则投票+1，不是该数则-1。
+如果票数为0，则从新开始投票，并将下一个数设为架设众数。
+因为众数多于一半，所以最终一定会耗尽其他数的票数并最终占有票数
+"""
+
+
+class Solution:
+    def majorityElement(self, nums):
+        vote = 0
+        for n in nums:
+            if vote == 0:
+                result = n
+                vote += 1
+                continue
+            if result == n:
+                vote += 1
+            else:
+                vote -= 1
+
+        return result
diff --git a/Week_04/id_3/division/LeetCode_240_3_v1.py b/Week_04/id_3/division/LeetCode_240_3_v1.py
@@ -0,0 +1,46 @@
+"""
+一时没太想到分治咋整，先按我最朴素的思路试试。
+行列都是升序，只要分别在行列中找到小于等于目标值的下标，然后访问判断即可。
+====我想错了 还是换回分治琢磨琢磨
+
+我懂了，目前的思路是，尝试把矩阵先分成2份, 先行后列，每份最大值和最小值都容易确定。然后分治并剪除不符合要求的矩阵
+"""
+
+
+class Solution:
+    def searchMatrix(self, matrix, target):
+        if not matrix or not matrix[0]:
+            return False
+        return self.division(matrix, target)
+
+    def division(self, matrix, target):
+        if not matrix or not matrix[0]:
+            return False
+
+        if matrix[0][0] == target:
+            return True
+
+        rows = len(matrix)
+        cols = len(matrix[0])
+        if matrix[0][0] > target or target > matrix[rows-1][cols-1]:
+            return False
+
+        if rows > 1:
+            index = rows//2
+            return self.division(matrix[:index], target) or self.division(matrix[index:], target)
+        else:
+            index = cols//2
+            return self.division([matrix[0][:index]], target) or self.division([matrix[0][index:]], target)
+
+
+s = Solution()
+matrix = [
+    [1,   4,  7, 11, 15],
+    [2,   5,  8, 12, 19],
+    [3,   6,  9, 16, 22],
+    [10, 13, 14, 17, 24],
+    [18, 21, 23, 26, 30]
+]
+
+print(s.searchMatrix(matrix, 5))
+print(s.searchMatrix(matrix, 20))