代码随想录训练营第III期--028--python_代码随想录有没有python版

# class Solution:
#     def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
#         MOD = 10 ** 9 + 7
#         l = min(a, b)
#         r = n * min(a, b)
#         c = lcm(a, b)
#         while l <= r:
#             mid = (l + r) // 2
#             cnt = mid // a + mid // b - mid // c
#             if cnt >= n:
#                 r = mid - 1
#             else:
#                 l = mid + 1
#         return (r + 1) % MOD

# 作者：LeetCode-Solution
# 链接：https://leetcode.cn/problems/nth-magical-number/solution/di-n-ge-shen-qi-shu-zi-by-leetcode-solut-6vyy/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 代码随想录训练营第III期--028--python
# 93 
# class Solution:
#     def restoreIpAddresses(self, s: str) -> List[str]:
#         '''
#         解题思路：回溯+剪枝
#             步骤1：先想清楚这种字符串如何取出数字，以便可以通过递归取出所有可能的数字
#             步骤2：在字符串里，截取不同长度的字符，需要s[start:i+1]来取，因为不像纯数字列表，每种情况直接可以拿到[1, 23, 4]
#             步骤3：何时添加到结果？start到终点位置，且也找到了4个数，即添加结果
#             步骤4：剪枝操作：1.当截取的字符转换为数字后的值大于255，且出现为'06'这样的不合法情况
#                          2.当取的数大于4的时候，不符合IP的格式，直接返回
#         :return: res: 最后所有ip的情况
#         '''
#         res = []
#         def back_tracking(start, temp):
#             if len(temp) > 4:   # 当添加的数字已经大于4时，不符合ip的格式直接返回
#                 return
#             if start == len(s) and len(temp) == 4:  # 当temp已经为4位数，且截取字符串的起始位索引start==len(s)，代表已经截取完所有的s
#                 res.append('.'.join(temp))
#             for i in range(start, len(s)):
#                 # 当截取的数字大于255时不符合，或者当截取的两位数及以上的数字有前导0时，不符合，直接返回
#                 if int(s[start:i+1]) > 255 or (s[start] == '0' and len(s[start:i+1]) >= 2): 
#                     return
#                 temp.append(s[start:i+1])
#                 back_tracking(i+1, temp)
#                 temp.pop()    
#         back_tracking(0, [])
#         return res

# 93 
class Solution:
    def restoreIpAddresses(self, s: str):
        res = []
        def backtrack(path, index):
            # print(path)
            if len(path) > 4: return 
            if index == len(s) and len(path) == 4:
                    res.append('.'.join(path))

            for i in range(index, len(s)):
                if int(s[index:i+1]) > 255 or (s[index] == '0' and len(s[index:i+1]) >= 2):
                    return # 同样需要类似去重的操作
                backtrack(path+[s[index:i+1]], i + 1)
                # backtrack(path + [s[i]], index + 1)
        
        backtrack([], 0)
        return res 

# 78 
    def subsets(self, nums):
        res = []
        def backtrack(tmp, index):
            res.append(tmp)
            for i in range(index, len(nums)):
                backtrack(tmp + [nums[i]], i + 1)
        backtrack([], 0)
        return res 

# 90
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort() # 需要排序，降重的问题需要排序
        def backtrack(tmp, index):
            res.append(tmp)
            for i in range(index, len(nums)):
                if i > index and nums[i] == nums[i - 1]:# 同，重复问题需要continue
                    continue
                backtrack(tmp + [nums[i]], i + 1)
            
        backtrack([], 0)

        return res


sl = Solution()
s = "25525511135"
print(sl.restoreIpAddresses(s))


nums = [1,2,3]
print(sl.subsets(nums))


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103