当前位置:网站首页>LeetCode每日一题(1997. First Day Where You Have Been in All the Rooms)
LeetCode每日一题(1997. First Day Where You Have Been in All the Rooms)
2022-07-06 06:26:00 【wangjun861205】
There are n rooms you need to visit, labeled from 0 to n - 1. Each day is labeled, starting from 0. You will go in and visit one room a day.
Initially on day 0, you visit room 0. The order you visit the rooms for the coming days is determined by the following rules and a given 0-indexed array nextVisit of length n:
Assuming that on a day, you visit room i,
if you have been in room i an odd number of times (including the current visit), on the next day you will visit a room with a lower or equal room number specified by nextVisit[i] where 0 <= nextVisit[i] <= i;
if you have been in room i an even number of times (including the current visit), on the next day you will visit room (i + 1) mod n.
Return the label of the first day where you have been in all the rooms. It can be shown that such a day exists. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nextVisit = [0,0]
Output: 2
Explanation:
On day 0, you visit room 0. The total times you have been in room 0 is 1, which is odd.
On the next day you will visit room nextVisit[0] = 0On day 1, you visit room 0, The total times you have been in room 0 is 2, which is even.
On the next day you will visit room (0 + 1) mod 2 = 1On day 2, you visit room 1. This is the first day where you have been in all the rooms.
Example 2:
Input: nextVisit = [0,0,2]
Output: 6
Explanation:
Your room visiting order for each day is: [0,0,1,0,0,1,2,…].
Day 6 is the first day where you have been in all the rooms.
Example 3:
Input: nextVisit = [0,1,2,0]
Output: 6
Explanation:
Your room visiting order for each day is: [0,0,1,1,2,2,3,…].
Day 6 is the first day where you have been in all the rooms.
Constraints:
- n == nextVisit.length
- 2 <= n <= 105
- 0 <= nextVisit[i] <= i
这题好像以前做过,也可能只是相似的, 但是自己一点印象都没有了
最近做的题都贱嗖嗖的, 难的不在解题思路, 都在各种细枝末节上
假设 dp[i][odd]为奇数次进到第 i 个房间所需要的步骤, dp[i][even]为偶数次进入到第 i 个房间所需要的步骤, 那么我们可以推倒出如下两条;
dp[i][odd] = dp[i-1][even] + 1
dp[i][even] = dp[i][odd] + (dp[i][odd]-dp[k][odd]) + 1
其中 k = next_visit[i]
这两条中的第一条好理解, 只有欧数次进入一个房间后才能向后推进一个房间。 第二条实际表达的是, 偶数次进入第 i 个房间的前提一定是有一个奇数次进入了, 因为是奇数次进入所以我们需要返回到前面的某一点, 注意,题目说的是返回到 next_visit[i]之前的任意一点,但是我们要的是最小距离, 按照题目的规则,我们返回的点距离当前点越远,我们走回当前点所需的步数一定是越多的, 所以不用考虑, 我们选择的返回点一定是 next_visit[i], 所以我们就相当于重走了一遍从 next_visit[i]到 i 的距离, 所以就是 dp[i][odd] - dp[k][odd] + 1。 整个计算过程需要注意, 因为结果都是做过 mod 运算的, 所以有可能出现 dp[i][odd] < dp[k][odd]的情况, 这时候算出来的结果就是负数了, 要避免这种情况可以将 dp[i][odd] + 10.pow(9) + 7
use std::collections::HashMap;
impl Solution {
fn dp(
next_visit: &Vec<i32>,
i: usize,
is_odd: bool,
cache: &mut HashMap<(usize, bool), i128>,
) -> i128 {
let m = 10i128.pow(9) + 7;
if is_odd {
let next = if let Some(c) = cache.get(&(i - 1, false)) {
*c
} else {
Solution::dp(next_visit, i - 1, false, cache)
};
let ans = (next + 1) % m;
cache.insert((i, is_odd), ans);
return ans;
}
let odd = if let Some(c) = cache.get(&(i, true)) {
*c
} else {
Solution::dp(next_visit, i, true, cache)
};
let prev = if let Some(c) = cache.get(&(next_visit[i] as usize, true)) {
*c
} else {
Solution::dp(next_visit, next_visit[i] as usize, true, cache)
};
let ans = if 2 * odd < prev {
(2 * odd + m - prev + 1) % m
} else {
(2 * odd - prev + 1) % m
};
cache.insert((i, is_odd), ans);
ans
}
pub fn first_day_been_in_all_rooms(next_visit: Vec<i32>) -> i32 {
let mut cache = HashMap::new();
cache.insert((0, true), 0);
cache.insert((0, false), 1);
Solution::dp(&next_visit, next_visit.len() - 1, true, &mut cache) as i32
}
}
边栏推荐
- Simulation volume leetcode [general] 1109 Flight reservation statistics
- Address bar parameter transmission of list page based on jeecg-boot
- 模拟卷Leetcode【普通】1414. 和为 K 的最少斐波那契数字数目
- Left matching principle of joint index
- Cobalt strike feature modification
- 基於JEECG-BOOT的list頁面的地址欄參數傳遞
- Qt:无法定位程序输入点XXXXX于动态链接库。
- Tms320c665x + Xilinx artix7 DSP + FPGA high speed core board
- Simulation volume leetcode [general] 1405 Longest happy string
- The internationalization of domestic games is inseparable from professional translation companies
猜你喜欢
Past and present lives of QR code and sorting out six test points
MFC关于长字符串unsigned char与CString转换及显示问题
Advanced MySQL: Basics (1-4 Lectures)
In English translation of papers, how to do a good translation?
Summary of leetcode's dynamic programming 4
How to translate professional papers and write English abstracts better
Address bar parameter transmission of list page based on jeecg-boot
How effective is the Chinese-English translation of international economic and trade contracts
Drug disease association prediction based on multi-scale heterogeneous network topology information and multiple attributes
金融德语翻译,北京专业的翻译公司
随机推荐
In English translation of papers, how to do a good translation?
Luogu p2141 abacus mental arithmetic test
Left matching principle of joint index
How much is it to translate Chinese into English for one minute?
Delete the variables added to watch1 in keil MDK
基于JEECG-BOOT的list页面的地址栏参数传递
How effective is the Chinese-English translation of international economic and trade contracts
Redis core technology and basic architecture of actual combat: what does a key value database contain?
专业论文翻译,英文摘要如何写比较好
Cobalt strike feature modification
Simulation volume leetcode [general] 1218 Longest definite difference subsequence
Resttemplate and feign realize token transmission
What are the commonly used English words and sentences about COVID-19?
Simulation volume leetcode [general] 1219 Golden Miner
Difference between backtracking and recursion
Summary of leetcode's dynamic programming 4
An article was uncovered to test the truth of outsourcing companies
Convert the array selected by El tree into an array object
模拟卷Leetcode【普通】1061. 按字典序排列最小的等效字符串
MFC on the conversion and display of long string unsigned char and CString