Ամենադանդաղ բանալին Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon
Դասավորություն

Slowest Key Leetcode Solution- ի խնդիրը մեզ տալիս է սեղմված ստեղների հաջորդականություն: Մեզ նույնպես տրվում է ան դասավորություն կամ ժամանակի վեկտորը, երբ այս ստեղները թողարկվել են: Բանալիների հաջորդականությունը տրված է լարի տեսքով: Այսպիսով, խնդիրը մեզ խնդրեց գտնել ամենադանդաղ բանալին, որը գործելու համար ամենաերկար ժամանակն է պահանջում: Բանալին գործելու կամ մուտքագրելու համար պահանջվող ժամանակը ընթացիկ ստեղնաշարի և նախորդ սեղմածի բացման ժամանակների տարբերությունն է: Այն դեպքում, երբ բախվում ենք երկու կամ ավելի բանալիների, որոնք միաժամանակ ժամանակ են պահանջում: Այսպիսով, մենք վերադարձնում ենք այն բանալին, որը բառարանագրորեն ամենամեծն է: Նախքան լուծումը խորը սուզվելը, նախ նայենք մի քանի օրինակների:

Ամենադանդաղ բանալին Leetcode լուծում

releaseTimes = [9,29,49,50], keysPressed = "cbcd"
"c"

Բացատրություն. Բանալիներից յուրաքանչյուրի ժամանակը տևում է 9, 20, 20, 1. Այս թողարկման ժամանակները համապատասխանաբար c, b, c և d ստեղների համար են: Քանի որ b և c ստեղների թողարկման ժամկետները նույնն են: Մենք վերադարձնում ենք բառարանագրորեն ամենամեծ բանալին, որը գ է:

Մոտեցում դանդաղ հիմնական ստեղնաշարի լուծման համար

Խնդիրն ամենադանդաղ բանալին կոճակի լուծման համար արդեն նկարագրված է վերևում: Կարճ ասած, խնդիրը մեզ խնդրել է գտնել այն բանալին, որը կատարման համար ամենաերկարատև տեսակն է պահանջում: Եթե ​​այդ դեպքում երկու կամ ավելի բանալիներ կատարում են նույն ժամանակը: Հետո մեզանից պահանջվում է վերադարձնել բառարանագրորեն ամենամեծ բանալին: Խնդիրը լուծելու համար մենք ուղղակի անցնում ենք սեղմված ստեղների վրայով և գնահատում ստեղներից յուրաքանչյուրի թողարկման ժամանակը: Առաջին ստեղնի համար այն հավասար է թողարկման [ամանակին [0], այնուհետև այն արձակում է Tամանակը [i] - թողարկման [ամանակը [i-1]: Այսպիսով, մենք պահում ենք երկու փոփոխական, մեկը պահում է պատասխանը, իսկ մյուսը պահում է այդ բանալին կատարելու ժամանակը:

Մենք անցնում ենք ստեղներով, գնահատելով դրանցից յուրաքանչյուրի թողարկման ժամանակը: Մենք թարմացնում ենք պատասխանը, երբ գտնում ենք մի բանալի, որը կա՛մ ավելի երկար է տևում, կա՛մ բառարանագրորեն ավելի մեծ է, քան ընթացիկ պատասխանը, և նույն ժամանակն է պահանջում կատարման համար: Վերջում պատասխանը վերադարձվում է զանգահարող գործառույթին:

Կոդը ամենադանդաղ բանալին տողային լուծման համար

C ++ ծածկագիր

#include <bits/stdc++.h>
using namespace std;

char slowestKey(vector<int>& releaseTimes, string keysPressed) {
    int time = releaseTimes[0];
    char ans = keysPressed[0];
    for(int i=1;i<keysPressed.length();i++){
        int cur_time = releaseTimes[i] - releaseTimes[i-1];
        if(cur_time >= time){
            if(cur_time > time)
                ans = keysPressed[i], time = cur_time;
            else
                ans = max(ans, keysPressed[i]);
        }
    }
    return ans;
}

int main(){
    vector<int> releaseTimes = {9, 29, 49, 50};
    string keysPressed = "cbcd";
    cout<<slowestKey(releaseTimes, keysPressed);
}
c

Java կոդ

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
  public static char slowestKey(int[] releaseTimes, String keysPressed) {
        int time = releaseTimes[0];
        char ans = keysPressed.charAt(0);
        for(int i=1;i<keysPressed.length();i++){
            int cur_time = releaseTimes[i] - releaseTimes[i-1];
            if(cur_time >= time){
                if(cur_time > time){
                    ans = keysPressed.charAt(i);
                    time = cur_time;
                }
                else
                    ans = ans > keysPressed.charAt(i) ? ans : keysPressed.charAt(i);
            }
        }
        return ans;
    }
 
  public static void main (String[] args) throws java.lang.Exception {
    int[] releaseTimes = {9, 29, 49, 50};
      String keysPressed = "cbcd";
      System.out.print(slowestKey(releaseTimes, keysPressed));
  }
}
c

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ տրված բոլոր ստեղների վրայով անցել են:

Տիեզերական բարդություն

O (1), քանի որ մենք խնդրի լուծման համար օգտագործեցինք ընդամենը երկու լրացուցիչ փոփոխական: