Python 刷Leetcode题库,顺带学英语单词(26)

简介: Python 刷Leetcode题库,顺带学英语单词(26)

Remove Duplicates from Sorted List


Given a sorted linked list, delete all duplicates such that each element appear only once.   [#83]

Examples:
Input: 1->1->2
Output: 1->2
Input: 1->1->2->3->3
Output: 1->2->3



题意:给定已排序的链表,删除所有重复项,使每个元素只显示一次

遍历出链表所有元素,转化成列表处理掉重复项,再遍历列表创建结果链表

>>> class Node():
  def __init__(self, value=None, Next=None):
    self.val = self.value = value
    self.next = Next
  def __repr__(self):
    return f'NodeList[{self.val}->{self.next}]'
  def __str__(self):
    return f'{self.val}->{self.next}'
  @property
  def values(self):
    ret,cur = [],self
    while cur:
      ret.append(cur.val)
      cur = cur.next
    return ret
  def build(lst: list):
    ret = Node(lst[0])
    cur = ret
    for i in lst[1:]:
      cur.next = Node(i)
      cur = cur.next
    return ret
  def delDup(node):
    lst1,lst2 = [],node.values
    for i in lst2:
      if i not in lst1:
        lst1.append(i)
    return Node.build(lst1)
>>> in1 = Node.build([1,1,2])
>>> in1
NodeList[1->1->2->None]
>>> out1 = Node.delDup(in1)
>>> out1
NodeList[1->2->None]
>>> 
>>> in2 = Node.build([1,1,2,3,3])
>>> in2
NodeList[1->1->2->3->3->None]
>>> out2 = Node.delDup(in2)
>>> out2
NodeList[1->2->3->None]
>>> 



上面这是偷懒的做法,但遍历了2次,取值和创建节点各一次遍历。正规的做法只要遍历一次,在遍历的同时创建符合结果要求的节点链表,就相当于在有条件地复制一个已节点。用以下函数替换上面的 delDup() 其它不变,再做测试:

  def removeDup(node):
    ret = Node()
    p1,p2 = node,ret  # 相当于设置了2个“指针”
    while p1 is not None:
      if p1.val != p2.val:
        p2.next = Node(p1.val)
        p2 = p2.next
      p1 = p1.next    # “指针”向后移动
    return ret.next  # 加上.next 去掉“空”的“头节点”
>>> a = Node.build([1,1,2,3,3])
>>> Node.removeDup(a)
NodeList[1->2->3->None]
>>> b = Node.build([1,2,2,3,4,4,4,5])
>>> Node.removeDup(b)
NodeList[1->2->3->4->5->None]
>>> 



Remove Duplicates from Sorted List II


Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.   [#82]


Examples:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Input: 1->1->1->2->3
Output: 2->3



题意:给定已排序的链表,删除所有重复项,只留不重复元素

和上题一样,先遍历出数据,完成任务后再创建节点,也是偷懒的做法:

>>> class Node():
  def __init__(self, value=None, Next=None):
    self.val = self.value = value
    self.next = Next
  def __repr__(self):
    return f'NodeList[{self.val}->{self.next}]'
  def __str__(self):
    return f'{self.val}->{self.next}'
  @property
  def values(self):
    ret,cur = [],self
    while cur:
      ret.append(cur.val)
      cur = cur.next
    return ret
  def build(lst):
    ret = Node(lst[0])
    cur = ret
    for i in lst[1:]:
      cur.next = Node(i)
      cur = cur.next
    return ret
  def delDup2(node):
    lst1 = node.values
    lst2 = [i for i in lst1 if lst1.count(i)==1]
    return Node.build(lst2)
>>> in1 = Node.build([1,2,3,3,4,4,5])
>>> in1
NodeList[1->2->3->3->4->4->5->None]
>>> out1 = Node.delDup2(in1)
>>> out1
NodeList[1->2->5->None]
>>> in2 = Node.build([1,1,1,2,3])
>>> in2
NodeList[1->1->1->2->3->None]
>>> out2 = Node.delDup2(in2)
>>> out2
NodeList[2->3->None]
>>> 


这题的正规做法: 头、尾节点除外,只遍历所有中间节点,它们的值与前后两个节点值比较,都不相等才能进入结果链表;头节点只和自己的后续节点比较,尾节点只和自己的前驱节点比较。

def removeDup(node):
        ret = Node()
        p1,p2 = node,ret
        if not Node.isNode(p1.next):
                return node
        if p1.val != p1.next.val:
                p2.next = Node(p1.val)
                p2 = p2.next
        t = p1.val
        p1 = p1.next
        while p1.next is not None:
                if t != p1.val != p1.next.val:
                        p2.next = Node(p1.val)
                        p2 = p2.next
                t = p1.val
                p1 = p1.next
        if t != p1.val:
                p2.next = Node(p1.val)
        return ret.next if ret.next!=None else Node()
''''
# 测试结果:
>>> a = Node.build([1,2,3,3,4,4,5]);removeDup(a)
Node(1->2->5->None)
>>> b = Node.build([1,1,1,2,3]);removeDup(b)
Node(2->3->None)
>>>
>>> b = Node.build([1,1]);removeDup(b)
Node(None->None)
>>> b = Node.build([1,2]);removeDup(b)
Node(1->2->None)
>>> b = Node.build([1,2,2]);removeDup(b)
Node(1->None)
>>> b = Node.build([1,1,2]);removeDup(b)
Node(2->None)
>>> b = Node.build([0,0,1,2,2,2,3,3]);removeDup(b)
Node(1->None)
>>> b = Node.build([0,0,1,2,2,2,3]);removeDup(b)
Node(1->3->None)
>>> 
''''



目录
打赏
0
0
0
0
74
分享
相关文章
Python实用记录(十四):python统计某个单词在TXT/JSON文件中出现的次数
这篇文章介绍了一个Python脚本,用于统计TXT或JSON文件中特定单词的出现次数。它包含两个函数,分别处理文本和JSON文件,并通过命令行参数接收文件路径、目标单词和文件格式。文章还提供了代码逻辑的解释和示例用法。
84 0
Python实用记录(十四):python统计某个单词在TXT/JSON文件中出现的次数
|
5月前
Leetcode(最后一个单词长度)
这篇文章介绍了两种解决LeetCode第58题的方法,即计算给定字符串中最后一个单词的长度,方法包括翻转字符串和逆向遍历统计。
36 0
|
5月前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
39 0
Python编写单词复习小程序
Python编写单词复习小程序
49 0
LeetCode第58题最后一个单词的长度
LeetCode第58题"最后一个单词的长度"的解题方法,通过从字符串末尾向前遍历并计数非空格字符,直接得出最后一个单词的长度。
LeetCode第58题最后一个单词的长度
|
7月前
|
【Leetcode刷题Python】1467. 两个盒子中球的颜色数相同的概率
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
96 0
|
7月前
|
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
51 1
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
167 2
|
7月前
|
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
65 0
【Leetcode刷题Python】73. 矩阵置零
|
7月前
|
【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
本文介绍了LeetCode 478题的解法,题目要求在给定圆的半径和圆心位置的情况下实现在圆内均匀随机生成点的功能,并提供了Python的实现代码。
55 1

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等