力扣go(LeetCode)21在l1上直接改就报错，加个head就行为啥？

来源：蜘蛛抓取(WebSpider) 时间：2022-05-10 08:29 标签： 开关l1l2l3怎么接电线

力扣题：多数元素。经典题型，经典解法。一道题目，学习多种经典算法思想，举一反三！

以前做数学题的时候，老师说：你们学习多种解题方法。遇到类似不同的问题，你都会了，这样能提高解题能力。如果你写出多种解法，面试官会对你刮目相看。

下面一题，我们将用多种解法实现，是面试中常见的一题。

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指，在数组中出现次数，大于 n / 2 的元素。

你可以假设数组是非空的，并且给定的数组中，总是存在多数元素。

哈希表方法：一边遍历，一边计数，一边找众数，并不是先计数完，再去遍历一次找最大值。

对数组排序后，直接可以通过下标来判断众数，这个方法简单。

先将数组划分，然后分别找到左边的众数和右边的众数，然后根据找到的众数和数组长度的 1 / 2 进行比较。

思想：我们把众数记为 +1，把其他数记为 -1，将它们全部加起来，显然和大于 0。从结果本身，我们可以看出，众数比其他数多。

遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，先将 x 的值赋予 more，随后我们判断 x：

时间复杂度：O(n)；空间复杂度：O(1)

Github 疯传！史上最强！BAT 大佬「LeetCode刷题手册」电子书开放下载了，有助于你提升数据结构与算法的功底。

看完对你算法能力会有很大的提升！

力扣上还有一个比较火的算法思想：动态规划。这个算法思想也是比较经典的，面试时考得最多，必须要掌握的。

题目：强盗抢劫一排房间，每个房间都有钱，不能抢劫两个相邻的房间，要求抢的钱最多。数组如：[2,7,9,3,1]

思路：当输入房间数为0,1,2时，这个很好判断，当输入房间数字大于3时，就要用到动态规划了，方程是:

dp[i]是当抢到第i个数时，能抢到最大值，从局部最大值推到最终结果最大。

假如抢到第5个房间，那么第5个房间有二种情况，抢不和不被抢，因为只能隔房间。

如果抢到第4个房间，有个最大值；抢到第3个房间，有个最大值。

如果加上第3房间最大值，加上第5房间的最大值，大于抢到第4个房间时的最大时。那就抢3,5而不抢4，反而，就按抢4的策略。

这样从前往后推，最后的结果一定是最大的。

题目描述：有 N 阶楼梯，每次可上一阶或两阶，求有多少种上楼梯的方法

当N=1时，这个很好理解，只能跨1步这一种了

当N=2时，你每次可以跨1步或2步，那就是走2步或走两个1步

当N=3时，因为你可以跨1步或2步，那你在台阶1或2都能行。要计算到台阶1有多少种走法，到台阶2有多少种走法，然后2种相加，依次逆推。

当N=4时，你在台阶2或3都能行，计算到台阶2有多少种走法，到台阶3有多少种走法，然后2者相加，依次逆推。

总结如下：你会发现，这是斐波拉切数列，使用递归出现重复计算问题，所以选择动态规划算法。


第三层：3种（在第一层走2步或在第二层走1步）

第四层：5种（在第二层走2步或在第三层走1步）

i,j首先赋边界值，res保存i+j的值，每次前进，i,j,res的值都会被赋到前面结果。

上面的算法是底向上，递归相当于自顶向下，避免了重复计算。

给定一个，包含非负整数的 m x n 网格。请找出一条，从左上角到右下角的路径。使得路径上，所有数字总和为最小，每次只能向下，或者向右移动一步。

说明：因为 i=0 和 j=0 是临界条件，所以要先求出来。当 i>0 和 j>0 时，看如上数组，5 可以由上方3，或者左方 1 走过来。

当走5的时候，要选取上方3对应的dp，与左方1 对应的dp进行比较，选择较小值累加，这样走出来的才是最小值。最后推出，到右下角的最小值。

