Skip to content

Latest commit

 

History

History
540 lines (472 loc) · 12.4 KB

0202.快乐数.md

File metadata and controls

540 lines (472 loc) · 12.4 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！

该用set的时候，还是得用set

第202题. 快乐数

力扣题目链接

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为  1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

思路

这道题目看上去貌似一道数学问题，其实并不是！

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

正如：关于哈希表，你该了解这些！中所说，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

判断sum是否重复出现就可以使用unordered_set。

还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。

C++代码如下：

class Solution {
public:
    // 取数值各个位上的单数之和
    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1) {
            int sum = getSum(n);
            if (sum == 1) {
                return true;
            }
            // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};
  • 时间复杂度: O(logn)
  • 空间复杂度: O(logn)

其他语言版本

Java：

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

    private int getNextNumber(int n) {
        int res = 0;
        while (n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n = n / 10;
        }
        return res;
    }
}

Python：

(版本一)使用集合

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

        while True:
            n = self.get_sum(n)
            if n == 1:
                return True
            
            # 如果中间结果重复出现，说明陷入死循环了，该数不是快乐数
            if n in record:
                return False
            else:
                record.add(n)

    def get_sum(self,n: int) -> int: 
        new_num = 0
        while n:
            n, r = divmod(n, 10)
            new_num += r ** 2
        return new_num

(版本二)使用集合

class Solution:
   def isHappy(self, n: int) -> bool:
       record = set()
       while n not in record:
           record.add(n)
           new_num = 0
           n_str = str(n)
           for i in n_str:
               new_num+=int(i)**2
           if new_num==1: return True
           else: n = new_num
       return False

(版本三)使用数组

class Solution:
   def isHappy(self, n: int) -> bool:
       record = []
       while n not in record:
           record.append(n)
           new_num = 0
           n_str = str(n)
           for i in n_str:
               new_num+=int(i)**2
           if new_num==1: return True
           else: n = new_num
       return False

(版本四)使用快慢指针

class Solution:
   def isHappy(self, n: int) -> bool:        
       slow = n
       fast = n
       while self.get_sum(fast) != 1 and self.get_sum(self.get_sum(fast)):
           slow = self.get_sum(slow)
           fast = self.get_sum(self.get_sum(fast))
           if slow == fast:
               return False
       return True
   def get_sum(self,n: int) -> int: 
       new_num = 0
       while n:
           n, r = divmod(n, 10)
           new_num += r ** 2
       return new_num

(版本五)使用集合+精简

class Solution:
   def isHappy(self, n: int) -> bool:
       seen = set()
       while n != 1:
           n = sum(int(i) ** 2 for i in str(n))
           if n in seen:
               return False
           seen.add(n)
       return True

(版本六)使用数组+精简

class Solution:
   def isHappy(self, n: int) -> bool:
       seen = []
       while n != 1:
           n = sum(int(i) ** 2 for i in str(n))
           if n in seen:
               return False
           seen.append(n)
       return True

Go：

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

func getSum(n int) int {
    sum := 0
    for n > 0 {
        sum += (n % 10) * (n % 10)
        n = n / 10
    }
    return sum
}

JavaScript:

var isHappy = function (n) {
    let m = new Map()

    const getSum = (num) => {
        let sum = 0
        while (n) {
            sum += (n % 10) ** 2
            n = Math.floor(n / 10)
        }
        return sum
    }

    while (true) {
        // n出现过，证明已陷入无限循环
        if (m.has(n)) return false
        if (n === 1) return true
        m.set(n, 1)
        n = getSum(n)
    }
}

// 方法二：使用环形链表的思想 说明出现闭环 退出循环
var isHappy = function(n) {
    if (getN(n) == 1) return true;
    let a = getN(n), b = getN(getN(n));
    // 如果 a === b 
    while (b !== 1 && getN(b) !== 1 && a !== b) {
        a = getN(a);
        b = getN(getN(b));
    }
    return b === 1 || getN(b) === 1 ;
};

// 方法三：使用Set()更简洁
/**
 * @param {number} n
 * @return {boolean}
 */

var getSum = function (n) {
    let sum = 0;
    while (n) {
        sum += (n % 10) ** 2;
        n =  Math.floor(n/10);
    }
    return sum;
}
var isHappy = function(n) {
    let set = new Set();   // Set() 里的数是惟一的
    // 如果在循环中某个值重复出现，说明此时陷入死循环，也就说明这个值不是快乐数
    while (n !== 1 && !set.has(n)) {
        set.add(n);
        n = getSum(n);
    }
    return n === 1;
};

// 方法四：使用Set()，求和用reduce
var isHappy = function(n) {
    let set = new Set();
    let totalCount;
    while(totalCount !== 1) {
        let arr = (''+(totalCount || n)).split('');
        totalCount = arr.reduce((total, num) => {
            return total + num * num
        }, 0)
        if (set.has(totalCount)) {
            return false;
        }
        set.add(totalCount);
    }
    return true;
};

