Leetcode шийдлийн хамгийн бага тэмдэгтийн давтамжаар мөрүүдийг харьцуул


Хэцүү байдлын түвшин Easy
Байнга асуудаг Google-ийн Oracle-ийн
Array String

Leetcode шийдлийн мөрүүдийг давтамжаар харьцуулах асуудал нь бид f (s) функцийг хоосон биш тодорхойлдог мөр 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 шийдлийн тэмдэгт мөрийг давтамжаар харьцуулах асуудал нь оролтоос тодорхойлсон функцын утга, асуулгад зориулагдсан функцын утгаас их утгатай үгсийн тоог олохыг хүсдэг. Хоосон биш мөр дээр тодорхойлогдсон f (s) функц нь мөрийн хамгийн бага тэмдэгтийн давтамжтай тэнцүү байна. Тиймээс, эхлээд бүх асуултын үгсийн функцийн утгыг олно. Оруулсан бүх үгсийн хувьд бид ижил зүйлийг хийдэг. Мөн i-тэй тэнцүү функцийн утгатай үгсийн тоог хадгалдаг нэмэлт массив үүсгэдэг. Энэ массив нь асуултын хариуг тогтмол хугацаанд олоход тусална. Массивын i индекс бүр = 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 код

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 хэмжээтэй нэмэлт массив үүсгэдэг. Сансрын нарийн төвөгтэй байдал нь мөн шугаман юм.