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

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

交流 | 在 LeetCode 刷题有没有必要开个会员？

看见很多名字长得很有趣的题被锁了，但一年400多还是有点贵，纠结ing

我开了会员。因为氪金了我就会心疼，我就会经常上去刷题以便于不浪费……

不论你是为了会员功能、题，lb、积分还是单纯信仰，你能通过lc真的学到东西找到工作，这可比码农培训班啥啥韭菜训练营值太多了

1.我也用非会员刷过一段时间，但是非会员一些题目的保存，标记，记录感觉功能较弱。多了个会员相当于买了笔记本。
2.很多代码似是而非，或者光看代码看不出来什么意思，这个时候可以用到调试功能。实在搞不懂，看看栈和变量，对于理解有一定好处
3.有一些代码补齐能力，还是很赞的
4.工作党，不缺钱（非凡尔赛），或者说不缺这几百块钱。一次油的事情，2顿饭，4条烟的事情。

1.除了力扣，还有其他平台。
2.算法就这么几种，动规，bfs，dfs，回溯，递归，模拟，排序，前缀和，双指针。永远不能指望，把题库背下来去面试，一定是每个类型刷几个，这个要求我认为有没有会员都可以用。如果为了解锁几个看起来很高大上的题目来开会员，开了也是白开，因为你刷题的思路和方法错了。
3.没有付费习惯，觉得不刷题，习惯刷刷B站，知乎，觉得比力扣好。
4.缺钱，觉得不划算，肉疼。
5.书非借不能读，不薅羊毛就浑身不舒服。

你可以先把当前题库做一半，再决定。以防浪费钱。前面也有人说了，大部分会员题目百度都能搜到。

说实话 断点调试调多了会影响做比赛题的感觉 我总有依赖心理

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

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

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

给定一个大小为 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学习者，让他们少走弯路！

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串的数目。回文字符串是正着读和倒过来读一样的字符串。子字符串是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

  • s 由小写英文字母组成

本题目有两种解题思路，分别是：

  • 枚举出所有的子串，然后再判断这些子串是否是回文；
  • 枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。
    官方题解中给出了从第二种思路出发的题解，我们这篇文章主要从第一种思路出发，给出三种方法。这三种方法层层优化，从暴力解法，到使用 动态规划 的解法，再对 动态规划 进行空间上的优化。希望能够帮助大家理解 动态规划 的使用方法。

我们最直观能想到的就是，枚举出所有的子串，然后再判断这些子串是否是回文。下面给出暴力解法的代码（Go）:

暴力法自然是思考难度最低的解法，相信的加都能够想到。然而我们可以看到遍历所有子字符串需要花费 O(n^2) 的时间，对于每个子字符串判断是否为回文需要花费 O(n) 的时间，那么这个算法的时间复杂度为 O(n^3) ，显然对于我们最求性能极致的程序设计师而言，这样的结果无法接受。接下来我们将使用 动态规划 的方法进行进一步的优化。

空间复杂度： O(1)。额外的常数空间即可。

我们先要找到暴力解法效率低在哪里。显然，字符串 s 的两个不同的字串 str1 和 str2 如果重叠的话，在计算过程中，重叠的子子串会执行相同的计算逻辑，于是造成了计算的冗余。

动态规划的思想，即是存储重复子运算的结果，从而使得每个子运算只需要计算一次，是一种时间和空间的权衡（trade-off）。

第一步，我们要归纳一个最优解的结构，我们判断一个字串是回文时，一共有三种情况：

以上三点就是递归定义的判断逻辑。前两种情况作为递归的基础情况（base case）。在第三种情况中，我们发现如果在判断另一个 内容为 “AstrB”的子字符串 str2时，则我们判断 str 是回文时，需要保证 str 是回文且 A == B。那我们需要再次判断一次 str 是不是回文呀，不能接受！

我们其实可以在第一次判断完 str 结果后，存储它。之后如果需要再判断 str 是否为回文时，直接返回结果，就省了很多计算内容。这就是 动态规划 了！

我们如何存储每一个子字符串呢？一种可行的方法是，我们搞一个 n x n 的二维布尔数组 a[i][j]，其中 i 代表子字符串的左端，j 代表子字符串的右端。就可以存储计算过的子字符串是否为回文了！

我们在写代码的时候采用 自下而上 的方法（具体概念参考我写过的一个关于动态规划的)。先贴代码（Go）:

首先我们创建一个 n x n 的数组，同时初始化 base case，用于存储各子字符串的计算结果。然后在设计代码时，我们要搞明白各个子字符串的依赖关系，如图：
假设我们 s 是长度为 5 的字符串，则我们创建这样的二维数组，初始化base case。图中我们可以看到， 对于数组的每一行而言，a[n] 依赖于 a[n+1] ，对于数组的每一列而言 a[n][m] 依赖于 a[n][m-1]。所以我们需要从base case 开始，即横坐标由大（n-1）到小(0)，纵坐标由小(当前横坐标i + 2)到大(n-1)遍历。对应于子字符串则是，子字符串的开端从 s 的最右端开始，确定开端后，再由小到大的设置子字符串尾端。

根据依赖的子子字符串的状态以及子字符串的开端尾端比较，可以在 O(1) 的时间内确定子字符串是否为回文。

时间复杂度： O(n^2)。遍历所有子字符串需要花费 O(n^2) 的时间

空间复杂度： O(n^2)。需要 n x n 的辅助二维数组。

我们再一次审视题解三，发现他需要额外的 n x n二位数组，且该二位数组其实有一半是用不到的，这无疑是一种浪费，那我们能不能节约空间呢？答案是肯定的。

通过观察我们发现，a[n] 只依赖于 a[n+1]，那么我们计算 a[n+1] 时可以只保留 a[n]， a[n+2] 再统计了 sum 之后则不需要再保存了。所以我们现在只需要两个长度为 n 的数组即可。

除此之外，我们发现， a[n][m] 也只依赖于 a[n][m-1]，也就是说对于 a[n] 的更新，是从后往前依次更新的，那我们可以考虑，只使用一个长度为 n 的数组。在一次迭代计算 a[n][m] 时，当前 a[n][m-1] 的值实际上是上一次迭代 a[n+1][m-1] 的值，即是计算 a[n][m] 时需要的子子字符串的状态。下面是优化空间后的代码（Go）：

时间复杂度： O(n^2)。遍历所有子字符串需要花费 O(n^2) 的时间

空间复杂度： O(n)。需要长度为 n 的辅助一维数组。

我要回帖

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

 

随机推荐