Самое медленное ключевое решение Leetcode


Сложный уровень Легко
Часто спрашивают в Амазонка
массив

Проблема Slowest Key Leetcode Solution предоставляет нам последовательность нажатых клавиш. Нам также дается массив или вектор отпускания этих ключей. Последовательность ключей дана в виде строки. Итак, задача попросила нас найти самую медленную клавишу, на срабатывание которой уходит больше всего времени. Время, затрачиваемое клавишей на действие или ввод, - это разница времен отпускания текущей клавиши и предыдущей нажатой клавиши. В случае, если мы встретим два или более ключа, которые занимают одно и то же время. Итак, мы возвращаем ключ, который является лексикографически самым большим. Прежде чем углубиться в решение, давайте сначала рассмотрим несколько примеров.

Самое медленное ключевое решение Leetcode

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

Объяснение: Время отпускания каждой из клавиш составляет 9, 20, 20, 1. Это время отпускания для клавиш c, b, c и d соответственно. Поскольку времена отпускания клавиш b и c одинаковы. Мы возвращаем лексикографически наибольший ключ, то есть 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

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

Сложность времени

НА), потому что прошел по всем заданным ключам.

Космическая сложность

О (1), потому что мы использовали только две дополнительные переменные для решения проблемы.