目录
- 一、概念
- 二、模板
- 三、例题
- 题：202. 快乐数
- 解：
- 题：168. Excel表列名称
- 解：
- 题：171. Excel 表列序号
- 解：
- 题：483. 最小好进制
- 解：
一、概念
转化不常用的进制、对应偏移
二、模板
看例题
三、例题
题：202. 快乐数
编写一个算法来判断一个数 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 <= 231 - 1
解：
解题思路：双指针 => 链表找环
情况1：
情况2：
情况3：值会越来越大，最后接近无穷大。（排除）
AC代码：
class Solution {
public boolean isHappy(int n) {
int l = n, f = getNext(n);
while(f != 1 && l != f) {
l = getNext(l);
f = getNext(getNext(f));
}
return f == 1;
}
int getNext(int num) {
int x = 0;
while(num != 0) {
int digit = num % 10;
x += digit * digit;
num /= 10;
}
return x;
}
}题：168. 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 <= 231 - 1
解：
解题思路：数学模拟
AC代码：
class Solution {
public String convertToTitle(int columnNumber) {
StringBuilder res = new StringBuilder();
while(columnNumber != 0) {
int digit = (columnNumber - 1) % 26 + 1; // 1-26对应
res.append((char)('A' + digit - 1));
columnNumber = (columnNumber - digit) / 26; // 这里要减去digit
}
return res.reverse().toString();
}
}解题思路：因为有错位问题，所以这里有简洁的写法AC代码：
class Solution {
public String convertToTitle(int columnNumber) {
StringBuilder res = new StringBuilder();
while(columnNumber != 0) {
-- columnNumber;
res.append((char)('A' + columnNumber % 26));
columnNumber = columnNumber / 26;
}
return res.reverse().toString();
}
}题：171. 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"] 内
解：
解题思路：数学模拟
AC代码：
class Solution {
public int titleToNumber(String columnTitle) {
int x = 0;
for(char c : columnTitle.toCharArray()) {
x = x * 26 + (int)(c - 'A' + 1);
}
return x;
}
}题：483. 最小好进制
以字符串的形式给出 n , 以字符串的形式返回 n 的最小 好进制 。
如果 n 的 k(k>=2)进制数的所有数位全为1，则称 k(k>=2) 是 n 的一个 好进制 。
示例 1：
输入：n = "13"
输出："3"
解释：13 的 3 进制是 111。
示例 2：
输入：n = "4681"
输出："8"
解释：4681 的 8 进制是 11111。
示例 3：
输入：n = "1000000000000000000"
输出："999999999999999999"
解释：1000000000000000000 的 999999999999999999 进制是 11。
提示：
n 的取值范围是 [3, 1018]
n 没有前导 0
解：
解题思路：数学推导
AC代码：
class Solution {
public String smallestGoodBase(String n) {
long m = Long.parseLong(n);
int max = (int)(Math.log(m) / Math.log(2) + 1);
for (int len = max; len >= 3; len--) {
long k = (long)Math.pow(m, 1.0 / (len - 1));
long res = 0;
for (int i = 0; i < len; i++) res = res * k + 1;
if (res == m) return String.valueOf(k);
}
return String.valueOf(m - 1);
}
}