此篇是数学篇,主要补充之前涉及得少但比较重要的与数学相关的技巧和算法,如位运算、计算GDC(最大公约数)、LCM(最小公倍数)、分解质因数等。 位运算此部分主要参考教程:位运算https://oi-wiki.org/math/bit/ 由于计算机内部以二进制来存储数据,所以位运算是相当快的——使用位运算可以在一定程度上优化我们的程序。 c++(其他语言同样)中的位运算有按位与、按位或、按位异或、按位取反,它们的描述如下: 运算 运算符 解释 按位与 & 两位都是1时结果才为1 按位或 \ 两位都是0时结果才为0 按位异或 ^ 两位不同时结果为1——重点是”异” 按位取反 ~ 所有位颠倒 位运算的应用主要有两方面: 一是题目本身要求我们对一个数进行位运算,这时我们往往需要用到位操作 ; 二是使用位运算可以帮助我们省时省力地完成某些操作——即位运算优化 。 位操作我们可以把一个数看成一个位串,如果我们需要像数组一样对这个位串进行操作,比如获得某一位的值,或者只为其中某一位赋值,就要用到位操作。 获得某一位的值如果我们需要知道一个数n的第 ...
前情提要在上一讲动态规划初步里面,我们从暴力递归的局限性引出了动态规划,并且知道了动态规划其实是对穷举的优化。和递归不同,它一般是自底向上通过迭代的方法来解决问题的。DP的三要素是最优子结构(可以暴力递归的前提)、重叠子问题(需要使用DP优化递归的前提)、状态转移方程(DP需要进行的操作)。 上一篇是DP的入门篇,解决了为什么要使用DP的问题。这一篇作为DP的基础篇,将以三大经典的背包问题为主线,进一步学习动态规划。 0-1背包问题引入前一篇中讲到了打家劫舍这个问题,如果将问题稍微改一下: 贼,夜入豪宅,可偷之物甚多,而负重能力有限。怎么偷才能更加不枉此行? 稍微分析一下,这个问题和之前的“打家劫舍”的区别就是多了一个负重能力作为限制因素。但是负重能力和打劫到第n间这个状态参数之间并没有明显的联系,我们该怎么做呢? 前信奥大佬(划去) 某lsp的回答……请无视 其实,这个问题的模型就是0-1背包。其问题描述如下: 有N 个物品和一个容量(可装重量)为M 的背包, ...
从斐波拉契数列说起 再贴一下斐波拉契数列的问题 已知斐波拉契数列的第一项和第二项分别为0和1,递推公式为$F(n)=F(n-1)+F(n-2)$,求第n项的值。 递归形式上一篇中,我们从递推公式得到了下面递归形式的斐波拉契数列的解法, 并且发现它的效率是很低的。 1234int Fabric(int n){ if(n==0||n==1) return n; return Fabric(n-1)+Fabric(n-2);} 究其原因,是递归的过程中存在大量的重复计算(重叠子问题)。通过递归树我们可以明显地看出这一点: 上一篇也提到过可以通过某种方法消除重复计算,给递归树“剪枝” ——即使用备忘录。 使用备忘录我们可以使用一个备忘录,把计算过的值都记下来,每次计算之前都判断一下这个值是否在备忘录中,这种方法就是记忆化搜索 。 这个备忘录可以是数组,也可以是哈希表。我们一般使用数组。 1234567891011int Fabric_memo ...
探讨:何为递归我们知道,在函数里面调用这个函数自身的方法就是递归。递归可以通过下面的例子形象理解: 排队的时候,假如你想知道你排在多少位,你就去问你前面的人,前面的人又去问他前面的人,一直传下去,直到问到第一个人,再一直传回来——这样你就知道自己的位置了。 这个模型可以用下面的数学公式描述: position(n)=\begin{cases} position(n-1)+1 & n>1 \\ 1 & n=1 \end{cases}对递归有了一个整体的认识后,我们再来看看其过程。递归包括两个过程:递 和归 。递自顶向下,将问题分解 ;归自底向上,将子问题合并 。 根据函数调用的机制:递的过程中函数不断地调用自身,每次调用的时候都会开辟一个栈帧来保存这次调用的信息;归的时候恢复当前栈帧,函数执行结束之后销毁这个栈帧然后再恢复上一个栈帧。 递归的一个典型例子就是计算斐波拉契数列的第n项值 : 问题: 已知斐波拉契数列的第一项和第二项分别为0和1,递推公式为$F(n)=F(n-1)+F(n-2)$,求第n项的值。 ...
树的层序遍历树的层序遍历 推广到图就是广度优先搜索 ,它是借助队列 这个数据结构实现的。 如图,我们先将根节点放入队列中;然后队首的节点出队,将其左右孩子入队;重复这个操作(迭代),直到队列为空时,遍历结束 。 合并二叉树 题目 给你两棵二叉树: root1 和 root2 。想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。返回合并后的二叉树。注意: 合并过程必须从两个树的根节点开始。 示例1: 输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] 输出:[3,4,5,5,4,null,7] 分析这是一道比较简单的题,但是如果我们把能想到的所有方法都实现一遍,或许这道题就没有那么简单了。题目要求我们合并两棵二叉树, ...
这次先从一道经典题说起。先通过理解这道题的思路,体会BFS与DFS算法的思想后,再对BFS和DFS做进一步讨论。 图像渲染 题目 有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。给你一个坐标 (sr, sc) 表示图像渲染开始的像素值(行 ,列)和一个新的颜色值 newColor,让你重新上色这幅图像。为了完成上色工作,从初始坐标开始,记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点,接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点,……,重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。最后返回经过上色渲染后的图像。示例: 输入: image = [[1,1,1],[1,1,0],[1,0,1]],sr = 1, sc = 1, newColor = 2 输出: [[2,2,2],[2,2,0],[2,0,1]]如果觉得题目不好理解,可以到原题的讨论区看一下:flood-fillhttps://leet ...
无重复字符的最长子串 题目 给定一个字符串 s ,请你找出其中不含有重复字符的最长子串 的长度。示例 1:输入: s = “abcabcbb” 输出: 3 示例 2:输入: s = “bbbbb” 输出: 1示例 3:输入: s = “pwwkew” 输出: 3示例 4:输入: s = “” 输出: 0 分析该题的滑动窗口模型 初始时两个指针都指向字符串的开头。此时子串中只有一个字符,满足子串中字符不重复这条件,但是还不是最优的。 我们使用滑动窗口的思想来计算最优解: 若右指针的下一个字符与该子串中的字符不重复,则右指针右移,增大窗口边界;若重复了,则左指针右移重新检测子串,直到右指针移动到字符串末尾。用两指针之差来计算字符串长度。 然后这道题的关键就是如何检测右指针的下一个字符是否与子串中的字符重复 。 第一个想法 是再遍历一次子串,判断是否重复。 12345678910111213141516171819class Solution {publi ...
移动零 题目 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。请注意 ,必须在不复制数组的情况下原地对数组进行操作。示例 1:输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]示例 2:输入: nums = [0] 输出: [0] 分析一: 我们可以把这道题视为排序的变形:0为大数,其他为小数。我们需要将0排在后面且保持非零数的顺序不变,所以应该选择稳定的排序算法。 我们使用插入排序 :从头遍历数组,遇到0即将其删去,然后插入到末尾。 123456789class Solution {public: void moveZeroes(vector<int>& nums){ int flag=0; while(flag<nums.size() && nums[flag]!=0) flag++; ...
二分查找 二分查找/折半查找的基本方法 二分查找 题目 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。示例 1:输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4示例 2:输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。 123456789101112131415class Solution {public: int search(vector<int>& nums, int ...
avatar
Sato
我们的前方究竟会通往何处?
Follow Me In Github
公告

莱莎的炼金工房

十年炼金无人问,一朝肉腿天下知。

住在村裡的萊莎有如鄰家女孩,是一位“再普通不過”的少女。
某日,萊莎一行下定決心,前往禁止進入的「浮島對岸」,展開首次探險活動。
于是,僅限今夏的冒險,从此开始。