学习面试题-阿里篇

1.如何实现一个高效的单向链表逆序输出？

递归与非递归方式

package wg;
public class Solution {
    static class Node<T> {//内部类
        Node next;
        T t;
        Node(T t) {
            this.t = t;
        }
        Node(){
        }
    }
    //递归方式实现反转
//递归方式：实现单链表反转
    public static Node ReverseList(Node head)
    {
        //递归终止条件：找到链表最后一个结点
        if (head == null || head.next == null)
            return head;
        else
        {
            Node newhead = ReverseList(head.next);//先反转后面的链表，从最后面的两个结点开始反转，依次向前
            head.next.next = head;//将后一个链表结点指向前一个结点 =>这就是最后一个节点得next head.next是最后一个节点 head是倒数第二个节点
            head.next = null;//将原链表中前一个结点指向后一个结点的指向关系断开
            return newhead;
        }
    }
    // 非递归方式实现反转
    public static void reverse(Node head){
        System.out.println("非递归逆序:");
        Node cur = head.next;
        // 新建链表节点
        Node pre = null;
        Node tmp = new Node();
        while(cur != null){
            tmp = cur.next;//tmp作为中间节点，记录当前结点的下一个节点的位置，因为下一步让该节点与下一个节点得联系断了，不提前存储就找不到了
            cur.next = pre;//断开该节点与下一个节点得联系  当前结点指向前一个节点
            pre = cur;//指针后移
            cur = tmp;////指针后移，处理下一个节点
        }
        //输出逆序
        while (pre != null) {
            System.out.print(pre.t+" ");
            pre = pre.next;
        }
    }
    public static void main(String[] args) {
            Node head = new Node();
            Node node= new Node(1);
            Node node2 = new Node(2);
            Node node3 = new Node(3);
            Node node4 = new Node(4);
            head.next = node;
            node.next = node2;
            node2.next = node3;
            node3.next = node4;
            Node head2 = head;
            head=head.next;
            while (head != null) {
                System.out.print(head.t+" ");
                head = head.next;
            }
            System.out.println("");
            //非递归
            reverse(head2);
            //递归
//            Node newhead = ReverseList(head2);
//            while (newhead.next != null) {
//                System.out.print(newhead.t+" ");
//                newhead = newhead.next;
//            }
    }
}

2.已知 sqrt (2)约等于 1.414，要求不用数学库，求 sqrt (2)精确到小数点后 10 位。

二分法,牛顿迭代法
已知 sqrt(2)约等于 1.414，那么就可以在(1.4, 1.5)区间做二分
查找，如：
a) high=1.5
b) low=1.4
c) mid = (high+low)/2=1.45
d) 1.45*1.45>2 ? high=1.45 : low = 1.45
e) 循环到 c)
退出条件
前后两次的差值的绝对值<=0.0000000001, 则可退出

package wg;
public class Solution {
    static final double EPSILON = 0.0000000001;
    public static double sqrt2(){
        double high = 1.5;
        double low = 1.4;
        double mid = (high+low)/2;
        while (high - low > EPSILON){
            if(mid*mid>2){
                high = mid;
            }else{
                low = mid;
            }
            mid = (high+low)/2;
        }
        return mid;
    }
    public static void main(String[] args) {
        System.out.println(sqrt2());
    }
}
//1.4142135623376817

3.给定一个二叉搜索树(BST)，找到树中第 K 小的节点

递归求解，左右子树分别遍历。联想到二叉搜索树的性质，root 大于左子树，小于右子树，如果左子树的节点数目等于 K-1，那么 root 就是结果，否则如果左子树节点数目小于 K-1，那么结果必然在右子树，否则就在左子树。因此在搜索的时候同时返回节点数目，跟 K 做对比，就能得出结果了。

示例 1:
输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 3

使用中序遍历

