天天快资讯:2023-05-31:给定一个整数数组 A,你可以从某一起始索引出发,跳跃一定次数 在你跳跃的过程中,第 1、3、5... 次跳跃称为奇数跳跃 而第 2、4、6... 次跳跃称为偶数跳跃 你可以按以下
博客园 2023-05-31 22:11:50

2023-05-31:给定一个整数数组 A,你可以从某一起始索引出发,跳跃一定次数


(资料图片)

在你跳跃的过程中,第 1、3、5... 次跳跃称为奇数跳跃

而第 2、4、6... 次跳跃称为偶数跳跃

你可以按以下方式从索引 i 向后跳转到索引 j(其中 i < j):

在进行奇数跳跃时(如,第 1,3,5... 次跳跃),你将会跳到索引 j

使得 A[i] <= A[j],A[j] 是可能的最小值。如果存在多个这样的索引 j

你只能跳到满足要求的最小索引 j 上。

在进行偶数跳跃时(如,第 2,4,6... 次跳跃)

你将会跳到索引 j,使得 A[i] >= A[j],A[j] 是可能的最大值

如果存在多个这样的索引 j,你只能跳到满足要求的最小索引 j 上。

(对于某些索引 i,可能无法进行合乎要求的跳跃。)

如果从某一索引开始跳跃一定次数(可能是 0 次或多次)

就可以到达数组的末尾(索引 A.length - 1)

那么该索引就会被认为是好的起始索引。

返回好的起始索引的数量。

输入:[2,3,1,1,4]。

输出:3。

答案2023-05-31:

大体步骤如下:

1.对于数组中的每个元素,使用有序表(treemap)分别找到奇数规则和偶数规则下的下一步位置。

2.奇数规则下要寻找第一个大于等于当前值的位置,而偶数规则下要寻找第一个小于等于当前值的位置。

3.使用动态规划方法,从后往前遍历数组,对于每个位置分别判断是否能够到达数组的末尾。

4.定义 dp[i][0] 表示当来到 i 位置,且在奇数规则下,最终能否到达数组末尾。同理,dp[i][1] 表示当来到 i 位置,且在偶数规则下,最终能否到达数组末尾。

5.对于每个位置 i,如果奇数规则下可以跳到下一个位置 odd[i],则 dp[i][0] = dp[odd[i]][1]。同理,如果偶数规则下可以跳到下一个位置 even[i],则 dp[i][1] = dp[even[i]][0]。

6.初始化 dp[n-1][0] 和 dp[n-1][1] 为 true,表示从数组末尾出发,无论是奇数规则还是偶数规则,都可以到达该位置。

7.遍历数组,对于每个位置 i,如果 dp[i][0] = true,则说明从该位置出发遵循奇数规则可以到达数组末尾,答案加 1。

8.返回答案。

时间复杂度:在该算法中,使用了一次 treemap 的查询操作和一次 treemap 的插入操作,这两种操作的时间复杂度均为 O(log n),对于遍历整个数组以及动态规划的过程,其时间复杂度均为 O(n),因此总的时间复杂度为 O(n log n)。

空间复杂度:算法中使用三个数组以及一个有序表。其中 odd 和 even 数组的长度为 n,dp 数组的大小为 n * 2,而有序表需要存储 n 个元素,因此算法的空间复杂度为 O(n)。

go语言完整代码如下:

