Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Easy 202. Happy Number

tags: leetcode

問題

イデア

与えられた2桁数がhappy numberかどうか返せという問題です.

happy numberとは

  • 各桁の2乗の和から出来た数をnext_numとします
    • next_num1になるときhappy numberです.
    • next_numの各桁の2乗の和が1になるまでこの作業を繰り返します.無限ループにならなければhappy numberです.

今までに出た数を記録するようなデータ構造を使えば良いですね.

解法

  • 各桁の2乗の和を得る関数を書きます.
  • std::unordered_mapを使って,今までの各桁の2乗の和を保存します.
    • std::vectorstd::liststd::arrayにしないのは検索する際の時間計算量とデータ構造に必要な空間計算量が良いからです.
    • 和が今までに出たことがあるならばfalse
    • そうでないならば,1か確認してそうならばtrueを返します.
      • 1でないならば,新しく数字を記録します.

計算量

登場する数字の数が$N$だとします.

  • 時間計算量
    • 和を得る関数は$O(1)$
    • std::unordered_mapへのアクセスには$O(\log N)$
    • 全体で$(<現れる数の種類>)$
  • 空間計算量
    • $O(<現れる数の種類>)$

C++

class Solution {
public:
  bool isHappy(int n) {
    unordered_map<int, int> mp; // <num, times>
    while (mp.find(n = getNext(n)) == mp.end()) {
      if (n == 1)
        return true;
      mp[n]++;
    }
    return false;
  }
  
private:
  int getNext(int n) {    
    int sum = 0;
    while (n) {
      sum += (n % 10) * (n % 10);
      n /= 10;
    }
    return sum;
  }
};

Python

class Solution:
    def isHappy(self, n: int) -> bool:
        used_nums = {}
        while not used_nums.get(n):
            if n == 1:
                return True
            
            used_nums[n] = True
            n = self.__get_next(n)
        return False
    
    def __get_next(self, n: int) -> int:
        total = 0
        while n != 0:
            total += (n % 10) * (n % 10)
            n //= 10
        return total