Python每日一练(20230423)
目录
2. 最小覆盖子串 🌟🌟🌟
3. 二叉树的层序遍历 🌟🌟
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 <= 300 <= Node.val <= 1001 <= 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 <= 105s和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]]
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
 | Golang每日一练 专栏 |
 | Python每日一练 专栏 |
 | C/C++每日一练 专栏 |
 | Java每日一练 专栏 |
相关文章
- Python该怎么入门?Python入门教程(非常详细)「建议收藏」
- python运行代码不成功_Python | PyCharm无法直接运行（Run）脚本
- 在pycharm中如何新建Python文件?_github下载的python源码项目怎么用
- python十进制转换_Python 进制转换
- Python入门系列（六）一篇学会python函数
- python 时间操作
- Python编程 数据类型
- python动态心形代码简单_python心形曲线代码
- Python：利用python代码编程实现将视频的avi格式转换为MP4格式
- Python学生信息管理系统课程设计报告_python做的项目管理系统
- 用python编写猴子吃桃问题_人工智能猴子摘香蕉
- Python win32api_python api文档
- 人生苦短，我用Python-手把手教你如何使用python写串口调试助手
- Python中三个装饰器函数用法（property、staticmethod、classmethod ）
- python多进程编程-进程通信之Manager
- Python-声明变量
- python-Python与MySQL数据库-使用Python执行MySQL查询
- python-Python与MongoDB数据库-处理MongoDB查询结果
- python监控本机cpu的利用百分比情况详解编程语言
- Linux上的Python之旅（linux自带python）
- 一步一步学会在Linux上运行Python程序（linux运行python程序）
- python-“*”号解压详解编程语言
- Python IDLE调试程序详解
- Linux 启动 Python编程之旅（linux打开python）
- 如何在使用 Vim 时访问/查看 Python 帮助
- 运维学python之爬虫工具篇（一）Requests库的用法
- python冒泡排序算法的实现代码
- 用python删除java文件头上版权信息的方法
- python处理PHP数组文本文件实例