讨论/《哈希表》 - 快乐数/
《哈希表》 - 快乐数
共 8 个回复
class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> set;
        int m = n;
        while(m != 1) {
            set.insert(m);
            int sum = 0;
            while(m != 0) {
                sum += pow(m % 10, 2);
                m = m / 10; 
            }
            m = sum;
            if(set.find(m) != set.end()) return false;
        }
        return true;
    }
};
3

Javascript版本~

快慢指针解法, 空间复杂度O(1)

var isHappy = function (n) {
    let fast = n + '', slow = n + ''    //快指针,慢指针
    //定义计算方法
    const calculate = (num) => {
        let result = 0
        for (let i = 0; i < num.length; i++) {
            result += Math.pow(num[i], 2)
        }
        console.log(result)
        return result + ''    //转字符串返回,方便下次遍历
    }
    //开始查找是否循环
    while (1) {
        //slow每次计算一步, fast计算两次, 若是slow和fast相等,表示进入循环,不是快乐数
        slow = calculate(slow)
        fast = calculate(fast)
        fast = calculate(fast)
        if (fast == 1 || slow == 1) return true
        if (fast === slow) return false

    }
};
1
class Solution
{
public:
    bool isHappy(int n)
    {
        unordered_set<int> hashset;
        int a;
        while (n != 1 && !hashset.count(n))
        {
            hashset.insert(n);
            a = 0;
            while (n > 0)
            {
                a += (n % 10) * (n % 10);
                n = n / 10;
            }
            n = a;
        }
        if(n == 1)
            return true;
        return false;
    }
};

niu

class Solution {
public:
    bool isHappy(int n) 
    {
        unordered_map<int,int> mp;
        mp[n]=1;
        while(n!=1)
        {
            int q=n;
            int count=0;
            int sum=0;
            while(q!=0)
            {
                sum=sum+(q%10)*(q%10);
                count++;
                q=q/10;
            }
            cout<<sum<<endl;
            if(sum!=1&&mp.find(sum)==mp.end())
            {
                 mp[sum]=1;
                 n=sum;
            }
            else if(sum==1)
            {
                return true;
            }
            else if(mp.find(sum)!=mp.end())
            {
                return false;
            }

        }
        return true;
    }
};

看原题下的题解找不到合适的,看看这个代码顿时醍醐灌顶,赞👍👍👍

class Solution {
public:
bool isHappy(int n) {
unordered_set<int> myset;
int m = 0;
while (m != 1)
{
m=0;
while (n)
{
int a = n % 10;
m = m + a * a;
n = n / 10;
}
if (myset.count(m))
return false;
else
{
myset.insert(m);
n = m;
}
}
return true;
}
};

typedef struct {
    int key;
    UT_hash_handle hh;
}HashTable;

HashTable *g_users;

/* 计算每个位置上的数字的平方和 */
int GetSum(int n)
{
    int sum = 0;
    while (n) {
        sum += (n % 10) * (n % 10);
        n /= 10;
    }
    return sum;
}

/* 清空哈希表 */
void DelHash()
{
    HashTable *tmp = NULL;
    HashTable *s = NULL;
    HASH_ITER(hh, g_users, s, tmp) {
        HASH_DEL(g_users, s);
        free(s);
    }
}

bool isHappy(int n){
    if (n == 1) {
        return true;
    }
    g_users = NULL;
    int sum;
    HashTable *cur = NULL;
    while (1) {
        sum = GetSum(n);
        if (sum == 1) {
            DelHash();
            return true;
        }
        HASH_FIND_INT(g_users, &sum, cur);
        if (cur != NULL) {
            DelHash();
            return false;
        }
        cur = (HashTable *)malloc(sizeof(HashTable));
        cur->key = sum;
        HASH_ADD_INT(g_users, key, cur);
        n = sum;
    }
}