搜索到
114
篇与
的结果
-
283. 移动零 双指针法+排序法 题目给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。示例 1:输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]示例 2: 输入: nums = [0] 输出: [0]提示:1 <= nums.length <= 104 -231 <= nums[i] <= 231 - 1进阶：你能尽量减少完成的操作次数吗？来源：力扣（LeetCode）链接：https://leetcode.cn/problems/move-zeroes著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法双指针法这个方法嘞，依旧是快慢指针，一个指针用来遍历，一个指针用来记录非零元素的位置。大概就是一个这样的过程：快指针一直往前走，如果遇到非零元素，就直接赋值给慢指针，然后慢指针+1这样一直执行下去，所有的非零元素都到了最前面。这时候，我们需要将后面的元素清零。我这边直接放在一个循环了。from typing import List class Solution: def moveZeroes(self, nums: List[int]) -> None: if nums: fast, slow, length = 0, 0, len(nums) while fast < length or slow < length: if fast != length: if nums[fast] != 0: nums[slow] = nums[fast] slow += 1 fast += 1 elif slow < length: nums[slow] = 0 slow += 1 Solution().moveZeroes([0, 1, 0, 3, 12])排序法刚刚看了下，我在2020年居然提交过这道题，一行解决。。。效率和上面方法差不多。class Solution: def moveZeroes(self, nums: List[int]) -> None: nums.sort(key=bool,reverse=True) -
88. 合并两个有序数组+双指针法 题目给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。 示例 1： 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。示例 2：输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。示例 3：输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] 解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。提示：nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -109 <= nums1[i], nums2[j] <= 109来源：力扣（LeetCode）链接：https://leetcode.cn/problems/merge-sorted-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法合并排序class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: nums1[m:] = nums2 nums1.sort()双指针法因为有两个list，因此就是两个指针，我们需要建立一个临时list，去存放结果。两个指针都从0开始，就是两个list的下标。fast = slow = 0然后两两比较，将小的那一个放到临时数组，并且下标+=1。最终，将临时list覆盖nums1。这是一种方法。然后还可以优化一下，不需要临时数组，因为nums1里面预留了nums2的位置，我们只需要将指针从大往小来插入即可。from typing import List class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: fast, slow, index = m - 1, n - 1, m + n - 1 while fast >= 0 or slow >= 0: if fast < 0: nums1[index] = nums2[slow] slow -= 1 elif slow < 0: nums1[index] = nums1[fast] fast -= 1 elif nums1[fast] > nums2[slow]: nums1[index] = nums1[fast] fast -= 1 else: nums1[index] = nums2[slow] slow -= 1 index -= 1 if __name__ == '__main__': Solution().merge([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3)
-
1. 两数之和 空间换时间 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例 1：输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：输入：nums = [3,2,4], target = 6输出：[1,2]示例 3：输入：nums = [3,3], target = 6输出：[0,1] 提示：2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109只会存在一个有效答案 进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？来源：力扣（LeetCode）链接：https://leetcode.cn/problems/two-sum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。这个题目为leetcode第一题，嗯的确有点坑。如果用暴力破解，因为要找两个数，所以至少需要循环两次。可以换一个思路。给我们了一个列表，和一个目标值，为表尊重，我们至少需要便利一次啵。然后两数之和嘛，a+b=c，现在a和c以及知道了，算出b的值。b=c-a。所以，我们就可以这样，循环一次，每次都是target-当前num得到的值判断得到的值是否在list。由于这是检索，因此可以配合字典，也就是hash，速度更快。class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: h = {} for index, value in enumerate(nums): num = h.get(target - value) if num is not None: return [index, num] else: h[value] = index
-
70. 爬楼梯，递归+递归优化+动态规划+动态规划优化 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？示例 1：输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 示例 2：输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶来源：力扣（LeetCode）链接：https://leetcode.cn/problems/climbing-stairs著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。昨天斐波拉契那道题，给我深受启发，然后今天又看见一个递归题，本来用递归是超时的，但是以空间换时间之后，直接通过class Solution: def __init__(self): self.r = [] def climbStairs(self, n: int) -> int: if len(self.r) == 0: self.r = [-1 for _ in range(n + 1)] if n <= 2: return n if self.r[n] != -1: return self.r[n] self.r[n] = self.climbStairs(n - 1) + self.climbStairs(n - 2) return self.r[n]然后再来动态规划一下。class Solution: def __init__(self): self.r = [1, 2] def climbStairs(self, n: int) -> int: if len(self.r) == 2: self.r = self.r + [-1 for _ in range(n - 1)] for i in range(2, n): self.r[i] = self.r[i - 1] + self.r[i - 2] return self.r[n - 1]以及优化一下空间class Solution: def climbStairs(self, n: int) -> int: if n <= 2: return n pre, cur = 1, 2 for i in range(2, n): pre, cur = cur, pre + cur return cur
-
剑指 Offer 10- I. 斐波那契数列，斐波拉契，递归优化法，动态规划法，及其优化 前言b站摸鱼，看见了这个视频，妙呀。先是递归，通过空间换时间。又是动态规划，优化空间。视频放在最后面了。前面是我个人学习笔记。笔记递归法up主直接三目运算符了，虽然代码简洁，但可读性体验感也会降低。体谅一下将来的我，还能看懂，所以我这里就拆开了。最基本的递归，求斐波拉契的第n项def fb_dg(n): if n < 2: return n return fb_dg(n - 1) + fb_dg(n - 2)如果要计算n项之和的话，就多了很多次重复的计算，因为每次都需要从n开始，一直减。然后可以新建一个list(虽然字典无序+哈希，检索比list要快，时间复杂度为O(1)，而list为O(n)，但是好像我们这个直接根据下标，所以用list更快），并且需要创建n+1个初始值，防止出现下标越界的情况。用于存放每次计算的结果，如果没有结果再进行计算。先来看一下效果，一个字6，本来想放毫秒的，但是它的实力不允许。def fb_dg_zd(n, r: list): if n < 2: return n v = r[n] if v != -1: return v else: r[n] = fb_dg_zd(n - 1, r) + fb_dg_zd(n - 2, r) return r[n]对比一下老方法。我已经不想等了，没有对比就没有伤害，在这个空间不值钱的时代，666。我想起了我之前公司项目的时候，也是用了空间换时间，我需要将某方案复制一份，包括其子项指标啥的一堆东西，是一个递归，然后我就用dict，建由于数据主键都是雪花id，所以每一条数据都是唯一的主键值，因此我只需要一个dict，并且直接存主键id即可，如果有就直接get，没有就新增进去，下次get就可以返回了，节省了很多时间。动态规划法def fb_dt(n): dp = [0, 1] + [-1 for _ in range(n - 1)] for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]优化空间之后，这个def fb_dt_zd(n): if n < 2: return n pre, cur = 0, 1 for i in range(2, n + 1): pre, cur = cur, pre + cur return cur时间对比，有进步，但不多，反正比原始递归强。源视频{bilibili bvid="BV1W14y1A7Eq" page=""/}Leetcode写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 示例 1：输入：n = 2 输出：1 示例 2：输入：n = 5 输出：5来源：力扣（LeetCode）链接：https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。代码class Solution: def __init__(self): self.r = [] self.MOD = 10 ** 9 + 7 def fib(self, n: int) -> int: if n < 2: return n if len(self.r) == 0: self.r = [-1 for _ in range(n + 1)] v = self.r[n] if v != -1: return v % self.MOD else: self.r[n] = self.fib(n - 1) + self.fib(n - 2) return self.r[n] % self.MOD
-
【逻辑智力题】水桶倒水问题 缘起今天逛牛客，然后看见了这个题目不禁想起了我的第一份offer，当时面笔试的时候最后一道题就是这个。然后发现还有几个类似的，汇总过来，记录一下题目1、取4L的水问题：水资源无限，3L和5L水桶各一个，怎样取4L的水？步骤：5L桶装满，倒满3L桶，5L桶剩2L3L桶倒空，5L桶倒至3L桶，3L桶剩2L5L桶装满，倒满3L桶，此时5L桶剩4L2. 取3L的水问题水资源无限，5L和6L水桶各一个，怎样取3L的水？步骤：6L桶装满，倒满5L桶，6L桶剩1L5L桶倒空，6L桶倒至5L桶，5L桶剩1L6L桶装满，倒满5L桶，6L桶剩4L5L桶倒空，6L桶倒至5L桶，5L桶剩2L6L桶装满，倒满5L桶，6L桶剩3L3. 3、取2个5L的水问题一个装了10L水的桶，一个7L的空桶，一个3L的空桶，怎样变成2个5L？步骤10L桶倒满3L桶，3L桶倒至7L桶 7 3 010L桶倒满3L桶，3L桶倒至7L桶 4 6 010L桶倒满3L桶，3L桶倒满7L桶 1 7 27L桶倒至10L桶 8 0 23L桶倒至7L桶 8 2 010L桶倒满3L桶，3L桶倒至7L桶 5 5 0总结这种题目其实有多种解法，我当时做出来后，回来和我同学说，发现有些同学的方法和我不一样，但是结果是对的。
-
链表设计 python 单链表class MyLinkedList: def __init__(self, head=None, size=0): self.head = head self.size = size def get(self, index): if index >= self.size or not self.head: return -1 cur = self.head while index: cur = cur.next index -= 1 return cur.val def add_at_head(self, val): self.head = ListNode(val, self.head) self.size += 1 def add_at_tail(self, val): if not self.head: self.head = ListNode(val) else: cur = self.head while cur.next: cur = cur.next cur.next = ListNode(val) self.size += 1 def add_at_index(self, val, index): if not index > self.size: if index <= 0: self.add_at_head(val) else: cur = self.head while index - 1: cur = cur.next index -= 1 cur.next = ListNode(val, cur.next) self.size += 1 def delete_at_index(self, index): if index < self.size: if not index: self.head = self.head.next else: cur = self.head while index - 1: cur = cur.next index -= 1 cur.next = cur.next.next self.size -= 1
