算法复健-第二天
今天的两道题是兄弟题 , 所以一共三道题 (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 <= 7columnTitle仅由大写英文组成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;
}