package wg;
import java.util.ArrayList;
import java.util.List;
public class Solution {
    public static class TreeNode {
        // 左节点(儿子)
        private TreeNode lefTreeNode;
        // 右节点(儿子)
        private TreeNode rightNode;
        // 数据
        private int value;
        public TreeNode() {
            super();
        }
        public TreeNode(int value) {
            super();
            this.value = value;
        }
        public TreeNode getLefTreeNode() {
            return lefTreeNode;
        }
        public void setLefTreeNode(TreeNode lefTreeNode) {
            this.lefTreeNode = lefTreeNode;
        }
        public TreeNode getRightNode() {
            return rightNode;
        }
        public void setRightNode(TreeNode rightNode) {
            this.rightNode = rightNode;
        }
        public int getValue() {
            return value;
        }
        public void setValue(int value) {
            this.value = value;
        }
    }
    //根节点
    public static class RootNode {
        private TreeNode treeRoot;
        public TreeNode getTreeRoot() {
            return treeRoot;
        }
        public void setTreeRoot(TreeNode treeRoot) {
            this.treeRoot = treeRoot;
        }
    }
    //rootNode 根节点 v需要创造的节点的值
    public static void createtree(RootNode rootNode,int v) {
        //如果树根为空(第一次访问)，将第一个值作为根节点
        if(rootNode.getTreeRoot()==null) {
            TreeNode treeNode = new TreeNode(v);
            rootNode.setTreeRoot(treeNode);
        }else {
            //当前树根
            TreeNode tempNode = rootNode.getTreeRoot();
            while(tempNode!=null) {
                //当前值大于根值，往右边走
                if(v>tempNode.getValue()) {
                    //右边没有树根，那就直接插入 并且返回 记着返回哦
                    if(tempNode.getRightNode()==null) {
                        tempNode.setRightNode(new TreeNode(v));
                        return;
                    }else {
                        //如果右边有树根，到右边的树根去
                        tempNode = tempNode.getRightNode();
                    }
                }else {
                    if(tempNode.getLefTreeNode()==null) {
                        tempNode.setLefTreeNode(new TreeNode(v));
                        return;
                    }else {
                        tempNode=tempNode.getLefTreeNode();
                    }
                }
            }
        }
    }
    static List<Integer> list = new ArrayList();
    //中序遍历
    public static void inTraverseBTree(TreeNode rootTreeNode) {
        if (rootTreeNode != null) {
            //访问左节点
            inTraverseBTree(rootTreeNode.getLefTreeNode());
            //访问根节点
            System.out.print(rootTreeNode.getValue()+" ");
            list.add(rootTreeNode.getValue());
            //访问右节点
            inTraverseBTree(rootTreeNode.getRightNode());
        }
    }
    //查找其中第 k 个最小的元素
    public static int kthSmallest(TreeNode root, int k) {
//先进行一边中序遍历把结果存储在list中
        inTraverseBTree(root);
        System.out.println("");
        for(int i=0;i<list.size();i++){
            if(i == k-1)
                return list.get(i);
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] arrays = {3, 2, 1, 4, 5};
        RootNode root = new RootNode();
        for(int value:arrays) {
            createtree(root, value);
        }
        System.out.println("中序遍历结果加第2小元素:");
        System.out.println(kthSmallest(root.getTreeRoot(),2));
    }
}

使用递归（计算节点数量）

    //递归方式
    public static int count(TreeNode root){
        if(root == null)
            return 0;
        return 1 + count(root.getLefTreeNode()) + count(root.getRightNode());
    }
    public  static int kthSmallest_digui(TreeNode root, int k) {
        int num = count(root.getLefTreeNode());
        if(num == k-1)
            return root.getValue();
        if(num > k-1)
            return kthSmallest(root.getLefTreeNode(),k);
        return kthSmallest(root.getRightNode(),k - num-1);
    }

4.输入 ping IP 后敲回车，发包前会发生什么？

首先根据目的IP和路由表决定走哪个网卡，再根据网卡的子网掩码地址判断目的IP是否在子网内。如果不在则会通过arp缓存查询IP的网卡地址，不存在的话会通过广播询问目的IP的mac地址，得到后就开始发包了，同时mac地址也会被arp缓存起来。

5.如何判断两个链表是否相交

