90题  子集2   我想起了上次写子集1 仿照那个写法 结果还不错

根据上题大佬解法有感
如果nums有n个数字 那么就分n轮进行 第i轮就只看nums[i]
每一轮，对于rel中的每一个结果 让这个结果添加一个nums[i] 再添加到结果中去。
如 [1,2,3]这个nums 第0轮 rel是[[]] 对于这个[] 添加nums[0] 加入结果得到rel = [[],[1]]
第1轮 rel有两个结果 都添加一个nums[1] 再加入rel 得到这轮结果[[],[1],[2],[1,2]]
第二轮再都添一个3 得到最后的8个元素的结果。

但是这道题有重复数字 如何避免重复 也很容易做到。
首先我们将列表排序
如果nums中 一个数字和前一轮的相同 那么他只需要在前一轮得到的结果上添加自己，而不是在所有的rel中添加自己
因为上一个数已经再前面所有结果上添加过了
举例 [1,2,2]
开始 rel = [[]]
0轮: rel = [[],[1]]
1轮: rel = [[],[1],[2],[1,2]]
在第二轮时我们发现 如果再对于rel中的[],[1]中添加2 就会得到重复的结果 [2] [1,2]
那么 怎么做 我们就仅仅对上一轮时添加的新结果[2],[1,2]添加nums[2]即可，这样得到不重复的[2,2],[1,2,2]。 前面的就不需要添加了 。
所以这里引入leni 记录 新添加结果的长度 如果第i轮数和前面的不同 leni 就是整个rel
如果相同 leni就还是上一组的长度，只需要将rel 后面leni个添加当前轮元素即可。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        n = len(nums)
        rel = [[]]
        leni = 1
        for i in range(n):
            if nums[i] != nums[i-1]:
                leni = len(rel)
                for each in rel[:leni]:
                    rel.append(each+[nums[i]])
            else:
                lenrel = len(rel)
                for each in rel[-leni:lenrel]:
                    rel.append(each+[nums[i]])
        return rel


作者：yizhu-jia
链接：https://leetcode-cn.com/problems/subsets-ii/solution/fei-hui-su-du-te-de-si-lu-zao-jiu-du-te-neyxp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

91：
无语凝噎泪潸然竟然还要看答案

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n+1)
        if s[0] == '0':
            return 0
        dp[0] = 1
        dp[1] = 1
        for i in range(1,n):
            if s[i] != '0':
                dp[i+1] += dp[i]
            if s[i-1] != '0' and int(s[i-1:i+1])<=26:
                dp[i+1] += dp[i-1]
        return dp[n]


作者：yizhu-jia
链接：https://leetcode-cn.com/problems/decode-ways/solution/wu-yu-ning-ye-lei-shan-ran-by-yizhu-jia-i1cx/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

92 ：
今天真是不应该，又被大部分击败

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        headnode = ListNode(0,head)
        p = headnode
        while left > 1:  #找到左结点的前一个结点。
            left -= 1
            right -= 1
            p  = p.next
        r = p.next
        if r == None:
            return head
        q = r.next
        while right > 1:
            right -=1
            r.next = q.next
            q.next = p.next
            p.next = q
            q = r.next
        return headnode.next


作者：yizhu-jia
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/jin-tian-zhen-shi-bu-ying-gai-you-bei-da-4icd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

93 
不错不错不错 真不错 今天回溯真不错

把判断提出来感觉好很多
len(s) <= 3*(4-len(path)):
这一句可是一个大剪枝

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def isvalid(s1):
            if s1 == '':
                return False
            if int(s1)>255:
                return False
            if s1=='0':
                return True
            if s1[0] == '0':
                return False
            return True

        def dfs(s,path):
            if len(path) == 3:
                if isvalid(s):
                    path.append(s)
                    rel.append(path[:])
                    path.pop()
            elif len(s) <= 3*(4-len(path)):
                if isvalid(s[:1]):
                    path.append(s[:1])
                    dfs(s[1:],path)
                    path.pop()
                if  len(s) > 2 and isvalid(s[:2]):
                    path.append(s[:2])
                    dfs(s[2:],path)
                    path.pop()
                if len(s) > 2 and isvalid(s[:3]):
                    path.append(s[:3])
                    dfs(s[3:],path)
                    path.pop()
        global rel
        rel = []
        if len(s) > 12 or len(s) < 4:
            return []
        dfs(s,[])
        for i,each in enumerate(rel):
            rel[i] = '.'.join(each)
        return rel

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/restore-ip-addresses/solution/bu-cuo-bu-cuo-bu-cuo-zhen-bu-cuo-jin-tia-9yh8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

94  ：中序遍历 

递归真好写 我都不想写非递归了

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        rel = []
        def mintra(node):
            if node!= None:
                if node.left != None:
                    mintra(node.left)
                rel.append(node.val)
                if node.right!= None:
                    mintra(node.right)
        mintra(root)
        return rel

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/di-gui-zhen-hao-xie-wo-du-bu-xiang-xie-f-5mb5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。