程序先把，第2行对应的sum都求出来，再把第2列对应的sum都求出来，最后求sum[2][2]就很容易了。

最后，sum[i-1][j-1]就是推出的最小值，上述代码就是dp方程的实现。

划分数组为两个相等的子集

思路是，相对数组中每个数求dp，最后就会找到dp[target]是否为true。

输入一个整形数组，数组里有正数也有负数。数组中连续的一个，或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。

思路：fmax(i) 表示，以第 i 个元素结尾的，乘积最大子数组的乘积，fmin(i) 表示，以第 i 个元素结尾的，乘积最小子数组的乘积。

这里分为最大和最小是因为数组可能存在负数，最大值乘以负数变成较小值，最小值乘以一个负数也可能变成最大值。

比较方程是：当前数乘以上一个最大值，当前值，当前数乘以上一个最小值。这三者比较，其中的最大值，就是我们要的最大值。

同样，每次也要把最小值计算出来，方式同上。

题目：求一个数组中等差递减区间个数，等差数列必须是连续的。

其实仔细观察，发现这是一个斐波拉切数列，0,1….n-2数的求和，动态规划找到方程了，就发现非常简单了。

这就是规律，但需要自己去发现规律，有些题目咋看一脸懵逼，仔细看就会发现其中的规律。

dp[i] 表示到i位置时，子数组的个数。数组长度大于3。

下面再看代码执行值的变化过程：

题目：求最长回文子串。输入: "babad"，输出: "bab"。注意: "aba" 也是一个有效答案。

dp[i][j]表示，字符s从下标i到下标j，是否为回文串。

如果bab是回文串，那么ababa也是回文串。因为，在两边增加了相同的数。同理，可以给出动态方程：

这段代码用利用了 dp[i + 1][j - 1]，其前面已经计算出来了。

当k = 4时，字符串最长，最后符合条件的回文子串最长。注意整个循环遍历的过程，用k最为两个下标的间距，然后遍历每种可能的结果，判断是否回文。

最长的子串最后判断，将符合条件的子串保存起来。动态规划方程推测极为重要。

求一个数组的最长自增子序列。

解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

dp[i]表示以a[i]这个元素结尾的最长递增子序列的长度。

想求 dp[5] 的值，也就是想求以 nums[5] 为结尾，其最长递增子序列。

nums[5] = 3，既然是递增子序列。我们只要找到，前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成新的递增子序列，而且这个新的子序列长度加一。

当然，可能形成很多种新的子序列，但是我们只要最长的，把最长子序列的长度作为 dp[5] 的值即可。

根据此依次类推到前面，d[0],d[1]…d[i]都是这样求出来的，看来动态规划有些是逆推的。

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

