202. Happy Number

using System.Collections.Generic;
public class Solution {
    private int GetNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int digit = n % 10;
            n /= 10;
            totalSum += digit * digit;
        }
        return totalSum;
    }
    public bool IsHappy(int n) {
        HashSet<int> seen = new HashSet<int>();
        while (n != 1 && !seen.Contains(n)) {
            seen.Add(n);
            n = GetNext(n);
        }
        return n == 1;
    }
}

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int GetNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int digit = n % 10;
            n /= 10;
            totalSum += digit * digit;
        }
        return totalSum;
    }
    public bool IsHappy(int n) {
        HashSet<int> seen = new HashSet<int>();
        while (n != 1 && !seen.Contains(n)) {
            seen.push_back(n);
            n = GetNext(n);
        }
        return n == 1;
    }
}

class Solution {
    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
}

class Solution {
    isHappy(n) {
        function getNext(n) {
            let totalSum = 0;
            while (n > 0) {
                let digit = n % 10;
                totalSum += digit * digit;
                n = Math.floor(n / 10);
            }
            return totalSum;
        }

        let seen = new Set();
        while (n !== 1 && !seen.has(n)) {
            seen.add(n);
            n = getNext(n);
        }

        return n === 1;
    }
}

class Solution:
    def isHappy(self, n: int) -> bool:

        def get_next(n):
            total_sum = 0
            while n > 0:
                n, digit = divmod(n, 10)
                total_sum += digit**2
            return total_sum

        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = get_next(n)

        return n == 1

package main

import "fmt"

func getNext(n int) int {
    totalSum := 0
    for n > 0 {
        digit := n % 10
        n /= 10
        totalSum += digit * digit
    }
    return totalSum
}

func isHappy(n int) bool {
    seen := make(map[int]bool)
    for n != 1 && !seen[n] {
        seen[n] = true
        n = getNext(n)
    }
    return n == 1
}

func main() {
    fmt.Println(isHappy(19))
}

Algorithm

Счастливое number определяется следующим процессом:

Начиная с любого положительного целого числа, замените number суммой квадратов его цифр.

Повторяйте процесс, пока number не станет равным 1 (где оно и останется), или пока оно бесконечно не будет циклически повторяться в цикле, который не включает 1.

Те числа, для которых этот процесс завершается 1, являются счастливыми.

return true, если n является счастливым numberм, и false, если нет.

示例:

Input: n = 2

Output: false

👨‍💻

算法:

1️⃣

Для заданного числа n определите следующее number в последовательности: используйте операторы деления и взятия остатка для последовательного извлечения цифр из числа, пока не закончатся все цифры. Каждую извлеченную цифру возводите в квадрат и суммируйте полученные значения. Это техника "последовательного извлечения цифр" является полезным инструментом для решения множества задач.

2️⃣

Отслеживайте цепочку чисел и определяйте, не вошли ли вы в цикл, используя структуру данных HashSet. Каждый раз, генерируя следующее number в цепочке, проверяйте, присутствует ли оно уже в HashSet.

3️⃣

Если числа нет в HashSet, добавьте его туда. Если number уже есть в HashSet, это означает, что вы находитесь в цикле, и следует вернуть false. HashSet используется вместо Vector, List или Array, потому что проверка присутствия числа в HashSet занимает время O(1), тогда как в других структурах данных это займет время O(n). Правильный выбор структур данных является ключевым elementом решения подобных задач.

😎