手把手教你如何玩转：面试的一些算法题

1：输入参数，两个数组，输出两个数组的公共元素。-—————-这个是阿里二面的一个题，虽然简单，但是可以看出一个人的算法水平，因为时间复杂度做出来会不一样

解答：其实这个问题并不难，就单纯的两个for也可以解决问题，但是这样的时间复杂度就是O(n^2)，这样必然不是一个好的算法，其实这个题，只需要O（K），其中K为两个数组中的最大值，代码如下：

public static int[] getSameNumber(int []array1, int []array2){  
        int[] array3;  
        int i=0,j=0,k=0;      
        Arrays.sort(array1);//先对两个数组排序   
        Arrays.sort(array2);  
        if(array1.length < array2.length){//定义数组长度，长度为两个数组长度小的  
            array3 = new int[array1.length];  
        }else{  
            array3 = new int[array2.length];  
        }  
        while( i< array1.length && j<array2.length){//遍历数组，看代码就明白了 
            if(array1[i] > array2[j]){  
                j++;  
            }else if(array1[i] < array2[j]){  
                i++;  
            }else{  
                array3[k] = array1[i];  
                i++;  
                j++;  
                k++;  
            }  
        }  
        array3 = Arrays.copyOf(array3, k);//之所以要这样，是因为初始化的时候，数组都是0，而如果公共元素没有那么多，就还有0占着，所以要去掉后面为0的内容  
        return array3;  
    }

2：输入一个int数字，使用递归，不能有全局变量，实现逆序输出该数字的字符串形式。————同样也是阿里二面的一个算法题目

比如：输入123

输出就为：“321”

解答：这个题，看起来，有点奇怪，但是并不难，关键要明白一个思路，就是前后两位，相差的是10倍的关系，我自己在做这个题目的时候，也是想到这里，才茅塞顿开，一下写出来的，所以关键还是要审题。代码如下：（后面看了下，好像还有人通过树来实现了，也是可以的）

//输入整数后，逆序输出为字符串，通过递归实现  
    public static String reverseIntNumber(int number){  
        if (number < 0) return "";  
        if( number <10) return Integer.toString(a);  
        int lastNumber = number - ( number/10 ) *10;//既然是逆序输出，那么就要从后面的数字开始，所以取得这个整数的最后一位  
        return Integer.toString(lastNumber) + reverse(a/10);//这样递归，就可以实现了  
    }

3：交换Integer类型的两个参数的值。函数定义如下; ———-一个超牛逼互联网公司的一面试题，你懂的

public void swap(Integer first , Integer second){

}

比如：输入参数为：3,5,

输出：5,3

解答：关于这个题，其实还是有难度的，因为真正的要实现的话，里面包含的知识点可是非常多的，下面我来说明一下吧，自己在做的时候，也没全对，我也会着重讲解一下：

代码如下：

