Leetcode-ийн хамгийн удаан шийдэл


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны
Array

Slowest Key Leetcode Solution гэсэн асуудал нь дарагдсан товчнуудын дарааллыг бидэнд өгдөг. Бидэнд мөн массив эсвэл эдгээр товчлуурууд гарсан хугацааны вектор. Түлхүүрүүдийн дарааллыг мөр хэлбэрээр өгдөг. Тиймээс асуудал нь биднээс хамгийн удаан ажиллахад хамгийн удаан түлхүүр олохыг хүссэн юм. Түлхүүрийг ажиллуулах эсвэл бичихэд зарцуулсан хугацаа нь одоогийн болон өмнөх дарагдсан товчлуурын суллах хугацааны зөрүү юм. Хэрэв бид ижил цаг хугацаа шаардагдах хоёр буюу түүнээс дээш түлхүүртэй таарвал. Тиймээс бид толь бичиг зүйн хувьд хамгийн том түлхүүрийг буцааж өгдөг. Шийдлийн гүн рүү шумбахаасаа өмнө эхлээд хэдэн жишээг авч үзье.

Leetcode-ийн хамгийн удаан шийдэл

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

Тайлбар: Түлхүүр тус бүрийн зарцуулсан хугацаа 9, 20, 20, 1. Эдгээр суллах хугацаа нь c, b, c, d товчлууруудад зориулагдсан болно. B ба 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 (N), Учир нь өгөгдсөн бүх түлхүүрүүдээр дамжин өнгөрөв.

Сансрын нарийн төвөгтэй байдал

O (1), Учир нь бид асуудлыг шийдвэрлэхийн тулд зөвхөн хоёр нэмэлт хувьсагч ашигласан болно.