算法题(三)
2021/12/9 1:17:00
本文主要是介绍算法题(三),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1、合并两个有序链表
解题思路:两个链表都是升序链表,要将其串成一个升序链表,则需要新建一个链表,每次都指向节点的最小值,要考虑链表越界的情况。时间复杂度O(m+n),空间复杂度O(1)。
代码:
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def mergeTwoLists(self, list1, list2): """ :type list1: Optional[ListNode] :type list2: Optional[ListNode] :rtype: Optional[ListNode] """ flage1 = list1;flage2= list2 newlist = ListNode() satrt = newlist while flage1 != None or flage2 != None: if flage1 == None: newlist.next = flage2 break if flage2 == None : newlist.next = flage1 break if flage1.val <= flage2.val: newlist.next = flage1 flage1 = flage1.next else: newlist.next = flage2 flage2 = flage2.next newlist = newlist.next return satrt.next
注意:此题可用递归法,也可以用循环法。
2、删除有序数组中的重复项
解题思路:这道题比较简单,但是letcode上很多解法是不符合题意的。题中明确提到,需要原地删除旧数组中的元素!如果不删除这道题就很简单,遍历一遍就可以找到结果,但是如果原地删除旧数组中的元素,将会导致索引变化。因此可以采用双指针的方式来记录删除前后的位置信息。时间复杂度O(n),空间复杂度O(1)。
class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums) <2: return len(nums) l = 0 f = 1 while l!=f: if f> len(nums)-1: break if nums[f] == nums[l]: del nums[f] else: l+=1 f+=1 return len(nums)
3、移除元素
解题思路:与上一题类似,只需要用一个指针记录位置就可以,符合条件就删除,不符合条件指针就+1。
class Solution(object): def removeElement(self, nums, val): """ :type nums: List[int] :type val: int :rtype: int """ p = 0 while p < len(nums): if nums[p] ==val: del nums[p] else: p += 1 return len(nums)
这篇关于算法题(三)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南