: 一层遍历，遍历完两个链表，如果两个链表的最后一个结点指针相同，则相交，否则不相交
2.这个问题我们可以转换为另一个等价问题：如何判断一个单链表是否有环，若有环，找出环的入口？
如何转化？
先遍历第一个链表到它的尾部，然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表。若该链表有环，则原两个链表一定相交。否则，不相交。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return false;
        }
        ListNode slow=head,fast=slow;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                return true;
            }
        }
        return false;
    }
}

6.请评估一下程序的执行结果？

public class SynchronousQueueQuiz {
    public static void main(String[] args) throws Exception {
        BlockingQueue<Integer> queue = new
        SynchronousQueue<>();
        System. out .print(queue.offer(1) + " ");
        System. out .print(queue.offer(2) + " ");
        System. out .print(queue.offer(3) + " ");
        System. out .print(queue.take() + " ");
        System. out .println(queue.size());
    }
}

A. true true true 1 3

B. true true true (阻塞)

C. false false false null 0

D. false false false (阻塞)

#### **参考答案**：D
/*
SynchronousQueue是这样一种阻塞队列，其中每个 put/offer(插入数据) 必须等待一个 take，反之亦然。
除非**另一个线程试图移除某个元素**，否则也不能（使用任何方法）添加元素;也不能迭代队列，因为其中没有元素可用于迭代。
*/

7.设计和实现一个 LRU（最近最少使用）缓存数据结构，使它应该支持一下操作：get 和 put。

• get(key) - 如果 key 存在于缓存中，则获取 key 的 value（总是正数），否则返回 -1。
• put(key,value) - 如果 key 不存在，请设置或插入 value。当缓存达到其容量时，它应该在插入新项目之前使最近最少使用的项目作废。

package wg;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class LRUCache {
    static Map<Integer,Integer> map;
    static Stack<Integer> stack;
    static int size;
    //构造函数
    public LRUCache(int a) {
      map = new HashMap<>(a);
      stack = new Stack<>();
      size = a;
    }
    //Get方法
    public static int get(int key){
        if(!stack.contains(key)){
            return -1;
        }
       stack.remove(Integer.valueOf(key));//移除关键字原先的位置 把它重新放在栈顶，表示最新使用 把key转换成整数
        stack.push(key);
        return map.get(key);
    }
    //Put方法
    public static void put(int key,int value){
        if(stack.contains(key)){//如果添加的元素是原来已经有的，现在相当于要改变
            stack.remove(Integer.valueOf(key));
        }else{
            if(stack.size()==size){//栈满了
                int c = stack.remove(0);//移除栈底元素，返回它的值
                map.remove(c);
            }
        }
        stack.push(key);
        map.put(key,value);
    }
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(4);
        System.out.println(lruCache.get(1));
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        lruCache.put(4,4);
        lruCache.put(5,5);
        System.out.println(lruCache.get(3));
        System.out.println("此刻的栈排列:");
        while(!stack.isEmpty()){
            System.out.println(stack.peek());
            stack.pop();
        }
    }
}

8.实现 FreqStack，模拟类似栈的数据结构的操作的一个类。FreqStack 有两个函数：push(int x)，将整数 x 推入栈中。pop()，它移除并返回栈中出现最频繁的元素。如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。
示例

push [5,7,5,7,4,5]
pop() -> 返回 5，因为 5 是出现频率最高的。栈变成
[5,7,5,7,4]。
pop() -> 返回 7，因为 5 和 7 都是频率最高的，但 7 最接近栈
顶。栈变成 [5,7,5,4]。
pop() -> 返回 5 。栈变成 [5,7,4]。
pop() -> 返回 4 。栈变成 [5,7]。

令freq 作为x的出现次数的映射 Map。
此外maxfreq，即栈中任意元素的当前最大频率，因为我们必须弹出频率最高的元素。
当前主要的问题就变成了：在具有相同的（最大）频率的元素中，怎么判断那个元素是最新的？我们可以使用栈来查询这一信息：靠近栈顶的元素总是相对更新一些。
为此，我们令group作为从频率到具有该频率的元素的映射。到目前，我们已经实现了FreqStack的所有必要的组件。
算法：
实际上，作为实现层面上的一点细节，如果x的频率为 f，那么我们将获取在所有group[i] (i <= f) 中的 x,而不仅仅是栈顶的那个。这是因为每个 group[i] 都会存储与第i个 x 副本相关的信息。

