2021.08.20-力扣刷题(70,69、83、88、100)
2021/8/19 23:07:05
本文主要是介绍2021.08.20-力扣刷题(70,69、83、88、100),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
70. 爬楼梯
链接:https://leetcode-cn.com/problems/climbing-stairs/
方法一:动态规划
class Solution: def climbStairs(self, n: int) -> int: dp = [0 for _ in range(n+1)] if n<=2: return n for i in range(3, n+1): dp[1] = 1 dp[2] = 2 dp[i] = dp[i-1] + dp[i-2] return dp[-1]
方法二:状态压缩
class Solution: def climbStairs(self, n: int) -> int: if n <= 2: return n dp = [1, 2] for i in range(3, n+1): ans = dp[0] + dp[1] dp[0], dp[1] = dp[1], ans return dp[1]
69. x 的平方根
链接:https://leetcode-cn.com/problems/sqrtx/
class Solution: def mySqrt(self, x: int) -> int: if x < 2: return x left = 1 right = x//2 while left <= right: mid = left + (right - left) // 2 if mid ** 2 > x: right = mid -1 else: left = mid + 1 return right
83. 删除排序链表中的重复元素
链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
# 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: ListNode) -> ListNode: start = head while start: cur = start.next while cur: if cur.val == start.val: cur = cur.next else: break start.next = cur start = start.next return head
88. 合并两个有序数组
链接:https://leetcode-cn.com/problems/merge-sorted-array/
方法一:双指针(但是通不过,在本地编辑器里能通过)
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ ans = [] if m == 0: ans = nums2 if n == 0: ans = nums1[:m] i=0 j=0 k=0 while i<m and j<n: if nums1[i] <= nums2[j]: ans.append(nums1[i]) i += 1 else: ans.append(nums2[j]) j += 1 k += 1 if i < m: ans.extend(nums1[i:]) elif j < n: ans.extend(nums2[j:]) nums1[:] = sorted(ans)
方法二:切片后排序
最直观的方法是先将数组nums2放进数组nums1[m:] 的尾部,然后直接对整个数组进行排序。
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ nums1[m:]= nums2 nums1.sort()
100. 相同的树
链接:https://leetcode-cn.com/problems/same-tree/submissions/
方法:深度优先dfs
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: if not p and not q: return True if p == None or q == None: return False if p.val != q.val: return False return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
这篇关于2021.08.20-力扣刷题(70,69、83、88、100)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)