精华内容
下载资源
问答
  • 问题:最长连续子序列是指:子节点的值大于父节点的值。 思路1:设置一个全局变量,记录树遍历时的最大连续长度,然后递归地求解树的长度,时间复杂度为O(n) 思路2:将每个结点作为根结点,依次求取每个结点的的...

    问题:最长连续子序列是指:子节点的值大于父节点的值。

    思路1:设置一个全局变量,记录树遍历时的最大连续长度,然后递归地求解树的长度,时间复杂度为O(n)

    思路2:将每个结点作为根结点,依次求取每个结点的的最大连续子序列长度。时间复杂度为O(n^2)

    相关程序实现:

    思路1的相关程序实现:

    #include <iostream>
    #include<malloc.h>
    
    using namespace std;
    static int length=0;
    
    typedef struct Btree
    {
        int num;
        struct Btree *lchild;
        struct Btree *rchild;
    } *PBtree,Btree;
    
    
    void inorder( PBtree root)
    {
        if(root==NULL)
            return;
        else
        {
            inorder(root->lchild);
            cout<<root->num<<" ";
            inorder(root->rchild);
        }
    }
    
    //从根节点开始记录满足条件的长度
    int getLong(PBtree root)
    {
        if(root==NULL)
            return 0;
        int res=-1;
        if(root->lchild&&(root->lchild)->num>root->num)
            res=max(res,getLong(root->lchild)+1);
        if(root->rchild&&(root->rchild)->num>root->num)
            res=max(res,getLong(root->rchild));
        return res;
    }
    
    //在所有的路径中选择满足条件的最大长度
    int getLongSubList(PBtree root)
    {
        if(root==NULL)
            return 0;
        int res=getLong(root);
        if(root->lchild)
            res=max(res,getLongSubList(root->lchild));
        if(root->rchild)
            res=max(res,getLongSubList(root->rchild));
        return res+1;
    }
    
    int main()
    {
        PBtree root=NULL;
        PBtree a1=new  Btree();
        PBtree a2=new  Btree();
        PBtree a3=new  Btree();
        PBtree a4=new  Btree();
        PBtree a5=new  Btree();
        PBtree a6=new  Btree();
        PBtree a7=new  Btree();
        PBtree a8=new  Btree();
    
        a1->num=10;
        a2->num=1;
        a3->num=2;
        a4->num=3;
        a5->num=4;
        a6->num=6;
        a7->num=1;
        a8->num=2;
    
        a1->lchild=a2;
        a1->rchild=a3;
    
        a2->lchild=a4;
        a4->lchild=a5;
        a5->lchild=a6;
    
        a3->lchild=a7;
        a7->lchild=a8;
    
        inorder(a1);
        cout<<endl;
        cout<<getLongSubList(a1)<<endl;
        return 0;
    }
    

    输出结果:

    6 4 3 1 10 2 1 2
    4

    思路2的相关程序实现:

    #include <iostream>
    #include<malloc.h>
    
    using namespace std;
    static int length=0;
    
    typedef struct Btree
    {
        int num;
        struct Btree *lchild;
        struct Btree *rchild;
    } *PBtree,Btree;
    
    
    void inorder( PBtree root)
    {
        if(root==NULL)
            return;
        else
        {
            inorder(root->lchild);
            cout<<root->num<<" ";
            inorder(root->rchild);
        }
    }
    
    
    //从根节点开始记录满足条件的长度
    int getLong(PBtree root)
    {
        if(root==NULL)
            return 0;
    
        if(root->lchild==NULL&&root->rchild==NULL)
        {
            length= max(length,1);
            //cout<<length<<endl;
            return 1;
        }
    
        int left_num=getLong(root->lchild);
        int right_num=getLong(root->rchild);
    
        if(root->lchild&&(root->lchild)->num>root->num)
            left_num++;
        if(root->rchild&&(root->rchild)->num>root->num)
            right_num++;
        if((root->lchild&&(root->lchild)->num<root->num)&&(root->rchild&&(root->rchild)->num<root->num))
        {
            length=max(length,1);
            //cout<<length<<endl;
            return 1;
        }
        length=max(length,max(left_num,right_num));
        //cout<<length<<endl;
        return max(left_num,right_num);
    }
    
    int main()
    {
        PBtree root=NULL;
        PBtree a1=new  Btree();
        PBtree a2=new  Btree();
        PBtree a3=new  Btree();
        PBtree a4=new  Btree();
        PBtree a5=new  Btree();
        PBtree a6=new  Btree();
        PBtree a7=new  Btree();
        PBtree a8=new  Btree();
    
        a1->num=10;
        a2->num=1;
        a3->num=2;
        a4->num=3;
        a5->num=4;
        a6->num=6;
        a7->num=1;
        a8->num=2;
    
        a1->lchild=a2;
        a1->rchild=a3;
    
        a2->lchild=a4;
        a4->lchild=a5;
        a5->lchild=a6;
    
        a3->lchild=a7;
        a7->lchild=a8;
    
        inorder(a1);
        cout<<endl;
        cout<<getLongSubList(a1)<<endl;
    
        return 0;
    }
    

    输出结果:

    6 4 3 1 10 2 1 2
    4

    总结:

    树的遍历是自底向上的,每次都是先子树,在向上回溯。(先得到叶子节点的信息,然后逐次得到根的信息)

    展开全文
  • 最长连续子序列长度

    千次阅读 2019-06-24 22:59:31
    给你一个排序的数组,例如 { 1, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15 } ,求最长连续子序列长度 public static int getLongest(int[] strs) { int max = 0; int oldmax = 0; for (int i = 1; i < strs....

    给你一个排序的数组,例如 { 1, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15 } ,求最长连续子序列的长度

    public static int getLongest(int[] strs) {
        int max = 0;
        int oldmax = 0;
        for (int i = 1; i < strs.length; ++i) {
            if (strs[i] - strs[i - 1] == 1) {
                max = max + 1;
                oldmax = max;
            } else {
                max = 0;
            }
        }
        return Math.max(max, oldmax);
    }
    

    时间复杂度应该是 O(n)

    如果变形呢?给你一个没有排序的。

    1. 先对数组进行排序,然后再进行如上操作
    2. 结合 hash 表
    public static int getLongestV2(int[] strs) {
        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for (int str : strs) {
            // 0 表示没有处理过
            if (map.getOrDefault(str, 0) == 0) {
                int left = map.getOrDefault(str - 1, 0); // 左序列长度
                int right = map.getOrDefault(str + 1, 0); // 右序列长度
                map.put(str, right + left + 1);
                // 设置左端点
                if (left != 0) {
                    map.put(str - left, left + right + 1);
                }
                // 设置右端点
                if (right != 0) {
                    map.put(str + right, right + left + 1);
                }
                max = max > (left + right + 1) ? max : (left + right + 1);
            }
        }
        return max;
    }
    

    注意:在更新两端节点的序列长度时,也要更新当前节点的序列长度。

    展开全文
  • 数组中的最长连续子序列 题目描述: 给定无序数组arr,返回其中最长的连续序列的长度(要求值连续,位置可以不连续,例如 3,4,5,6为连续的自然数) ...输出一个整数,代表最长连续子序列长度。 示例1
    数组中的最长连续子序列

    题目描述:

    给定无序数组arr,返回其中最长的连续序列的长度(要求值连续,位置可以不连续,例如 3,4,5,6为连续的自然数)

    输入描述:

    输出两行,第一行包括一个整数 n ( 1 ≤ n ≤ 1 0 5 ) n(1 \leq n \leq10^5) n(1n105),第二行包含n个整数,分别代表 a r r [ i ] ( 1 ≤ a r r [ i ] ≤ 1 0 8 ) arr[i](1 \leq arr[i] \leq 10^8 ) arr[i](1arr[i]108)

    输出描述:

    输出一个整数,代表最长连续子序列的长度。

    示例1
    输入
    6
    100 4 200 1 3 2
    
    输出
    4
    
    示例2
    输入
    3
    1 1 1
    
    输出
    1
    
    备注:

    时间复杂度 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n),空间复杂度 O ( n ) O(n) O(n)


    题解:

    解法一:

    直接对数组进行排序,连续的数字必然挨在一块,逐个遍历一遍即可。

    时间复杂度: O ( n ) O(n) O(n)

    额外空间复杂度: O ( 1 ) O(1) O(1)

    解法一代码:

    #include <cstdio>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1e5 + 10;
    
    int n;
    int a[N];
    
    int main(void) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", a + i);
        sort(a, a + n);
        int max_len = 1, len = 1;
        for (int i = 1; i < n; ++i) {
            if (a[i] == a[i - 1] + 1) ++len;
            else if (a[i] == a[i - 1]) continue;
            else {
                max_len = max(max_len, len);
                len = 1;
            }
        }
        printf("%d\n", max(max_len, len));
        return 0;
    }
    

    解法二:

    使用哈希表,hash<key, val> 表示 key 所在的最长连续序列的长度。逐个遍历数组元素,假设当前遍历元素为 a[i],并且 a[i] 未在 hash 中出现,则按照以下规则更新:

    • 若 a[i] - 1 在 hash 中出现,则 a[i] - 1 可以和 a[i] 进行合并,找到序列最左边的位置: l e f t = a [ i ] − 1 − h a s h [ a [ i ] − 1 ] + 1 left = a[i] - 1 - hash[a[i] - 1] + 1 left=a[i]1hash[a[i]1]+1,最右边位置: r i g h t = a [ i ] + h a s h [ a [ i ] ] − 1 right = a[i] + hash[a[i]] - 1 right=a[i]+hash[a[i]]1

    • 若 a[i] + 1 在 hash 中出现,则 a[i] + 1 可以和 a[i] 进行合并,找到序列最左边的位置:

      l e f t = a [ i ] − h a s h [ a [ i ] ] + 1 left = a[i] - hash[a[i]] + 1 left=a[i]hash[a[i]]+1,最右边位置: r i g h t = a [ i ] + 1 + h a s h [ a [ i ] + 1 ] − 1 right = a[i] + 1 + hash[a[i] + 1] - 1 right=a[i]+1+hash[a[i]+1]1;

    • 序列长度为 r i g h t − l e f t + 1 right - left + 1 rightleft+1,更新最大序列长度,并在 hash 中更新 left 和 right 的状态。

    时间复杂度: O ( n ) O(n) O(n)

    额外空间复杂度: O ( n ) O(n) O(n)

    解法二代码:

    #include <cstdio>
    #include <unordered_map>
    
    using namespace std;
    
    int n, ret = 1;
    unordered_map<int, int> Hash;
    
    void merge(int less, int more) {
        int left = less - Hash[less] + 1;
        int right = more + Hash[more] - 1;
        int len = right - left + 1;
        if (len > ret) ret = len;
        Hash[left] = Hash[right] = len;
    }
    
    int main(void) {
        scanf("%d", &n);
        int x;
        while (n--) {
            scanf("%d", &x);
            if (!Hash.count(x)) {
                Hash[x] = 1;
                if (Hash.count(x - 1)) merge(x - 1, x);
                if (Hash.count(x + 1)) merge(x, x + 1);
            }
        }
        printf("%d\n", ret);
        return 0;
    }
    
    展开全文
  • 主要介绍了C语言实现最长递增子序列问题的解决方法,采用递归的方法解决该问题,是非常经典的一类算法,需要的朋友可以参考下
  • 最长连续序列 1. 题目描述 给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 来源:力扣(LeetCode) 链接...

    本题地址:128. 最长连续序列

    1. 题目描述

    给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

    请你设计并实现时间复杂度为 O(n) 的算法解决此问题。


    来源:力扣(LeetCode
    链接:https://leetcode-cn.com/problems/longest-consecutive-sequence


    2. 解答

    2.1 朴素解法

    如果我们不考虑要求时间复杂度为 O(n),那么我们可以采用最直观的方式来做这个题。比如:

    • 先将数组排序;
    • 然后在排序数组中找最长的连续子序列;
    class Solution {
        public int longestConsecutive(int[] nums) {
            if(nums == null || nums.length == 0)
                return 0;
            Arrays.sort(nums);
            int len = 1, longestlen = 1;
            for(int i=1;i<nums.length;i++){
                if(nums[i] == nums[i - 1]) continue; // 相同的不需要判断
                if(nums[i] == nums[i -1] + 1) len++; // 我们需要相差1的连续序列
                else len = 1; // 否则初始化为1
                longestlen = Math.max(longestlen, len);
            }
            return longestlen;
        }
    }
    

    上面算法的时间复杂度为 O ( n l o g 2 n ) O(nlog_2^n) O(nlog2n),显然不满足 O ( n ) O(n) O(n)的时间复杂度。

    结果:
    在这里插入图片描述

    2.2 使用Hash表来解决

    由于Hash表在进行查找的时候通过散列函数来进行,故而查找效率很高,为 O ( 1 ) O(1) O(1)。所以可以考虑使用哈希表来解决这个问题。

    因为我并不需要考虑他的次数,所以这里可以使用HashSet集合。

    class Solution {
        public int longestConsecutive(int[] nums) {
            if(nums == null || nums.length == 0)
                return 0;
            Set<Integer> set = new HashSet<>();
            for (int i : nums) {
                set.add(i);
            }
            int longestLen = 1;
            for (int x : set) {
                // 不是连续子序列的第一个就跳过
                if(set.contains(x - 1))
                    continue;
                int y = x;
                while(set.contains(y + 1)) y++;
                longestLen = Math.max(longestLen, y - x + 1);
            }
            return longestLen;
        }
    }
    

    上面的算法的时间复杂度满足 O ( n ) O(n) O(n)的要求。

    结果:
    在这里插入图片描述

    2.3 并查集

    可以考虑使用并查集,代码如下:

    class Solution {
        public int longestConsecutive(int[] nums) {
            if(nums == null || nums.length == 0) return 0;
            Map<Integer, Integer> parent = new HashMap<>();
            Map<Integer, Integer> size = new HashMap<>();
            for (int num : nums) {
                parent.put(num, num); // 初始化指定根节点为自己;
                size.put(num, 1); // 初始化指定当前以自己为根的集合大小为1
            }
    
            // 合并集合
            for (int i = 0; i < nums.length; i++) {
            	// 跳过局部重复
                if(i + 1 < nums.length && nums[i] == nums[i + 1]) continue;
                if (parent.containsKey(nums[i] + 1)) {
                    union(parent, size, nums[i], nums[i] + 1);
                }
            }
    
            int longestLen = 1;
            // 寻找各个集合的最大长度,因为存储在每个集合的根,所以需要找到Parent
            for (int num : nums) {
                longestLen = Math.max(longestLen, size.get(findParent(parent, num)));
            }
    
            return longestLen;
        }
    
        private void union(Map<Integer, Integer> parent, Map<Integer, Integer> size, int x, int y){ // 条件 y = x + 1
            // 分别找到x和y的根
            int rootX = findParent(parent, x);
            int rootY = findParent(parent, y);
            if(rootX != rootY){  // 如果没有相连
                parent.put(rootX, rootY); // 连接
                size.put(rootY, size.get(rootY) + size.get(rootX));
            }
        }
    
        private int findParent(Map<Integer, Integer> parent, int x){
            while(parent.get(x) != x){ // 根不是自己,就需要找根
                x = parent.get(x);
            }
            return x;
        }
    }
    

    结果:
    在这里插入图片描述


    Thanks

    展开全文
  • 最长特殊序列定义如下:该序列为某字符串独有的最长子序列(即不能是其他字符串的子序列)。 子序列可以通过删去字符串中的某些字符实现,但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列,任何字符串为...
  • 给定无序数组arr,返回其中最长连续序列长度(值连续,位置无需连续) 题目链接 题目思路: 1、对数组元素进行排序 2、设置两个变量max和maxFinal,max记录当前序列最大连续长度,maxFinal记录最终的所有序列中...
  • 最长连续子序列 思路 1.空间换时间,利用哈希表存储原始数据。 2.遍历原始数组,例如遍历到nums[i],在哈希表中先往num[i]右边找,即num[i] + 1方向;再往左边找,即nums[i] - 1方向。 3.优化,每次往左右找时,...
  • 求一个数组的最长连续子序列

    千次阅读 2018-07-31 16:33:23
    分析: 如果允许O(nlogn)的复杂度,那么可以先排序,可是本题要求O(n)。 ...对每个元素,以该元素为中心,往左右扩张,直到不连续为止,记录下最长长度。 class Solution { public: int ...
  • 描述 给定一棵二叉树,找到最长连续序列...对于每个节点root,求以root为起始节点的最长连续递增递增序列长度up和最长连续递减序列长度down,结果返回 &lt; up,down &gt;。初始化up, down均为1,left...
  • 最长连续递增子序列长度和最长不连续递增子...设数组dp[i],表示以i为结尾的最长连续子序列长度,即上述数组的dp数组即为 dp[6] = {1,1,1,2,1,2} 代码如下 #include&lt;iostream&gt; using namespace s...
  • 最长连续单调子序列 package adk; import java.util.ArrayList; import java.util.Collections; import java.util.Random; public class SearchMax { public static void main(String[] args) { // 模拟...
  • 最长连续子序列

    千次阅读 2019-04-21 17:34:35
    给定一个无序的子序列,判定这个子序列中最长连续子序列长度。子序列是这样定义的:比如给定{2, 3, 100, 5, 4},那么2, 3, 4, 5就算是一个连续的子序列。假设没有重复的数据。 解题思路 O(n)O(n)O(n)的复杂度,...
  • 无序数组中找到最长连续子序列 public function index(){ $str = "13 14 21 15 23 18 56 42 22 4 16 17"; $res = explode(' ',$str); // var_dump($res);die; // $res = preg_split("//",$str,5,PR...
  • 找到其中最长上升子序列长度 给定一个无序的整数数组,找到其中最长上升子序列长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明: 可能会有多种...
  • 找出最长连续子序列

    千次阅读 2018-06-30 17:18:59
    import java.util.*; public class Solution { //方法一:时间复杂度为O(nlog(n)) public int longestConsecutive(int[] num) { if(num==null||num.length==0) return 0; Arrays.sort(...
  • leetcode 128 最长连续子序列 但是有所不同的是,这里求得不仅仅是长度,同时需要将整个子序列给复原出来,最后返回一个子序列的数组。 100, 4, 200, 1, 3, 2 => [1,2,3,4] 2. 分析 第一种方法是利用Map的方法...
  • 最长公共子序列长度

    千次阅读 2019-03-15 21:06:37
    求两个字符串的公共子序列1.求最长公共子序列(子序列可以不连续)2.最长连续子串 1.求最长公共子序列(子...例如,a串abbcd,b串abcd,dp[3][3]就表示的a的前三个字符与b的前三个字符的最长公共子序列长度,值为2。...
  • 题目描述 给定无序数组arr,返回其中最长的连续序列的长度(要求值连续,位置可以不连续,例如 3,4,5,6为连续的...输出一个整数,代表最长连续子序列长度。 示例1 输入 6 100 4 200 1 3 2 输出 4 示例2 输入
  • 如果两个串的最后结尾的字符相同,其最长公共子序列长度=分别去掉结尾字符剩下的部分的最长公共子序列长度+1; 不相同,则转化为相同:在其中任意一个串上补与另一个串结尾字符相等的字符,然后转化成...
  • 46.数组中最长连续子序列

    千次阅读 2021-03-28 19:29:08
    46.数组中最长连续子序列 题目描述 给定无序数组arr,返回其中最长的连续序列的长度(要求值连续,位置可以不连续,例如 3,4,5,6为连续的自然数) 输入 [100,4,200,1,3,2] 返回值 4 输入 [1,1,1] 返回值 1 分析 ...
  • 给你一个整数数组 nums ,找到其中最长严格递增子序列长度子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1:...
  • 主要介绍了JavaScript实现找出数组中最长连续数字序列的方法,需要的朋友可以参考下
  • 实现明确一个点就是,子序列是一个序列中去掉若干元素后得到的序列,也就是说子序列的元素下标是递增的就行,不需要在原序列中连续最长公共子序列,显而易见就是序列X和Y都有的最长子序列。 2 BruteForce ...
  • 给定一个无序的整数数组,找到其中最长上升子序列长度。 输入: [10,9,2,5,3,7,101,18] 输出: 4  解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明:可能会有多种最长上升子序列的组合,你只需要输出...
  • 128. 最长连续序列(python)

    千次阅读 2019-03-12 20:07:04
    给定一个未排序的整数数组,找出最长连续序列长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。 思路: 遍历每个数,若是起点...
  • 最长连续子序列 有n个正整数组成的一个序列。给定正整数sum,求长度最长的连续子序列,使得他们的和等于sum。返回此子序列的长度,如果没有要求的序列,返回-1. 输入序列仅有数字和英文逗号构成,数字之间采用英文...
  • 然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置。 def find_lcsubstr(s1, s2): m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #生成0矩阵,为方便后续计算,比字符串长度多了...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,712
精华内容 10,284
关键字:

最长连续子序列长度