1. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
出处：
https://edu.csdn.net/practice/26319573
代码：
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)))
输出：
[1, 2, 3, 5]
2. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
提示：
1 <= s.length, t.length <= 105
s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
以下程序实现了这一功能，请你填补空白处内容：
```python
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]) ____________________________; 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('a', 'a')) ```
出处：
https://edu.csdn.net/practice/26319574
代码：
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'))
输出：
BANC
a
3. 二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]
出处：
https://edu.csdn.net/practice/26319575
代码：
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))
输出：
[[3], [9, 20], [15, 7]]
