ປຽບທຽບສະຕິງໂດຍຄວາມຖີ່ຂອງການແກ້ໄຂຕົວອັກສອນ Leetcode ທີ່ມີຂະ ໜາດ ນ້ອຍທີ່ສຸດ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ກູໂກ Oracle
Array string

ບັນຫາປຽບທຽບສະຕິງໂດຍຄວາມຖີ່ຂອງການແກ້ໄຂຕົວອັກສອນນ້ອຍທີ່ສຸດ, Leetcode ລະບຸວ່າພວກເຮົາ ກຳ ນົດ f ໜ້າ ທີ່ f (s) ຫຼາຍກວ່າທີ່ບໍ່ແມ່ນຫວ່າງ string s ດັ່ງກ່າວ f (s) ເທົ່າກັບຄວາມຖີ່ຂອງຕົວອັກສອນນ້ອຍທີ່ສຸດໃນສາຍ. ຫຼັງຈາກນັ້ນພວກເຮົາໄດ້ຮັບບາງ ຄຳ ແລະບາງ ຄຳ ຖາມ. ສຳ ລັບການສອບຖາມແຕ່ລະຄັ້ງ, ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາ ຈຳ ນວນ ຄຳ ສັບດັ່ງກ່າວ f (ຄຳ ສັບ)> f (query_word). ຫຼັງຈາກນັ້ນພວກເຮົາຕ້ອງຕອບຄືນ ຄຳ ຕອບ ສຳ ລັບການສອບຖາມທັງ ໝົດ ເປັນ vector ຫລື array. ສະນັ້ນ, ກ່ອນຈະລົງເລິກໃນການແກ້ໄຂ, ໃຫ້ເຮົາພິຈາລະນາບາງຕົວຢ່າງ.

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

ຄຳ ອະທິບາຍ: f (“ zaaaz”) = 3, ເພາະວ່າຕົວອັກສອນນ້ອຍທີ່ສຸດແມ່ນ 'a' ທີ່ມີຄວາມຖີ່ເທົ່າກັບ 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. ຄ້າຍຄືກັນ, ສຳ ລັບ ຄຳ ວ່າ "ຊີຊີ", ພວກເຮົາມີ ຄຳ ວ່າ "aaa", "aaaa" ທີ່ມີຄຸນຄ່າໃນ ໜ້າ ທີ່ຫຼາຍກວ່າເກົ່າ.

ວິທີການ ສຳ ລັບການປຽບທຽບສະຕິງໂດຍຄວາມຖີ່ຂອງການແກ້ໄຂຕົວອັກສອນນ້ອຍທີ່ສຸດ

ບັນຫາປຽບທຽບສະຕິງໂດຍຄວາມຖີ່ຂອງຕົວອັກສອນນ້ອຍທີ່ສຸດ Leetcode Solution ຂໍໃຫ້ຊອກຫາ ຈຳ ນວນ ຄຳ ສັບຈາກການປ້ອນຂໍ້ມູນທີ່ມີຄຸນຄ່າ ສຳ ລັບ ໜ້າ ທີ່ທີ່ໄດ້ ກຳ ນົດສູງກວ່າມູນຄ່າຂອງຟັງຊັນ ສຳ ລັບ ຄຳ ຖາມ. ຟັງຊັ່ນ f (s) ທີ່ ກຳ ນົດໃນໄລຍະທີ່ບໍ່ແມ່ນຫວ່າງແມ່ນເທົ່າກັບຄວາມຖີ່ຂອງຕົວອັກສອນນ້ອຍທີ່ສຸດໃນສາຍ. ດັ່ງນັ້ນ, ກ່ອນອື່ນ ໝົດ, ພວກເຮົາຊອກຫາຄຸນຄ່າຂອງ ໜ້າ ທີ່ ສຳ ລັບທຸກ ຄຳ ທີ່ໃຊ້ໃນການສອບຖາມ. ພວກເຮົາເຮັດແບບດຽວກັນ ສຳ ລັບທຸກ ຄຳ ສັບປ້ອນຂໍ້ມູນ. ພວກເຮົາຍັງໄດ້ສ້າງຕາຕະລາງພິເສດທີ່ເກັບຮັກສາ ຈຳ ນວນ ຄຳ ທີ່ມີຄຸນຄ່າຂອງ ໜ້າ ທີ່ໃຫ້ເທົ່າກັບ i. ຕາຕະລາງນີ້ຈະຊ່ວຍໃຫ້ພວກເຮົາຊອກຫາ ຄຳ ຕອບ ສຳ ລັບການສອບຖາມໃນເວລາຄົງທີ່. ແຕ່ລະດັດນີ i ຂອງຂບວນ ໝາຍ ເຖິງ ຈຳ ນວນ ຄຳ ສັບທີ່ມີຄ່າ function = i.

ຫຼັງຈາກການປະເມີນຄຸນຄ່າຂອງ ໜ້າ ທີ່ແລະເກັບມ້ຽນມັນໄວ້ໃນແຖວຊົ່ວຄາວຂອງພວກເຮົາ. ພວກເຮົາຖືເອົາຜົນບວກຂອງແຖວຊົ່ວຄາວເຊັ່ນວ່າດັດຊະນີແຕ່ລະອັນປະຈຸບັນເກັບ ຈຳ ນວນ ຄຳ ສັບທັງ ໝົດ ທີ່ມີຄຸນຄ່າໃນການເຮັດວຽກທີ່ໃຫຍ່ກວ່າຫຼືເທົ່າກັບ i. ຕອນນີ້ພວກເຮົາພຽງແຕ່ເກັບ ຄຳ ຕອບ ສຳ ລັບແຕ່ລະ ຄຳ ຄົ້ນໃນແບບຂອດຫລື vector ແລະສົ່ງຄືນມັນ.

ລະຫັດ ສຳ ລັບການປຽບທຽບເຊືອກໂດຍຄວາມຖີ່ຂອງການແກ້ໄຂຕົວອັກສອນນ້ອຍທີ່ສຸດ

ລະຫັດ 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 ເພີ່ມເຕີມ ສຳ ລັບການ ນຳ ໃຊ້ຊົ່ວຄາວ. ຄວາມສັບສົນຂອງພື້ນທີ່ຍັງເປັນເສັ້ນ.