TypeScript:

function isHappy(n: number): boolean {
    // Utils
    // 计算val各位的平方和
    function calcSum(val: number): number {
        return String(val).split("").reduce((pre, cur) => (pre + Number(cur) * Number(cur)), 0);
    }

    let storeSet: Set<number> = new Set();
    while (n !== 1 && !storeSet.has(n)) {
        storeSet.add(n);
        n = calcSum(n);
    }
    return n === 1;
};

Swift：

// number 每个位置上的数字的平方和
func getSum(_ number: Int) -> Int {
    var sum = 0
    var num = number
    while num > 0 {
        let temp = num % 10
        sum += (temp * temp)
        num /= 10
    }
    return sum
}
func isHappy(_ n: Int) -> Bool {
    var set = Set<Int>()
    var num = n
    while true {
        let sum = self.getSum(num)
        if sum == 1 {
            return true
        }
        // 如果这个sum曾经出现过，说明已经陷入了无限循环了
        if set.contains(sum) {
            return false
        } else {
            set.insert(sum)
        }
        num = sum
    }
}

PHP:

class Solution {
    /**
     * @param Integer $n
     * @return Boolean
     */
    function isHappy($n) {
        // use a set to record sum
        // whenever there is a duplicated, stop
        // == 1 return true, else false
        $table = [];
        while ($n != 1 && !isset($table[$n])) {
            $table[$n] = 1;
            $n = self::getNextN($n);
        }
        return $n == 1;
    }

    function getNextN(int $n) {
        $res = 0;
        while ($n > 0) {
            $temp = $n % 10;
            $res += $temp * $temp;
            $n = floor($n / 10);
        }
        return $res;
    }
}

Rust:

use std::collections::HashSet;
impl Solution {
    pub fn get_sum(mut n: i32) -> i32 {
        let mut sum = 0;
        while n > 0 {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        sum
    }

    pub fn is_happy(n: i32) -> bool {
        let mut n = n;
        let mut set = HashSet::new();
        loop {
            let sum = Self::get_sum(n);
            if sum == 1 {
                return true;
            }
            if set.contains(&sum) {
                return false;
            } else { set.insert(sum); }
            n = sum;
        }
    }
}

C:

int get_sum(int n) {
    int sum = 0;
    div_t n_div = { .quot = n };
    while (n_div.quot != 0) {
        n_div = div(n_div.quot, 10);
        sum += n_div.rem * n_div.rem;
    }
    return sum;
}

// (版本1)使用数组
bool isHappy(int n) {
    // sum = a1^2 + a2^2 + ... ak^2
    // first round:
    // 1 <= k <= 10
    // 1 <= sum <= 1 + 81 * 9 = 730
    // second round:
    // 1 <= k <= 3
    // 1 <= sum <= 36 + 81 * 2 = 198
    // third round:
    // 1 <= sum <= 81 * 2 = 162
    // fourth round:
    // 1 <= sum <= 81 * 2 = 162

    uint8_t visited[163] = { 0 };
    int sum = get_sum(get_sum(n));
    int next_n = sum;

    while (next_n != 1) {
        sum = get_sum(next_n);

        if (visited[sum]) return false;

        visited[sum] = 1;
        next_n = sum;
    };

    return true;
}

// (版本2)使用快慢指针
bool isHappy(int n) {
    int slow = n;
    int fast = n;

    do {
        slow = get_sum(slow);
        fast = get_sum(get_sum(fast));
    } while (slow != fast);

    return (fast == 1);
}

Scala:

object Solution {
  // 引入mutable
  import scala.collection.mutable
  def isHappy(n: Int): Boolean = {
    // 存放每次计算后的结果
    val set: mutable.HashSet[Int] = new mutable.HashSet[Int]()
    var tmp = n // 因为形参是不可变量，所以需要找到一个临时变量
    // 开始进入循环
    while (true) {
      val sum = getSum(tmp) // 获取这个数每个值的平方和
      if (sum == 1) return true // 如果最终等于 1，则返回true
      // 如果set里面已经有这个值了，说明进入无限循环，可以返回false，否则添加这个值到set
      if (set.contains(sum)) return false
      else set.add(sum)
      tmp = sum
    }
    // 最终需要返回值，直接返回个false
    false
  }

  def getSum(n: Int): Int = {
    var sum = 0
    var tmp = n
    while (tmp != 0) {
      sum += (tmp % 10) * (tmp % 10)
      tmp = tmp / 10
    }
    sum
  }

C#：

public class Solution {
    private int getSum(int n) {
        int sum = 0;
        //每位数的换算
        while (n > 0) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    public bool IsHappy(int n) {
        HashSet <int> set = new HashSet<int>();
        while(n != 1 && !set.Contains(n)) { //判断避免循环
            set.Add(n);
            n = getSum(n);
        }
        return n == 1;
    }
}