算法复健-第二天

今天的两道题是兄弟题 , 所以一共三道题 (Easy题确实水 , 但是有些地方也蛮值得思考)

Math-Easy-Excel表列名称+Excel表列序号

题面 – Excel表列名称

给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

例如：

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

示例 1：

输入：columnNumber = 1
输出："A"

示例 2：

输入：columnNumber = 28
输出："AB"

示例 3：

输入：columnNumber = 701
输出："ZY"

示例 4：

输入：columnNumber = 2147483647
输出："FXSHRXW"

提示：

• 1 <= columnNumber <= 2^31 - 1

题面 – Excel表列序号

给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。

例如：

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

示例 1:

输入: columnTitle = "A"
输出: 1

示例 2:

输入: columnTitle = "AB"
输出: 28

示例 3:

输入: columnTitle = "ZY"
输出: 701

提示：

• 1 <= columnTitle.length <= 7
• columnTitle 仅由大写英文组成
• columnTitle 在范围 ["A", "FXSHRXW"] 内

解答过程

不难看出这两道题互为逆运算 , 列名称为十进制转26进制 , 列序号为26进制转十进制 , 但要注意的是 , 这两道题中’A’代表的是26进制的’1′ , 即本题的26进制中数字范围为[1,25] , 所以在十进制转26进制时需要特别注意 , 除了这点 , 本题只需写一个正常的进制转换就行 , 即列名称模拟短除法 , 列序号则正常累加出结果 , 如果有困难可以参考二进制与十进制互转

代码

列名称

string convertToTitle(int columnNumber) {
        string ans;
        int bit26[8],bit10 = columnNumber;
        int count = 0; // 位数
        while (bit10 >= 26)
        {
            if (bit10 % 26 == 0)
            {
                bit26[count] = 26;
                bit10--;
            }
            else{
                bit26[count] = bit10 % 26;
            }
            count++;
            bit10 /= 26;
        }
        if (bit10 == 0) 
        {
            count--;
        }
        else{
            bit26[count] = bit10;
        }
        for (size_t i = 0; i <= count ; i++)
        {
            ans.push_back('A' - 1 + bit26[i]);
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }

列序号

int titleToNumber(string columnTitle) {
        int ans = 0;
        reverse(columnTitle.begin(),columnTitle.end());
        for (size_t i = 0; i < columnTitle.size(); i++)
        {
            ans += (columnTitle[i] - 'A' + 1) * pow(26,i);
        }
        return ans;
    }

Math-Easy-快乐数

题面

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

「快乐数」 定义为：

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

• 1 <= n <= 2^31 - 1

解答过程

本题初见没有摸着什么头脑 , 显然直接暴力是不现实的 , 则一定有玄机 , 思考一下发现可能有以下三种情况 : 结果为1 , 无限循环 , 结果无限递增

动笔分析 , 发现三位数最大的数(999)的三位数字平方和为241 , 也就是说 , 三位数的每位数字平方和必少于或等于三位 , 三位数以上数的每位数字平方和会永远递减 到三位数及以下 , 所以循环的结果一定不可能是无限递增 , 只有为1 , 无限循环两种情况 , 故想到使用哈希表成功解决问题.

每次重复这个过程后把结果存储到哈希表 , 一直重复这个过程 , 直到结果为1或者在哈希表中找到了同样的数字, 跳出循环

代码

bool isHappy(int n) {
        int num = n;
        unordered_multimap<int,int> map ;
        while (map.find(num) == map.end())
        {   
            map.insert({map.size(),num});
            string sum = to_string(num);
            num = 0;
            for (size_t i = 0; i < sum.size(); i++)
            {
                num += pow(sum.at(i) - '0',2);
            }
            if (num == 1)
            {
                return true;
            }
        }
        return false;   
    }