昨天转载了篇关于递归算法的解读文,很佩服可以透彻掌握算法又能信手拈来做讲解。反思之前我刷题的记录,像是记流水账、没太多营养,所以希望有时间的话能继续深挖下算法,也能加深自己的理解。
今天要刷的两道题,第一个是昨天链表交换节点的升级版的困难级别题目,第二个是对数组去重的简单级别题目。本着能做完就算过关的态度,我先分享自己的尝试,再来观摩题解区可借鉴的思路。
第 25 题:K 个一组翻转链表
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例:
给你这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
#来源:力扣(LeetCode)
#链接:https://leetcode-cn.com/problems/reverse-nodes-in-k-group
说明:
你的算法只能使用常数的额外空间。你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
最初是想就着昨天那个能够两两交换节点的递归算法来实现,尝试半天没能写出来,只好先降低难度来解决了。因为对链表不好操作,我们不妨把链表就转化为数字组成的列表,题目也就转化为了将列表中的元素每 k 个进行一翻转:
输入:[1,2,3,4,5]
k = 2 时,输出:[2,1,4,3,5]
k = 3 时,输出:[3,2,1,4,5]
最后再将翻转后的列表按顺序生成链表即可。至于每 k 个元素一翻转,这个过程我是靠列表切片实现的。
比如 lst = [1,2,3,4,5] 列表中,我们可以通过 lst[0] 取其中第一个元素 1,也可以通过切片 lst[2:4] 对列表切片提取其中的第三、四位元素组成的列表。
切片的格式是“列表[起始位置:结束位置:步长]”,起始位置默认为 0、结束位置默认为列表长度值、步长默认为1,lst[:] 即省略掉三者,即 lst 所有元素,lst[::-1] 则将步长调整为 -1,可以实现对列表的翻转或逆向提取得到 [5,4,3,2,1]。
回到题目中,我们想将列表中的前两位翻转,可以取 lst[1::-1],之后的两位翻转取 lst[3:1:-1],最后无需翻转的部分 lst[4:] 。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
# 复制下起点节点,后续会用
start_copy = head
# 遍历链表,将节点值存到列表中
lst =[]
while head!=None:
lst.append(head.val)
head = head.next
# 记录链表长度
l = len(lst)
# 若链表长度小于k,则无需翻转
if l<k:
return start_copy
# 我们先将前 k 个点切片翻转,因为它和其它中间切片表示形式不一样
lst2 = lst[k-1::-1]
# 用 count 来记录其余切片的位置
count = k-1+k
# 当切片起点小于列表长度,就进行切片翻转
while count<l:
lst2+=lst[count:count-k:-1]
count+=k
# 可以计算出剩余不足 k 的节点
lst2+=lst[l//k*k:]
# 新建链表起点
new_start = ListNode(0)
new_copy = new_start
# 遍历生成的列表,以值来生成新链表
for item in lst2:
new_start.next = ListNode(item)
new_start = new_start.next
# 将生成的链表返回
return new_copy.next
执行用时 : 52 ms, 在所有 Python3 提交中击败了 80.47% 的用户
内存消耗 : 15.1 MB, 在所有 Python3 提交中击败了 7.69% 的用户
提交了几次,用时 52 到 76ms 都有出息,76ms 就只击败 25.93% 用户了,差之毫秒,击败的比例却不小。
第 26 题:删除排序数组中的重复项
给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
#来源:力扣(LeetCode)
#链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
既然是道简单题,又看到要求返回的是去重之后的数组长度,最初我想的是将 nums 列表转化为集合 set(nums),然后用 len() 来求集合长度来返回。但提交后无法通过,因为它要求代码过程中要实现对 nums 重复元素的删除,最终是通过去重后的 nums 来检查结果的。
感觉这里可能要考的就是,如何在遍历列表的过程中删除元素,因为删除元素会影响列表长度,可能导致遍历的 for 语句报错。于是我们可以复制一个列表用来控制 for 语句,这样删除列表元素并不影响控制进度的列表。
题目中提到了是个排序数组,所以我们只要检测到该位与上一位相同时,在列表中删除掉一位该元素即可。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
# 用来控制 for 的列表
copy = nums[:]
# 对复制的列表遍历
for i in range(1,len(copy)):
# 当元素与之前元素相同时
if copy[i]==copy[i-1]:
# 在 nums 列表中删除该元素
nums.remove(copy[i])
# 返回最终删完元素后列表长度
return len(nums)
执行用时 : 700 ms, 在所有 Python3 提交中击败了 9.32% 的用户
内存消耗 : 14.5 MB, 在所有 Python3 提交中击败了 8.16% 的用户
原本应该再对推荐题解进行分析解读的,今天完不成了,明天补上吧。别看写的题目简单,还挺费时间的,尤其是我可能卡几个小时完全没头绪才去参考题解,再稍微一分心,时间就没了。
目前这两个题算是独立解决,但可能解决方法不太切中题目考点、或者使用的思路还可以继续优化,所以仍需补充整理,这个明天补上~