Сравнете низовете по честота на най-малкия разтвор на Leetcode


Ниво на трудност Лесно
Често задавани в Google Оракул
Array Низ

Проблемът Сравни низовете по честота на най-малкия символ Leetcode Solution, гласи, че дефинираме функция f (s) над непразна низ s такова, че f (s) е равно на честотата на най-малкия символ в низа. След това ни се дават някои думи и някои запитвания. за всяка заявка се изисква да намерим броя на думите, така че f (думи)> f (query_word). След това трябва да върнем отговора за всички заявки като вектор или масив. Така че, преди да се потопите дълбоко в решението, нека разгледаме няколко примера.

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

Обяснение: f („zaaaz“) = 3, тъй като най-малкият знак е „a“, който има честота, равна на 3, докато f („cbd“) = 1. И така, имаме само една дума, която има f (i )> f (дума_запитване).

Сравнете низовете по честота на най-малкия разтвор на 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 на масива се отнася до броя на думите, които имат стойност на функцията = 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 за временно ползване. Сложността на пространството също е линейна.