力扣题86~90

题86（中等）：

python代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        #分组，分两丢
        small_node=ListNode()
        high_node=ListNode()
        p_small=small_node
        p_high=high_node
        p_h=head
        while p_h!=None:
            #如果小于，应该放到smaller
            print(p_h.val)
            if p_h.val<x:
                p_small.next=p_h
                p_small=p_small.next
                p_h=p_h.next

            else:
                p_high.next=p_h
                p_high=p_high.next
                p_h=p_h.next

        p_small.next=high_node.next
        p_high.next=None
        head=small_node.next
        return head


        

题87（困难）：

python代码：

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        if len(s1) != len(s2) or sorted(s1) != sorted(s2):
            return False
        n = len(s1)
        dp = [[[False] * (n + 1) for _ in range(n)] for _ in range(n)]
        
        # 初始化长度为1的子串
        for i in range(n):
            for j in range(n):
                dp[i][j][1] = s1[i] == s2[j]
        
        # 遍历所有可能的子串长度
        for k in range(2, n + 1):
            for i in range(n - k + 1):
                for j in range(n - k + 1):
                    for p in range(1, k):
                        # 不交换的情况
                        if dp[i][j][p] and dp[i + p][j + p][k - p]:
                            dp[i][j][k] = True
                            break
                        # 交换的情况
                        if dp[i][j + k - p][p] and dp[i + p][j][k - p]:
                            dp[i][j][k] = True
                            break
        return dp[0][0][n]

题88（简单）：

python代码：

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        for i in range(m,m+n):
            nums1[i]=nums2[i-m]
        nums1.sort()
        

题89（中等）：

分析：

找规律00 01 11 10-----> 000 001 011 010(前4+0) / 110 111 101 100 (后4加1并倒序排列)

class Solution:
    def grayCode(self, n: int) -> List[int]:


        def call_back(n,bin_list):
            if n == 1:
                bin_list.extend(['0', '1'])
                return bin_list
            bin_list=call_back(n - 1,bin_list)
            new = ['1' + i for i in bin_list][::-1]
            bin_list=['0' + i for i in bin_list]

            print(new)
            bin_list.extend(new)
            return bin_list

        bin_list=call_back(n,[])

        return [int(i, 2) for i in bin_list]

题90（中等）：

python代码：

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        n_list=sorted(nums)
        res=[[]]
        def call_back(nums,k,now_list):
            #判断出递归条件，当
            if nums==[]:
                return
            for i in range(0,len(nums)):
                if i>0 and nums[i]==nums[i-1]:
                    continue
                #加一个i处的值
                new_now=now_list.copy()
                new_now.append(nums[i])
                #把这个去了
                new_num=nums[i+1:]
                res.append(new_now)
                call_back(new_num,k+1,new_now)

        call_back(n_list,0,[])
        return res