翻转链表与数组去重—— LeetCode 第 25、26 题记
翻转链表与数组去重—— LeetCode 第 25、26 题记
昨天转载了篇关于递归算法的解读文，很佩服可以透彻掌握算法又能信手拈来做讲解。反思之前我刷题的记录，像是记流水账、没太多营养，所以希望有时间的话能继续深挖下算法，也能加深自己的理解。
今天要刷的两道题，第一个是昨天链表交换节点的升级版的困难级别题目，第二个是对数组去重的简单级别题目。本着能做完就算过关的态度，我先分享自己的尝试，再来观摩题解区可借鉴的思路。
题目一
第 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% 的用户
后记
原本应该再对推荐题解进行分析解读的，今天完不成了，明天补上吧。别看写的题目简单，还挺费时间的，尤其是我可能卡几个小时完全没头绪才去参考题解，再稍微一分心，时间就没了。
目前这两个题算是独立解决，但可能解决方法不太切中题目考点、或者使用的思路还可以继续优化，所以仍需补充整理，这个明天补上～