ch3_4 快乐数字 ch3_5 数组中的两数之和

1. 快乐数字

快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 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$

1.1 解题步骤

1. 对当前的数值，写出各个位上的数字的平方和函数；
   1. 通过求模运算， 先求出当前数最低位上 数字的平方和；
   2. 从地位到高位， 将当前数更新为 整除 10 后的数；

2. 判断是否是快乐数：
   新建一个 关联式容器， unorder_set:
   条件始终为真的循环， （循环内部 跳出）
   获取最后一个平方和；
   判断最后的平方和是否为1; 若是， 返回true；

   判断 该平方和 是否出现在 容器中，
   若果出现过，说明陷入了循环， 返回 false;
   否则， 将该平方和 插入到 关联式容器中；

   更新 当前数 = 平方和

1.2 code

#include "unordered_set"

using namespace std;


class Solution{
    
public:
    int getSum(int n){
    
        int sum = 0;
        while(n){
    
            sum += (n % 10) * (n % 10);
            n = n / 10;
        }
        return  sum;
    }

    bool isHappy(int& n){
    

        unordered_set<int>  set;
        while(1){
    

            int cur_sum = getSum(n);
            if (cur_sum == 1) return  true;
            // 当前值 不为空， 说明在容器中查找到了； 说明sum 进入循环了， 返回 false ，不是快来数字；
            if( set.find( cur_sum ) != set.end()){
    
                return false;}else {
    
                set.insert(cur_sum);
            }

            n = cur_sum;
        }
    }

};

2. 数组中的两数之和

考虑到， 数组和集合set 自身的局限性：

1. 数组的大小受限， 而且如果元素很少，而哈希值太大会造成内存空间的浪费。

2. set是一个集合，集合中只能存放一个 key (关键字)， 而不能存放关键字所对应的值; 本题要判读 关键字（数组中的元素) 是否存在， 还要保存 关键字所对应的值（数组元素所对应的下标），所以 最小组成成分，是由两个元素构成， 故set 不用，使用map;

2.1 解题步骤

解题前， 先了解一下知识点；

1.关联式容器中的哈希容器 unordered_map
2. 使用了 容器中的 find(), end(), insert() 这三种内置方法；
3. 使用了 auto 自动变量类型推导
4. 使用 pair 类模板；

#include "vector"
#include "unordered_map"
#include "iostream"
#include "utility"
using namespace std;


class  Solution{
    
public:
    vector<int> twoSum(vector<int>& nums, int target){
    
        unordered_map<int, int> map;
        for(int i = 0 ; i < nums.size(); i++){
    
            auto it = map.find(target - nums[i]);
            if (it != map.end()){
     return  {
    it->second, i};}  // 注意这里， 返回的是两个下标， 第一个 it->second 返回的是map中的 单个项的下标， 第二个i 返回的当前数组的下标， 代表了找到与map中匹配的数字，
            map.insert(pair<int, int>(nums[i], i)) ;  // 这里使用了 内置的 pair类模板； 并且初始化其中的数值， 然后将其插入到 map 中；
        }


    }


};

0. 函数返回的是一个序列式中的向量容器， 函数 传入的参数是（向量容器的 引用， 整型数字）

1. 声明一个unordered_map 的关联式容器，里面的每一项都是一组键值对的存在形式<key, value> , 用来存放 数组中的数值， 和该数值所对应的数组下标；

2. 遍历数组，
   遍历过程中， 使用关联式容器的查找方法， 在容器中查找当前的数组值，
   将 查找到的结果 赋值 一个 自动变量类型的 item
   如果该 item != 容器的结尾， 表明在容器中查找到所需要的值：
   则返回该值所对应的 项

   否则，没有查到：
   则将 数组的数值，和下标 使用 pair 构成一组键值对， 插入到 map容器中；