写在前：
- 对于整数反转问题，可以采用栈结构，也可以先转字符串，然后反转，但均不友好。使用数学方式是最优解。
- 对于整数（阿拉伯数字）和罗马数字转换，主要是根据规则进行映射。
1.整数反转（7 - 易）
题目描述：给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 :
输入：x = 120
输出：21
输入：x = -123
输出：-321
思路：注意反转结果用long类型进行存储，最终强转int类型，判断是够存在溢出情况。
代码实现：
public int reverse(int x) {
long n = 0;
while (x != 0) {
n = x % 10 + n * 10;
x /= 10;
}
return (int)n == n ? (int)n : 0;
}
2.字符串转换整数 （8 - 中）
题目描述：函数 myAtoi(string s) 的算法如下：
- 读入字符串并丢弃无用的前导空格
- 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
- 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
- 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
- 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
- 返回整数作为最终结果。
注意：
- 本题中的空白字符只包括空格字符 ' ' 。
- 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
0 <= s.length <= 200-
s由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-'和'.'组成
示例 :
输入：x = 121
输出：true
输入：x = -121
输出：false
思路：字符串转数字注意几个要点：
- 去掉前导空格
- 判断第一个字符+和-的情况，可以用变量flag，初始化1，遇到-，flag修正为-1
- 判断是否为数字，使用ascii码进行判断
- 遇到第一个不为数字字符情况，就停止转换，退出循环
- 如果转换以后的数字超过了 int 类型的范围，需要截取。这里不能将结果 res 变量设计为 long 类型，注意：由于输入的字符串转换以后也有可能超过 long 类型，因此需要在循环内部就判断是否越界，只要越界就退出循环，这样也可以减少不必要的计算
特别注意：
- 由于题目中说「环境只能保存 32 位整数」，因此这里在每一轮循环之前先要检查乘以 10 以后是否溢出
- Java 、Python 和 C++ 字符串的设计都是不可变的，所以使用 trim() 会产生新的变量，因此我们尽量不使用库函数，使用一个变量 index 去做遍历，这样遍历完成以后就得到转换以后的数值。
代码实现：
public int myAtoi(String s) {
int n = s.length();
char[] chs = s.toCharArray();
int index = 0;
// 1.去掉先导空格
while (index < n && chs[index] == ' ') {
index++;
}
// 特殊情况，全是空格，已经完成遍历
if (index == n) return 0;
// 2.判断正负
int flag = 1;
char sign = chs[index];
if (sign == '+') {
index++;
} else if (sign == '-') {
flag = -1;
index++;
}
// 3.将字符转换为数字，ans为int类型，题目要求
int ans = 0;
while (index < n) {
char curChar = chs[index];
// 不为数字字符，直接终止
if (curChar < '0' || curChar > '9') {
break;
}
// 环境只能保存 32 位整数， 转化之前，先判断是否溢出
if (ans > Integer.MAX_VALUE / 10 || ans == Integer.MAX_VALUE / 10 && (curChar - '0') > Integer.MAX_VALUE % 10) {
return flag > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
// 符合条件的进行转化
ans = ans * 10 + curChar - '0';
index++;
}
return flag > 0 ? ans : ans * flag;
}
3.回文数（9 - 易）
题目描述：给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
示例 :
输入：x = 121
输出：true
输入：x = -121
输出：false
思路：定义一个变量right记录右部分，对于左部分直接复用x，最终记得判断一下整数位数奇偶情况。
注：负数一定不回文，0是回文。
代码实现：
public boolean isPalindrome(int x) {
if (x == 0) return true;
if (x < 0 || x % 10 == 0) return false;
int right = 0;
while (x > right) {
right = x % 10 + right * 10; //更新右半部分
x = x / 10; //更新左半部分（复用x）
}
return x == right || x == right / 10;
}
4.整数转罗马数字（12 - 中）
题目描述：罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
- I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
- X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。
示例 :
输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
思路：建立映射，然后从左到右构建罗马数字，优先构建数值高的罗马字符（如果有足够的分值，尽量尝试构建 "M"，直到分值不够，再尽量尝试构建 "CM" ... ）
代码实现：
public String intToRoman(int num) {
int[] val = new int[] {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] str = new String[] {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
StringBuilder ans = new StringBuilder();
for (int i = 0; i < val.length && num > 0; i++) {
int cv = val[i];
String cs = str[i];
while (num >= cv) {
ans.append(cs);
num -= cv;
}
}
return ans.toString();
}
5.罗马数字转整数（13 - 易）
示例 :
输入: "IV"
输出: 4
思路：与上题类似，从左向右构建整数，优先匹配数值高的罗马字符即可。
代码实现：
public int romanToInt(String s) {
int[] val = new int[] {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] str = new String[] {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int n = s.length();
int ans = 0, j = 0;
for (int i = 0; i < str.length && j < n; i++) {
int cv = val[i];
String cs = str[i];
int size = cs.length();
while (j + size <= n && s.substring(j, j + size).equals(cs)) {
ans += cv;
j += size;
}
}
return ans;
}
网友评论