try{
     Field field = Integer.class.getDeclareField("value');
    field.setAccessible(true);
    int temp = first.intValue();
    field.set(first ,  second);
    field.set(second , new Integer(temp));//主动new下，是不走自动装箱操作
    //或者用下面的这句
    field.setInt(second , temp); //setInt方法也不会产生自动拆箱的
}catch(Exception e){
   e.printStackTrace();
}

哇塞，，看完解析感觉怎么样呢？有没有发现原来写的交换都是假的呢？当然，这个题确实有点难度，这要求对JDK源码有一定的了解，而且对Integer包装类型有一定的了解才行，我自己在做的时候，在后面也是直接set两次，所以还是出问题了，只交换了a的值，b的值还是自己。好了，我来说一下，这个题涉及到的知识点吧。当然，这个也是自己在后面写完这个题的时候，去网上查阅资料和看JDK的源码才给的一点见解，如果有问题，欢迎指出。。

知识点一：Java访问对象的方式

在 Java 堆中还必须包含能查找到此对象类型数据（如对象类型、父类、实现的接口、方法等）的地址信息，这些类型数据则存储在方法区中。
既然java栈中的是对象的引用，那么我们如何使用对象那，主流的访问方式有两种：使用句柄和直接指针。
（1）使用句柄：
如果使用句柄访问方式， Java 堆中将会划分出一块内存来作为句柄池，reference 中存储的就是对象的句柄地址，而句柄中包含了对象实例数据和类型数据各自的具体地址信息，如图：

（2）直接指针
如果使用直接指针访问方式， Java 堆对象的布局中就必须考虑如何放置访问类型数据的相关信息， reference 中直接存储的就是对象地址，如图：

这两种对象的访问方式各有优势，使用句柄访问方式的最大好处就是 reference 中存储的是稳定的句柄地址，在对象被移动（垃圾收集时移动对象是非常普遍的行为）时只会改变句柄中的实例数据指针，而 reference 本身不需要被修改。
使用直接指针访问方式的最大好处就是速度更快，它节省了一次指针定位的时间开销，由于对象的访问在 Java 中非常频繁，因此这类开销积少成多后也是一项非常可观的执行成本。
接着我们回到正题，这里也是今天要讲的第一个知识点：Java的传值在java中，有两种传值方式：一种是按值传递，一种是引用传递！
那么，按值传递意味着将当前的参数传递给方法的时候，方法中的变量接收的是传过来变量的副本值（相当于拷贝了一份值），因此，我们修改了方法里面的变量的值，并不会改变外面变量的值。
引用传递：传递的是指向值的地址的指针
那么，请问大家，这里是按值传递还是引用传递？好，老司机告诉你们，这里是按值传递，为什么？Integer不是对象吗？对象传递不是传递的指针吗？大家有没有去看过Integer类的源码，看看这个类是怎么定义的，我们来看下，实际上面Integer使用的final定义的，也就意味着通过Integer实例化的对象是不能改变的，跟String是不是差不多。所以这里的话，是传递的值，我们来画下图：

知识点二：Java运行时数据区域

那么，我们首先看一下Java运行时数据区域：
我们一般在开发中认为JVM不过有堆和栈两部分组成，但是实际的Java 虚拟机在执行 Java 程序的过程中会把它所管理的内存划分为若干个不同的数据区域。这些区域都有各自的用途，以及创建和销毁的时间，有的区域随着虚拟机进程的启动而存在，有些区域则是依赖用户线程的启动和结束而建立和销毁。如下图：

Java中的内存主要分为两块把：堆和栈，栈存储变量本身，堆存储对象的值，然后通过栈执行堆内存地址来建立关系。
通过swap方法后：意味着，会同样创建两个变量num1和num2,他们的值是刚刚拷贝过来的ab的值，此时内存中时怎么变化的呢：

大家，知道为什么会有地址指针这个东西，主要是我们的堆内存他主要是存储的是一些对象，对象是最占内存的，为了能够节省对内从的空间，就出现了这种概念。好，讲到这里，至少大家应该清楚了一点：引用传递和按值传递的不同。
我们再来看，这个Integer他内部是如何赋值的，我们来看下：进入Integer类Ctrl+o搜索Integer构造方法：

然后我们发现这个value定义的是final类型的：

如果他有一个setValue()的方法的话，那么我们是是不是可以通过这个方法来改变值，但是Integer并没有提供。也就是说这种方法是行不通的，好，那么我们今天讲到第二个知识点：反射有没有人在做这个题目的时候有没有想过用反射来实现？
有想过的，看有多少人有往这个方面去想，我们刚刚看到Integer类中存在一个value值变量吗？对吧，所以我们需要拿到这个value变量然后来改变他的值，对吧，那么我们怎么来做，我们可以通过反射的方式拿到这个变量，这个Filed，然后去改变他的值，对吧。我们来看下怎么写：

try{
     Field field = Integer.class.getDeclareField("value');
    int temp = first.intValue();
    field.set(first ,  second);
    field.set(second , new Integer(temp));//主动new下，是不走自动装箱操作
    //或者用下面的这句
    field.setInt(second , temp); //setInt方法也不会产生自动拆箱的
}catch(Exception e){
   e.printStackTrace();
}

理论上来说，这种方式是一定能够实现我们的要求的.Run下：报错：“Class com.edu.example.test.Test can not access a member of class java.lang.Integer with modifiers “private final””

知识点三：私有的成员属性是不能通过反射来赋值的！

这个问题的话，还是比较好解决的，就是可以进去看看Feild的源码，可以通过设置一个flag就可以，所以就有了下面的这个代码：

 field.setAccessible(true);

如果按照这样的话，运行后，确实是没有发生错误，但是但是但是，，并没有交换，知识first的值变为了second，而second的值并没有改变

知识点四：Java中的装箱和拆箱

装箱：把基本类型用它们相应的引用类型包装起来，使其具有对象的性质。int包装成Integer、float包装成Float;
拆箱：和装箱相反，将引用类型的对象简化成值类型的数据;
Integer a = 100; // 这是自动装箱 (编译器调用的是static Integer valueOf(int i))
int b = new Integer(100); //这是自动拆箱

而且进入源码可以看看Integer，它在-128–127的值都是直接从缓存拿到的，所以如果有Integer对象在这个范围进行比较的话，返回的都是同一个引用，所以比较就是相等的，这也就引发了一个问题，就是当比较Integer对象的时候，要注意将这个转为int类型，比如可以first.intValue()，然后再比较，所以这样就不是从缓存中拿了，既然知道了这个知识点，所以再对上面的代码进行改造，就成为了正确的答案了。

哇塞，，，回头再看看这个问题，是不是觉得，一个交换就让自己长知识了呢？确实，多了解下JDK很多的源码还是有必要性的。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/12372.html