Сызыктарды эң кичинекей символ Leetcode чечиминин жыштыгы менен салыштырыңыз


Кыйынчылык деңгээли жеңил
Көп суралган Гугл Oracle
согуштук тизме аркан

Leetcode Чечиминин Жыштыгын Жыштык менен Салыштырыңыз деген көйгөй, бош (F) функциясын аныктайбыз аркан s, f (s) саптагы эң кичинекей белгинин жыштыгына барабар. Андан кийин бизге бир нече сөздөр жана айрым суроолор берилет. ар бир суроо үчүн, бизден f (сөздөр)> f (query_word) сыяктуу сөздөрдүн санын табуу талап кылынат. Андан кийин бардык суроолордун жообун вектор же массив катары кайтарып беришибиз керек. Ошентип, чечимге терең сүңгөөрдөн мурун, бир нече мисалдарды карап көрөлү.

queries = ["cbd"], words = ["zaaaz"]
[1]

Түшүндүрмө: f (“заааз”) = 3, анткени эң кичинекей тамга “а” жыштыгы 3кө барабар, ал эми f (“cbd”) = 1. Демек, бизде f (i) бар бир гана сөз бар )> f (query_word).

Сызыктарды эң кичинекей символ Leetcode чечиминин жыштыгы менен салыштырыңыз

queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
[1,2]

Түшүндүрмө: Ошентип, берилген сөздөрдүн бардыгы үчүн аныкталган функциянын мааниси эсептелгенден кийин. F ("a") = 1, f ("aa") = 2, f ("aaa") = 3, f ("aaaa") = 4. табабыз, анда берилген сөздөр үчүн функциянын маанисин баалагандан кийин сурамдар, биз f ("bbb") = 3, f ("cc") = 2. деп табабыз, ошондо f ("bbb") сөзү үчүн функциянын маанисине ээ болгон жалгыз "aaaa" сөзү бар 3. Ушул сыяктуу эле, "cc" сөзү үчүн функциянын мааниси чоңураак "aaa", "aaaa" деген сөздөр бар.

Leetcode эритмесинин жыштыгын жиптер менен салыштыруу ыкмасы

Эң кичинекей символдун жыштыгын жыштык менен салыштырып көрүңүз Leetcode Solution, сурам сөзү үчүн функциянын маанисинен чоңураак аныкталган функция үчүн мааниге ээ болгон сөздөрдүн санын табууну суранат. Бош эмес саптар боюнча аныкталган f (s) функциясы саптагы эң кичинекей белгинин жыштыгына барабар. Ошентип, биринчиден, биз бардык суроо сөздөр үчүн функциянын маанисин табабыз. Бардык кирген сөздөр үчүн биз дагы ушундай кылабыз. Ошондой эле, функциянын мааниси i ге барабар сөздөрдүн санын сактай турган кошумча массивди түзөбүз. Бул массив суроолордун жоопторун туруктуу убакытта табууга жардам берет. Массивдин ар бир индекси = i функционалдык мааниси бар сөздөрдүн санын билдирет.

Функциянын маанисин баалап, аларды убактылуу массивибизде сактагандан кийин. Убактылуу массивдин суффиксин алабыз, эми ар бир индексте функциянын мааниси иден чоң же барабар болгон сөздөрдүн жалпы саны сакталат. Эми биз ар бир суроо боюнча жоопту массивде же вектордо сактап, аны кайтарып беребиз.

Leetcode Чечиминин Эң Чакан Символунун Жыштыгы боюнча Саптарды Салыштырууга Кодекс

C ++ коду

#include <bits/stdc++.h>
using namespace std;

vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
    vector<int> q;
    for(auto x: queries){
        int f[26] = {0};
        int mn = 26;
        for(auto y: x){
            f[y-'a']++;
            mn = min(mn, y-'a');
        }
        q.push_back(f[mn]);
    }

    int fr[12];memset(fr, 0, sizeof fr);
    for(auto x: words){
        int f[26] = {0};
        int mn = 26;
        for(auto y: x){
            f[y-'a']++;
            mn = min(mn, y-'a');
        }
        fr[f[mn]]++;
    }
    for(int i=9;i>=0;i--)
        fr[i] += fr[i+1];
    vector<int> ans;
    for(auto x: q){
        ans.push_back(fr[x+1]);
    }
    return ans;
}

int main(){
    vector<string> queries = {"bbb","cc"};
    vector<string> words = {"a","aa","aaa","aaaa"};

    vector<int> answer = numSmallerByFrequency(queries, words);
    for(auto x: answer)
        cout<<x<<" ";
}
1 2

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    public static int[] numSmallerByFrequency(String[] queries, String[] words) {
        ArrayList<Integer> q = new ArrayList<Integer>();
        for(String x: queries){
            int[] f = new int[26];
            for(int i=0;i<26;i++)
                f[i] = 0;
            int mn = 26;
            int sz = x.length();
            for(int i=0;i<sz;i++){
                int y = x.charAt(i);
                f[y-'a']++;
                mn = Math.min(mn, y-'a');
            }
            q.add(f[mn]);
        }
 
        int[] fr = new int[12];
        for(int i=0;i<12;i++)
            fr[i] = 0;
        for(String x: words){
            int[] f = new int[26];
            for(int i=0;i<26;i++)
                f[i] = 0;
            int mn = 26;
            int sz = x.length();
            for(int i=0;i<sz;i++){
                int y = x.charAt(i);
                f[y-'a']++;
                mn = Math.min(mn, y-'a');
            }
            fr[f[mn]]++;
        }
        for(int i=9;i>=0;i--)
            fr[i] += fr[i+1];
        int[] ans = new int[queries.length];
        for(int i=0;i<q.size();i++){
            ans[i] = (fr[q.get(i)+1]);
        }
        return ans;
    }
 
  public static void main (String[] args) throws java.lang.Exception
  {
    String[] queries = {"bbb","cc"};
      String[] words = {"a","aa","aaa","aaaa"};
 
      int[] answer = numSmallerByFrequency(queries, words);
      for(int x: answer)
          System.out.print(x+" ");
  }
}
1 2

Комплекстик анализ

Убакыт татаалдыгы

O (Q + N), анткени биз бардык сөздөр үчүн функциянын маанисин эсептешибиз керек жана сөздөрдүн узундугу да 10го барабар же барабар. Ошентип, убакыттын татаалдыгы сызыктуу.

Космостун татаалдыгы

O (Q), биз жоопту сактоо үчүн массивди жана убактылуу колдонуу үчүн 10 өлчөмүндөгү кошумча массивди жаратабыз. Космостун татаалдыгы дагы сызыктуу.