package mainimport ("fmt""github.com/emirpasic/gods/maps/treemap")func oddEvenJumps(arr []int) int {n := len(arr)// 来到了i位置,如果要遵循奇数规则,应该去哪?odd[i]odd := make([]int, n)// 来到了i位置,如果要遵循偶数规则,应该去哪?even[i]even := make([]int, n)// 有序表,// key : 某个值// value : key这个值,出现的最左位置// >= key 且最小// <= key 且最大orderMap := treemap.NewWithIntComparator()for i := n - 1; i >= 0; i-- {// i位置,arr[i],奇数规则,>= arr[i]且最小的!to, to2 := orderMap.Ceiling(arr[i])if to != nil {odd[i] = to2.(int)} else {odd[i] = -1}// i位置,arr[i],偶数规则,<= arr[i]且最大的!to, to2 = orderMap.Floor(arr[i])if to != nil {even[i] = to2.(int)} else {even[i] = -1}orderMap.Put(arr[i], i)}// dp[i][0] : 当来到i位置,且在奇数规则下,最终能不能到结尾?// dp[i][1] : 当来到i位置,且在偶数规则下,最终能不能到结尾?dp := make([][]bool, n)for i := range dp {dp[i] = make([]bool, 2)}dp[n-1][0] = truedp[n-1][1] = trueans := 1for i := n - 2; i >= 0; i-- {// dp[i][0] : 当来到i位置,且在奇数规则下,最终能不能到结尾// odd[i] -> 右走! -1if odd[i] != -1 {dp[i][0] = dp[odd[i]][1]}// dp[i][1] : 当来到i位置,且在偶数规则下,最终能不能到结尾if even[i] != -1 {dp[i][1] = dp[even[i]][0]}if dp[i][0] {ans++}}return ans}func main() {arr := []int{2, 3, 1, 1, 4}result := oddEvenJumps(arr)fmt.Println(result)}

rust语言完整代码如下:

use std::collections::BTreeMap;fn odd_even_jumps(arr: Vec) -> i32 {    let n = arr.len();    // 来到了i位置,如果要遵循奇数规则,应该去哪?odd[i]    let mut odd = vec![0; n];    // 来到了i位置,如果要遵循偶数规则,应该去哪?even[i]    let mut even = vec![0; n];    // 有序表,    // key : 某个值    // value : key这个值,出现的最左位置    // >= key 且最小    // <= key 且最大    let mut order_map = BTreeMap::new();    let mut i = n as i32 - 1;    while i >= 0 {        // i位置,arr[i],奇数规则,>= arr[i]且最小的!        if let Some((&_to, &to2)) = order_map.range(arr[i as usize]..).next() {            odd[i as usize] = to2;        } else {            odd[i as usize] = -1;        }        // i位置,arr[i],偶数规则,<= arr[i]且最大的!        if let Some((&_to, &to2)) = order_map.range(..=arr[i as usize]).rev().next() {            even[i as usize] = to2;        } else {            even[i as usize] = -1;        }        order_map.insert(arr[i as usize], i);        i -= 1;    }    // dp[i][0] : 当来到i位置,且在奇数规则下,最终能不能到结尾?    // dp[i][1] : 当来到i位置,且在偶数规则下,最终能不能到结尾?    let mut dp = vec![vec![false; 2]; n];    dp[n - 1][0] = true;    dp[n - 1][1] = true;    let mut ans = 1;    let mut i = n as i32 - 2;    while i >= 0 {        // dp[i][0] : 当来到i位置,且在奇数规则下,最终能不能到结尾        // odd[i] -> 右走! -1        dp[i as usize][0] = odd[i as usize] != -1 && dp[odd[i as usize] as usize][1];        // dp[i][1] : 当来到i位置,且在偶数规则下,最终能不能到结尾        dp[i as usize][1] = even[i as usize] != -1 && dp[even[i as usize] as usize][0];        ans += if dp[i as usize][0] { 1 } else { 0 };        i -= 1;    }    ans}fn main() {    let arr = vec![2,3,1,1,4];    let result = odd_even_jumps(arr);    println!("{}", result);}

c++完整代码如下:

#include #include #include using namespace std;int oddEvenJumps(vector& arr) {int n = arr.size();// 来到了i位置,如果要遵循奇数规则,应该去哪?odd[i]vector odd(n);// 来到了i位置,如果要遵循偶数规则,应该去哪?even[i]vector even(n);// 有序表,// key : 某个值// value : key这个值,出现的最左位置// >= key 且最小// <= key 且最大map orderMap;for (int i = n - 1; i >= 0; --i) {// i位置,arr[i],奇数规则,>= arr[i]且最小的!auto it = orderMap.lower_bound(arr[i]);if (it != orderMap.end()) {odd[i] = it->second;}else {odd[i] = -1;}// i位置,arr[i],偶数规则,<= arr[i]且最大的!it = orderMap.upper_bound(arr[i]);if (it != orderMap.begin()) {even[i] = (--it)->second;}else {even[i] = -1;}orderMap[arr[i]] = i;}// dp[i][0] : 当来到i位置,且在奇数规则下,最终能不能到结尾?// dp[i][1] : 当来到i位置,且在偶数规则下,最终能不能到结尾?vector> dp(n, vector(2));dp[n - 1][0] = true;dp[n - 1][1] = true;int ans = 1;for (int i = n - 2; i >= 0; --i) {// dp[i][0] : 当来到i位置,且在奇数规则下,最终能不能到结尾// odd[i] -> 右走! -1if (odd[i] != -1) {dp[i][0] = dp[odd[i]][1];}// dp[i][1] : 当来到i位置,且在偶数规则下,最终能不能到结尾if (even[i] != -1) {dp[i][1] = dp[even[i]][0];}if (dp[i][0]) {++ans;}}return ans;}int main() {vector arr = { 2,3,1,1,4 };int result = oddEvenJumps(arr);cout << result << endl;return 0;}

c语言完整代码如下:

#include #include #include struct BTreeNode {    int key;    int value;    struct BTreeNode* left;    struct BTreeNode* right;};struct BTreeMap {    struct BTreeNode* root;};struct BTreeNode* createNode(int key, int value) {    struct BTreeNode* node = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));    node->key = key;    node->value = value;    node->left = NULL;    node->right = NULL;    return node;}struct BTreeNode* insertNode(struct BTreeNode* node, int key, int value) {    if (node == NULL) {        return createNode(key, value);    }    if (key < node->key) {        node->left = insertNode(node->left, key, value);    }    else if (key > node->key) {        node->right = insertNode(node->right, key, value);    }    else {        node->value = value;    }    return node;}struct BTreeNode* findCeiling(struct BTreeNode* node, int target) {    if (node == NULL) {        return NULL;    }    if (node->key == target) {        return node;    }    if (node->key < target) {        return findCeiling(node->right, target);    }    struct BTreeNode* leftNode = findCeiling(node->left, target);    if (leftNode != NULL) {        return leftNode;    }    return node;}struct BTreeNode* findFloor(struct BTreeNode* node, int target) {    if (node == NULL) {        return NULL;    }    if (node->key == target) {        return node;    }    if (node->key > target) {        return findFloor(node->left, target);    }    struct BTreeNode* rightNode = findFloor(node->right, target);    if (rightNode != NULL) {        return rightNode;    }    return node;}struct BTreeMap* createMap() {    struct BTreeMap* map = (struct BTreeMap*)malloc(sizeof(struct BTreeMap));    map->root = NULL;    return map;}void insert(struct BTreeMap* map, int key, int value) {    map->root = insertNode(map->root, key, value);}int getCeiling(struct BTreeMap* map, int target) {    struct BTreeNode* ceilingNode = findCeiling(map->root, target);    if (ceilingNode == NULL) {        return -1;    }    return ceilingNode->value;}int getFloor(struct BTreeMap* map, int target) {    struct BTreeNode* floorNode = findFloor(map->root, target);    if (floorNode == NULL) {        return -1;    }    return floorNode->value;}void destroyNode(struct BTreeNode* node) {    if (node == NULL) {        return;    }    destroyNode(node->left);    destroyNode(node->right);    free(node);}void destroyMap(struct BTreeMap* map) {    destroyNode(map->root);    free(map);}int oddEvenJumps(int* arr, int arrSize) {    int n = arrSize;    // 来到了i位置,如果要遵循奇数规则,应该去哪?odd[i]    int* odd = (int*)malloc(n * sizeof(int));    // 来到了i位置,如果要遵循偶数规则,应该去哪?even[i]    int* even = (int*)malloc(n * sizeof(int));    // 有序表,    // key : 某个值    // value : key这个值,出现的最左位置    // >= key 且最小    // <= key 且最大    struct BTreeMap* orderMap = createMap();    for (int i = n - 1; i >= 0; --i) {        // i位置,arr[i],奇数规则,>= arr[i]且最小的!        int to2 = getCeiling(orderMap, arr[i]);        if (to2 == -1) {            odd[i] = -1;        }        else {            odd[i] = to2;        }        // i位置,arr[i],偶数规则,<= arr[i]且最大的!        to2 = getFloor(orderMap, arr[i]);        if (to2 == -1) {            even[i] = -1;        }        else {            even[i] = to2;        }        insert(orderMap, arr[i], i);    }    destroyMap(orderMap);    // dp[i][0] : 当来到i位置,且在奇数规则下,最终能不能到结尾?    // dp[i][1] : 当来到i位置,且在偶数规则下,最终能不能到结尾?    bool** dp = (bool**)malloc(n * sizeof(bool*));    for (int i = 0; i < n; ++i) {        dp[i] = (bool*)malloc(2 * sizeof(bool));        dp[i][0] = false;        dp[i][1] = false;    }    dp[n - 1][0] = true;    dp[n - 1][1] = true;    int ans = 1;    for (int i = n - 2; i >= 0; --i) {        // dp[i][0] : 当来到i位置,且在奇数规则下,最终能不能到结尾        // odd[i] -> 右走! -1        if (odd[i] != -1) {            dp[i][0] = dp[odd[i]][1];        }        // dp[i][1] : 当来到i位置,且在偶数规则下,最终能不能到结尾        if (even[i] != -1) {            dp[i][1] = dp[even[i]][0];        }        if (dp[i][0]) {            ++ans;        }    }    // 释放内存    for (int i = 0; i < n; ++i) {        free(dp[i]);    }    free(dp);    free(odd);    free(even);    return ans;}int main() {    int arr[] = { 2,3,1,1,4 };    int arrSize = sizeof(arr) / sizeof(int);    int result = oddEvenJumps(arr, arrSize);    printf("%d\n", result);     return 0;}

天天快资讯:2023-05-31:给定一个整数数组 A,你可以从某一起始索引出发,跳跃一定次数 在你跳跃的过程中,第 1、3、5... 次跳跃称为奇数跳跃 而第 2、4、6... 次跳跃称为偶数跳跃 你可以按以下

2023-05-31 22:11:50

30秒速探沧州园博园丨邢台园:造清风梅苑,述清廉典故

2023-05-31 21:12:33

【世界时快讯】极米与坚果的辩论引发热议 超20%网友:二人转式的碰瓷营销

2023-05-31 20:42:04

十一画家人(十一人画家) 当前热门

2023-05-31 19:31:38

楼组特色居民说了算!普陀这里社区自治有妙招→

2023-05-31 19:13:22

雷丁汽车所持野马汽车1.2亿元股权被冻结 环球微速讯

2023-05-31 14:40:05

2023鱼别丢的微信心情说说(成年人的平和,一半是理解,一)(魔兽鱼别丢啥意思) 环球信息

2023-05-31 13:57:13

2023网名大全成熟精选网名116个(2o20网名)|全球快报

2023-05-31 13:40:30

“虫专家”用上了!1克虫卵“吃掉”10公斤厨余垃圾_天天报道

2023-05-31 13:34:39

环球热文:每日酒企动态 | 张永踊出任汾酒销售公司总经理;五粮液集团涉足新能源

2023-05-31 13:26:54

如何制作跳房子板_送女朋友一千左右的礼物选什么好一点 每日快看

2023-05-31 12:47:43

主打“冷”“素” 刷屏的极简午餐适合每个人吗?

2023-05-31 12:14:35

新华全媒+丨点亮不懈探索的精神火炬——基层科技工作者工作生产一线见闻_信息

2023-05-31 11:32:36

国网宝鸡供电公司:“降温神器”为电网迎峰度夏保驾护航_资讯推荐

2023-05-31 11:16:25

2021河北高考状元是衡水中学吗_2021河北高考状元 天天报资讯

2023-05-31 11:03:34

合肥高新区630套保障性租赁住房开工建设 天天即时看

2023-05-31 10:37:17

今日报丨绿色消费应有更宽广视野

2023-05-31 10:12:31

家政维修乱象亟待根治-全球新动态

2023-05-31 09:42:04

泰嘉股份(002843)5月30日主力资金净买入6859.94万元|要闻

2023-05-31 09:05:31

朝云集团近三年营收净利润下滑数亿,巨压下押注宠物食品前景难料 环球视点

2023-05-31 08:58:08

梅德韦杰夫不敌资格赛球员 7战法网5次一战出局

2023-05-31 08:19:06

官方售价15.29-20.39万元 奇瑞瑞虎9正式上市_环球速递

2023-05-31 07:52:02

浙能电力(600023):5月30日北向资金增持343.98万股

2023-05-31 07:33:31

文化差异引起的尴尬矛盾或者冲突的事例_文化差异的事例

2023-05-31 06:24:14

观速讯丨沿海地区怎么预防台风_台风时沿海地区有哪些预防措施

2023-05-31 06:12:57

贷款上征信多久才能消除,五年

2023-05-31 05:47:13

帕金斯:实在搞不懂斯波为什么没得到过年度最佳教练

2023-05-31 05:30:25

世界观察:北京童装批发市场在哪里_北京童装批发市场

2023-05-31 04:20:16

世界关注:暨怎么读 暨

2023-05-31 03:13:26

杭州解百: 公司旗下悦胜体育将以特许零售商的身份为契机,积极推动亚运会相关产品销售,助力杭州亚运会_天天报道

2023-05-31 02:08:20

钢材的重量计算公式_45号钢重量计算公式

2023-05-31 01:56:31

全球观点:熄火,上海豪宅云锦东方暂停摇号

2023-05-30 23:14:05

最新中国农业行业标准第十辑:植保分册(对于最新中国农业行业标准第十辑:植保分册简单介绍)

2023-05-30 23:13:29

全球速读:剑灵洪门崛起成就大全(剑灵洪门崛起成就)

2023-05-30 22:50:29

西部(重庆)科学城高新技术企业年底有望达1150家-环球热点评

2023-05-30 21:57:34

当前速递!神舟十六号载人飞船发射取得圆满成功

2023-05-30 21:42:56

世界快看点丨救人一命胜造七级浮图的意思_救人一命胜造七级浮图的出处

2023-05-30 20:56:43

记者:梅西不会回巴萨,俱乐部找不到合适的解决方案-全球观天下

2023-05-30 21:00:43

武汉湘口街汉江村开展慰问送真情活动

2023-05-30 20:02:05

大同大学主专业怎么样什比较好材料

2023-05-30 19:59:45

分数三分之一怎么打(三分之一分数形式) 世界播报

2023-05-30 19:39:19

世界快资讯丨广东省肇庆市市场监管局开展2023年反不正当竞争“守护”专项执法行动

2023-05-30 19:31:56

局域网如何共享文件和设置权限(如何设置局域网共享) 快播报

2023-05-30 18:55:19

流连什么沛的成语有哪些(流连什么沛的成语)

2023-05-30 18:44:50

里昂:维持美团-W买入评级 目标价235港元_环球简讯

2023-05-30 18:30:27

最新快讯!2024年贵州同等学力申硕报考条件及流程

2023-05-30 18:15:45

摩托罗拉e11测评(摩托罗拉e11)

2023-05-30 17:43:19

全球今亮点!基金赎回为什么资金冻结 可能是这些原因

2023-05-30 17:42:02

双色球2004009期补摇奖录像(事件) 焦点讯息

2023-05-30 16:54:30

2023“新一线”城市排行榜发布 成都再次位居榜首

2023-05-30 16:52:31

褫职_褫

2023-05-30 15:56:12

天刀IP八周年主题曲《少侠好功夫》

2023-05-30 15:44:21

世界新动态:重庆:三峡旅游持续升温

2023-05-30 15:28:28

2023珠峰科考|先进设备、新技术助力2023年珠峰科考

2023-05-30 15:10:27

头发的发的偏旁部首是什么 头发的发的偏旁是什么|环球报道

2023-05-30 14:46:36

当前热文:路虎揽胜星脉将于2025年变身纯电动汽车

2023-05-30 14:35:25

聚焦车规功率器件领域的Fablite公司云潼科技完成数亿元A轮融资_每日播报

2023-05-30 14:25:45

武汉杨森三层仿生结构人工血管项目首次亮相,预计两年内上市|环球动态

2023-05-30 13:51:34

世界关注:“吴谢宇弑母案”二审公开宣判:驳回上诉 维持原判

2023-05-30 13:10:20

你好毒红九好看吗_你好毒 红九

2023-05-30 11:29:46

江宁推动横溪西瓜创新发展 书写“甜蜜经济”好文章-环球讯息

2023-05-30 10:56:59

热闹的“五道口德比” 发展中的校园篮球 天天观点

2023-05-30 10:45:44

环球要闻:耕海牧渔把大海变成“蓝色粮仓”

2023-05-30 10:09:42

卓朗科技:5月29日融资买入559.88万元,融资融券余额2.86亿元 天天速递

2023-05-30 08:45:24

美媒:极端天气多发,气象学家频受威胁

2023-05-30 08:06:10

山竹台风

2023-05-30 07:08:12

狼王梦好词100个字 狼王梦好词100个

2023-05-30 06:20:41

【环球播资讯】正威新材(002201):5月29日北向资金增持16.82万股

2023-05-30 05:37:39

京挑客是什么符号_京挑客是什么|全球聚焦

2023-05-30 04:48:05

复合木地板优缺点 复合地板和实木地板的区别 天天观察

2023-05-30 04:08:01

【环球新要闻】永贵电器:子公司液冷欧标直流充电枪产品获得认证

2023-05-30 03:10:33

焦点速讯:indangerous和indanger的区别_indanger

2023-05-30 01:52:20

力鼎光电:5月29日召开业绩说明会,投资者参与

2023-05-30 01:08:21

暴雨来袭!有人趟进齐腰深水救人,有人用身体压住窨井盖……|全球今日讯

2023-05-30 00:18:47

全球关注:整就完事儿,刘能谢广坤这综艺我能笑 100 期!

2023-05-29 23:13:22

今热点:荔枝是几月份的水果(五一的时候荔枝熟了吗)

2023-05-29 23:03:22

双鹭药业:出于财务审慎原则公司先已按合同约定作了计提处理

2023-05-29 22:37:51

环球快看:2023高招进行时丨香港浸会大学:预计招130-150人 独立招生 报名截止日期6月13日

2023-05-29 21:47:06

世界即时看!认房不认贷什么意思?意味着什么?

2023-05-29 20:56:16

畅通郑州在行动!郑州交警服务过境麦收收割机驾驶员|全球播资讯

2023-05-29 20:35:31

中国卫通:控股股东拟非公开发行可交换公司债券_每日精选

2023-05-29 18:34:05

世界百事通!2023年广元旺苍县蓝莓采摘节时间+活动

2023-05-29 18:00:34

佛教三宝

2023-05-29 17:38:26

天天快消息!恻隐的拼音_恻隐

2023-05-29 16:41:48

大约 94000 辆本田和讴歌跨界 SUV小型货车皮卡和轿车将被召回 今亮点

2023-05-29 15:59:00

恒大高新(002591)5月29日主力资金净买入4411.02万元 世界微资讯

2023-05-29 15:23:32

环球百事通!2023数博会,惠农网带领农业走入人工智能时代

2023-05-29 15:01:08

“为万物、齐创造” 苹果系列课程收官:保护生物多样性

2023-05-29 13:58:43

【天天快播报】淅川农商银行助农民“雨口”夺粮保丰收

2023-05-29 13:06:28

24支队伍逐浪竞渡,粤港澳大湾区茅洲河龙舟赛决赛开桨

2023-05-29 12:25:51

平板办公和笔记本的区别_平板与笔记本的区别-环球信息

2023-05-29 11:06:08

【全球聚看点】三面不规则裸眼3D创意屏!联建光电600㎡大屏点亮天津商业新地标

2023-05-29 10:38:21

海参泡发简单方法(海参泡发最好方法步骤)

2023-05-29 10:18:50

西部创业:5月26日融资净买入32.32万元,连续3日累计净买入135.62万元-焦点报道

2023-05-29 09:10:38

核电核准及开工项目渐次增多产业链订单重回历史高位

2023-05-29 08:22:51

一个“迷人”的县,总人口32万,就在江西

2023-05-29 07:11:25

江苏省徐州市2023-05-29 04:43发布暴雨蓝色预警

2023-05-29 06:00:43

小吃吃出大产业——来自餐饮业一线的观察-焦点信息

2023-05-29 04:52:24

梨树

2023-05-29 02:02:33

键盘中百分号怎么打_百分号在键盘上怎么打

2023-05-29 00:23:13