前言：
笔者小菜一枚，大学学的设计专业，毕业之后抢了程序员的饭碗来搞 Android 开发，自己知道底子薄弱，经常自习框架源码，买了几本算法的书籍，还没排上号，在未刷题情况下，参加了一次今年的面试，试了试水。笔者敢不怕被嘲笑，希望对你有些许帮助吧。
正题：
1、手动 Java 实现栈
答案：
栈示意图
栈是后进先出的形式进行存取数据的，
1)、基于集合实现
public class TestOne {
private int size;//栈的容积
private int top;
private char[] content;
public TestOne(int size) {
this.size = size;
top = -1;
content = new char[size];
}
//入栈
public void pusha(char value) {
content[++top] = value;
}
//出栈
public char out() {
return content[--top];
}
//获取栈顶元素
public char topContent() {
return content[top];
}
//判断是否满了
public boolean isFull() {
return size - 1 == top;
}
//判断是否为空
public boolean isEmpty() {
return top == -1;
}
}
2)、基于链表实现
import java.util.LinkedList;
public class TestOne {
//容器
private LinkedList<Object> tasks = new LinkedList<>();
//入栈
public void push(Object o) {
tasks.add(o);
}
//出栈
public Object out() {
return tasks.removeFirst();
}
//获取元素（第一个元素）
public Object getTop() {
return tasks.getFirst();
}
//判断是否为空
public boolean empty() {
return tasks.isEmpty();
}
}
回来琢磨琢磨，感觉也没什么，面试的时候 笔者就把 Activity 的栈模型给画上了，没有写东西，估计这一点人家就深深的感觉到了笔者菜鸡的本质。不过重在积累，下次就好了。
2、将 String="1234"; 转换为 int =1234;
笔者第一想法 ：这不是在嘲笑我这只菜鸡呢？二话没说 上去就写了个
String s = "1234";
int i = Integer.parseInt(s);
结果是：面试官下了逐客令。原来人家让笔者写具体转换逻辑呢。。。
我们来看一下这个方法的具体逻辑吧，方便记忆。
跟着方法追进去 是这样的，
//调用的同名重载方法 抛了个数字转换异常
public static int parseInt(String s) throws NumberFormatException {
return parseInt(s,10);
}
我们来看看他的重载方法
public static int parseInt(String s, int radix)
throws NumberFormatException
{
/*
* WARNING: This method may be invoked early during VM initialization
* before IntegerCache is initialized. Care must be taken to not use
* the valueOf method.
*/
// 下面三个判断好理解，其中表示进制的 radix 要在（2~36）范围内
if (s == null) {
throw new NumberFormatException("null");
}
if (radix < Character.MIN_RADIX) {
throw new NumberFormatException("radix " + radix +
" less than Character.MIN_RADIX");
}
if (radix > Character.MAX_RADIX) {
throw new NumberFormatException("radix " + radix +
" greater than Character.MAX_RADIX");
}
int result = 0; // 表示结果， 在下面的计算中会一直是个负数，
// 假如说 我们的字符串是一个正数 "7" ，
// 那么在返回这个值之前result保存的是 -7，
// 这个可能是为了保持正数和负数在下面计算的一致性
boolean negative = false;
int i = 0, len = s.length();
//limit 默认初始化为 最大正整数的 负数 ，假如字符串表示的是正数，
//那么result(在返回之前一直是负数形式)就必须和这个最大正数的负数来比较，判断是否溢出
int limit = -Integer.MAX_VALUE;
int multmin;
int digit;
if (len > 0) { // 首先是对第一个位置判断，是否含有正负号
char firstChar = s.charAt(0);
if (firstChar < '0') { // Possible leading "+" or "-"
if (firstChar == '-') {
negative = true;
// 这里，在负号的情况下，判断溢出的值就变成了 整数的 最小负数了。
limit = Integer.MIN_VALUE;
} else if (firstChar != '+')
throw NumberFormatException.forInputString(s);
if (len == 1) // Cannot have lone "+" or "-"
throw NumberFormatException.forInputString(s);
i++;
}
multmin = limit / radix;
// 这个是用来判断当前的 result 在接受下一个字符串位置的数字后会不会溢出。
// 原理很简单，为了方便，拿正数来说
// （multmin result 在计算中都是负数），假如是10
// 进制,假设最大的10进制数是 21，那么multmin = 21/10 = 2,
// 如果我此时的 result 是 3 ，下一个字符c来了，result即将变成
// result = result * 10 + c;那么这个值是肯定大于 21 ，即溢出了，
// 这个溢出的值在 int里面是保存不了的，不可能先计算出
// result（此时的result已经不是溢出的那个值了） 后再去与最大值比较。
// 所以要通过先比较 result < multmin （说明result * radix 后还比 limit 小）
while (i < len) {
// Accumulating negatively avoids surprises near MAX_VALUE
digit = Character.digit(s.charAt(i++),radix);
if (digit < 0) {
throw NumberFormatException.forInputString(s);
}
// 这里就是上说的判断溢出，由于result统一用负值来计算，所以用了 小于 号
// 从正数的角度看就是 reslut > mulmin 下一步reslut * radix 肯定是 溢出了
if (result < multmin) {
throw NumberFormatException.forInputString(s);
}
result *= radix;
// 这里也是判断溢出， 由于是负值来判断，相当于 （-result + digit）> - limit
// 但是不能用这种形式，如果这样去比较，那么得出的值是肯定判断不出溢出的。
// 所以用 result < limit + digit 很巧妙
if (result < limit + digit) {
throw NumberFormatException.forInputString(s);
}
result -= digit; // 加上这个 digit 的值 （这里减就相当于加）
}
} else {
throw NumberFormatException.forInputString(s);
}
return negative ? result : -result; // 正数就返回 -result
}
3、 其他问题 简单的不值得一提。
未完待续，下次面试继续 ，直到找到工作为止。
网友评论