牛客网高频算法题系列-BM19-寻找峰值

2022-10-10
阅读 3 分钟
972
给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个所在位置即可。峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于假设 nums[-1] = nums[n] = -\infty−∞对于所有有效的 i 都有 nums[i] != nums[i + 1]你可以使用O(logN)的时间复杂度实现此问题吗...
封面图

牛客网高频算法题系列-BM18-二维数组中的查找

2022-10-09
阅读 2 分钟
570
在一个二维数组array中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。原题目见:二维数组中的查找
封面图

牛客网高频算法题系列-BM17-二分查找-I

2022-10-08
阅读 2 分钟
584
请实现无重复数字的升序数组的二分查找给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标(下标从 0 开始),否则返回 -1原题目见:BM17 二分查找-I
封面图

牛客网高频算法题系列-BM16-删除有序链表中重复的元素-II

2022-10-04
阅读 2 分钟
1.2k
首先,考虑特殊情况,如果链表为空或者只有一个结点,不会有重复的元素,返回原链表。否则,遍历链表判断是否有重复元素,处理过程如下:首先,因为头结点也可能重复,所以使用一个虚拟头结点dummyNode;然后,用lastNonRedundantNode为上一个不重复的结点,初始化为头结点,count记录该结点的元素的重复次数,初始为1;...
封面图

牛客网高频算法题系列-BM15-删除有序链表中重复的元素-I

2022-06-08
阅读 2 分钟
1.1k
首先,考虑特殊情况,如果链表为空或者只有一个结点,不会有重复的元素,返回原链表。否则,遍历链表结点,判断是否有重复的元素,处理过程如下:使用pre记录上一个未重复的结点,初始化为链表头;然后从链表的第二个结点next开始遍历链表结点;如果next和pre的值相同,则删除当前重复结点;如果next和pre的值不相同,则...
封面图

牛客网高频算法题系列-BM14-链表的奇偶重排

2022-06-07
阅读 3 分钟
997
首先,判断如果链表为空或者只有1或2个结点,不用重排,直接返回原链表。否则,使用2个list额外记录奇数和偶数位的结点,处理过程如下:遍历链表,分别将奇数和偶数位的结点值放到不同的list中;按照奇数位在前、偶数位在后的顺序,将2个list中的值重组成新的链表即为重排后的链表,返回之。
封面图

牛客网高频算法题系列-BM13-判断一个链表是否为回文结构

2022-06-06
阅读 2 分钟
973
首先,考虑特殊情况,如果链表为空或只有一个链表,默认是回文结构,直接返回true。否则,使用一个额外的list进行处理,处理过程如下:遍历原链表,将链表中所有结点的值添加到一个list中;遍历list中的值判断该链表是否是回文结构,遍历过程如下:遍历list中0-list.size()/2的值;判断i的值和list.size() - i - 1的值是...
封面图

牛客网高频算法题系列-BM12-单链表的排序

2022-06-05
阅读 3 分钟
733
首先判断如果链表为空或者只有一个结点,则不需要排序,直接返回原链表。否则,使用额外空间进行排序,处理过程如下:首先遍历链表,将所有结点值暂存在一个List中;然后,使用库函数将List排序(也可以使用各种排序算法进行排序);最后,将排序后的结点值构造成新的链表并返回。
封面图

牛客网高频算法题系列-BM11-链表相加(二)

2022-06-04
阅读 3 分钟
813
假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。给定两个这种链表,请生成代表两个整数相加值的结果链表。原题目见:BM11 链表相加(二)
封面图

牛客网高频算法题系列-BM10-两个链表的第一个公共结点

2022-06-03
阅读 2 分钟
937
输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)原题目见:BM10 两个链表的第一个公共结点
封面图

牛客网高频算法题系列-BM9-删除链表的倒数第n个节点

2022-06-02
阅读 2 分钟
859
首先,考虑两种特殊情况:如果原链表为空,直接返回null。如果k不是正数,直接返回null。否则,使用双指针求解,求解过程如下:因为有可能删掉头结点,所以先设置一个假的头结点dummyNode,并指向原有的头结点;然后,遍历链表,将fast结点指向第n-1个结点;如果遍历完后fast为null或者fast的next为空,说明链表长度小于...
封面图

牛客网高频算法题系列-BM8-链表中倒数最后k个结点

2022-06-01
阅读 2 分钟
1.1k
描述:输入一个长度为 n 的链表,设链表中的元素的值为 a~i~ ,返回该链表中倒数第k个节点。如果该链表长度小于k,请返回一个长度为 0 的链表。原题目见:BM8 链表中倒数最后k个结点
封面图

牛客网高频算法题系列-BM7-链表中环的入口结点

2022-05-31
阅读 2 分钟
927
使用两个指针,fast 与 slow。它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置,而fast 指针向后移动两个位置。如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇。如果相遇了,从相遇处到入口结点的距离与头结点与入口结点的距离相同。所以将fast重新设置为头结点,fast和sow结点都一步...
封面图

牛客网高频算法题系列-BM6-判断链表中是否有环

2022-05-30
阅读 2 分钟
952
使用两个指针,fast 与 slow。它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置,而fast 指针向后移动两个位置。如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇。原理可参考:双指针算法原理详解
封面图

牛客网高频算法题系列-BM5-合并k个已排序的链表

