മന്ദഗതിയിലുള്ള കീ ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ
അറേ

സ്ലോവസ്റ്റ് കീ ലീറ്റ്കോഡ് സൊല്യൂഷൻ അമർത്തിയ കീകളുടെ ഒരു ശ്രേണി ഞങ്ങൾക്ക് നൽകുന്നു. ഞങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ട് ശ്രേണി അല്ലെങ്കിൽ ഈ കീകൾ എത്ര തവണ വെക്റ്റർ ചെയ്തു. കീകളുടെ ശ്രേണി ഒരു സ്ട്രിംഗിന്റെ രൂപത്തിൽ നൽകിയിരിക്കുന്നു. അതിനാൽ, വേഗത കുറഞ്ഞ കീ കണ്ടെത്താൻ പ്രശ്നം ഞങ്ങളോട് ആവശ്യപ്പെട്ടു, ഇത് പ്രവർത്തിക്കാൻ ഏറ്റവും കൂടുതൽ സമയം എടുക്കും. പ്രവർത്തിക്കാനോ ടൈപ്പുചെയ്യാനോ കീ എടുത്ത സമയം നിലവിലെ കീയുടെയും മുമ്പത്തെ കീയുടെയും റിലീസ് സമയങ്ങളുടെ വ്യത്യാസമാണ്. ഒരേ സമയം എടുക്കുന്ന രണ്ടോ അതിലധികമോ കീകൾ ഞങ്ങൾ കണ്ടാൽ. അതിനാൽ, നിഘണ്ടുവിൽ ഏറ്റവും വലിയ കീ ഞങ്ങൾ നൽകുന്നു. പരിഹാരത്തിലേക്ക് ആഴത്തിൽ പ്രവേശിക്കുന്നതിനുമുമ്പ്, ആദ്യം നമുക്ക് കുറച്ച് ഉദാഹരണങ്ങൾ നോക്കാം.

മന്ദഗതിയിലുള്ള കീ ലീറ്റ്കോഡ് പരിഹാരം

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

വിശദീകരണം: ഓരോ കീകളും എടുക്കുന്ന സമയം 9, 20, 20, 1. ഈ റിലീസ് സമയങ്ങൾ യഥാക്രമം സി, ബി, സി, ഡി എന്നീ കീകൾക്കാണ്. ബി, സി കീകളുടെ റിലീസ് സമയം ഒന്നുതന്നെയാണ്. നിഘണ്ടുവിൽ ഏറ്റവും വലിയ കീ ഞങ്ങൾ നൽകുന്നു.

വേഗത കുറഞ്ഞ കീ ലീറ്റ്കോഡ് പരിഹാരത്തിനായുള്ള സമീപനം

സ്ലോവസ്റ്റ് കീ ലീറ്റ്കോഡ് പരിഹാരം പ്രശ്നം ഇതിനകം മുകളിൽ വിശദീകരിച്ചിട്ടുണ്ട്. ചുരുക്കത്തിൽ, എക്സിക്യൂട്ട് ചെയ്യുന്നതിന് ദൈർഘ്യമേറിയ തരം എടുക്കുന്ന കീ കണ്ടെത്താൻ പ്രശ്നം ഞങ്ങളോട് ആവശ്യപ്പെട്ടു. അങ്ങനെയാണെങ്കിൽ, രണ്ടോ അതിലധികമോ കീകൾ എക്സിക്യൂട്ട് ചെയ്യുന്നതിന് ഒരേ സമയം എടുക്കും. അതിനുശേഷം ഞങ്ങൾ നിഘണ്ടുവിൽ ഏറ്റവും വലിയ കീ തിരികെ നൽകേണ്ടതുണ്ട്. പ്രശ്നം പരിഹരിക്കുന്നതിന്, ഞങ്ങൾ അമർത്തിയ കീകളിലൂടെ സഞ്ചരിച്ച് ഓരോ കീകളുടെയും റിലീസ് സമയം വിലയിരുത്തുന്നു. ആദ്യ കീയ്‌ക്ക് ഇത് റിലീസ്ടൈമിന് തുല്യമാണ് [0], തുടർന്ന് അത് റിലീസ്ടൈം [i] - റിലീസ്ടൈം [i-1]. അതിനാൽ ഞങ്ങൾ രണ്ട് വേരിയബിളുകൾ സൂക്ഷിക്കുന്നു, ഒന്ന് ഉത്തരം സംഭരിക്കുന്നു, മറ്റൊന്ന് ആ കീ എക്സിക്യൂട്ട് ചെയ്യാൻ എടുക്കുന്ന സമയം സംഭരിക്കുന്നു.

ഓരോന്നിനും റിലീസ് സമയം വിലയിരുത്തി ഞങ്ങൾ കീകളിലൂടെ സഞ്ചരിക്കുന്നു. നിലവിലെ ഉത്തരത്തേക്കാൾ കൂടുതൽ സമയമെടുക്കുന്നതോ നിഘണ്ടുവിൽ വലുതോ ആയ ഒരു കീ കണ്ടെത്തുമ്പോൾ ഞങ്ങൾ ഉത്തരം അപ്‌ഡേറ്റുചെയ്യുന്നു, ഒപ്പം എക്സിക്യൂട്ട് ചെയ്യുന്നതിന് ഒരേ സമയം എടുക്കും. അവസാനം, ഉത്തരം കോളിംഗ് ഫംഗ്ഷനിലേക്ക് തിരികെ നൽകും.

വേഗത കുറഞ്ഞ കീ ലീറ്റ്കോഡ് പരിഹാരത്തിനുള്ള കോഡ്

സി ++ കോഡ്

#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

ജാവ കോഡ്

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 (N), കാരണം തന്നിരിക്കുന്ന എല്ലാ കീകളിലൂടെയും സഞ്ചരിക്കുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), കാരണം പ്രശ്നം പരിഹരിക്കാൻ ഞങ്ങൾ രണ്ട് അധിക വേരിയബിളുകൾ മാത്രമാണ് ഉപയോഗിച്ചത്.