【每日算法Day 24】算术基础1
一些操作中涉及进位、int值溢出的问题，PCG2面考查过的atoi问题。
# LeetCode 7. 整数反转 (opens new window)
# 题目描述
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
# 示例
示例 1:
输入: -123
输出: -321
示例 2:
输入: 120
输出: 21
2
3
4
5
6
7
# 解题思路
可以转成字符串再翻转（负号、首位为0和溢出需要特别处理），不过效率较低，不赘述了。
可以采用对原数字10取模的方式获得最低位，除10扣去最低位，另一方面翻转数字每次乘10再加上最低位。至于判断可能的溢出方面，结合32位机器能处理最大和最小int值来计算边界。
public static int reverse(int x) {
int reversed=0;
while (x != 0) {
if (reversed>Integer.MAX_VALUE/10||(reversed==Integer.MAX_VALUE/10&&x%10>Integer.MAX_VALUE%10)||
reversed<Integer.MIN_VALUE/10||(reversed==Integer.MIN_VALUE/10&&x%10<Integer.MIN_VALUE%10)
)
return 0;
reversed=reversed*10+x%10;
x/=10;
}
return reversed;
}
2
3
4
5
6
7
8
9
10
11
12
再java虚拟机中判断溢出也可以用下面的方法来判断是否会溢出（其他语言不一定可以）。
public int reverse(int x) {
int ans = 0;
while (x != 0) {
if ((ans * 10) / 10 != ans) {
ans = 0;
break;
}
ans = ans * 10 + x % 10;
x = x / 10;
}
return ans;
}
2
3
4
5
6
7
8
9
10
11
12
# LeetCode 66. 加一 (opens new window)
# 题目描述
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
# 示例
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
2
3
# 解题思路
这一题的考点在于进位的处理。
public int[] plusOne(int[] digits) {
for(int i=digits.length-1;i>=0;i--){
digits[i]+=1;
if(digits[i]==10){
digits[i]=0;
}else{return digits;}
}
int[] res=new int[digits.length+1];
res[0]=1;
System.arraycopy(digits, 0, res, 1, digits.length);
return res;
}
2
3
4
5
6
7
8
9
10
11
12
# LeetCode 8. 字符串转换整数 (atoi) (opens new window)
# 题目描述
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
- 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
- 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
- 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
本题中的空白字符只包括空格字符 ' ' 。 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。
# 示例
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。因此无法执行有效的转换。
2
3
4
5
6
7
8
9
10
11
12
13
14
# 解题思路
使用确定有限状态机(Deterministic Finite Automaton)可以避免写出非常多的条件控制语句。
public int myAtoi(String str) {
Automaton automaton=new Automaton();
for (int i=0;i<str.length();i++) {
automaton.enter(str.charAt(i));
}
return automaton.sign * (int)automaton.ans;
}
private class Automaton {
final String START="start";
final String SIGNED="singed";
final String IN_NUM="in_number";
final String END="end";
String state=START;
Map<String,String[]> map;
int sign=1;
long ans=0;
public Automaton() {
map=new HashMap<>();
map.put(START,new String[]{START,SIGNED,IN_NUM,END});
map.put(SIGNED,new String[]{END,END,IN_NUM,END});
map.put(IN_NUM,new String[]{END,END,IN_NUM,END});
map.put(END,new String[]{END,END,END,END});
}
public int chooseColumn(char c) {
if (c==' ') return 0;
if (c=='+'||c=='-') return 1;
if (Character.isDigit(c)) return 2;
return 3;
}
public void enter(char c) {
if (state.equals(END)) return;
//这里就实现了自动机状态的转换
state=map.get(state)[chooseColumn(c)];
switch (state) {
case SIGNED:
sign=(c=='+')?1:-1;
break;
case IN_NUM:
ans=ans*10+c-'0';
if (sign == 1) {
ans = Math.min(ans, Integer.MAX_VALUE);
} else {
ans = -Math.max(-ans, Integer.MIN_VALUE);
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
时间复杂度：O(n)，其中 n 为字符串的长度。我们只需要依次处理所有的字符，处理每个字符需要的时间为 O(1)。空间复杂度：O(1)，自动机的状态只需要常数空间存储。