[21/08/25 KATA NINJA] leetcode #5 DP & subway transfer nums
DP
動的計画法は大きな問題を小さな問題に転化することである.Boottom Up方式小さい問題から始めて,大きな問題を解決する.
条件
1小さな問題の繰り返しであれば、
フィボナッチにとって,F(5)を求めるにはF(4)F(3),F(4)を求めるにはF(3),F(2)が必要である.小さな問題が繰り返される.
2ますます同じ問題は、求めるたびに答えが同じです.
memoization
計算された小さな問題は、その値が見つかる資料構造に保存されます.再計算を避けるために、キャッシュとコメントが完了しました.
TIP
最小の問題から考え始め,さらに法則を発見し,点火式を導出した.
Fibonacci
n番目の項目は、以前の項目で評価できます./**
* @param {number} n
* @return {number}
*/
var fib = function(n) {
let array = [...new Array(n+1)].map(()=>-1);
array[0] = 0;
array[1] = 1;
for(let check=2;check<=n;check++){
array[check] = array[check-1]+array[check-2];
}
return array[n];
};
Count Sorted Vowel Strings
/**
* @param {number} n
* @return {number}
*/
var countVowelStrings = function(n) {
let dp = [1,1,1,1,1];
for(let i=1;i<n;i++){
for(let j=0;j<dp.length;j++){
dp[j] = dp[j] + (dp[j-1] || 0);
}
}
return dp.reduce((a,b)=>a+b)
};
想像しがたい...
与えられたn−1回繰り返す.n−1を繰り返すと,dp配列は正しい答え配列を生成する.
図に示すように、現在の繰返し回数がiの場合、check−1回のdp[i]+check回のdp[i−1]がcheck回のdp[i]値となる.dp[i](check回の)＝dp[i](check-1回の)＋dp[i-1](check回の)
BFS
subway transfer nums
駅ごとにどの路線に乗り換えることができますか?
どのような路線にどの駅があるかは、因子で表します.
この2つの資料構造があれば,BFSで解くことができる.
タイムアウト
/**
* @param {number[][]} routes
* @param {number} source
* @param {number} target
* @return {number}
*/
var numBusesToDestination = function(routes, source, target) {
let flag = false;
routes.forEach((route)=>{
if(route.includes(source) && route.includes(target)){
flag = true;
}
})
if(flag) return source === target ? 0 : 1;
let answer = -1;
let busLine = {}
let queue = [];
let finish = [];
let visited = [];
routes.forEach((route,idx)=>{
visited[idx] = false;
route.forEach(sta=>{
if(busLine[sta]){
busLine[sta].push(idx);
}else{
busLine[sta] = [idx];
}
})
})
// bus번호로 호선 번호를 만듬
// 처음 시작 지점에서 탈 수 있는 호선들을 큐에 넣는다.
busLine[source].forEach(possible=>{
// 호선, 횟수, 갈아타는 버스 번호
queue.push([possible,0,source]);
})
while(queue.length !== 0){
// 호선 횟수 갈아타서 온 버스 번호를 받는다.
const [possibleIdx,ans,station] = queue.shift();
// 현재 호선 트루로 바꾼다.
visited[possibleIdx] = true;
// 현재 호선에서 갈 수 있는 버스 정류소 들을 알아둔다.
const possibleBusStops = routes[possibleIdx]
for(let i=0;i<possibleBusStops.length;i++){
// 버스정류소가 [1,2,7] 이면 1번 버스일 때 갈 수 있는 호선들을 받아둔다.
const possible = busLine[possibleBusStops[i]];
// 갈 수 있는 호선 체크
for(let j=0;j<possible.length;j++){
// 호선이다.
const line = possible[j];
// 이미 방문한 호선이면 큐에 넣지 않는다.
if(!visited[line]){
if(routes[line].includes(target)){
// 종료
return station === possibleBusStops[i] ? ans+1:ans+2;
}else{
// 큐에 푸시
queue.push([line,ans+1,possibleBusStops[i]]);
}
}
}
}
}
return answer;
};
スピードアップ
/**
* @param {number[][]} routes
* @param {number} source
* @param {number} target
* @return {number}
*/
var numBusesToDestination = function(routes, source, target) {
let flag = false;
routes.forEach((route)=>{
if(route.includes(source) && route.includes(target)){
flag = true;
}
})
if(flag) return source === target ? 0 : 1;
let answer = -1;
let busLine = {}
let queue = [];
let visited = [];
routes.forEach((route,idx)=>{
visited[idx] = false;
route.forEach(sta=>{
if(busLine[sta]){
busLine[sta].push(idx);
}else{
busLine[sta] = [idx];
}
})
})
busLine[source].forEach(possible=>{
visited[possible] = true;
queue.push([possible,0]);
})
while(queue.length !== 0){
const [갈수있는라인,ans] = queue.shift();
const 현재호선에서탈수있는버스 = routes[갈수있는라인]
for(let i=0;i<현재호선에서탈수있는버스.length;i++){
const 현재호선에서갈수있는호선 = busLine[현재호선에서탈수있는버스[i]];
for(let j=0;j<현재호선에서갈수있는호선.length;j++){
const line = 현재호선에서갈수있는호선[j];
if(!visited[line]){
if(routes[line].includes(target)){
// 만약 다음라인에 목적지 있다면 ans+2해주면된다. (버스를 타고 갈아타는 버스로 가서 또 도착버스까지 이동해야함)
// 갈아타는 버스가 목적지이게되면 이전에 이미 답이 도출되었다.
return ans+2;
}else{
visited[line] = true;
queue.push([line,ans+1]);
}
}
}
}
}
return answer;
};
diff
キューに入れてドアをたたく.これにより、キューに重複するノードが現れなくても、キューに入ることはありません.
Q出てきたときに部屋のドアを撮るとキューから終了する前に、重複するノードはすべてキューに入り、すべてのキューをナビゲートするのに長い時間がかかります....
busLine[source].forEach(possible=>{
visited[possible] = true; // <- diff
queue.push([possible,0]);
})
while(queue.length !== 0){
const [갈수있는라인,ans] = queue.shift();
const 현재호선에서탈수있는버스 = routes[갈수있는라인]
for(let i=0;i<현재호선에서탈수있는버스.length;i++){
const 현재호선에서갈수있는호선 = busLine[현재호선에서탈수있는버스[i]];
for(let j=0;j<현재호선에서갈수있는호선.length;j++){
const line = 현재호선에서갈수있는호선[j];
if(!visited[line]){
if(routes[line].includes(target)){
return ans+2;
}else{
visited[possible] = true; // <- diff
queue.push([line,ans+1]);
}
}
}
}
}
...
≪タイムアウト|Timeout|emdw≫:キューに表示されたときにアクセスが撮影されます(重複ノードがキューに入ります).
1105ミリ秒:BFS中にキューに入るのは、アクセスを撮影してキューに入れることです(最初にキューに入れる以外に、アクセスを撮影してキューに入ることもできます).
689ミリ秒:初めてキューに入れたときも、アクセスを撮ってキューに入れます.
Description
つまり、バスに乗れる弧を調べ、列に入れるということです.このため,2つの資料構造を構築した.一つは人字でroutesもう一つはバス番号-行ける弧で並ぶハッシュ資料構造です.
スタート地点から歩けるアークをゴールポストに入れる.この時はバス番号を入れなければなりません.
Reference
この問題について([21/08/25 KATA NINJA] leetcode #5 DP & subway transfer nums), 我々は、より多くの情報をここで見つけました
https://velog.io/@rat8397/210825-5-leetcode-DP-subway-transfer-nums
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
/**
* @param {number} n
* @return {number}
*/
var fib = function(n) {
let array = [...new Array(n+1)].map(()=>-1);
array[0] = 0;
array[1] = 1;
for(let check=2;check<=n;check++){
array[check] = array[check-1]+array[check-2];
}
return array[n];
};/**
* @param {number} n
* @return {number}
*/
var countVowelStrings = function(n) {
let dp = [1,1,1,1,1];
for(let i=1;i<n;i++){
for(let j=0;j<dp.length;j++){
dp[j] = dp[j] + (dp[j-1] || 0);
}
}
return dp.reduce((a,b)=>a+b)
};subway transfer nums
駅ごとにどの路線に乗り換えることができますか?
どのような路線にどの駅があるかは、因子で表します.
この2つの資料構造があれば,BFSで解くことができる.
タイムアウト
/**
* @param {number[][]} routes
* @param {number} source
* @param {number} target
* @return {number}
*/
var numBusesToDestination = function(routes, source, target) {
let flag = false;
routes.forEach((route)=>{
if(route.includes(source) && route.includes(target)){
flag = true;
}
})
if(flag) return source === target ? 0 : 1;
let answer = -1;
let busLine = {}
let queue = [];
let finish = [];
let visited = [];
routes.forEach((route,idx)=>{
visited[idx] = false;
route.forEach(sta=>{
if(busLine[sta]){
busLine[sta].push(idx);
}else{
busLine[sta] = [idx];
}
})
})
// bus번호로 호선 번호를 만듬
// 처음 시작 지점에서 탈 수 있는 호선들을 큐에 넣는다.
busLine[source].forEach(possible=>{
// 호선, 횟수, 갈아타는 버스 번호
queue.push([possible,0,source]);
})
while(queue.length !== 0){
// 호선 횟수 갈아타서 온 버스 번호를 받는다.
const [possibleIdx,ans,station] = queue.shift();
// 현재 호선 트루로 바꾼다.
visited[possibleIdx] = true;
// 현재 호선에서 갈 수 있는 버스 정류소 들을 알아둔다.
const possibleBusStops = routes[possibleIdx]
for(let i=0;i<possibleBusStops.length;i++){
// 버스정류소가 [1,2,7] 이면 1번 버스일 때 갈 수 있는 호선들을 받아둔다.
const possible = busLine[possibleBusStops[i]];
// 갈 수 있는 호선 체크
for(let j=0;j<possible.length;j++){
// 호선이다.
const line = possible[j];
// 이미 방문한 호선이면 큐에 넣지 않는다.
if(!visited[line]){
if(routes[line].includes(target)){
// 종료
return station === possibleBusStops[i] ? ans+1:ans+2;
}else{
// 큐에 푸시
queue.push([line,ans+1,possibleBusStops[i]]);
}
}
}
}
}
return answer;
};スピードアップ
/**
* @param {number[][]} routes
* @param {number} source
* @param {number} target
* @return {number}
*/
var numBusesToDestination = function(routes, source, target) {
let flag = false;
routes.forEach((route)=>{
if(route.includes(source) && route.includes(target)){
flag = true;
}
})
if(flag) return source === target ? 0 : 1;
let answer = -1;
let busLine = {}
let queue = [];
let visited = [];
routes.forEach((route,idx)=>{
visited[idx] = false;
route.forEach(sta=>{
if(busLine[sta]){
busLine[sta].push(idx);
}else{
busLine[sta] = [idx];
}
})
})
busLine[source].forEach(possible=>{
visited[possible] = true;
queue.push([possible,0]);
})
while(queue.length !== 0){
const [갈수있는라인,ans] = queue.shift();
const 현재호선에서탈수있는버스 = routes[갈수있는라인]
for(let i=0;i<현재호선에서탈수있는버스.length;i++){
const 현재호선에서갈수있는호선 = busLine[현재호선에서탈수있는버스[i]];
for(let j=0;j<현재호선에서갈수있는호선.length;j++){
const line = 현재호선에서갈수있는호선[j];
if(!visited[line]){
if(routes[line].includes(target)){
// 만약 다음라인에 목적지 있다면 ans+2해주면된다. (버스를 타고 갈아타는 버스로 가서 또 도착버스까지 이동해야함)
// 갈아타는 버스가 목적지이게되면 이전에 이미 답이 도출되었다.
return ans+2;
}else{
visited[line] = true;
queue.push([line,ans+1]);
}
}
}
}
}
return answer;
};diff
キューに入れてドアをたたく.これにより、キューに重複するノードが現れなくても、キューに入ることはありません.
Q出てきたときに部屋のドアを撮るとキューから終了する前に、重複するノードはすべてキューに入り、すべてのキューをナビゲートするのに長い時間がかかります.
...
busLine[source].forEach(possible=>{
visited[possible] = true; // <- diff
queue.push([possible,0]);
})
while(queue.length !== 0){
const [갈수있는라인,ans] = queue.shift();
const 현재호선에서탈수있는버스 = routes[갈수있는라인]
for(let i=0;i<현재호선에서탈수있는버스.length;i++){
const 현재호선에서갈수있는호선 = busLine[현재호선에서탈수있는버스[i]];
for(let j=0;j<현재호선에서갈수있는호선.length;j++){
const line = 현재호선에서갈수있는호선[j];
if(!visited[line]){
if(routes[line].includes(target)){
return ans+2;
}else{
visited[possible] = true; // <- diff
queue.push([line,ans+1]);
}
}
}
}
}
...1105ミリ秒:BFS中にキューに入るのは、アクセスを撮影してキューに入れることです(最初にキューに入れる以外に、アクセスを撮影してキューに入ることもできます).
689ミリ秒:初めてキューに入れたときも、アクセスを撮ってキューに入れます.
Description
つまり、バスに乗れる弧を調べ、列に入れるということです.このため,2つの資料構造を構築した.一つは人字で
routesもう一つはバス番号-行ける弧で並ぶハッシュ資料構造です.スタート地点から歩けるアークをゴールポストに入れる.この時はバス番号を入れなければなりません.
Reference
この問題について([21/08/25 KATA NINJA] leetcode #5 DP & subway transfer nums), 我々は、より多くの情報をここで見つけました https://velog.io/@rat8397/210825-5-leetcode-DP-subway-transfer-numsテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol