Ən Böyük Qrup Leetcode həllini sayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Mercari
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 25

Count Complete Group Leetcode Solution problemi bizə bir tam ədədi təqdim edir. Hər ədədin rəqəmlərinin cəmini 1 ilə n arasında (daxil olmaqla) tapmamız lazımdır. Daha sonra rəqəmləri eyni rəqəmlərin cəmi ilə qruplaşdıracağıq və bir sayma aparacağıq. Sonra qrup sayını maksimum saymaqla hesablamalıyıq. Bu əvvəlcə qarışıq görünür. Beləliklə, bir neçə nümunəyə nəzər salaq.

Nümunələr

Ən Böyük Qrup Leetcode həllini sayınPin

n = 13
4

İzahat: Rəqəmlərinin cəminə görə qruplaşdırılan rəqəmlər [1, 10], [2,11], [3,12], [4,13], [5], [6], [7], [ 8], [9]. Beləliklə, maksimum tezliyi 4 olan 2 qrup var. Buna görə cavab, 4.

n = 2
2

İzahat: Eynilə, 2-ə qədər olan rəqəmləri görürsənsə, yalnız 2 və 1 ədəd var. Hər ikisi hər birində bir ədəd olan bir qrup yaradır. Beləliklə, cavab maksimum 2 tezlik olan 2 qrupdur.

Yanaşma

Problem Ən Böyük Qrup Leetcode Çözümünü saymaq bizə bir tam ədədi təmin etdi. Və rəqəmləri rəqəmlərin cəminə görə qruplaşdırdığımız maksimum tezliyə sahib olan say qruplarının sayını istədi. Giriş maksimum 10000 bir məhdudiyyət olduğundan array rəqəmlərin rəqəmlərinin cəminin tezliyini saxlamaq. Maksimum ölçüsü CNT massiv 36 olmalıdır. Çünki maksimum cəmi olan giriş 36 olacaqdır. Beləliklə, 1-dən n-ə qədər olan hər rəqəm üçün rəqəmlərin cəmini tapmaq prosesini simulyasiya edirik. Tezliyin qiymətləndirilməsi zamanı indiyə qədər hesablanmış maksimum tezliyi saxlayırıq. İndi yeni bir dövrəyə başlayırıq və maksimum tezliyə sahib qrup sayını hesablayırıq.

Sayı Ən Böyük Qrup Leetcode Çözümünün Kodu

C ++ kodu

#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

Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki ilk döngə girişdən asılıdır. Beləliklə, zamanın mürəkkəbliyi doğrudur.

Kosmik Mürəkkəblik

O (1), sabit ölçülü bir sıra olduğumuz üçün. Beləliklə, girişdən asılı olmayaraq kosmik mürəkkəblik sabit qalır.

Şərh yaz

Translate »
1