天天看點

Remove Duplicates系列筆記

第一題

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

第二題

Remove Duplicates系列筆記

在上題的基礎上稍加修改就好了,對于删除節點問題而言,最關鍵的是知道删除位置的前驅和後繼,是以加入一個節點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      
Remove Duplicates系列筆記

第三題

Remove Duplicates系列筆記

思路很簡單,遇到一樣數的就删除,不過删除的效率低了些。第一次使用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)      
Remove Duplicates系列筆記

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

第四題

Remove Duplicates系列筆記

與上一題不同的是,重複的數字最多可以保留兩個,直接把上面程式中第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;
    }
}