மெதுவான விசை லீட்கோட் தீர்வு


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான்
அணி

மெதுவான விசை லீட்கோட் தீர்வு சிக்கல் அழுத்தும் விசைகளின் வரிசையை நமக்கு வழங்குகிறது. எங்களுக்கும் ஒரு வழங்கப்படுகிறது வரிசை அல்லது இந்த விசைகள் வெளியிடப்பட்ட நேரங்களின் திசையன். விசைகளின் வரிசை ஒரு சரம் வடிவில் கொடுக்கப்பட்டுள்ளது. எனவே, சிக்கல் மெதுவான விசையை கண்டுபிடிக்கும்படி எங்களிடம் கேட்டது, இது செயல்பட அதிக நேரம் எடுக்கும். செயல்பட அல்லது தட்டச்சு செய்ய விசையால் எடுக்கப்பட்ட நேரம் தற்போதைய விசையின் வெளியீட்டு நேரங்களின் வித்தியாசம் மற்றும் அழுத்தப்பட்ட முந்தைய விசை. ஒரே நேரத்தில் இரண்டு அல்லது அதற்கு மேற்பட்ட விசைகளை நாங்கள் கண்டால். எனவே, அகராதி ரீதியாக மிகப் பெரிய விசையை நாங்கள் திருப்பித் தருகிறோம். தீர்வுக்கு ஆழமாக டைவ் செய்வதற்கு முன், முதலில் சில எடுத்துக்காட்டுகளைப் பார்ப்போம்.

மெதுவான விசை லீட்கோட் தீர்வு

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

விளக்கம்: ஒவ்வொரு விசையும் எடுக்கும் நேரம் 9, 20, 20, 1. இந்த வெளியீட்டு நேரங்கள் முறையே சி, பி, சி மற்றும் டி விசைகளுக்கு. விசைகள் b மற்றும் c க்கான வெளியீட்டு நேரங்கள் ஒரே மாதிரியாக இருப்பதால். சி என்ற சொற்பொருளியல் ரீதியாக மிகப்பெரிய விசையை நாங்கள் திருப்பித் தருகிறோம்.

மெதுவான விசை லீட்கோட் தீர்வுக்கான அணுகுமுறை

மெதுவான விசை லீட்கோட் தீர்வு ஏற்கனவே மேலே விவரிக்கப்பட்டுள்ளது. சுருக்கமாக, செயல்படுத்தப்படுவதற்கு மிக நீண்ட வகையை எடுக்கும் விசையை கண்டுபிடிக்க சிக்கல் எங்களிடம் கேட்டுள்ளது. வழக்கில், இரண்டு அல்லது அதற்கு மேற்பட்ட விசைகள் இயக்க ஒரே நேரத்தை எடுக்கும். பின்னர் நாம் அகராதி ரீதியாக மிகப் பெரிய விசையைத் திருப்பித் தர வேண்டும். சிக்கலைத் தீர்க்க, அழுத்தும் விசைகள் மீது நாம் பயணித்து, ஒவ்வொரு விசையின் வெளியீட்டு நேரத்தையும் மதிப்பீடு செய்கிறோம். முதல் விசைக்கு இது வெளியீட்டு நேரத்திற்கு சமம் [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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்), ஏனெனில் கொடுக்கப்பட்ட அனைத்து விசைகளிலும் பயணிக்கிறது.

விண்வெளி சிக்கலானது

ஓ (1), ஏனெனில் சிக்கலைத் தீர்க்க இரண்டு கூடுதல் மாறிகள் மட்டுமே பயன்படுத்தினோம்.