网站规划与建设是什么意思,东莞php网站建设,南宁网站建设找哪家公司,wordpress 反斜杠目录
1. 排序链表 ★★
2. 最长连续序列 ★★
3. 扰乱字符串 ★★★
#x1f31f; 每日一练刷题专栏 #x1f31f;
Golang每日一练 专栏
Python每日一练 专栏
C/C每日一练 专栏
Java每日一练 专栏 1. 排序链表
给你链表的头结点 head #xff0c;请将其按 升序 …
目录
1. 排序链表 ★★
2. 最长连续序列 ★★
3. 扰乱字符串 ★★★ 每日一练刷题专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C每日一练 专栏
Java每日一练 专栏 1. 排序链表
给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。
进阶
你可以在 O(nlogn) 时间复杂度和常数级空间复杂度下对链表进行排序吗
示例 1 输入head [4,2,1,3]
输出[1,2,3,4]示例 2 输入head [-1,5,3,4,0]
输出[-1,0,3,4,5]示例 3
输入head []
输出[]提示
链表中节点的数目在范围 [0, 5 * 10^4] 内-10^5 Node.val 10^5
代码
class ListNode:def __init__(self, x):self.val xself.next Noneclass Solution:def sortList(self, head: ListNode) - ListNode:if head None:return Noneelse:return self.mergeSort(head)def mergeSort(self, head):if head.next None:return headfast headslow headpre Nonewhile fast ! None and fast.next ! None:pre slowslow slow.nextfast fast.next.nextpre.next Noneleft self.mergeSort(head)right self.mergeSort(slow)return self.merge(left, right)def merge(self, left, right):tempHead ListNode(0)cur tempHeadwhile left ! None and right ! None:if left.val right.val:cur.next leftcur cur.nextleft left.nextelse:cur.next rightcur cur.nextright right.nextif left ! None:cur.next leftif right ! None:cur.next rightreturn tempHead.nextclass LinkList:def __init__(self):self.head Nonedef initList(self, data):if not data: return Noneself.head ListNode(data[0])p head self.headfor i in data[1:]:node ListNode(i)p.next nodep p.nextreturn headdef showList(self, head):if head:print(head.val, end -)self.showList(head.next)else:print(null)if __name__ __main__:s Solution()l LinkList()head l.initList([4,2,1,3])l.showList(head)head s.sortList(head)l.showList(head)head l.initList([-1,5,3,4,0])l.showList(head)head s.sortList(head)l.showList(head)
输出
4-2-1-3-null 1-2-3-4-null -1-5-3-4-0-null -1-0-3-4-5-null 2. 最长连续序列
给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1
输入nums [100,4,200,1,3,2]
输出4
解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2
输入nums [0,3,7,2,5,8,4,6,0,1]
输出9提示
0 nums.length 10^5-10^9 nums[i] 10^9
代码
class ListNode:def __init__(self, x):self.val xself.next Noneclass Solution:def longestConsecutive(self, nums: list) - int:hash_dict {}max_length 0for num in nums:if num not in hash_dict:pre_length hash_dict.get(num - 1, 0)next_length hash_dict.get(num 1, 0)cur_length pre_length 1 next_lengthif cur_length max_length:max_length cur_lengthhash_dict[num] cur_lengthhash_dict[num - pre_length] cur_lengthhash_dict[num next_length] cur_lengthreturn max_lengthif __name__ __main__:s Solution()nums [100,4,200,1,3,2]print(s.longestConsecutive(nums))nums [0,3,7,2,5,8,4,6,0,1]print(s.longestConsecutive(nums))输出
4 9 3. 扰乱字符串
使用下面描述的算法可以扰乱字符串 s 得到字符串 t
如果字符串的长度为 1 算法停止如果字符串的长度 1 执行下述步骤 在一个随机下标处将字符串分割成两个非空的子字符串。即如果已知字符串 s 则可以将其分成两个子字符串 x 和 y 且满足 s x y 。随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即在执行这一步骤之后s 可能是 s x y 或者 s y x 。在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。
给你两个 长度相等 的字符串 s1 和 s2判断 s2 是否是 s1 的扰乱字符串。如果是返回 true 否则返回 false 。
示例 1
输入s1 great, s2 rgeat
输出true
解释s1 上可能发生的一种情形是
great -- gr/eat // 在一个随机下标处分割得到两个子字符串
gr/eat -- gr/eat // 随机决定「保持这两个子字符串的顺序不变」
gr/eat -- g/r / e/at // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
g/r / e/at -- r/g / e/at // 随机决定第一组「交换两个子字符串」第二组「保持这两个子字符串的顺序不变」
r/g / e/at -- r/g / e/ a/t // 继续递归执行此算法将 at 分割得到 a/t
r/g / e/ a/t -- r/g / e/ a/t // 随机决定「保持这两个子字符串的顺序不变」
算法终止结果字符串和 s2 相同都是 rgeat
这是一种能够扰乱 s1 得到 s2 的情形可以认为 s2 是 s1 的扰乱字符串返回 true示例 2
输入s1 abcde, s2 caebd
输出false示例 3
输入s1 a, s2 a
输出true提示
s1.length s2.length1 s1.length 30s1 和 s2 由小写英文字母组成
代码
class Solution(object):def isScramble(self, s1, s2, memo{}):if len(s1) ! len(s2) or sorted(s1) ! sorted(s2):return Falseif len(s1) len(s2) 1:return s1 s2if s1 s2:return Trueif (s1, s2) in memo:return memo[s1, s2]n len(s1)for i in range(1, n):a self.isScramble(s1[:i], s2[:i], memo) and self.isScramble(s1[i:], s2[i:], memo)if not a:b self.isScramble(s1[:i], s2[-i:], memo) and self.isScramble(s1[i:], s2[:-i], memo)if a or b:memo[s1, s2] Truereturn Truememo[s1, s2] Falsereturn False# %%
s Solution()
print(s.isScramble(s1 great, s2 rgeat))
print(s.isScramble(s1 abcde, s2 caebd))
print(s.isScramble(s1 a, s2 a))
输出
True False True 每日一练刷题专栏
✨ 持续努力奋斗做强刷题搬运工 点赞你的认可是我坚持的动力 收藏你的青睐是我努力的方向
✎ 评论你的意见是我进步的财富 Golang每日一练 专栏 Python每日一练 专栏 C/C每日一练 专栏 Java每日一练 专栏
