Решение за среќен број Leetcode


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Јаболко
Хашинг

Изјава за проблем

Проблемот е да проверите дали бројот е среќен број или не.

За голем број се вели дека се среќни број ако го замениме бројот со збирот на квадратите од неговите цифри, и повторувањето на процесот го прави бројот еднаков на 1. ако не стане 1 и бесконечно се циклуси во циклус кој не вклучува 1, тоа не е среќен број.

пример

19
true

објаснување:

Среќен број

1 ^ 2 + 9 ^ 2 = 82
8 ^ 2 + 2 ^ 2 = 68
6 ^ 2 + 8 ^ 2 = 100
1 ^ 2 + 0 ^ 2 + 0 ^ 2 = 1 (среќен број)

2
false

објаснување:

Бидејќи повторно се достигнува до бројот 4, оттука тој ќе се врти во синџирот засекогаш и никогаш не може да заврши со 1. Оттука, дадениот број не е среќен број.

Пристап

Можеме да повториме во временска јамка и да го замениме бројот со збир од квадратот на неговите цифри додека бројот не стане 1, со услов секој нов конвертиран број да не се случил порано, во спротивно ќе влеземе во неопределена јамка.
За ова можеме да земеме множество цели броеви, првично празни и да ги извршиме следниве чекори:

  1. Ако тековниот број е веќе присутен во поставеното враќање неточно (најде јамка).
  2. Друго ако е еднакво на 1 врати точно.
  3. Друго, вметнете го тековниот број во множеството и заменете го тековниот број со збир од квадратот на неговите цифри.
  4. Повторете го истиот процес.

Имплементација

Програма C ++ за решение со среќен број Leetcode

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

bool isHappy(int n) {
                 
    set<int> s;

    while(s.count(n)==0)
    {
        if(n==1) return true;
        s.insert(n);
        int temp=0;

        while(n)
        {
            temp+= (n%10)*(n%10);
            n/=10;
        }
        n=temp;
    }
    return false;
}

int main()
{ 
    int n=19;
    
    if(isHappy(n)) 
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
    
 return 0;
}
true

Јава програма за решение со среќен број Leetcode

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

class Happy
{  
     public static boolean isHappy(int n) 
     {
        
        Set<Integer> set = new HashSet<Integer>();
        int sum,digit;

        while (set.add(n)) 
        {
            sum = 0;
            while (n > 0) {
                digit = n%10;
                sum += digit*digit;
                n /= 10;
            }
            if (sum == 1)
                return true;
            else
                n = sum;

        }
        return false;
    }
    
    
    public static void main(String args[])
    {
       int n=19;
       System.out.println(isHappy(n));
    }
}
true

Анализа на сложеност за решение со среќен број на леткод

Временска комплексност

О (логн):  Каде што n е дадениот број. Трошоците за наоѓање збир на квадратот на секоја цифра од број во синџирот се најавуваат (n) и бројот продолжува да се намалува со логаритамскиот фактор. Оттука, комплексноста = О (логн) + О (логлогн) + О (лологлог) +….
Тука О (log⁡n) е доминантен дел. Оттука, целокупната сложеност е О (логн).

Комплексноста на просторот 

О (логн):  Максималната големина на множеството исто така ќе биде логаритамска со даден број како временска сложеност.