当前位置:网站首页>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
}
}
边栏推荐
- CS certificate fingerprint modification
- CS通过(CDN+证书)powershell上线详细版
- [web security] nodejs prototype chain pollution analysis
- 模拟卷Leetcode【普通】1218. 最长定差子序列
- 红蓝对抗之流量加密(Openssl加密传输、MSF流量加密、CS修改profile进行流量加密)
- Manage configuration using Nacos
- Resttemplate and feign realize token transmission
- 电子书-CHM-上线CS
- Simulation volume leetcode [general] 1249 Remove invalid parentheses
- My daily learning records / learning methods
猜你喜欢
What are the commonly used English words and sentences about COVID-19?
How to do a good job in financial literature translation?
[mqtt from getting started to improving series | 01] quickly build an mqtt test environment from 0 to 1
LeetCode 732. My schedule III
云服务器 AccessKey 密钥泄露利用
Address bar parameter transmission of list page based on jeecg-boot
How to translate biomedical instructions in English
生物医学本地化翻译服务
红蓝对抗之流量加密(Openssl加密传输、MSF流量加密、CS修改profile进行流量加密)
LeetCode 731. My schedule II
随机推荐
On weak network test of special test
A 27-year-old without a diploma, wants to work hard on self-study programming, and has the opportunity to become a programmer?
专业论文翻译,英文摘要如何写比较好
LeetCode 1200. Minimum absolute difference
MFC on the conversion and display of long string unsigned char and CString
Is the test cycle compressed? Teach you 9 ways to deal with it
Selenium source code read through · 9 | desiredcapabilities class analysis
模拟卷Leetcode【普通】1061. 按字典序排列最小的等效字符串
Making interactive page of "left tree and right table" based on jeecg-boot
Luogu p2089 roast chicken
电子书-CHM-上线CS
LeetCode 729. My schedule I
Engineering organisms containing artificial metalloenzymes perform unnatural biosynthesis
Customize the gateway filter factory on the specified route
The pit encountered by keil over the years
Use shortcut LNK online CS
云服务器 AccessKey 密钥泄露利用
Black cat takes you to learn UFS protocol Chapter 4: detailed explanation of UFS protocol stack
Cannot create poolableconnectionfactory (could not create connection to database server. error
如何将flv文件转为mp4文件?一个简单的解决办法