动态规划：定义dp[i]表示为nums[i]为结尾的[连续子数组的最大和。

动态规划一定要重点掌握！

我这里整理学习近百本计算机经典书籍，包括各种编程语言，算法，网络编程，数据库，分布式等等各种技术。对于学习计算机的同学帮助非常大，且十分系统！面试找工作的资料汇总都打包放在这了，这套资源可不是一般那种网上找的资源，非常宝贵，这些书能帮助你收割BAT offer，不要错过！


觉得不错的话，记得帮我 @盼盼编程 点个赞哦，祝大家都能学有所获！

也可以关注下我哟，致力于分享硬核学习路线，技术。希望能帮助更多CS学习者，让他们少走弯路！

//3.无重复字符的最长子串 //5.最长回文子串 中心扩散法 //15.三数之和 排序+双指针 //双指针在nums[i]后面的区间寻找和为0-nums[i]的另外两个数 //剑指offer03.数组中重复的数字 哈希 //21.合并两个有序链表 //4.寻找两个正序数组的中位数 //中位数的定义：如果某个有序数组长度是奇数，那么中位数就是中间那个，如果是偶数，那么就是中间两个数的平均值 //45.跳跃游戏 贪心算法 //9.回文数 反转这个整数，如果相等就是回文数 //设置dummyNode 是这一类问题的一般做法 //1.遍历至第一个节点 //53.最大子序和 贪心算法 //14.最长公共前缀 暴力 纵向扫描 //143.重排链表 快慢指针、反转链表、合并链表 //寻找链表的中间节点 快慢指针方法 //146.LRU缓存机制 数据库设计 链表和哈希表都是很快的数据结构 //主要考察 哈希表+双向链表（list）组合体 设计一个缓存机制 //72.编辑距离 动态规划 //剑指offer22.链表中倒数第k个节点 快慢指针 //31.下一个排列 模拟 //82.删除排序链表中的重复元素II //跳过当前的重复节点，使得cur指向当前重复元素的最后一个位置 //pre和cur之间没有重复节点，pre后移 //pre->next指向cur的下一个位置（相当于跳过了当前的重复元素） //但是pre不移动，仍然指向已遍历的链表结尾 //如果起始位置已经大于s的大小，说明已经找到了一组分割方案了 //121.买卖股票最佳时机 //19.删除链表的倒数第N个结点 //11.盛最多水的容器 双指针 //10.正则表达式匹配 //739.每日温度 单调递减栈 //单调栈：通过维持栈内值的递增（递减）性，在整体O(n)的时间内处理需要大小比较的问题。 /*题解：我们维持一个单调递减的栈，表示每天的温度；为了方便计算天数差，我们这里存放位置（即日期）而非温度本身。我们从左向右遍历温度数组，对于每个日期p， 如果p的温度比栈顶存储位置q的温度高，则我们取出q，并记录q需要等待的天数为p-q；我们重复这一过程，直到p的温度小于等于栈顶存储位置的温度（或栈空）时，我们将p 插入栈顶，然后考虑下一天。 //剑指Offer42.连续子数组的最大和 //103.二叉树的锯齿形层序遍历 二叉树层序遍历想到队列解决 queue //105.从前序与中序遍历序列构造二叉树 //前序遍历中第一个节点就是根节点 //在中序遍历中定位根节点 //先把根节点简历出来 //得到左子树的节点数目 //递归的构造左子树，并连接到根节点 //递归的构造右子树，并连接到根节点 //56.合并区间 排序+双指针 //剑指Offer25.合并两个排序的链表 //118.杨辉三角 找规律，模拟 //16.最接近的三数之和 排序+双指针 //215.数组中的第K大个元素 priority_queue优先队列，最大值先出数据结构 //322.零钱兑换 动态规划 //23.合并K个升序链表 递归+合并两个有序数组 //69.x的平方根 二分查找 边界问题 //剑指Offer07.重建二叉树 已知前序中序重建二叉树 //前序遍历中第一个节点就是根节点 //在中序遍历中定为根节点 //先把根节点建立出来 //得到左子树的节点数目 //递归的构造左子树并连接到根节点 //递归的构造右子树并连接到根节点 //32.最长有效括号 动态规划解决比较好 //13.罗马数字转整数 //41.缺失的第一个正数 //76.最小覆盖子串 滑动窗口 hard 比较有用 //199.二叉树的右视图 使用层序遍历，并只保存最后一个节点的值 //83.删除排序链表中的重复元素 //59.螺旋矩阵 上下左右边界要分清楚 模拟法 //剑指Offer04.二维数组中的查找 二分查找 //18.四数之和 三数之和 排序+双指针 //34.在排序数组中查找元素的第一个和最后一个位置 二分查找 //1047.删除字符串中的所有相邻重复项 //221.最大正方形 动态规划 //88.合并两个有序数组 双指针 //剑指Offer52.两个链表的第一个公共节点 相交链表 //剑指Offer11.旋转数组的最小数字 二分查找 //104.二叉树的最大深度 递归 //子数组长度为1时终止递归 //64.最小的路径和 动态规划 //面试题01.01.判断字符是否唯一 //面试题02.03.删除中间节点 //33.搜索旋转排序数组 //剑指Offer48.最长不包含重复字符的子字符串 //349.两个数组的交集 //面试题01.06字符串压缩 //35.搜索插入位置 二分查找 //81.搜索旋转排序数组（数组中值可以重复）

嗯，如果是前一段时间写论文，写累了，厌学了，那就什么也别管，放空一段时间吧！可以去做之前一直想做却没机会做的，也可以约几个小伙伴出去打打球（比如，羽毛球），多运动一下。俗话说（我说的），健康之体魄是人类从事一切活动的基础！

嗯，如果上面的你不听，你非要刷题，你想刷题，你喜欢刷题，那就做个刷题计划吧！

每日一题？ 难度不定，时而简单，时而中等，时而困难，TARI TARI！有些难点儿的题，你可能一时间搞不定：

if 标签所列技能 in 已掌握技能： 再思考一下，一边思考一边写 把题解代码抄一遍，一边抄一边整理思路 把题解代码抄一遍，一边抄一边整理思路 把题解代码抄一遍，一边抄一边整理思路

看你的竞赛积分，感觉你的潜力非常大！看你的刷题量，为什么每次周赛只有一题或两题呢？是因为比赛时的状态不好吗？比赛时的状态很重要！举个例子说明比赛时状态的重要性吧，本来以你的水平是能做出两题或三题的，如果你的状态很差，那么你可能做出一题都很费劲！如果状态没问题，那很可能是基础不扎实！你可以刷一下基础题。嗯，我认为的基础题，是指用到的数据结构和算法不超出本科数据结构和算法课程所学之外的题。嗯，用到竞赛知识的不算基础题。当然，基础题并不等于简单题，就像期末考试考的知识点都是学过的，你也未必都能得满分一样。我每次基本都是两题，每次第三题都是，我感觉会，但是比赛中又做不出来，所以，我认为自己基础掌握的不扎实！这个我是基于以下个人主观标准去准判断的：

周赛一题 —— 编程入门水平，或者刚开始学习编程
周赛两题 —— 有一定的数据结构和算法基础，但基础不扎实，或者说广度不够，应用不够熟练
周赛三题 —— 熟悉基础的算法和数据结构及其应用，基础比较扎实
周赛四题 —— 你已经很优秀啦
每次周赛根本不需要多想 —— 大佬你是来降维打击的

注：以上只是我一个菜鸟的主观判断！如果你有不同看法，轻拍！！！

所以，我打算去刷基础题，大概就是所有免费的 LeetBook!

下面 三个部分 大概是我未来几个月的刷题计划~

第一部分 数据结构基础（155 题）

还有一个关于 图 的，可以找其他题单凑凑~

第二部分 算法基础 （141 题）

注：与数据结构部分有重复

第三部分 其他 （629 题）

嗯，你大概没必要把上面的所有题都刷完，不过你可以尝试把 算法基础（初级算法, 中级算法 和 高级算法）部分的 141 题 刷完。

上面的刷题计划，我才刚开始，所以我并不知道认真刷完一遍之后，周赛能做出几题。不过，我目前的预期是能做出前三题！希望年内能拿到 骑士勋章！目前还很菜，只有 1600 左右，离目标还差 200 多分，接近 300 分的样子~

好吧，上面的你又不听！你非要 DFS 和 BFS 的题单（其实，DFS 和 BFS 也算基础算法技能吧），那给你 三叶小姐姐 的题单吧，里面有你想要的 DFS 和 BFS:

嗯，我觉得吧，要想有所突破，一定要敢于尝试自己不擅长的题，尽可能一题多解，用自己擅长的技术，也要用自己不擅长的技术，比如，我擅长 BFS，但不擅长 DFS，擅长 迭代，不擅长 递归。是的，我是能用 BFS，绝不用 DFS，能写 迭代，绝不写 递归，这是不好的！

嗯，就这么多吧！祝您刷题愉快~ ^_^

PS：嗯，有人建议你，找一个一起刷题的小伙伴。我觉得，如果能找到一个和自己水平大致相当的小伙伴，相互学习，相互竞争，我觉得也是挺不错的~

我要回帖

更多关于 开关l1l2l3怎么接电线 的文章

 

随机推荐