చిన్న అక్షర లీట్‌కోడ్ పరిష్కారం యొక్క ఫ్రీక్వెన్సీ ద్వారా తీగలను పోల్చండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది గూగుల్ ఒరాకిల్
అర్రే స్ట్రింగ్

చిన్న అక్షర లీట్‌కోడ్ సొల్యూషన్ యొక్క ఫ్రీక్వెన్సీ ద్వారా స్ట్రింగ్స్‌ను పోల్చడం సమస్య, ఖాళీగా లేని ఎఫ్ (ల) ఫంక్షన్‌ను మేము నిర్వచిస్తాము స్ట్రింగ్ s (f) స్ట్రింగ్‌లోని అతిచిన్న అక్షరం యొక్క ఫ్రీక్వెన్సీకి సమానం. అప్పుడు మాకు కొన్ని పదాలు మరియు కొన్ని ప్రశ్నలు ఇవ్వబడతాయి. ప్రతి ప్రశ్నకు, f (పదాలు)> f (query_word) వంటి పదాల సంఖ్యను మనం కనుగొనవలసి ఉంటుంది. అప్పుడు మేము అన్ని ప్రశ్నలకు వెక్టర్ లేదా అర్రేగా సమాధానం ఇవ్వాలి. కాబట్టి, ద్రావణంలో లోతుగా డైవింగ్ చేయడానికి ముందు, కొన్ని ఉదాహరణలను పరిశీలిద్దాం.

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

వివరణ: f (“zaaaz”) = 3, ఎందుకంటే అతిచిన్న అక్షరం 3 కి సమానమైన పౌన frequency పున్యాన్ని కలిగి ఉన్న 'a', అయితే f (“cbd”) = 1. కాబట్టి, మనకు f (i )> f (ప్రశ్న_వర్డ్).

చిన్న అక్షర లీట్‌కోడ్ పరిష్కారం యొక్క ఫ్రీక్వెన్సీ ద్వారా తీగలను పోల్చండి

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 కన్నా ఎక్కువ. అదేవిధంగా, “సిసి” అనే పదానికి, మనకు “ఆఆ”, “ఆఆ” అనే పదాలు ఎక్కువ ఫంక్షన్ విలువను కలిగి ఉన్నాయి.

అతిచిన్న అక్షర లీట్‌కోడ్ పరిష్కారం యొక్క ఫ్రీక్వెన్సీ ద్వారా తీగలను పోల్చడానికి విధానం

చిన్న అక్షర లీట్‌కోడ్ సొల్యూషన్ యొక్క ఫ్రీక్వెన్సీ ద్వారా తీగలను పోల్చండి సమస్య ప్రశ్న పదాల కోసం ఫంక్షన్ విలువ కంటే ఎక్కువ నిర్వచించిన ఫంక్షన్‌కు విలువ కలిగిన ఇన్‌పుట్ నుండి పదాల సంఖ్యను కనుగొనమని అడుగుతుంది. ఖాళీ కాని తీగలపై నిర్వచించిన ఫంక్షన్ f (లు) స్ట్రింగ్‌లోని అతి చిన్న అక్షరం యొక్క ఫ్రీక్వెన్సీకి సమానం. కాబట్టి, మొదట, అన్ని ప్రశ్న పదాలకు ఫంక్షన్ యొక్క విలువను మేము కనుగొంటాము. మేము అన్ని ఇన్పుట్ పదాలకు అదే చేస్తాము. ఫంక్షన్ విలువను i కి సమానమైన పదాల సంఖ్యను నిల్వ చేసే అదనపు శ్రేణిని కూడా మేము సృష్టిస్తాము. ఈ శ్రేణి ప్రశ్నలకు సమాధానాలను స్థిరమైన సమయంలో కనుగొనడంలో మాకు సహాయపడుతుంది. శ్రేణి యొక్క ప్రతి సూచిక i ఫంక్షన్ విలువ = i ఉన్న పదాల సంఖ్యను సూచిస్తుంది.

ఫంక్షన్ విలువను అంచనా వేసిన తరువాత మరియు వాటిని మా తాత్కాలిక శ్రేణిలో నిల్వ చేసిన తరువాత. మేము తాత్కాలిక శ్రేణి యొక్క ప్రత్యయం మొత్తాన్ని తీసుకుంటాము, అంటే ప్రతి సూచిక ఇప్పుడు ఫంక్షన్ విలువ ఎక్కువ లేదా i కి సమానమైన మొత్తం పదాల సంఖ్యను నిల్వ చేస్తుంది. ఇప్పుడు మనం ప్రతి ప్రశ్న పదానికి సమాధానాన్ని శ్రేణి లేదా వెక్టర్‌లో నిల్వ చేసి తిరిగి ఇస్తాము.

చిన్న అక్షర లీట్‌కోడ్ పరిష్కారం యొక్క ఫ్రీక్వెన్సీ ద్వారా తీగలను పోల్చడానికి కోడ్

సి ++ కోడ్

#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

జావా కోడ్

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 యొక్క అదనపు శ్రేణిని సృష్టిస్తాము కాబట్టి. స్థల సంక్లిష్టత కూడా సరళంగా ఉంటుంది.