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

举报
福大大架构师每日一题 发表于 2023/05/31 20:14:17 2023/05/31
【摘要】 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...

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{2, 3, 1, 1, 4}
	result := oddEvenJumps(arr)
	fmt.Println(result)
}

在这里插入图片描述

rust语言完整代码如下:

use std::collections::BTreeMap;

fn odd_even_jumps(arr: Vec<i32>) -> 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 <iostream>
#include <vector>
#include <map>
using namespace std;

int oddEvenJumps(vector<int>& arr) {
	int n = arr.size();
	// 来到了i位置,如果要遵循奇数规则,应该去哪?odd[i]
	vector<int> odd(n);
	// 来到了i位置,如果要遵循偶数规则,应该去哪?even[i]
	vector<int> even(n);
	// 有序表,
	// key : 某个值
	// value : key这个值,出现的最左位置
	// >= key 且最小
	// <= key 且最大
	map<int, int> 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<vector<bool>> dp(n, vector<bool>(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] -> 右走! -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() {
	vector<int> arr = { 2,3,1,1,4 };
	int result = oddEvenJumps(arr);
	cout << result << endl;
	return 0;
}

在这里插入图片描述

c语言完整代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

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

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。