将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
- 选择第一个节点值较小的链表作为新链表头节点
- 依次比较两个节点的值大小,将新链表尾指向值较小的节点
- 如果一个链表遍历完,另一个链表还有剩余节点则把剩余节点直接附加
力扣题:多数元素。经典题型,经典解法。一道题目,学习多种经典算法思想,举一反三!
以前做数学题的时候,老师说:你们学习多种解题方法。遇到类似不同的问题,你都会了,这样能提高解题能力。如果你写出多种解法,面试官会对你刮目相看。
下面一题,我们将用多种解法实现,是面试中常见的一题。
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指,在数组中出现次数,大于 n / 2 的元素。
你可以假设数组是非空的,并且给定的数组中,总是存在多数元素。
哈希表方法:一边遍历,一边计数,一边找众数,并不是先计数完,再去遍历一次找最大值。
对数组排序后,直接可以通过下标来判断众数,这个方法简单。
先将数组划分,然后分别找到左边的众数和右边的众数,然后根据找到的众数和数组长度的 1 / 2 进行比较。
思想:我们把众数记为 +1,把其他数记为 -1,将它们全部加起来,显然和大于 0。从结果本身,我们可以看出,众数比其他数多。
遍历数组 nums 中的所有元素,对于每个元素 x,在判断 x 之前,如果 count 的值为 0,先将 x 的值赋予 more,随后我们判断 x:
时间复杂度:O(n);空间复杂度:O(1)
看完对你算法能力会有很大的提升!
力扣上还有一个比较火的算法思想:动态规划。这个算法思想也是比较经典的,面试时考得最多,必须要掌握的。
题目:强盗抢劫一排房间,每个房间都有钱,不能抢劫两个相邻的房间,要求抢的钱最多。数组如:[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学习者,让他们少走弯路!
版权声明:本文为博主原创文章,遵循 版权协议,转载请附上原文出处链接和本声明。
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。