首页
学习
活动
专区
圈层
工具
发布

最长的连续元素序列的长度

题目描述 给定一个无序的整数类型数组,求最长的连续元素序列的长度。 例如: 给出的数组为[100, 4, 200, 1, 3, 2], 最长的连续元素序列为[1, 2, 3, 4]....返回这个序列的长度:4 你需要给出时间复杂度在O(n)之内的算法 思路: 先排序,记住三个数 int count=1;//当前连续序列长度 int last=num[0];//上一个数字(连续判断条件...) int max=1;//前面最大的连续序列长度 做的时候搞错了一个点,就是1,1,2,3,算连续三个,我算成连续四个了,后来改掉了 代码: public int longestConsecutive...(int[] num) { // 给定一个无序的整数类型数组,求最长的连续元素序列的长度。...// 例如: // 给出的数组为[100, 4, 200, 1, 3, 2], // 最长的连续元素序列为[1, 2, 3, 4].

1.2K30
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    【序列贪心】摆动序列 最长递增子序列 递增的三元子序列 最长连续递增序列

    摆动序列 摆动序列 贪心策略:统计出所有的极大值和极小值,以及最前和最后的两个点。...最长递增子序列 贪心策略:用辅助数组存储当前最长递增子序列,遍历数组,先拿当前元素和辅助数组的最后一个数比较,如果大于则插入到辅助数组最后一个位置,如果不大于则在辅助数组中二分查找当前元素可以替换的位置...遍历完数组后辅助数组中存的就是最长递增子序列。...if (nums[i] > a) b = nums[i]; else a = nums[i]; } return false; } }; 最长连续递增序列...最长连续递增序列 class Solution { public: int findLengthOfLCIS(vector& nums) { int n = nums.size

    64510

    算法 最长的斐波那契子序列的长度

    X_{i+2} 给定一个严格递增的正整数数组形成序列 arr ,找到 arr 中最长的斐波那契式的子序列的长度。...(回想一下,子序列是从原序列 arr 中派生出来的,它从 arr 中删掉任意数量的元素(也可以不删),而不改变其余元素的顺序。...例如, [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列) 测试用例: 示例 1: 输入: arr = [1,2,3,4,5,6,7,8] 输出: 5 解释: 最长的斐波那契式子序列为...示例 2: 输入: arr = [1,3,7,11,12,14,18] 输出: 3 解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。...2、dp + hash 对于长度为n的数列,需要为其构建一个n ^ 2的二维数组dp,保存其dp[raw][col]位置满足斐波那契序列的组数。

    92910

    由子序列构造的最长回文串的长度(最长回文子序)

    题目 给你两个字符串 word1 和 word2 ,请你按下述方法构造一个字符串: 从 word1 中选出某个 非空 子序列 subsequence1 。...从 word2 中选出某个 非空 子序列 subsequence2 。 连接两个子序列 subsequence1 + subsequence2 ,得到字符串。...返回可按上述方法构造的最长 回文串 的 长度 。 如果无法构造回文串,返回 0 。 字符串 s 的一个 子序列 是通过从 s 中删除一些(也可能不删除)字符而不更改其余字符的顺序生成的字符串。...回文串 是正着读和反着读结果一致的字符串。...最长回文子序列(动态规划) 将两个字符串拼接,题目要求非空,在516题基础上,稍加限制即可 class Solution { public: int longestPalindrome(string

    1K10

    Dilworth定理:最少的下降序列个数就等于整个序列最长上升子序列的长度

    概念如下: 狄尔沃斯定理_百度百科 (baidu.com) 本质就是找要求序列中最长的单调的子序列(不一定连续)的长度。...3, 5, 8) ),它的长度为4,因此该序列的最长上升子序列长度为4。...最后剩一个元素7,由于我们在求严格上升的子序列,不能将它插入尾部,于是我们把7替换成7——这个元素对子序列长度没有贡献。好了,最后得到的数组长度是4,所以最长上升子序列的长度就是4 。...;大的在前,小的在后 2、然后对已经排好的数组,统计最长连续单调递减子序列数目即可。...我们先来看看长度为n的序列a1和长度为m的序列a2最长公共子序列的匹配,暴力求解 #include #include #include

    64110

    最长的斐波那契子序列的长度(难度:中等)

    +2}; 给定一个严格递增的正整数数组形成序列arr,找到arr中最长的斐波那契式的子序列的长度。...例如, [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列 二、示例 示例 1: 输入: arr = [1,2,3,4,5,6,7,8] 输出: 5 解释: 最长的斐波那契式子序列为...[1,2,3,5,8] 示例 2: 输入: arr = [1,3,7,11,12,14,18] 输出: 3 解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18...我的解题思路是这样的,既然想要获取最长的斐波那契序列的长度,那么我们需要找出哪些序列是符合斐波那契数列的。...全部更新完毕,一定要记得,如果result不等于0,则返回值是result+2,因为只要匹配到了斐波那契子序列,最短的举例就是3的长度,而我们上面逻辑中,如果找到了斐波那契子序列,result值赋值的是

    48940

    【算法手记8】NC95 数组中的最长连续子序列 && 字母收集

    一.NC95 数组中的最长连续子序列 牛客网题目链接(点击即可跳转):NC95 数组中的最长连续子序列 题目详情: 本题详情如下图: 题目思路: 本题解题思路如下: 解法一:...去重+排序后双指针统计递增序列元素个数,记录最长序列长度.时间复杂度主要是排序的复杂度O(nlogn)....用哈希表记录数据范围内这个数字是否出现过,而后遍历哈希表查看连续位置是否存在数字,统计递增序列元素个数,记录最长序列长度.但是注意本题数据范围是10^8,开这么大的整型数组会内存超限,我们可以开一个位图或者...char类型的数组来标记数据是否存在,本文解题代码用的是位图。...= 0, max_leght = 0; for (int i = 0; i <tmp.size(); i++) { //判断是不是第一个有序的

    73700

    BAT面试算法进阶- 最长的斐波那契子序列的长度(暴力法)

    ,X_n 满足下列条件,就说它是 斐波拉契式的: n >= 3 对于所有 i+2 <= n ,都有X_i + X_{i+1} = X_{i+2} ; 给定一个严格递增的正整数数组形成序列.找到A中最长的斐波拉契式子序列的长度...二.案例 案例(1) 输入:[1,2,3,4,5,6,7,8] 输出: 5 原因: 最长的斐波拉契式子序列: [1,2,3,5,8] 案例(2) 输入:[1,3,7,11,12,14,18] 输出:...3 原因: 最长的斐波拉契式子序列: [1,11,12],[3,11,14],[7,11,18] 三.解决方案-- 使用Set(集合)暴力法 思路 每个斐波拉契的子序列都依靠2个相邻项来确定下一个预期项...注意: 由于子序列的长度大于等于3,只能是斐波拉契式的,所以我们必须进行检查ans >= 3?...ans:0 四.代码实现 C++ Code Java Code python Code 五.复杂度分析 时间复杂度: O(N^2logM),其中N指的是A的长度,M指的是A的最大值 空间复杂度

    41030

    BAT面试算法进阶(10)- 最长的斐波那契子序列的长度(暴力法)

    ,X_n 满足下列条件,就说它是 斐波拉契式的: n >= 3 对于所有 i+2 <= n ,都有X_i + X_{i+1} = X_{i+2} ; 给定一个严格递增的正整数数组形成序列.找到A中最长的斐波拉契式子序列的长度...案例 案例(1) 输入:[1,2,3,4,5,6,7,8] 输出: 5 原因: 最长的斐波拉契式子序列: [1,2,3,5,8] 案例(2) 输入:[1,3,7,11,12,14,18] 输出: 3 原因...: 最长的斐波拉契式子序列: [1,11,12],[3,11,14],[7,11,18] 解决方案-- 使用Set(集合)暴力法 思路 每个斐波拉契的子序列都依靠2个相邻项来确定下一个预期项,例如,对于...注意: 由于子序列的长度大于等于3,只能是斐波拉契式的,所以我们必须进行检查ans >= 3?...ans:0 代码实现 C++ Code Java Code python Code 复杂度分析 时间复杂度: O(N^2logM),其中N指的是A的长度,M指的是A的最大值 空间复杂度: O(N)

    49520

    BAT面试算法进阶(10)- 最长的斐波那契子序列的长度(暴力法)

    ,X_n 满足下列条件,就说它是 斐波拉契式的: n >= 3 对于所有 i+2 <= n ,都有X_i + X_{i+1} = X_{i+2} ; 给定一个严格递增的正整数数组形成序列.找到A中最长的斐波拉契式子序列的长度...二.案例 案例(1) 输入:[1,2,3,4,5,6,7,8] 输出: 5 原因: 最长的斐波拉契式子序列: [1,2,3,5,8] 案例(2) 输入:[1,3,7,11,12,14,18] 输出: 3...原因: 最长的斐波拉契式子序列: [1,11,12],[3,11,14],[7,11,18] 三.解决方案-- 使用Set(集合)暴力法 思路 每个斐波拉契的子序列都依靠2个相邻项来确定下一个预期项...注意: 由于子序列的长度大于等于3,只能是斐波拉契式的,所以我们必须进行检查ans >= 3?...ans:0 四.代码实现 C++ Code Java Code python Code 五.复杂度分析 时间复杂度: O(N^2logM),其中N指的是A的长度,M指的是A的最大值 空间复杂度:

    40220

    每日三题-无重复字符的最长子串、最长连续序列、找到字符串中所有字母异位词

    ‍个人主页: 才疏学浅的木子 ‍♂️ 本人也在学习阶段如若发现问题,请告知非常感谢 ‍♂️ 本文来自专栏: 算法 算法类型:Hot100题 每日三题 无重复字符的最长子串 最长连续序列...找到字符串中所有字母异位词 无重复字符的最长子串 解法一 暴力 使用双层for循环来遍历,第一层for循环的是开头,第二层的是结尾 使用HashSet来保存字符,如果HashSet中存在时,add...右边界就是当前循环的i 左边界最开始就是left = 0; 然后如果滑动窗口中有当前值就把left移动到上一个当前值的上一个位置 注意: 我滑动窗口用的HashMap所以left需要比较left...与当前值的上一个位置的大小 class Solution { public int lengthOfLongestSubstring(String s) { int len...map.put(s.charAt(i),i); ans = Math.max(ans,i-left+1); } return ans; } } 最长连续序列

    81230

    BAT算法面试题(11)--最长的斐波那契子序列的长度(动态规划法)

    ,X_n 满足下列条件,就说它是 斐波拉契式的: n >= 3 对于所有 i+2 <= n ,都有X_i + X_{i+1} = X_{i+2} ; 给定一个严格递增的正整数数组形成序列.找到A中最长的斐波拉契式子序列的长度...二.案例 案例(1) 输入:[1,2,3,4,5,6,7,8] 输出: 5 原因: 最长的斐波拉契式子序列: [1,2,3,5,8] 案例(2) 输入:[1,3,7,11,12,14,18] 输出: 3...原因: 最长的斐波拉契式子序列: [1,11,12],[3,11,14],[7,11,18] 三.解决方案-- 使用Set(集合)暴力法 思路 将斐波拉契式的子序列中的2个连续项A[i],A[j...] 视为单个结点(i,j).整个子序列是这些连续结点的之间的路径.例如,对于斐波拉契式的子序列,(A[1] = 2,A[2] = 3,A[4] = 5,A[7] = 8,A[10] = 13),结点的路径就为...五.复杂度分析 时间复杂度: O(N^2),其中N指的是A的长度 空间复杂度: O(NlogM),其中M是A中的最大的元素.

    84030
    领券