精华内容
下载资源
问答
  • 题意:给定一个数组,数组中元素的值只能是1或者-1,求其和为0的最长连续子序列长度;  数组为1,-1,1,-1,1,-1,1,-1,其结果为:8  数组为1,1,-1,1,1,-1,-1,其结果为:6 解析:  通过分析可知...

     

    题意:给定一个数组,数组中元素的值只能是1或者-1,求其和为0的最长连续子序列的长度;

        数组为1,-1,1,-1,1,-1,1,-1,其结果为:8

        数组为1,1,-1,1,1,-1,-1,其结果为:6

    解析:

      通过分析可知,要使其和为0,只有当1和-1的个数相等时,才会成立,但题目要求是连续子序列,所以单纯统计其1和-1个数不可取。

      由题目中求最长连续子序列,可想到动态规划来求解,动态规划的求解既是寻找其状态转移方程和建立状态转移表的过程

      设dp[i]为下标为i及其之前数组中所有元素的和,

                                                   

     

       
     

     

     

    如图所示,数组为1,-1,1,-1,1,-1,1,-1最后一个值为0,直接满足结果,输出8

    如上图,数组1,1,-1,1,1,-1,-1,dp取值为dp[0] = dp[2] = dp[6] = 1; dp[1] = dp[3] = d[5] = 3; dp[4] = 3;

    对于每个值,取最后一次出现的位置和第一次出现的位置之差,取它们的最大值,max((6 - 0),(5 - 1),(4 - 4) = 6

    代码如下所示:

     1 #include <cstdio>
     2 #include <map>
     3 #include <vector>
     4 #include <iostream>
     5 #include <cstdlib>
     6 
     7 using namespace std; 
     8 
     9 int main()
    10 {
    11     int n,val;
    12     while (cin >> n) {
    13         vector<int> arr(n + 1);
    14         for (int i = 1; i <= n; i++) {
    15             cin >> val;
    16             arr[i] = val;
    17         }
    18         vector<int> dp(n + 1);
    19         dp[1] = arr[1];
    20         for (int i = 2; i <= n; i++)
    21             dp[i] = arr[i] + dp[i - 1];
    22 
    23         //求取dp[i] = dp[j],i表示dp[i]的值第一次出现的位置,j表示其最后一次出现的位置
    24         //for (const auto &s : dp)
    25         //    cout << s << " ";
    26         //cout << endl;
    27         map<int, int> m;
    28         int begin, max = 0;
    29         for (int i = 1; i <= n; i++) {
    30             begin = m[dp[i]];
    31             if (begin == 0 && dp[i] != 0) {
    32                 m[dp[i]] = i;
    33             }
    34             else {
    35                 if (i - begin > max) {
    36                     max = i - begin;
    37                 }
    38             }
    39         }
    40         cout << max << endl;
    41     }
    42     system("pause");
    43     return 0;
    44 }

     

     

     

    转载于:https://www.cnblogs.com/coding-wtf/p/5849222.html

    展开全文
  • 无序数组中找到最长连续子序列 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...

    无序的一组数字中找到最长连续子序列长度

    例:

    1 20 4 21 22 最长连续数列是20 21 22,输出就是3
    12 15 31 5 14 23 13 最长数列是12 13 14 15,输出就是4

    思路:

    首先有一种方法是大家都能想到的,先把这组数字从小到大排序,然后找出最长的连续数列,计算长度,但是笔试的时候要求最优时间复杂度,所以先排序只是一种方法,不是最优方法。所以带来了下面的方法,拿出一个元素来在数组当中寻找该元素+1,+2,+3…找到之后,将找到的元素从数组中删除,这个时候就需要该初始元素必须为此连续数列最小值,so我们先在数组中寻找该元素-1的元素,若存在,就跳出这次循环,对下个元素进行操作,若没有就证明此元素是连续数列的最小值,可进行++操作。

    方法:

            public function selNum($arr){
            	$num = count($arr);//由于下面有删除数组操作,提前把数组初始长度赋值给$num,避免循环当中出错
            	for ($i = 0;$i< $num;$i++){
                	if (in_array($arr[$i]-1,$arr)){
                    	continue;//挨个取数组元素找有没有比它小1的元素,有就continue跳出当前循环
                	} else {
                    	$tmp = $arr[$i];
                    	$beg = $arr[$i];//把这个元素赋值给一个变量,便于计算数列长度
                    	while(in_array($tmp,$arr)){//循环依次找比该元素+1,+2,+3...直到找不到为止,就是该数列最大长度
                        	$key = array_search($tmp,$arr);
                        	unset($arr[$key]);
                        	$tmp++;
                    	}
                    	if ($tmp != $arr[$i]){
                        	$max[] = intval($tmp-$beg);//计算数列长度添加到数组中
                    	}
                	}
            	}
            	return $max;
        	}
    

    使用:

    	 	$str = "13 14 21 15 23 18 56 43 12 22 4 16 17 11";
            $res = explode(' ',$str);
            $info = $this->selNum($res);
            var_dump($info);die;
    

    输出:

    array(5) { [0]=> int(3) [1]=> int(1) [2]=> int(1) [3]=> int(1) [4]=> int(8) }
    //然后一目了然,最大的就是8位
    
    展开全文
  • 最长连续递增子序列长度和最长不连续递增子...设数组dp[i],表示以i为结尾的最长连续子序列长度,即上述数组的dp数组即为 dp[6] = {1,1,1,2,1,2} 代码如下 #include&lt;iostream&gt; using namespace s...

    最长连续递增子序列长度和最长不连续递增子序列长度

    1.最长连续递增子序列
    例如:Array[6] = {1,5,2,4,3,8}
    其最长连续递增子序列就2,4或3,8,最长长度为2
    设数组dp[i],表示以i为结尾的最长连续子序列长度,即上述数组的dp数组即为
    dp[6] = {1,1,1,2,1,2}
    代码如下

    #include<iostream>
    using namespace std;
    int main(){
        int Array[6] = {1,5,2,4,3,8};
        int dp[6];
        dp[0] = 1;
        for(int i=1;i<6;i++){
            dp[i] = 1;
            if(Array[i] > Array[i-1]){
                dp[i] = dp[i-1] + 1;
            }
        }
        for(int i=0;i<6;i++)
        	cout<<dp[i]<<" ";
    }
    
    

    2.最长不连续递增子序列
    例如:Array[6] = {1,5,2,4,3,8}
    其最长连续递增子序列就1,2,418或1,2,3,8,最长长度为4
    设数组dp[i],表示以i为结尾的最长不连续子序列长度,即上述数组的dp数组即为
    dp[6] = {1,2,2,3,3,4}
    代码如下

    #include<iostream>
    using namespace std;
    int main(){
        int Array[10] = {1,5,2,4,3,8,7,2,9,10};
        int dp[10];
        dp[0]=1;
        for(int i=1;i<10;i++){
            dp[i] = 1;
            for(int j=i-1;j>=0;j--){
                if(Array[i]>Array[j]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }
        for(int i=0;i<10;i++)
            cout<<dp[i]<<" ";
    }
    
    
    展开全文
  • 最长连续子序列长度 题目描述: 给你一个排序的数组,例如 { 1, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15 } ,求最长连续子序列长度。 public static int getLongest(int[] strs) { int max = 0; int oldmax = 0...

    求最长连续子序列的长度

    题目描述:

    给你一个排序的数组,例如 { 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)

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

    • 先对数组进行排序,然后再进行如上操作
    • 结合 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;
    }
    
    
    展开全文
  • 最长连续子序列 思路 1.空间换时间,利用哈希表存储原始数据。 2.遍历原始数组,例如遍历到nums[i],在哈希表中先往num[i]右边找,即num[i] + 1方向;再往左边找,即nums[i] - 1方向。 3.优化,每次往左右找时,...
  • 问题:最长连续子序列是指:子节点的值大于父节点的值。 思路1:设置一个全局变量,记录树遍历时的最大连续长度,然后递归地求解树的长度,时间复杂度为O(n) 思路2:将每个结点作为根结点,依次求取每个结点的的...
  • 目录1 最长公共子序列长度2 输出所有的最长公共子序列3 最长公共子串的长度4 输出所有的最长公共子串最长公共子串(Longest Common Substring)与最长公共子序列(Longest Common Subsequence)的区别: 子串要求...
  • /* 线段树维护区间最长连续子序列 */ #include <iostream> #include <cstdio>...//从左边开始往右的最长连续子序列长度,从右边开始往左的最长连续子序列长度,整段区间之和 }t[maxn<<2
  • 求两个字符串的公共子序列1.求最长公共子序列(子序列可以不连续)2.最长连续子串 1.求最长公共子序列(子...例如,a串abbcd,b串abcd,dp[3][3]就表示的a的前三个字符与b的前三个字符的最长公共子序列长度,值为2。...
  • 作者:Izayoi_w来源:牛客网【题目描述】给定N个数,求这N个数的最长上升子序列长度。【样例输入】72 5 3 4 1 7 6【样例输出】4所谓最长上升子序列,就是给定一列数,求序列中严格上升(后一个数 > 前一个数)的...
  • 最长递增子序列问题:给定一个长度为N的数组,给定一个长度为N的数组,找出一个最长的单调自增子序列(不一定连续,但是顺序不能乱)。例如:给定一个长度为6的数组A{5, 6, 7, 1, 2,8},则其最长的单调递增子序...
  • 问题描述:给定两个字符串A和B,返回两个字符串的最长公共子序列,并记录最长公共子序列长度。例如,两个字符串A、B分别为“1A2C3D4B56”和“B1D23CA45B6A”,则“123456”和“12C4B6”都是最长公共子序列,且最长...
  • 题目:给定一个无序的整数数组,找到其中最长上升子序列长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 理解:由于题目只要最长上升子序列长度,并不...
  • 最长递增子序列长度算法

    千次阅读 2015-06-13 22:15:15
    最长连续子序列的长度,数字保存在数组中使用动态规划算法,理解状态转移,dp[i]表示i位置下的最大连续子序列长度。 初始状态dp[0] = 1,表示在数组下标为0的时候,它的最长子序列长度就是1, 接着从1开始从左到右...
  • 题目给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列长度。一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后...
  • 题目描述给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列长度。一个字符串的子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)...
  • 最长连续子序列

    千次阅读 2019-04-21 17:34:35
    给定一个无序的子序列,判定这个子序列中最长连续子序列长度。子序列是这样定义的:比如给定{2, 3, 100, 5, 4},那么2, 3, 4, 5就算是一个连续的子序列。假设没有重复的数据。 解题思路 O(n)O(n)O(n)的复杂度,...
  • 题目:给定两个字符串 str1 和 str2,返回这两个字符串的最长公共子序列长度解释:一个字符串的子序列是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符...
  • 1. 什么是最长公共子序列?什么是最长公共子串?1.1. 最长公共子序列(Longest-Common-Subsequences...这与查找最长公共子串的问题不同的地方是:子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经...
  • 字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个...
  • 字符串b:ABCBDAB,字符串a、b的最长公共子序列长度为4,最长公共子序列是:BCBA或者BDAB,子序列可以不用连续1.求字符串a(0~m)和b(0~n)的最长公共子序列:如果a[m]等于b[n],问题是不是转化为求a...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,225
精华内容 890
热门标签
关键字:

最长连续子序列长度