当前位置:网站首页>Leetcode daily question (1997. first day where you have been in all the rooms)
Leetcode daily question (1997. first day where you have been in all the rooms)
2022-07-06 06:35: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
This problem seems to have been done before , It may just be similar , But I have no impression at all
The questions I have done recently are cheap , The difficulty is not in solving problems , All in various details
hypothesis dp[i][odd] For an odd number of times into the i Steps required for a room , dp[i][even] Enter the... For an even number of times i Steps required for a room , Then we can push down the following two ;
dp[i][odd] = dp[i-1][even] + 1
dp[i][even] = dp[i][odd] + (dp[i][odd]-dp[k][odd]) + 1
among k = next_visit[i]
The first of these two is easy to understand , Only after Ou enters a room several times can he push back into a room . The second actual expression is , Enter the third even number of times i The premise of a room must be an odd number of times , Because it is an odd number of entries, we need to return to a certain point in front , Be careful , The title says to return to next_visit[i] Any point before , But what we want is the minimum distance , According to the rules of the topic , The farther the point we return from the current point , The number of steps we need to go back to the current point must be more , So don't worry , The return point we choose must be next_visit[i], So we walked again from next_visit[i] To i Distance of , So is dp[i][odd] - dp[k][odd] + 1. The whole calculation process needs attention , Because the results are done mod Operational , So there may be dp[i][odd] < dp[k][odd] The situation of , At this time, the result is negative , To avoid this situation, you can 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
}
}
边栏推荐
- 基於JEECG-BOOT的list頁面的地址欄參數傳遞
- Py06 字典 映射 字典嵌套 键不存在测试 键排序
- How to do a good job in financial literature translation?
- 利用快捷方式-LNK-上线CS
- LeetCode每日一题(1997. First Day Where You Have Been in All the Rooms)
- Mise en œuvre d’une fonction complexe d’ajout, de suppression et de modification basée sur jeecg - boot
- CS certificate fingerprint modification
- 翻译公司证件盖章的价格是多少
- How to convert flv file to MP4 file? A simple solution
- 如何做好金融文献翻译?
猜你喜欢
翻译影视剧字幕,这些特点务必要了解
翻译生物医学说明书,英译中怎样效果佳
Summary of leetcode's dynamic programming 4
The whole process realizes the single sign on function and the solution of "canceltoken" of undefined when the request is canceled
金融德语翻译,北京专业的翻译公司
How much is the price for the seal of the certificate
LeetCode 739. Daily temperature
[mqtt from getting started to improving series | 01] quickly build an mqtt test environment from 0 to 1
生物医学本地化翻译服务
Chinese English comparison: you can do this Best of luck
随机推荐
模拟卷Leetcode【普通】1062. 最长重复子串
模拟卷Leetcode【普通】1219. 黄金矿工
Simulation volume leetcode [general] 1218 Longest definite difference subsequence
Traffic encryption of red blue confrontation (OpenSSL encrypted transmission, MSF traffic encryption, CS modifying profile for traffic encryption)
LeetCode每日一题(1997. First Day Where You Have Been in All the Rooms)
Luogu p2089 roast chicken
Today's summer solstice
What are the commonly used English words and sentences about COVID-19?
keil MDK中删除添加到watch1中的变量
SSO流程分析
Wish Dragon Boat Festival is happy
国际经贸合同翻译 中译英怎样效果好
Selenium source code read through · 9 | desiredcapabilities class analysis
oscp raven2靶机渗透过程
What are the characteristics of trademark translation and how to translate it?
Delete the variables added to watch1 in keil MDK
Office-DOC加载宏-上线CS
国产游戏国际化离不开专业的翻译公司
[ 英语 ] 语法重塑 之 英语学习的核心框架 —— 英语兔学习笔记(1)
A 27-year-old without a diploma, wants to work hard on self-study programming, and has the opportunity to become a programmer?