-
LeetCode27——移除元素【简单】
问题描述：给定一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。不要使用额外的数组空间，必须仅使用 O(1) 额外空间并原地修改输入数组。
双指针法：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
n = len(nums)
left = 0
right = 0
while right < n:
if nums[right] != val:
nums[left] = nums[right]
left += 1
right += 1
return left
-
问题描述：给你一个 升序排列 的数组 nums ，请原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持一致。必须将结果放在数组nums的第一部分，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。不要使用额外的空间，必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
双指针法：
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return None
left = 1
right = 1
while right < n:
if nums[right] != nums[right - 1]:
nums[left] = nums[right]
left += 1
right += 1
return left
-
问题描述：给你一个有序数组 nums ，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。不要使用额外的数组空间，必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
双指针法：
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
if n <= 2:
return n
left = 1
right = 1
count = 1
while right < n:
if nums[right] != nums[right - 1]:
nums[left] = nums[right]
left += 1
count = 1
else:
count += 1
if count <= 2:
nums[left] = nums[right]
left += 1
right += 1
return left
-
问题描述：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。
转化为查找第K小的元素：
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m = len(nums1)
n = len(nums2)
if (m + n) % 2 == 1:
return self.findKthElement(nums1, nums2, (m + n + 1) // 2)
else:
return (self.findKthElement(nums1, nums2, (m + n )//2) + self.findKthElement(nums1, nums2, (m + n )//2 + 1)) / 2.0
def findKthElement(self, nums1, nums2, k):
m = len(nums1)
n = len(nums2)
idx1 = 0
idx2 = 0
while True:
if idx1 == m:
return nums2[idx2 + k - 1]
if idx2 == n:
return nums1[idx1 + k - 1]
if k == 1:
return min(nums1[idx1], nums2[idx2])
newIdx1 = min(idx1 + k // 2 - 1, m - 1)
newIdx2 = min(idx2 + k // 2 - 1, n - 1)
if nums1[newIdx1] <= nums2[newIdx2]:
k -= newIdx1 - idx1 + 1
idx1 = newIdx1 + 1
else:
k -= newIdx2 - idx2 + 1
idx2 = newIdx2 + 1
-
问题描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1:
return list2
if not list2:
return list1
while list1 and list2:
if list1.val <= list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
-
问题描述：给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
ans = head
if not head:
return None
while head.next:
if head.val == head.next.val:
if head.next.next:
head.next = head.next.next
else:
head.next = None
else:
head = head.next
return ans
-
LeetCode203——移除链表元素【简单】
问题描述:给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
ans = head
if not head:
return None
while head.next:
if head.next.val == val:
if head.next.next:
head.next = head.next.next
else:
head.next = None
else:
head = head.next
# 判断头节点是否等于val
if ans.val == val:
return ans.next
else:
return ans
-
问题描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
length = 0
temp = head
while temp:
length += 1
temp = temp.next
if length == 0:
return None
if length - n == 0:
return head.next
temp = head
for i in range(length - n - 1):
temp = temp.next
if temp.next.next:
temp.next = temp.next.next
else:
temp.next = None
return head
-
LeetCode234——回文链表【简单】
问题描述：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
invertedList = ListNode(val=head.val)
temp = head
while temp.next:
newNode = ListNode(val = temp.next.val)
newNode.next = invertedList
invertedList = newNode
temp = temp.next
while head:
if head.val != invertedList.val:
return False
head = head.next
invertedList = invertedList.next
return True
-
LeetCode61——旋转链表【中等】
问题描述：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
length = 0
temp = head
while temp:
length += 1
temp = temp.next
if length <= 1:
return head
for i in range(k % length):
head = self.rotate(head)
return head
def rotate(self, root):
temp = root
while temp.next.next:
temp = temp.next
ans = ListNode(val=temp.next.val)
temp.next = None
ans.next = root
root = ans
return root
