首页 > 编程语言 >【算法题】2765. 最长交替子序列

【算法题】2765. 最长交替子序列

时间:2023-10-31 12:35:11浏览次数:36  
标签:nums int s1 lt 2765 交替 算法 数组 序列


题目:

给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件,我们称它是一个 交替子序列 :

m 大于 1 。
s1 = s0 + 1 。
下标从 0 开始的子数组 s 与数组 [s0, s1, s0, s1,…,s(m-1) % 2] 一样。也就是说,s1 - s0 = 1 ,s2 - s1 = -1 ,s3 - s2 = 1 ,s4 - s3 = -1 ,以此类推,直到 s[m - 1] - s[m - 2] = (-1)m 。
请你返回 nums 中所有 交替 子数组中,最长的长度,如果不存在交替子数组,请你返回 -1 。

子数组是一个数组中一段连续 非空 的元素序列。

示例 1:

输入:nums = [2,3,4,3,4]
输出:4
解释:交替子数组有 [3,4] ,[3,4,3] 和 [3,4,3,4] 。最长的子数组为 [3,4,3,4] ,长度为4 。
示例 2:

输入:nums = [4,5,6]
输出:2
解释:[4,5] 和 [5,6] 是仅有的两个交替子数组。它们长度都为 2 。

提示:

2 <= nums.length <= 100
1 <= nums[i] <= 10^4

java代码:

class Solution {
    public int alternatingSubarray(int[] nums) {
        // 累加计数     最长长度    本次交替差值
        int count = 1, maxLen = -1, flag = 1;
        // 左指针记录子序列起始位置
        for (int lt = 0; lt < nums.length - 1; lt++) {
            // 右侧指针用于对数组进行遍历
            for (int ind = lt, gt = lt + 1; gt < nums.length; ind++, gt++) {
                // 差值是否满足交替数组
                if (nums[gt] - nums[ind] == flag) {
                    // 满足
                    ++count;
                    flag = -flag;
                } else {
                    // 不满足结束当前循环
                    break;
                }
            }
            maxLen = Math.max(count, maxLen);
            // 重置计数
            count = 1;
            // 重置差值
            flag = 1;
            // 如果最长交替数组大于剩余数组长度,则直接返回
            if (nums.length - lt <= maxLen) {
                return maxLen;
            }
        }
        // 由于count的初值为1,所以需要解决没有交替子序列返回-1的问题
        return maxLen == 1 ? -1 : maxLen;
    }
}


标签:nums,int,s1,lt,2765,交替,算法,数组,序列
From: https://blog.51cto.com/u_6813689/8103641

相关文章

  • 【算法题】2769. 找出最大的可达成数字
    题目:给你两个整数num和t。如果整数x可以在执行下述操作不超过t次的情况下变为与num相等,则称其为可达成数字:每次操作将x的值增加或减少1,同时可以选择将num的值增加或减少1。返回所有可达成数字中的最大值。可以证明至少存在一个可达成数字。示例1:输入:num=4,......
  • 【算法题】2817. 限制条件下元素之间的最小绝对差
    题目:给你一个下标从0开始的整数数组nums和一个整数x。请你找到数组中下标距离至少为x的两个元素的差值绝对值的最小值。换言之,请你找到两个下标i和j,满足abs(i-j)>=x且abs(nums[i]-nums[j])的值最小。请你返回一个整数,表示下标距离至少为x的两个元素之......
  • 【算法题】7004. 判别首字母缩略词
    题目:给你一个字符串数组words和一个字符串s,请你判断s是不是words的首字母缩略词。如果可以按顺序串联words中每个字符串的第一个字符形成字符串s,则认为s是words的首字母缩略词。例如,“ab”可以由[“apple”,“banana”]形成,但是无法从[“bear”,“aardvark......
  • 10.31算法
    最长回文子串给你一个字符串s,找到s中最长的回文子串。如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 示例1:输入:s="babad"输出:"bab"解释:"aba"同样是符合题意的答案。示例2:输入:s="cbbd"输出:"bb"class Solution {public:    string longes......
  • 3.最长连续序列
    题目概述:给定一个无序数组,问这个数组的元素能够组成的连续数组的最长长度为多少。解题思路:很明显,我们需要对该数组先进行排序处理。我一开始用的是双指针,第一个指针枚举起点,第二个指针枚举该起点能够到达的最右边的距离,WA了。因为该数组有重复元素。(其实只要使用set去个重,这种方......
  • R语言非参数方法:使用核方法和K-NN(k近邻算法)分类预测心脏病数据|附代码数据
    原文链接: http://tecdat.cn/?p=22181 原文出处:拓端数据部落公众号 最近我们被客户要求撰写关于非参数方法的研究报告,包括一些图形和统计输出。本文考虑一下基于核方法进行分类预测。注意,在这里,我们不使用标准逻辑回归,它是参数模型。非参数方法用于函数估计的非参数方法大......
  • 文心一言 VS 讯飞星火 VS chatgpt (124)-- 算法导论10.5 5题
    五、用go语言,给定一个n结点的二叉树,写出一个O(n)时间的非递归过程,将该树每个结点的关键字输出。要求除该树本身的存储空间外只能使用固定量的额外存储空间,且在过程中不得修改该树,即使是暂时的修改也不允许。文心一言:您可以使用一个栈来存储节点,以便在遍历二叉树时进行回溯。由于您......
  • 学习笔记432—VBM_DARTEL算法对灰质变化的计算
    VBM_DARTEL算法对灰质变化的计算根据一些文献得知,VBM目前比较新的算法是DARTEL算法,这一算法被集成在SPM里,这里记录一下做法。VBM是对T1像进行分割得到灰质等。所以要有结构T1加权像数据。整个流程应该是这样:1.手动调整前联合(AC)首先就是需要我们自己手动调整一下结构像,打开SPM,sp......
  • 基于GRU门控循环网络的时间序列预测matlab仿真,对比LSTM网络
    1.算法运行效果图预览 LSTM:    GRU    2.算法运行软件版本matlab2022a 3.算法理论概述       门控循环单元(GatedRecurrentUnit,简称GRU)是一种用于序列建模和预测的递归神经网络(RNN)变体。GRU通过引入门控机制,克服了传统RNN在处理长序列时......
  • 排序算法——冒泡,插入,选择排序
    冒泡排序冒泡排序是一种简单的排序算法实际上是每一次排序都会将最大的元素放到最后比较相邻的元素,如果第一个比第二个大,就交换他们两个对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数针对所有的元素重复以上的步骤点击查看......