Αργότερη λύση Leetcode Key  


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα
αλγόριθμοι Παράταξη κωδικοποίησης συνέντευξη συνέντευξηprep LeetCode LeetCodeSolutions

Το πρόβλημα Slowest Key Leetcode Solution μας παρέχει μια ακολουθία πλήκτρων που έχουν πατηθεί. Μας δίνεται επίσης ένα παράταξη ή διάνυσμα των χρόνων που έχουν κυκλοφορήσει αυτά τα κλειδιά. Η ακολουθία των κλειδιών δίνεται με τη μορφή μιας συμβολοσειράς. Έτσι, το πρόβλημα μας ζήτησε να βρούμε το πιο αργό κλειδί, το οποίο διαρκεί περισσότερο χρόνο για να δράσουμε. Ο χρόνος που χρειάζεται το πλήκτρο για να ενεργήσει ή να πληκτρολογήσει είναι η διαφορά των χρόνων απελευθέρωσης για το τρέχον πλήκτρο και το προηγούμενο πλήκτρο που έχει πατηθεί. Σε περίπτωση που συναντήσουμε δύο ή περισσότερα πλήκτρα που χρειάζονται τον ίδιο χρόνο. Γι 'αυτό επιστρέφουμε το κλειδί που είναι λεξικογραφικά μεγαλύτερο. Πριν βυθίσουμε βαθιά τη λύση, ας ρίξουμε πρώτα μια ματιά σε μερικά παραδείγματα.

Αργότερη λύση Leetcode KeyΚαρφώστε

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

Επεξήγηση: Ο χρόνος που απαιτείται για κάθε ένα από τα πλήκτρα είναι 9, 20, 20, 1. Αυτοί οι χρόνοι απελευθέρωσης είναι για τα πλήκτρα c, b, c και d αντίστοιχα. Δεδομένου ότι οι χρόνοι έκδοσης για τα πλήκτρα b και c είναι οι ίδιοι. Επιστρέφουμε το λεξικογραφικά μεγαλύτερο κλειδί που είναι γ.

Προσέγγιση για την πιο αργή λύση Leetcode Key  

Το πρόβλημα Slowest Key Leetcode Solution έχει ήδη περιγραφεί παραπάνω. Εν συντομία, το πρόβλημα μας ζήτησε να βρούμε το κλειδί που χρειάζεται τον πιο μακρύ τύπο για εκτέλεση. Εάν σε περίπτωση, δύο ή περισσότερα πλήκτρα χρειάζονται τον ίδιο χρόνο εκτέλεσης. Τότε απαιτείται να επιστρέψουμε το λεξικογραφικά μεγαλύτερο κλειδί. Για να λύσουμε το πρόβλημα, διασχίζουμε απλά τα πλήκτρα που πατάμε και αξιολογούμε το χρόνο απελευθέρωσης για κάθε ένα από τα πλήκτρα. Για το πρώτο κλειδί είναι ίσο με το ReleaseTime [0] και μετά είναι το ReleaseTime [i] - releaseTime [i-1]. Διατηρούμε λοιπόν δύο μεταβλητές, η μία αποθηκεύει την απάντηση και η άλλη αποθηκεύει τον χρόνο που απαιτείται για την εκτέλεση αυτού του κλειδιού.

Βλέπε επίσης
Βρείτε αν ένα υπόγειο έχει τη μορφή ενός βουνού ή όχι

Διασχίζουμε τα πλήκτρα, αξιολογώντας τον χρόνο κυκλοφορίας για καθένα από αυτά. Ενημερώνουμε την απάντηση όταν βρίσκουμε ένα κλειδί που είτε χρειάζεται περισσότερο χρόνο ή είναι λεξικογραφικά μεγαλύτερο από την τρέχουσα απάντηση και επίσης χρειάζεται τον ίδιο χρόνο για να εκτελεστεί. Στο τέλος, η απάντηση επιστρέφεται στη λειτουργία κλήσης.

Κωδικός για πιο αργή λύση Leetcode Key  

Κωδικός 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), γιατί χρησιμοποιήσαμε μόνο δύο επιπλέον μεταβλητές για να λύσουμε το πρόβλημα.

1