第一題
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;
}
}