ប្រៀបធៀបខ្សែអក្សរដោយប្រេកង់នៃដំណោះស្រាយតួអក្សរតូចបំផុត Leetcode


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន google ក្រុមហ៊ុន Oracle
អារេ ខ្សែអក្សរ

បញ្ហាប្រៀបធៀបខ្សែអក្សរដោយប្រេកង់នៃដំណោះស្រាយតួអក្សរតូចបំផុត Leetcode បានចែងថាយើងកំណត់មុខងារ f (s) លើមិនមែនទទេ ខ្សែអក្សរ ដូចជា f (s) ស្មើនឹងប្រេកង់នៃតួអក្សរតូចបំផុតនៅក្នុងខ្សែអក្សរ។ បន្ទាប់មកយើងត្រូវបានផ្តល់ឱ្យនូវពាក្យនិងសំណួរមួយចំនួន។ សម្រាប់សំណួរនីមួយៗយើងត្រូវរកចំនួនពាក្យដូចជា f (ពាក្យ)> f (query_word) ។ បន្ទាប់មកយើងត្រូវផ្តល់ចម្លើយសម្រាប់សំណួរទាំងអស់ជាវ៉ិចទ័រឬអារេមួយ។ ដូច្នេះមុននឹងមុជទឹកជ្រៅទៅក្នុងដំណោះស្រាយសូមក្រឡេកមើលឧទាហរណ៍មួយចំនួន។

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

ការពន្យល់ៈ f (“ zaaaz”) = ៣ ពីព្រោះតួអក្សរតូចបំផុតគឺ a a has ដែលមានប្រេកង់ស្មើនឹង ៣ ខណៈពេល f (“ cbd”) = ១ ។ ដូច្នេះយើងមានតែពាក្យមួយគត់ដែលមាន 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”) = ៣, f (“ cc”) = ២ ។ ដូច្នេះបន្ទាប់មកយើងរកឃើញថាសម្រាប់ពាក្យ f (“ bbb”) យើងមានពាក្យតែមួយ“ aaaa” ដែលមានតម្លៃមុខងារ ធំជាង ៣ ។ ស្រដៀងគ្នានេះដែរសម្រាប់ពាក្យ“ ស៊ី។ ស៊ី” យើងមានពាក្យ“ អាកា”“ អាណា” ដែលមានតម្លៃកាន់តែច្រើន។

វិធីសាស្រ្តសម្រាប់ប្រៀបធៀបខ្សែអក្សរដោយប្រេកង់នៃដំណោះស្រាយឡេតិចកូដដែលតូចជាងគេ

បញ្ហាប្រៀបធៀបខ្សែអក្សរដោយប្រេកង់នៃដំណោះស្រាយតួអក្សរតូចបំផុត Leetcode ស្នើឱ្យរកចំនួនពាក្យពីការបញ្ចូលដែលមានតម្លៃសម្រាប់មុខងារដែលបានកំណត់ធំជាងតម្លៃនៃមុខងារសម្រាប់ពាក្យសំណួរ។ មុខងារ f (s) ដែលបានកំណត់លើខ្សែដែលមិនទទេគឺស្មើនឹងប្រេកង់នៃតួអក្សរតូចបំផុតនៅក្នុងខ្សែអក្សរមួយ។ ដូច្នេះដំបូងយើងរកឃើញតម្លៃនៃមុខងារសម្រាប់ពាក្យសំណួរទាំងអស់។ យើងធ្វើដូចគ្នាសម្រាប់ពាក្យបញ្ចូលទាំងអស់។ យើងក៏បង្កើតអារេបន្ថែមដែលរក្សាទុកចំនួននៃពាក្យដែលមានតម្លៃមុខងារស្មើនឹងអ៊ី។ អារេនេះនឹងជួយយើងរកចម្លើយសម្រាប់សំណួរនៅក្នុងពេលវេលាថេរ។ សន្ទស្សន៍និមួយៗនៃអារេសំដៅទៅលើចំនួនពាក្យដែលមានតំលៃមុខងារ = i ។

បន្ទាប់ពីការវាយតម្លៃនៃតម្លៃមុខងារនិងរក្សាទុកពួកវានៅក្នុងអារេបណ្តោះអាសន្នរបស់យើង។ យើងយកផលបូកនៃជួរបណ្តោះអាសន្នដូចជាសន្ទស្សន៍នីមួយៗផ្ទុកចំនួនពាក្យសរុបដែលមានតម្លៃមុខងារធំជាងឬស្មើ i ។ ឥឡូវនេះយើងគ្រាន់តែរក្សាទុកចម្លើយសម្រាប់ពាក្យសំណួរនីមួយៗនៅក្នុងអារេឬវ៉ិចទ័រហើយត្រឡប់វា។

កូដសម្រាប់ប្រៀបធៀបខ្សែអក្សរដោយប្រេកង់នៃដំណោះស្រាយឡេតិចកូដដែលតូចជាងគេ

លេខកូដ 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

ចាវ៉ាកូដ

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)ដោយសារយើងត្រូវគណនាតម្លៃមុខងារសម្រាប់ពាក្យទាំងអស់ហើយប្រវែងពាក្យក៏តិចជាងឬស្មើ ១០ ដែរ។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

O (Q)ចាប់តាំងពីយើងបង្កើតអារេមួយដើម្បីរក្សាទុកចម្លើយនិងអារេបន្ថែមនៃទំហំ ១០ សម្រាប់ការប្រើប្រាស់ជាបណ្តោះអាសន្ន។ ភាពស្មុគស្មាញនៃលំហរក៏ជាលីនេអ៊ែរដែរ។