2022-05-29
阅读 2 分钟
932
分治法,可以将大问题分解成小问题,然后继续分解成最小的子问题并解决之。具体处理过程如下,将k个链表分解成2部分处理,递归处理这2部分,并调用 BM4 合并两个排序的链表 中的方法将2个合并好的链表进行合并,最小的子问题的条件是:没有待合并的链表,直接返回空。如果只有一个链表,则不需要合并,直接返回该链表。...
封面图

牛客网高频算法题系列-BM4-合并两个排序的链表

2022-05-28
阅读 2 分钟
804
输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。数据范围: 0 <= n <= 1000,-1000 <= 节点值 <= 1000要求:空间复杂度 O(1),时间复杂度 O(n)原题目见:BM4 合并两个排序的链表
封面图

牛客网高频算法题系列-BM3-链表中的节点每k个一组翻转

2022-05-27
阅读 2 分钟
853
将给出的链表中的节点每 k 个一组翻转,返回翻转后的链表如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样你不能更改节点中的值,只能更改节点本身。原题目见:BM3 链表中的节点每k个一组翻转
封面图

牛客网高频算法题系列-BM2-链表内指定区间反转

2022-05-26
阅读 2 分钟
1.5k
因为起始位置可能是头结点,所以首先设置一个虚拟的头结点dummyNode并将next指向原有的头结点,然后处理过程如下:首先遍历链表,找到起始位置m的前一个结点pre,用来记录反转前的结点;然后用cur和next记录pre的next结点,用next记录cur的next结点;然后继续遍历链表,通过交换pre、next、cur的next指针,将next结点转...
封面图

牛客网高频算法题系列-BM1 反转链表

2022-05-25
阅读 2 分钟
810
首先,如果head为空或者只有一个结点,直接返回。否则,分别用first和next指针指向链表的前两个结点,并将它们的next指针域反转,然后继续往后遍历处理链表的后续结点直到将最后一个结点反转。注意,需要将head头结点的next指向null。最后,返回first结点,即为反转后的新链表的头结点。
封面图

LeetCode-459-重复的子字符串

2022-04-30
阅读 2 分钟
1.2k
题目描述:给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。示例说明请见LeetCode官网。来源:力扣(LeetCode) 链接:[链接] 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
封面图

LeetCode-496-下一个更大元素 I

2022-04-29
阅读 2 分钟
863
题目描述:给你两个 没有重复元素 的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在,对应位置输出 -1 。示例说明请见LeetCode官网。来源:力扣(Leet...
封面图

LeetCode-485-最大连续 1 的个数

2022-04-28
阅读 2 分钟
1k
题目描述:给定一个二进制数组, 计算其中最大连续 1 的个数。示例说明请见LeetCode官网。来源:力扣(LeetCode) 链接:[链接] 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
封面图

LeetCode-448-找到所有数组中消失的数字

2022-04-27
阅读 2 分钟
1.3k
题目描述:给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。示例说明请见LeetCode官网。来源:力扣(LeetCode) 链接:[链接] 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
封面图

LeetCode-190-颠倒二进制位

2022-04-26
阅读 2 分钟
1.1k
题目描述:颠倒给定的 32 位无符号整数的二进制位。提示:请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。在 Java 中,编译器使用二进制补码记法来表示有符...
封面图

LeetCode-187-重复的DNA序列

2022-04-25
阅读 2 分钟
1.2k
题目描述:所有 DNA 都由一系列缩写为 'A','C','G' 和 'T' 的核苷酸组成,例如:"ACGAATTCCG"。在研究 DNA 时,识别 DNA 中的重复序列有时会对研究非常有帮助。编写一个函数来找出所有目标子串,目标子串的长度为 10,且在 DNA 字符串 s 中出现次数超过一次。示例说明请见LeetCode官网。来源:力扣(LeetCode) 链接:...
封面图

LeetCode-441-排列硬币

2022-04-24
阅读 2 分钟
983
题目描述:你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。给定一个数字 n,找出可形成完整阶梯行的总行数。n 是一个非负整数,并且在32位有符号整型的范围内。示例说明请见LeetCode官网。来源:力扣(LeetCode) 链接:[链接] 著作权归领扣网络所有。商业转载请联系官方授权,非商业...
封面图

LeetCode-279-完全平方数

2022-04-23
阅读 2 分钟
1.8k
题目描述:给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n ,返回和为 n 的完全平方数的 最少数量 。完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平...
封面图

LeetCode-238-除自身以外数组的乘积

2022-04-22
阅读 2 分钟
991
题目描述:给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。示例说明请见LeetCode官网。来源:力扣(LeetCode) 链接:[链接] 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
封面图

LeetCode-209-长度最小的子数组

2022-04-21
阅读 2 分钟
905
题目描述:给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [nums ~l~, nums~l+1~​​, ..., nums~r-1~, nums~r~] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。示例说明请见LeetCode官网。来源:力扣(LeetCode) 链接:[链接] 著作权归领扣网络所...
封面图

LeetCode-189-旋转数组

2022-04-20
阅读 2 分钟
1.1k
题目描述:给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。进阶:尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?示例说明请见LeetCode官网。来源:力扣(LeetCode) 链接:[链接] 著作权归领扣网络所有。商业转载请联...
封面图