Најспоро клучно решение за леткод


Ниво на тешкотија Лесно
Често прашувано во Амазон
Низа

Проблемот Slowest Key Leetcode Solution ни обезбедува низа клучеви што биле притиснати. Ние исто така ни е даден низа или вектор на пати кога овие копчиња се ослободени. Редоследот на копчињата е даден во форма на низа. Значи, проблемот побара од нас да го најдеме најбавниот клуч, за кој е потребно најдолго време да се делува. Времето потребно за клуч да дејствува или да напише е разликата во времето на ослободување на тековниот и претходниот копче што е притиснато. Во случај да наидеме на две или повеќе клучеви за кои е потребно исто време. Значи, го враќаме клучот што е лексикографски најголем. Пред да се нурнете длабоко во решението, ајде прво да погледнеме неколку примери.

Најспоро клучно решение за леткод

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

Објаснување: Времето потребно за секое од копчињата е 9, 20, 20, 1. Овие времиња на ослободување се однесуваат на копчињата c, b, c и d, соодветно. Бидејќи времињата на ослободување на копчињата b и c се исти. Го враќаме лексикографски најголемиот клуч што е в.

Пристап за најспоро клучно решение за леткод

Проблемот Најспоро клучно решение за леткод веќе е опишан погоре. Накратко, проблемот побара од нас да го најдеме клучот што трае најдолго за да се изврши. Ако во случај, на две или повеќе копчиња им е потребно исто време да се извршат. Тогаш од нас се бара да го вратиме лексикографски најголемиот клуч. За да го решиме проблемот, ние едноставно поминуваме низ притиснатите копчиња и го проценуваме времето на ослободување за секое од копчињата. За првиот клуч е еднакво на releaseTime [0], а потоа е ReleaseTime [i] - ReleaseTime [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

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

Временска комплексност

НА), бидејќи се премина преку сите дадени клучеви.

Комплексноста на просторот

О (1), затоа што искористивме само две дополнителни променливи за да го решиме проблемот.