Skip to content

Latest commit

 

History

History
445 lines (379 loc) · 10.6 KB

0202.快乐数.md

File metadata and controls

445 lines (379 loc) · 10.6 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;
        }
    }
};

其他语言版本

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:
        def calculate_happy(num):
            sum_ = 0
            
            # 从个位开始依次取，平方求和
            while num:
                sum_ += (num % 10) ** 2
                num = num // 10
            return sum_

        # 记录中间结果
        record = set()

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

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;
    }
}

C:

typedef struct HashNodeTag {
    int key;   /* num  */
    struct HashNodeTag *next;
}HashNode;

/* Calcualte the hash key */
static inline int hash(int key, int size) {
    int index = key % size;
    return (index > 0) ? (index) : (-index);
}

/* Calculate the sum of the squares of its digits*/
static inline int calcSquareSum(int num) {
    unsigned int sum = 0;
    while(num > 0) {
        sum += (num % 10) * (num % 10);
        num = num/10; 
    }
    return sum;
}

#define HASH_TABLE_SIZE     (32)

bool isHappy(int n){
    int sum = n;
    int index = 0;
    bool bHappy = false;
    bool bExit = false;
    /* allocate the memory for hash table with chaining method*/
    HashNode ** hashTable = (HashNode **)calloc(HASH_TABLE_SIZE, sizeof(HashNode));
    
    while(bExit == false) {
        /* check if n has been calculated */
        index = hash(n, HASH_TABLE_SIZE);

        HashNode ** p = hashTable + index;

        while((*p) && (bExit == false)) {
            /* Check if this num was calculated, if yes, this will be endless loop */
            if((*p)->key == n) { 
                bHappy = false;
                bExit = true;
            }
            /* move to next node of the same index */
            p = &((*p)->next);
        }

        /* put n intot hash table */
        HashNode * newNode = (HashNode *)malloc(sizeof(HashNode));
        newNode->key = n;
        newNode->next = NULL;

        *p = newNode;

        sum = calcSquareSum(n);
        if(sum == 1) {
            bHappy = true;
            bExit = true;
        }
        else {
            n = sum;
            
        }
    }

    return bHappy;
}

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#：
```csharp
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;
    }
}