package wg;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class FreqStack {
    static Map<Integer,Integer> freq;//存储每个数字的频率
    static Map<Integer,Stack<Integer> > group;//频率到具有该频率的元素的映射 参数1表示频率，参数2栈表示有哪些元素
    static int maxfreq;//当前最大频率

    public  FreqStack() {//构造函数
        freq = new HashMap<>();
        group = new HashMap<>();
        maxfreq = 0;
    }
    public static void push (int x){
        //当Map集合中有这个key（x）时，就使用这个key值，如果没有就使用默认值defaultValue（0）
        int f = freq.getOrDefault(x,0)+1;
        freq.put(x,f);
        if(f>maxfreq)maxfreq=f;
        //此方法首先判断缓存MAP中是否存在指定key的值，如果不存在，会自动调用mappingFunction(key)(这里指z -> new Stack<>())计算key的value，然后将key = value放入到缓存Map
        group.computeIfAbsent(f,z -> new Stack<>() ).push(x);
    }
    public static int pop(){
        int x = group.get(maxfreq).pop();//弹出频率最高的且最新的元素
        int f = freq.get(x);//得到x此刻的频率
        freq.put(x,f-1);//修改这个频率
        if(group.get(maxfreq).size()==0){//如果此时最大频率的元素没有了，最大频率--
            maxfreq--;
        }
        return x;
    }
    public static void main(String[] args) {
        FreqStack freqStack = new FreqStack();
        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(4);
        freqStack.push(5);
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
    }
}

9.给定一个链表，删除链表的倒数第 N 个节点，并且返回链表的头结点。
示例

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
要求：
只允许对链表进行一次遍历。

我们可以使用两个指针而不是一个指针。第一个指针从链表的开头向前移动 n+1 步，而第二个指针将从链表的开头出发。现在，这两个指针被 n 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n 个结点。我们重新链接第二个指针所引用的结点的 next 指针指向该结点的下下个结点。

package wg;
public class RemoveNthFromEnd {
    static ListNode head = new ListNode();//链表头
    public RemoveNthFromEnd(){
    }
    static class ListNode{
        int x;
        ListNode next;
        public ListNode(int x){
            this.x = x;
            next = null;
        }
        public ListNode(){
        }
    }
    public static ListNode DeleteNthFromEnd(ListNode head,int n){
        ListNode first = head;
        ListNode second = head;
        for(int i=0;i<=n;i++){
            first = first.next;
        }
        while (first!=null){
            first=first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return head;
    }
    public static void main(String[] args) {
        ListNode wg1 = new ListNode(1);
        ListNode wg2 = new ListNode(2);
        ListNode wg3 = new ListNode(3);
        ListNode wg4 = new ListNode(4);
        ListNode wg5 = new ListNode(5);
        head.next = wg1;
        wg1.next = wg2;
        wg2.next = wg3;
        wg3.next = wg4;
        wg4.next = wg5;
        ListNode head2 = DeleteNthFromEnd(head,2);
        head2 = head2.next;
        while (head2!=null){
            System.out.println(head2.x);
            head2 = head2.next;
        }
    }
}

10.给定一个整数数组和一个整数，返回两个数组的索引，这两个索引指向的数字的加和等于指定的整数。需要最优的算法，分析算法的空间和时间复杂度

package wg;
import java.util.Arrays;
import java.util.HashMap;
public class Solution {
    public static int[] twoSum(int[] nums,int sum){
        if(nums==null||nums.length<2){
            return new int[]{0,0};
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0,j=nums.length;i<j;i++){
            if(map.containsKey(nums[i])){
                return new int[]{i,map.get(nums[i])};
            }else{
                map.put(sum-nums[i],i);
            }
        }
        return new int[]{0,0};
    }
    public static void main(String[] args) {
        int[] nums = {1,2,6,7,9};
        System.out.println(Arrays.toString(twoSum(nums,8)));
    }
}
// 2 1
//O(n)