រាប់ដំណោះស្រាយឡេឡេលេខកូដជាក្រុមធំបំផុត


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ម៉ារារី
អារេ

បញ្ហាការរាប់ជាក្រុម Leetcode Solution ផ្តល់អោយយើងនូវចំនួនគត់។ យើងតំរូវអោយរកផលបូកនៃខ្ទង់នៃលេខនីមួយៗចន្លោះពី ១ ទៅ n (រាប់បញ្ចូល) ។ បន្ទាប់មកយើងនឹងដាក់លេខដែលមានលេខដូចគ្នានៃខ្ទង់ហើយរក្សាលេខ។ បន្ទាប់មកយើងត្រូវគណនាចំនួនក្រុមជាមួយនឹងចំនួនអតិបរមា។ នេះហាក់ដូចជាច្រឡំនៅពេលដំបូង។ ដូច្នេះតោះមើលឧទាហរណ៍ខ្លះ។

ឧទាហរណ៍

រាប់ដំណោះស្រាយឡេឡេលេខកូដជាក្រុមធំបំផុត

n = 13
4

ការពន្យល់ៈលេខដែលបានដាក់ជាក្រុមតាមផលបូកនៃខ្ទង់របស់ពួកគេគឺ [១, ១០], [២.១១], [៣.១២], [៤, ១៣], [៥], [៦], [៧], [ ៨], [៩] ។ ដូច្នេះមាន ៤ ក្រុមដែលមានប្រេកង់អតិបរមា ២។ ដូច្នេះចម្លើយគឺ ៤ ។

n = 2
2

ការពន្យល់ៈស្រដៀងគ្នានេះដែរប្រសិនបើអ្នកឃើញលេខរហូតដល់លេខ ២ មានតែលេខ ២ លេខ ១ និងលេខ ២ ទេ។ ទាំងពីរបង្កើតក្រុមមួយដែលមានលេខរៀងៗខ្លួន។ ដូច្នេះចម្លើយគឺ ២ ក្រុមដែលមានប្រេកង់អតិបរមា ១ ។

វិធីសាស្រ្ត

បញ្ហារាប់លេខធំជាងគេនៃដំណោះស្រាយឡេឡេលេខកូដផ្តល់ឱ្យយើងនូវចំនួនគត់តែមួយ។ ហើយស្នើសុំឱ្យរាប់ចំនួនក្រុមនៃចំនួនលេខដែលមានប្រេកង់អតិបរមាដែលយើងដាក់ជាក្រុមតាមចំនួនសរុបនៃខ្ទង់របស់ពួកគេ។ ចាប់តាំងពីការបញ្ចូលគឺជាឧបសគ្គដល់អតិបរមា 10000. យើងបង្កើតមួយ អារេ ដើម្បីរក្សាប្រេកង់នៃផលបូកនៃខ្ទង់នៃលេខ។ ទំហំអតិបរមានៃឯកសារ CNT អារេគួរតែមាន ៣៦. ពីព្រោះការបញ្ចូលជាមួយផលបូកអតិបរិមានឹងមាន ៣៦ ។ ដូច្នេះយើងធ្វើត្រាប់តាមដំណើរការនៃការស្វែងរកផលបូកនៃខ្ទង់លេខនីមួយៗពីលេខ ១ ដល់លេខ n ។ ក្នុងអំឡុងពេលនៃការវាយតម្លៃប្រេកង់យើងរក្សាទុកប្រេកង់អតិបរមាដែលបានគណនារហូតមកដល់ពេលនេះ។ ឥឡូវនេះយើងចាប់ផ្តើមរង្វិលជុំថ្មីហើយរាប់ចំនួនក្រុមដែលមានប្រេកង់អតិបរមា។

លេខកូដសំរាប់ដំណោះស្រាយក្រុម Leetcode ដែលធំជាងគេ

លេខកូដ C ++

#include <bits/stdc++.h>
using namespace std;

int sumDigits(int n){
    int sum = 0;
    while(n>0){
        sum += (n%10);
        n /= 10;
    }
    return sum;
}

int countLargestGroup(int n) {
    int cnt[37];
    memset(cnt, 0, sizeof cnt);
    int mx = 0;
    for(int i=0;i<=n;i++){
        int s = sumDigits(i);
        cnt[s]++;
        if(cnt[s] > mx)
            mx = cnt[s];
    }
    
    int ans = 0;
    for(int i=0;i<37;i++){
        if(cnt[i] == mx)
            ans++;
    }
    return ans;
}

int main(){
    cout<<countLargestGroup(13);
}
4

ចាវ៉ាកូដ

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
  
    public static int sumDigits(int n){
        int sum = 0;
        while(n>0){
            sum += (n%10);
            n /= 10;
        }
        return sum;
    }

    public static int countLargestGroup(int n) {
        int cnt[] = new int[37];
        for(int i=0;i<37;i++)cnt[i] = 0;
        int mx = 0;
        for(int i=1;i<=n;i++){
            int s = sumDigits(i);
            cnt[s]++;
            if(cnt[s] > mx)
                mx = cnt[s];
        }

        int ans = 0;
        for(int i=0;i<37;i++){
            if(cnt[i] == mx)
                ans++;
        }
        return ans;
    }
    
    public static void main(String[] args){
    	System.out.print(countLargetGroup(13));
    }
    
}
4

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (N), ពីព្រោះរង្វិលជុំដំបូងដំណើរការអាស្រ័យលើធាតុបញ្ចូល។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

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

ឱ (១), ចាប់តាំងពីយើងមានអារេទំហំថេរ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហនៅតែមិនទាក់ទងនឹងធាតុបញ្ចូល។