搜索到
450
篇与
的结果
-
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
-
Git 常用指令笔记，pycharm+gitlab，保姆级笔记 前言其实，我不用指令来管理代码版本，毕竟Pycharm提供的version control工具这么好用，效率这么高，还用啥指令嘞，但是吧，一切为了准备面试。 然后，昨晚睡不着，刷掘金，发现了一篇文章十分通俗易懂URL: https://juejin.cn/post/7084966730506141704因此也想借鉴一篇（码农的事情怎么能说是抄袭呢）本文将以Pycharm编辑器，Gitlab作为远程仓库介绍相关使用，不使用Github因为他老抽风（刚刚本来想用github演示，结果拉不下来了）。以我在Github创建的GitDemo为例。URL: https://gitlab.com/vastsa/gitdemo常用指令1. 拉取项目命令git clone 仓库地址操作其实也可以直接用pycharm的，但是为了体现标题，所以用系统终端拉取。打开终端，选择好目录。复制仓库地址。粘贴回车执行。如果是首次拉取Github代码，可能需要你登录认证，我之前拉取过，所以就不好演示了。然后记得cd切换到到项目目录2. 查看本地分支命令git branch操作既然说是pycharm，那就打开pycharm的终端，我这里用的是新版ui执行git branch目前只有一个main分支，并且颜色为绿色，表示正在当前分支3. 新建分支指令git branch <branch name>操作创建一个dev分支，执行git branch dev，然后再执行git brach查看本地分支新分支会根据现有分支进行创建4. 切换分支指令git checkout <branch name>操作我们现在切换到刚刚新建的dev分支，执行指令git checkout dev，并查看本地分支Tip:可以使用git checkout -b <branch name>新建并切换到该分支5. 查看（文件的）状态报告指令git status操作执行指令git status，可以查看未提交至暂存区以及发生更改的文件Tips:在提交（commit）代码之前，我们需要将发生变化的文件（staged changes）存入一个位置——暂存区暂存区的意义在于，它会追踪变化，只会提交有变化的文件。6. 添加文件到暂存区指令git add <文件名或文件夹>操作我新增了三个文件newfile、newhtml.html、test\newpy.py。执行指令git add .，这个.就表示当前文件夹下的所有文件，也可以直接换成文件名，只添加这一个文件。通过status可以看见，该目录下所有文件以及子目录的文件都添加进暂存区。7. 提交暂存区文件指令git commit -m 'hello www.lanol.cn'后面这个-m 就是message，就是说明这次提交的，相当于注释。操作执行指令git commit -m 'hello www.lanol.cn'推送分支至远程仓库指令git push操作我们在本地新建了dev分支，但是远程还没有，这时候我们执行git push的话，会怎么样呢。fatal: The current branch dev has no upstream branch. To push the current branch and set the remote as upstream, use git push --set-upstream origin dev告诉我们需要先用这条指令，推当前分支。回到gitlab，可以看见文件都已经上来了。
-
【逻辑智力题】水桶倒水问题 缘起今天逛牛客，然后看见了这个题目不禁想起了我的第一份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总结这种题目其实有多种解法，我当时做出来后，回来和我同学说，发现有些同学的方法和我不一样，但是结果是对的。
