首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

2023-05-31:给定一个整数数组A,你可以从某一起始索引出发,跳跃一定次数在你跳跃的过程中,第1、3、5 次跳

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 main

import (

"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] = true

dp[n-1][1] = true

ans := 1

for 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++

}

}

return ans

}

func main() {

arr := []int

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]

vectorodd(n);

// 来到了i位置,如果要遵循偶数规则,应该去哪?even[i]

vectoreven(n);

// 有序表,

// key : 某个值

// value : key这个值,出现的最左位置

// >= key 且最小

// <= key 且最大

maporderMap;

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 - 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;

}

}

return ans;

}

int main() {

vectorarr = { 2,3,1,1,4 };

int result = oddEvenJumps(arr);

cout << result

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 (keykey) {

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

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;

}

在这里插入图片描述

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20230531A08VPM00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

相关快讯

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券