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)      

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;
    }
}