精华内容
参与话题
问答
  • 376. 摆动序列

    2019-08-03 15:21:17
    如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。 例如,[1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5...

    题目描述

    如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。

    例如, [1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。

    给定一个整数序列,返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。

     

    示例

    示例 1:

    输入: [1,7,4,9,2,5]
    输出: 6 
    解释: 整个序列均为摆动序列。
    示例 2:

    输入: [1,17,5,10,13,15,10,5,16,8]
    输出: 7
    解释: 这个序列包含几个长度为 7 摆动序列,其中一个可为[1,17,10,13,10,16,8]。
    示例 3:

    输入: [1,2,3,4,5,6,7,8,9]
    输出: 2

     

    思路

    先去掉所有重复数字。

    然后找局部最小值点和局部最大值点。

     

    代码

    class Solution {
    public:
        int wiggleMaxLength(vector<int>& nums) {
            // 删除相同元素
            nums.erase(unique(nums.begin(), nums.end()), nums.end());
            int size = nums.size();
            if (size <= 2)
                return size;
            int ret = 2;
            for (int i = 1; i < size-1; i++){
                int pre = nums[i-1], mid = nums[i], next = nums[i+1];
                if (mid > pre && mid > next) ret++;
                if (mid < pre && mid < next) ret++;
            }
            return ret;
        }
    };

     


     

     

    展开全文
  • 摆动序列(C++)

    2020-10-13 16:10:05
    如果一个序列的奇数项都比前一项大,偶数项都比前一项小,则称为一个摆动序列。 即 a2i<ai−1 , a2i+1>a2i kekao想知道,长度为 m,每个数都是 1 到n 之间的正整数的摆动序列一共有多少个。 输入格式: 输入一...

    题目描述

    如果一个序列的奇数项都比前一项大,偶数项都比前一项小,则称为一个摆动序列。 即 a2i<ai−1 , a2i+1>a2i

    kekao想知道,长度为 m,每个数都是 1 到n 之间的正整数的摆动序列一共有多少个。

    输入格式:
    输入一行包含两个整数 m,n。

    输出格式:
    输出一个整数,表示答案。答案可能很大,请输出答案除以10000的余数。

    输入样例:
    在这里给出一组输入。例如:
    3 4

    输出样例:
    在这里给出相应的输出。例如:
    14

    样例说明:
     以下是符合要求的摆动序列:

    2 1 2
    2 1 3
    2 1 4
    3 1 2
    3 1 3
    3 1 4
    3 2 3
    3 2 4
    4 1 2
    4 1 3
    4 1 4
    4 2 3
    4 2 4
    4 3 4
      
    PS:
    并没有卡时间 1<=n,m<=1000

    参考代码

    记忆化搜索版(一个测试点超时)

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <iostream>
    
    using namespace std;
    
    #define MOD 10000
    
    int M,N;
    int ans;
    bool book[1005];
    int a[1005];
    int dp[1005][1005];
    
    void print()
    {
        printf("\n");
        for(int i = 1;i<=M;i++)
        {
            printf("%d ",a[i]);
        }
        printf("\n");
    }
    
    int dfs(int step)
    {
        if (dp[step-1][a[step-1]] != -1)
        {
            //print();
            ans += dp[step-1][a[step-1]];
            ans %= MOD;
            return dp[step-1][a[step-1]];
        }
            
            
        if(step>M)
        {
            //print();
            ans += 1;
            ans %= MOD;
            return 1;
        }
        int t = 0;
        for(int i = 1;i<=N;i++)
        {
            if(step==1)
            {
                a[step] = i;
                t += dfs(step+1);
            }
            else if(step%2==1&&a[step-1]<i)
            {
                a[step] = i;
                t += dfs(step+1);
            }
            else if(step%2==0&&a[step-1]>i)
            {
                a[step] = i;
                t += dfs(step+1);
            }
        }
        
        dp[step-1][a[step-1]] = t %MOD;
        return dp[step-1][a[step-1]];
    }
    void print_2()
    {
        for(int k = 0;k<=N;k++)
        {
            printf("%4d ",k);
        }
        cout << endl;
        for(int i = 1;i<=M;i++)
        {
            printf("%4d ", i);
            for(int j = 1;j<=N;j++)
            {
                printf("%4d ",dp[i][j]);
            }
            cout << endl;
        }
    }
    int main()
    {
        //freopen("test.in","r",stdin);
        //freopen("test.out","w",stdout);
        
        memset(dp,-1,sizeof(dp));
        
        scanf("%d%d",&M,&N);
        dfs(1);
        printf("%d\n",ans);
        
        print_2();
        
    
        return 0;
    }
    
    

    dp版

    https://blog.csdn.net/salmone/article/details/105721647
    https://blog.csdn.net/kobe_cb/article/details/105594390

    展开全文
  • [LeetCode 376]摆动序列

    2020-11-08 15:49:34
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20201108152007482.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nhc2VyMTMw,...t_70#pic_center

    [LeetCode 376]C++实现验证摆动序列

    如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。

    例如, [1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。

    给定一个整数序列,返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。

    示例 1:

    输入: [1,7,4,9,2,5]
    输出: 6
    解释: 整个序列均为摆动序列。
    示例 2:

    输入: [1,17,5,10,13,15,10,5,16,8]
    输出: 7
    解释: 这个序列包含几个长度为 7 摆动序列,其中一个可为[1,17,10,13,10,16,8]。
    示例 3:

    输入: [1,2,3,4,5,6,7,8,9]
    输出: 2

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/wiggle-subsequence

    贪心思想:只保存上下峰值数量,中间的部分不计入length

    方法:状态机

    class Solution {
    public:
        enum table{//枚举标识三种状态
            begin,up,down//相等,上升,下降
        };
        int wiggleMaxLength(vector<int>& nums) {
            if(nums.empty())
                return NULL;
            //不为空情况下,子序列长度至少为1
            int max_Length=1;
            //当前状态
            int time=0;
            
            for(int i=1;i<nums.size();++i){
                switch(time){
                    case begin:
                        if(nums[i-1]<nums[i]){
                            time=up;
                            max_Length++;
                        }
                        else if(nums[i-1]>nums[i]){
                            time=down;
                            max_Length++;
                        }
                        else
                            time=begin;
                        break;
                    case up:
                        if(nums[i-1]<nums[i]){
                            time=up;
                        }
                        else if(nums[i-1]>nums[i]){
                            time=down;
                            max_Length++;
                        }
                        break;
                    case down:
                        if(nums[i-1]<nums[i]){
                            time=up;
                            max_Length++;
                        }
                        else if(nums[i-1]>nums[i]){
                            time=down;
                        }
                        break;
                }
            }
            return max_Length;  
        }
    };
    
    展开全文
  • 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。 例如, [1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5...

    如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。

    例如, [1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。

    给定一个整数序列,返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。

    示例 1:

    输入: [1,7,4,9,2,5]
    输出: 6 
    解释: 整个序列均为摆动序列。
    

    示例 2:

    输入: [1,17,5,10,13,15,10,5,16,8]
    输出: 7
    解释: 这个序列包含几个长度为 7 摆动序列,其中一个可为[1,17,10,13,10,16,8]。
    

    示例 3:

    输入: [1,2,3,4,5,6,7,8,9]
    输出: 2
    

    进阶:
    你能否用 O(n) 时间复杂度完成此题?

    思路分析:使用贪心算法。(时间复杂度O(n),额外空间复杂度O(1))
    不难发现,我们一直重复确定上一个峰或者谷的下标,然后寻找下一个谷或者峰。每一个峰、谷即为一个结果元素。
    比如[1, 7, 4, 9, 11, 15, 5]

    我们将第0个元素作为起始端点(峰、谷)lastIndex = 0
    	第一个元素是7,大于上一个端点nums[lastIndex],所以此时是寻找下一个峰,第二个元素为4,所以第一个元素即为峰,更新lastIndex  = 1
    	第二个元素是4,小于上一个端点nums[lastIndex],所以此时是寻找下一个谷,第三个元素为9,所以第二个元素即为谷,更新lastIndex  = 2
    	第三个元素是9,大于上一个端点nums[lastIndex],所以此时是寻找下一个峰,但是第四个元素比第三个元素大,第五个元素比第四个元素大,所以(贪心策略)下一个峰应该为第五个元素,更新lastIndex  = 5
    	第六个元素是5,小于上一个端点nums[lastIndex],所以此时是寻找下一个谷,最后的元素为5,所以最后的元素即为谷,更新lastIndex  = 6
    	退出
    
    class Solution {
    public:
    	int wiggleMaxLength(vector<int>& nums) {
    		int numsSize = nums.size();
    		int result = 0, lastIndex = 0;//lastIndex用于标记上一个端点(峰、谷)
    		if (numsSize < 2) {
    			return numsSize;
    		}
    		result = 1;
            //扫描数组
    		for (int index = 1; index < numsSize; ++index) {
    			if (nums[index] > nums[lastIndex]) {//大于上一个端点,所以是寻找下一个峰
    				lastIndex = index;//采取贪心策略,更新端点为递增序列端的最大值
    				while (index + 1 < numsSize && nums[index + 1] >= nums[lastIndex]) {
    					lastIndex = ++index;
    				}
    				result += 1;
    			}
    			else if (nums[index] < nums[lastIndex]) {//小于上一个端点,所以是寻找下一个谷
    				lastIndex = index;//采取贪心策略,更新端点为递减序列端的最小值
    				while (index + 1 < numsSize && nums[index + 1] <= nums[lastIndex]) {
    					lastIndex = ++index;
    				}
    				result += 1;
    			}
    		}
    		return result;
    	}
    };
    

    在这里插入图片描述

    展开全文
  • 摆动序列

    2020-04-21 15:20:03
    摆动序列 问题描述  如果一个序列的奇数项都比前一项大,偶数项都比前一项小,则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。  小明想知道,长度为 m,每个数都是 1 到 n 之间的正整数的摆动序列...
  • 蓝桥杯 算法训练 摆动序列 的三种解法

    千次阅读 多人点赞 2018-02-05 11:03:17
    算法训练 摆动序列    时间限制:1.0s 内存限制:512.0MB   问题描述  如果一个序列满足下面的性质,我们就将它称为摆动序列:  1. 序列中的所有数都是不大于k的正整数;  2. 序列中至少有...
  • 摆动序列(DP)

    千次阅读 2014-03-14 03:02:55
    算法训练 摆动序列 时间限制:1.0s 内存限制:512.0MB   问题描述  如果一个序列满足下面的性质,我们就将它称为摆动序列:  1. 序列中的所有数都是不大于k的正整数;  2. 序列中至少有两个数。  3. ...
  • 蓝桥杯模拟赛 摆动序列 详细题解 多种解法

    万次阅读 多人点赞 2020-04-19 21:23:02
    如果一个序列的奇数项都比前一项大,偶数项都比前一项小,则称为一个摆动序列。即 a[2i][2i-1], a[2i+1]>a[2i]。  小明想知道,长度为 m,每个数都是 1 到 n 之间的正整数的摆动序列一共有多少个。 蓝桥杯模拟赛 ...
  • 如果一个序列的奇数都比前一项大偶数都比前一项小则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。 小明想知道,长度为 m,每个数是 1 到 n 之间的正整数的摆动序列一共有多少个。 输入格式 ...
  • Java 第十届 蓝桥杯 省模拟赛 正整数的摆动序列

    万次阅读 多人点赞 2020-04-13 17:15:15
    如果一个序列的奇数都比前一项大偶数都比前一项小则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。  小明想知道,长度为 m,每个数是 1 到 n 之间的正整数的摆动序列一共有多少个。 输入...
  • 蓝桥杯模拟赛 摆动序列 题目+题解

    万次阅读 多人点赞 2020-04-13 15:06:46
    如果一个序列的奇数都比前一项大偶数都比前一项小则称为一个摆动序列。即 a[2i][2i-1], a[2i+1]>a[2i]。  小明想知道,长度为 m,每个数是 1 到 n 之间的正整数的摆动序列一共有多少个。
  •  如果一个序列的奇数都比前一项大偶数都比前一项小则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。  小明想知道,长度为 m,每个数是 1 到 n 之间的正整数的摆动序列一共有多少个。 输入...
  • 蓝桥 摆动序列 (dp)

    2020-05-03 20:25:21
    如果一个序列的奇数都比前一项大偶数都比前一项小则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。 小明想知道,长度为 m,每个数是 1 到 n 之间的正整数的摆动序列一共有多少个。 输入格式 ...
  • 如果一个序列的奇数都比前一项大偶数都比前一项小则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。  小明想知道,长度为 m,每个数是 1 到 n 之间的正整数的摆动序列一共有多少个。 输入...
  • 如果一个序列的奇数都比前一项大偶数都比前一项小则称为一个摆动序列。 即 a[2i]<a[2i-1], a[2i+1]>a[2i]。 小明想知道,长度为 m,每个数是 1 到 n 之间的正整数的摆动序列一共有多少个。 输入格式...
  • 摆动序列 蓝桥杯

    千次阅读 2014-03-18 19:06:18
     如果一个序列满足下面的性质,我们就将它称为摆动序列:  1. 序列中的所有数是不大于k的正整数;  2. 序列中至少有两个数。  3. 序列中的数两两不相等;  4. 如果第i – 1个数第i – 2个数第i个数...
  • 如果一个序列的奇数都比前一项大偶数都比前一项小则称为一个摆动序列。 即 a2i<a2i−1,a2i+1>a2i 小明想知道,长度为 m,每个数是 1 到n 之间的正整数的摆动序列一共有多少个。 输入: 输入一行包含...
  • Java实现 蓝桥杯VIP 算法训练 摆动序列

    万次阅读 多人点赞 2019-06-19 13:26:52
     如果一个序列满足下面的性质,我们就将它称为摆动序列:  1. 序列中的所有数是不大于k的正整数;  2. 序列中至少有两个数。  3. 序列中的数两两不相等;  4. 如果第i – 1个数第i – 2个数第i个数...
  • 问题描述 如果一个序列满足下面的性质,我们就将它称为摆动序列: 1. 序列中的所有数是不大于k的正整数; 2. 序列中至少有两个数。 3. 序列中的数两两不相等; 4. 如果第i – 1个数第i – 2个数...
  • 正整数的摆动序列:dp

    千次阅读 2020-04-15 20:36:20
    如果一个序列的奇数都比前一项大偶数都比前一项小则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。  小明想知道,长度为 m,每个数是 1 到 n 之间的正整数的摆动序列一共有多少个。 输入...
  • java:摆动序列

    2020-03-02 12:42:20
     如果一个序列满足下面的性质,我们就将它称为摆动序列:  1. 序列中的所有数是不大于k的正整数;  2. 序列中至少有两个数。  3. 序列中的数两两不相等;  4. 如果第i – 1个数第i – 2个数第i个数...
  • 算法训练 摆动序列

    千次阅读 2017-02-24 15:48:35
     如果一个序列满足下面的性质,我们就将它称为摆动序列:  1. 序列中的所有数是不大于k的正整数;  2. 序列中至少有两个数。  3. 序列中的数两两不相等;  4. 如果第i – 1个数第i – 2个数第i...
  • 蓝桥杯--摆动序列

    2018-03-17 23:00:35
    问题描述 如果一个序列满足下面的性质,我们就将它称为摆动序列: 1. 序列中的所有数是不大于k的正整数; 2. 序列中至少有两个数。 3. 序列中的数两两不相等; 4. 如果第i – 1个数第i – 2个数第i...
  • 如果一个序列的奇数都比前一项大偶数都比前一项小则称为一个摆动序列。即 a2i < a2i-1, a2i+1 > a2i。 小明想知道,长度为 m,每个数是 1 到 n 之间的正整数的摆动序列一共有多少个。 输入格式 输入...
  • 贪心算法&摆动序列

    2020-02-24 18:10:48
    如果连续数字之间的差严格地在正数和负数之间交替,数字序列称为摆动序列。...相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列,第一个序列是因为它的两个差值是正数,第二个序列是因为它的最后一个差...

空空如也

1 2 3 4 5 ... 20
收藏数 13,469
精华内容 5,387
关键字:

摆动序列