Python每日一练(20230423) 链表倒数结点、最小子串、二叉树层序遍历

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class LinkList:
    def __init__(self):
        self.head=None
    def initList(self, data):
        self.head = ListNode(data[0])
        r=self.head
        p = self.head
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r
    def convert_list(self,head):
        ret = []
        if head == None:
            return
        node = head
        while node != None:
            ret.append(node.val)
            node = node.next
        return ret
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        v = ListNode(0, head)
        handle = v
        index = []
        while v is not None:
            index.append(v)
            v = v.next
        pre = len(index)-n-1
        next = len(index)-n+1
        index[pre].next = index[next] if next >= 0 and next < len(
            index) else None
        return handle.next
# %%
l = LinkList()
list1 = [1,2,3,4,5]
head = l.initList(list1)
n = 2
s = Solution()
print(l.convert_list(s.removeNthFromEnd(head, n)))

class Solution(object):
    def minWindow(self, s, t):
        ls_s, ls_t = len(s), len(t)
        need_to_find = [0] * 256
        has_found = [0] * 256
        min_begin, min_end = 0, -1
        min_window = 100000000000000
        for index in range(ls_t):
            need_to_find[ord(t[index])] += 1
        count, begin = 0, 0
        for end in range(ls_s):
            end_index = ord(s[end])
            if need_to_find[end_index] == 0:
                continue
            has_found[end_index] += 1
            if has_found[end_index] <= need_to_find[end_index]:
                count += 1
            if count == ls_t:
                begin_index = ord(s[begin])
                while need_to_find[begin_index] == 0 or\
                    has_found[begin_index] > need_to_find[begin_index]:
                    if has_found[begin_index] > need_to_find[begin_index]:
                        has_found[begin_index] -= 1
                    begin += 1
                    begin_index = ord(s[begin])
                window_ls = end - begin + 1
                if window_ls < min_window:
                    min_begin = begin
                    min_end = end
                    min_window = window_ls
        if count == ls_t:
            return s[min_begin:min_end + 1]
        else:
            return ''
if __name__ == '__main__':
    s = Solution()
    print(s.minWindow(s = "ADOBECODEBANC", t = "ABC"))
    print(s.minWindow('a', 'a'))

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        queue, res = [root], []
        while queue:
            size = len(queue)
            temp = []
            for i in range(size):
                data = queue.pop(0)
                temp.append(data.val)
                if data.left:
                    queue.append(data.left)
                if data.right:
                    queue.append(data.right)
            res.append(temp)
        return res
def listToTree(lst):
    if not lst:
        return None
    root = TreeNode(lst[0])
    queue = [root]
    i = 1
    while i < len(lst):
        node = queue.pop(0)
        if lst[i] is not None:
            node.left = TreeNode(lst[i])
            queue.append(node.left)
        i += 1
        if i < len(lst) and lst[i] is not None:
            node.right = TreeNode(lst[i])
            queue.append(node.right)
        i += 1
    return root
if __name__ == '__main__':
    s = Solution()
    null = None
    nums = [3,9,20,null,null,15,7]
    root = listToTree(nums)
    print(s.levelOrder(root))