最慢的密鑰Leetcode解決方案


難度級別 容易獎學金
經常問 亞馬遜
排列

最慢的鍵Leetcode解決方案問題為我們提供了一系列已被按下的鍵。 我們還得到了 排列 或釋放這些鍵的時間向量。 鍵序列以字符串形式給出。 因此,問題要求我們找到最慢的密鑰,這需要最長的時間才能採取行動。 按鍵動作或鍵入所花費的時間是當前按鍵和已按下的上一個按鍵的釋放時間之差。 如果我們碰到兩個或更多的鍵需要花費相同的時間。 因此,我們返回了字典上最大的密鑰。 在深入研究解決方案之前,讓我們先來看一些示例。

最慢的密鑰Leetcode解決方案

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

說明:每個鍵花費的時間分別為9、20、20、1。這些釋放時間分別對應於鍵c,b,c和d。 由於鍵b和c的釋放時間相同。 我們返回字典上最大的鍵c。

最慢的密鑰Leetcode解決方案的方法

上面已經描述了最慢鍵Leetcode解決方案的問題。 簡而言之,該問題已要求我們找到執行時間最長的鍵。 如果出現這種情況,則兩個或多個鍵需要花費相同的時間來執行。 然後,我們需要返回字典上最大的鍵。 為了解決該問題,我們只需遍歷按下的鍵並評估每個鍵的釋放時間即可。 對於第一個鍵,它等於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(1), 因為我們只使用了兩個額外的變量來解決問題。