Най-бавно решение с Leetcode


Ниво на трудност Лесно
Често задавани в Амазонка
Array

Проблемът Slowest Key Leetcode Solution ни предоставя последователност от клавиши, които са били натиснати. Също така ни се дава масив или вектор на пускане на тези ключове. Последователността на ключовете е дадена под формата на низ. И така, проблемът ни помоли да намерим най-бавния ключ, който отнема най-много време за действие. Времето, необходимо на клавиша за действие или тип, е разликата във времето за освобождаване на текущия клавиш и предишния бутон, който е бил натиснат. В случай, че попаднем на два или повече клавиша, които отнемат едно и също време. Така че връщаме ключа, който е лексикографски най-голям. Преди да се потопите дълбоко в решението, нека първо разгледаме няколко примера.

Най-бавно решение с Leetcode

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

Обяснение: Времето, необходимо на всеки от клавишите, е 9, 20, 20, 1. Тези времена на освобождаване са съответно за клавишите c, b, c и d. Тъй като времената за освобождаване на клавишите b и c са еднакви. Връщаме лексикографски най-големия ключ, който е c.

Подход за най-бавното решение с Leetcode

Проблемът Slowest Key Leetcode Solution вече е описан по-горе. Накратко, проблемът ни помоли да намерим ключа, който отнема най-дългия тип, за да бъде изпълнен. В случай, че два или повече клавиша отнемат същото време за изпълнение. Тогава се изисква да върнем най-големия лексикографски ключ. За да разрешим проблема, ние просто преминаваме през натиснатите клавиши и оценяваме времето за освобождаване на всеки от клавишите. За първия ключ тя е равна на releaseTime [0], а след това е releaseTime [i] - releaseTime [i-1]. Така че запазваме две променливи, едната съхранява отговора, а другата съхранява времето, необходимо за изпълнение на този ключ.

Преминаваме през клавишите, като оценяваме времето за пускане на всеки от тях. Актуализираме отговора, когато намерим ключ, който или отнема повече време, или е лексикографски по-голям от текущия отговор и също отнема същото време, за да бъде изпълнен. В крайна сметка отговорът се връща на повикващата функция.

Код за най-бавно решение на Leetcode

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

Анализ на сложността

Сложност във времето

НА), тъй като е преминал през всички дадени ключове.

Сложност на пространството

O (1), защото използвахме само две допълнителни променливи за решаване на проблема.