面经

链接：[https://www.nowcoder.com/discuss/35473]
首先进行一个小时的笔试。一面的主要内容就是讨论笔试题，然后聊了一些简历上的东西。面试官人很和蔼，沟通起来不累。笔试题如下：

1、有一个数组包含1000w个整数，给定一个整数n，在数组中找到所有ai和bi，使得ai+bi=n，写出代码。

首先想到了暴力法，时间复杂度是O(n^2)，然后使用了一个桶排序优化暴力。其实能不能优化心里也不清楚，感觉可以就写上了。

补充：感谢 @zssasa
Two Sum问题：[http://blog.csdn.net/u010429424/article/details/77648989]

public int[] twoSum(int[] numbers,int target){
    HashMap<Integer,Integer> map=new HashMap<>();
    int[] res=new int[2];
    for (int i = 0; i <numbers.length ; i++) {
        if(map.containsKey(numbers[i])){
            res[0]=map.get(numbers[i])+1;
            res[1]=i+1;
            break;
        }else {
            map.put(target-numbers[i],i);
        }
    }
    return res;
}

2、二叉树，找到两个节点的最近公共父节点，写出代码。

由于题目没有给出二叉树的输入形式，因此根据以往的做题经验，如果二叉树以数组的形式给出，则直接用公式就能计算出父节点。比如二叉树【1，2，3，4，5】，则4、5的父节点下标为(3-1)/2 = 1和(4-1)/2 = 1。

20170828123905634.jpg

如果二叉树以树的形式给出，分两种情况考虑，如果二叉树节点中有指向父节点的指针，则可以通过这个指针很方便地找到公共父节点。如果二叉树中没有指向父节点的指针，则先通过dfs找到根节点到4、5节点的路径：1、2、4和1、2、5，路径使用链表存储，然后从4、5向前找到第一次出现的公共节点。

但是面试官说，通过遍历树会有更好的方法。

补充：通过后续遍历，可以解决这个问题：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == p || root == q || root == null)
        return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left == null) {
        return right;
    } else if (right == null) {
        return left;
    } else {
        return root;
    }
}

3、一个袋中有n个球，球上面有标号，标号可以相同也可以不同。如果袋中球的编号之和大于编号之积，则叫做幸运袋，反之就是不幸运的。比如【1、3】1+3 > 1* 3就是幸运的；【2、3】，2+3 < 2 * 3就是不幸运的。现在给出一个有n个球的袋子，可以去掉m个球使得剩余的球构成幸运袋，问能够成的幸运袋的个数，写出代码。

深度优先遍历

public class YiQiu {
    public static  int getNum(int[] a,int start,long sum,long multi){
        int res=0;
        for (int i = start; i <a.length ; i++) {
            sum+=a[i];
            multi*=a[i];
            if(sum>multi){
                res+=1+getNum(a,i+1,sum,multi);
            }
            else if(a[i]==1){
                res+=getNum(a,i+1,sum,multi);
            }
            else {
                break;
            }
            sum=sum-a[i];
            multi=multi/a[i];
            for (; (i < (a.length-1))&&(a[i]==a[i+1]); i++) ;

        }
        return  res;
    }

    public static void main(String[] args) {
        int[] a={1,1,2,3};
        System.out.println(getNum(a,0,0,0));
    }
}

4、通过IP怎么查找到城市。给出一组IP地址和对应的城市名，问使用怎样的数据结构，能够找到城市，写出代码。

第一个思路使用Trie树来存储IP，叶子节点对应城市。但看到题目的函数输入是整型的ip，瞬间感觉也可以用Hash来做，key是ip，value是对应的城市。因为不知道怎样把ip转换成int，被面试官鄙视了。。。。（当时说ip本质上也是用二进制来表示的，因此可以通过位运算转换成int）

补充：Ip转long http://www.mkyong.com/java/java-convert-ip-address-to-decimal-number/

public long ipToLong(String ipAddress){
    String[] ipAddressArray=ipAddress.split("\\.");
    long res=0;
    for (int i = 0; i <ipAddressArray.length ; i++) {
        int power=3-i;
        int ip=Integer.parseInt(ipAddressArray[i]);

        res += ip*Math.pow(256,power);
    }
    return res;
}

5、编辑器的undo撤销，redo恢复怎样实现，写出代码。

看到这道题的第一反应就是Git。但是不懂git的数据结构，只能装模作样地设计了一个双向链表。这样，通过指针的改变就能很快地前移和后退。结构又被面试官鄙视了~
（补充：后来听同学讲可以用两个栈来实现，
参考：
http://blog.csdn.net/cb0912cn/article/details/444393）

一 定义栈结构
Public Type stack
Num As Integer '记录栈的大小
contents As String '记录内容
Pos As Long '记录光标位置
End Type
分别需要两个栈，一个栈stackundo来存放撤消内容，一个栈stackredo来存放恢复内容
二 在文本内容改变的同时，将文本内容，以及此时光标位置存入栈stackundo中。
三 进行undo操作后，把undo前的内容和光标位置存入栈stackredo中，同时在栈stackundo中清除该内容。
四 进行redo操作后，把redo前的内容和光标位置存入栈stackundo中，同时在栈stackredo中清除该内容。
通过上述过程就能很简单的实现无限次undo和redo操作。