Remove Duplicates系列笔记

第一题

Python代码：

# Definition for singly-linked list. class ListNode(object): def __init__(self, x): self.val = x self.next = None class Solution(object): def deleteDuplicates(self, head): """ :type head: ListNode :rtype: ListNode """ p = head q = p while p != None: while q is not None and q.val == p.val: q = q.next p.next = q p = q return head def printList(head): while head != None: print(head.val) head = head.next head = ListNode(-1) h = head arr = [1,1,2,2,3] for i in arr: h.next = ListNode(i) h = h.next r = Solution().deleteDuplicates(head.next) printList(r)

附java代码

class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode p = head; ListNode q = p; while(p != null) { while(q != null && p.val == q.val) { q = q.next; } p.next = q; p = q; } return head; } }

第二题

在上题的基础上稍加修改就好了，对于删除节点问题而言，最关键的是知道删除位置的前驱和后继，因此加入一个节点pre表示p的前驱。

Python代码：

# Definition for singly-linked list. class ListNode(object): def __init__(self, x): self.val = x self.next = None class Solution(object): def deleteDuplicates(self, head): """ :type head: ListNode :rtype: ListNode """ p = head q = p pre = ListNode(-1) pre.next = p h = pre while p != None: while q != None and q.val == p.val: q = q.next if p.next is q: pre = pre.next pre.next = q p = q return h.next

第三题

思路很简单，遇到一样数的就删除，不过删除的效率低了些。第一次使用list的remove()方法删除，结果在第161个用例时，超时。后来看了这篇博客，了解Python中list的底层是如何实现的，改用list.pop()方法删除，就不超时了，不过时间上还是较慢。

Python代码如下：

class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ for i in range(0, len(nums)): j = i + 1 while j < len(nums) and nums[j] == nums[i]: # nums.remove(nums[j]) # 用remove超时 nums.pop(j) return len(nums) # 第161个用例 -999 ~ 9999超时了 nums = [] for i in range(-999, 10000): nums.append(i) # 每个元素都重复一次 nums.append(i) length = Solution().removeDuplicates(nums) print(length)

附java 代码

class Solution { public int removeDuplicates(int[] nums) { int len = 0; for(int i = 0; i < nums.length; i++) { while(i < nums.length-1 && nums[i] == nums[i+1]) { i++; } nums[len++] = nums[i]; } return len; } }

第四题

与上一题不同的是，重复的数字最多可以保留两个，直接把上面程序中第8行的j = i + 1改为j = i + 2，就AC了

Python 代码：

class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ for i in range(0, len(nums)): j = i + 2 # i + 1改为 i + 2 while j < len(nums) and nums[j] == nums[i]: # nums.remove(nums[j]) nums.pop(j) print(nums) return len(nums)

附java代码

class Solution { public int removeDuplicates(int[] nums) { int len = 0; for(int i = 0; i < nums.length; i++) { while(i < nums.length-2 && nums[i] == nums[i+1] && nums[i] == nums[i+2]) { i++; } nums[len++] = nums[i]; } return len; } }