关于java:Java面试问题汇总数据结构算法

哈希

1.hashCode() 和equals() 办法的重要性体现在什么中央

Java中的HashMap应用hashCode()和equals()办法来确定键值对的索引，当依据键获取值的时候也会用到这两个办法。如果没有正确的实现这两个办法，两个不同的键可能会有雷同的hash值，因而，可能会被汇合认为是相等的。而且，这两个办法也用来发现反复元素。所以这两个办法的实现对HashMap的精确性和正确性是至关重要的。

2.HashMap的工作原理

HashMap类有一个叫做Entry的外部类。这个Entry类蕴含了key-value作为实例变量。 每当往hashmap外面寄存key-value对的时候，都会为它们实例化一个Entry对象，这个Entry对象就会存储在后面提到的Entry数组table中。Entry具体存在table的那个地位是 依据key的hashcode()办法计算出来的hash值（来决定）。
1.8之后存数据的是动态外部类Node

3.什么是hashmap

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。
HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
HashMap 的实现不是同步的，这意味着它不是线程平安的。它的key、value都能够为null。此外，HashMap中的映射不是有序的。

HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。容量 是哈希表中桶的数量，初始容量 只是哈希表在创立时的容量。加载因子 是哈希表在其容量主动减少之前能够达到多满的一种尺度。当哈希表中的条目数超出了加载因子与以后容量的乘积时，则要对该哈希表进行 rehash 操作（即重建外部数据结构），从而哈希表将具备大概两倍的桶数。
通常，默认加载因子是 0.75, 这是在工夫和空间老本上寻求一种折衷。加载因子过高尽管缩小了空间开销，但同时也减少了查问老本（在大多数 HashMap 类的操作中，包含 get 和 put 操作，都反映了这一点）。在设置初始容量时应该思考到映射中所需的条目数及其加载因子，以便最大限度地缩小 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会产生 rehash 操作。

hashmap共有4个构造函数：

• // 默认构造函数。HashMap()
• // 指定“容量大小”的构造函数 HashMap(int capacity)
• // 指定“容量大小”和“加载因子”的构造函数 HashMap(int capacity, float loadFactor)
• // 蕴含“子Map”的构造函数 HashMap(Map<? extends K, ? extends V> map)

4.如何结构一致性 哈希算法

先结构一个长度为2^32的整数环（这个环被称为一致性Hash环），依据节点名称的Hash值（其散布为[0, 2^32-1]）将服务器节点搁置在这个Hash环上，而后依据数据的Key值计算失去其Hash值（其散布也为[0, 2^32-1]），接着在Hash环上顺时针查找间隔这个Key值的Hash值最近的服务器节点，实现Key到服务器的映射查找。

这种算法解决了一般余数Hash算法伸缩性差的问题，能够保障在上线、下线服务器的状况下尽量有多的申请命中原来路由到的服务器。

5.Object作为HashMap的key的话，对Object有什么要求

1.重写hashCode(),因为须要计算存储数据的存储地位，须要留神不要试图从散列码计算中排除掉一个对象的要害局部来进步性能，这样尽管能更快但可能会导致更多的Hash碰撞；
2.重写equals()办法，须要恪守自反性、对称性、传递性、一致性以及对于任何非null的援用值x，x.equals(null)必须返回false的这几个个性，目标是为了保障key在哈希表中的唯一性；

树

1.二叉树构造

二叉树每个节点至少有两个节点，左节点永远比右节点小，并且小于根节点。

查找最好工夫复杂度O(longN), 最坏O(N)

插入删除操作工夫复杂度跟查找差不多

2.均衡二叉树（AVL）

左右子树的高度差不超过1，并且左右子树都是均衡二叉树，超过1就旋转。

比二叉树稳固，查找时间复杂度O(logN)

插入操作最多须要旋转1次，工夫复杂度O(logN)左右

删除工夫复杂度O(2logN)

3.红黑树

每个节点上都有节点色彩，能够是红色或者彩色；根节点必须是彩色；每个红色节点的子节点，父节点是彩色；从任一节点到每个叶子节点的所有门路都蕴含雷同数目的彩色节点。

查找效率最好状况下是O(logN)，最坏状况下比均衡二叉树要差一些，但也比二叉树要好

插入和删除操作扭转树的平衡性概率小于均衡二叉树

4.B+树 和 B-树

B+树 和 B-树

B+树 的两头节点不保留数据，所以磁盘页能包容更多节点元素；

B+树查问必须查找到叶子节点，B树只有匹配到即可不必管元素地位，因而B+树查找更稳固

对于范畴查找来说，B+树只需遍历叶子节点链表即可，B树却要反复地中序遍历

效率总结：https://blog.csdn.net/z702143…

区别比照：https://blog.csdn.net/wyqwill…

5.TreeMap和TreeSet在排序时如何比拟元素？Collections工具类中的sort()办法如何比拟元素

TreeSet要求寄存的对象所属的类必须实现Comparable接口，该接口提供了比拟元素的compareTo()办法，当插入元素时会回调该办法比拟元素的大小。

TreeMap要求寄存的键值对映射的键必须实现Comparable接口从而依据键对元素进行排序。

Collections工具类的sort办法有两种重载的模式，第一种要求传入的待排序容器中寄存的对象比拟实现Comparable接口以实现元素的比拟；第二种不强制性的要求容器中的元素必须可比拟，然而要求传入第二个参数，参数是Comparator接口的子类型（须要重写compare办法实现元素的比拟），相当于一个长期定义的排序规定，其实就是通过接口注入比拟元素大小的算法，也是对回调模式的利用（Java中对函数式编程的反对）。

public class
Student implements Comparable<Student> {
     private String name;        // 姓名
     private int age;            // 年龄
     public Student(String name, int age) {
         this.name = name;
         this.age = age;
     }
     @Override
     public String toString() {
         return "Student [name=" + name + ", age=" + age + "]";
     }
     @Override
     public int compareTo(Student o) {
         return this.age - o.age; // 比拟年龄(年龄的升序)
     }
 }
 import java.util.Set;
 import java.util.TreeSet;
 class Test01 {
     public static void main(String[] args) {
         Set<Student> set = new TreeSet<>();     // Java 7
     }
 }
 import java.util.Set;
 import java.util.TreeSet;
 class Test01 {
     public static void main(String[] args) {
         Set<Student> set = new TreeSet<>();     // Java 7的钻石语法(结构器前面的尖括号中不须要写类型)
         set.add(new Student("Hao LUO", 33));
         set.add(new Student("XJ WANG", 32));
         set.add(new Student("Bruce LEE", 60));
         set.add(new Student("Bob YANG", 22));
 
         for(Student stu : set) {
            System.out.println(stu);
         }
 //      
         set.add(new Student("Hao LUO", 33));
         set.add(new Student("XJ WANG", 32));
         set.add(new Student("Bruce LEE", 60));
         set.add(new Student("Bob YANG", 22));
         for(Student stu : set) {
            System.out.println(stu);
         }
 //      输入后果: 
 //      Student [name=Bob YANG, age=22]
 //      Student [name=XJ WANG, age=32]
 //      Student [name=Hao LUO, age=33]
 //      Student [name=Bruce LEE, age=60]
     }
 }
 //      Student [name=Bob YANG, age=22]
 //      Student [name=XJ WANG, age=32]
 //      Student [name=Hao LUO, age=33]
 //      Student [name=Bruce LEE, age=60]
     }
 }

6.打印二叉树每层的节点

import java.util.ArrayList;
import java.util.Scanner;
public class Main{
    // 定义节点
    class Node{
        int val;
        Node left;
        Node right;
        publicNode(int val) {
            this.val = val;
        }
    }
   
    public ArrayList<Integer> gzy; // 保留根左右的序列
    public ArrayList<Integer> zgy; // 保留左跟右的序列
    public ArrayList<Node> pack;       // 保留曾经排好的节点
   
    public static void main(String[] args) {
        Main main = new Main();
        main.getResult();
       
    }
   
    public void getResult() {
        // init
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        gzy = new ArrayList<>();
        zgy = new ArrayList<>();
        for(int i = 0; i < count; i++) {
            gzy.add(scanner.nextInt());
        }
        for(int j = 0; j < count; j++) {
            zgy.add(scanner.nextInt());
        }
        pack = new ArrayList<>();       // 曾经还原的节点
       
        // exception
        if(count== 1) {
            System.out.println(gzy.get(0));
            return;
        }
        // 结构最左侧节点的二叉树
        Node node = new Node(gzy.get(0));
        pack.add(node);
        int index1 = 1;     // 根左右的下标
        Node tmp = node;
        while(gzy.get(index1) != zgy.get(0)) {      // 如果没拜访到最右边的叶子节点,持续还原最左侧二叉树
            tmp.left = new Node(gzy.get(index1++));
            tmp = tmp.left;
            pack.add(tmp);
        }
        tmp.left = new Node(gzy.get(index1++));
        pack.add(tmp.left);
       
        // 退出残余的节点欠缺二叉树
        for(int k = index1; k < gzy.size(); k++) {
            fillErCS(gzy.get(k));
        }
       
        // 档次遍历
        ArrayList<Node> res = new ArrayList<>();
        res.add(node);
        int num = 0;
        while(res.size() != num) {
            System.out.print(res.get(num).val + " ");
            if(res.get(num).left != null) {
                res.add(res.get(num).left);
            }
            if(res.get(num).right != null) {
                res.add(res.get(num).right);
            }
            num++;
        }
    }
   
    // 将值为val的节点退出二叉树
    private void fillErCS(int val) {
        int index = zgy.indexOf(val);
        // 每一个遍历的节点都是val节点的根或者在其右边
        for(int i = index-1; i >= 0; i--) {
            if(findNode(zgy.get(i)) != null) {  // 找到待插入节点的根节点或者其右边的节点
                Node node = findNode(zgy.get(i));
                insert(node, val);
                break;
            }      
        }
    }
   
    // 将节点val插入二叉树
    private void insert(Node node, int val) {
        if(zgy.indexOf(node.val) > zgy.indexOf(val)) {  // node在待插入节点的左边
            if(node.left == null) {
                node.left = new Node(val);
                pack.add(node.left);
                return;
            }
            insert(node.left, val);
        }else {     //node在待插入节点的右边或是其根
            if(node.right == null) {
                node.right = new Node(val);
                pack.add(node.right);
                return;
            }
            insert(node.right, val);
        }
    }
    // 依据val找到pack里的节点
    private Node findNode(int val) {
        for(Node node : pack) {
            if(node.val == val) {
                return node;
            }
        }
        return null;
    }
}

7.如何晓得二叉树的深度

实现二叉树的深度形式有两种，递归以及非递归。

①递归实现：

为了求树的深度，能够先求其左子树的深度和右子树的深度，能够用递归实现，递归的进口就是节点为空。返回值为0；

②非递归实现：

利用档次遍历的算法，设置变量level记录以后节点所在的层数，设置变量last指向以后层的最初一个节点，当解决完以后层的最初一个节点，让level指向+1操作。设置变量cur记录以后层曾经拜访的节点的个数，当cur等于last时，示意该层拜访完结。

档次遍历在求树的宽度、输入某一层节点，某一层节点个数，每一层节点个数都能够采取相似的算法。

树的宽度：在树的深度算法根底上，加一个记录拜访过的层节点个数最多的变量max,在拜访每层前max与last比拟，如果max比拟大，max不变，如果max小于last，把last赋值给max;

import java.util.LinkedList;
public class Deep {
    //递归实现1
  public int findDeep(BiTree root) {
      int deep = 0;
     
        if(root != null) {
          int lchilddeep = findDeep(root.left);
          int rchilddeep = findDeep(root.right);
          deep = lchilddeep > rchilddeep ? lchilddeep + 1 : rchilddeep + 1;    }
     
            return deep;
  }
 
 
  //递归实现2
  public int findDeep1(BiTree root) {
   
     if(root == null) {
          return 0;
      } else {
      
          int lchilddeep = findDeep1(root.left);//求左子树的深度
          int rchilddeep = findDeep1(root.left);//求右子树的深度
          return lchilddeep > rchilddeep ? lchilddeep + 1 : rchilddeep + 1;//左子树和右子树深度较大的那个加一等于整个树的深度
      }
  }
  //非递归实现
  public int findDeep2(BiTree root) {
     if(root == null)
         return 0;
   
     BiTree current = null;
     LinkedList<BiTree> queue = new LinkedList<BiTree>();
     queue.offer(root);
     int cur,last;
     int level = 0;
     while(!queue.isEmpty()){
         cur = 0;//记录本层曾经遍历的节点个数
         last = queue.size();//当遍历完以后层当前，队列里元素全是下一层的元素，队列的长度是这一层的节点的个数
         while(cur < last)//当还没有遍历到本层最初一个节点时循环
         {
             current = queue.poll();//出队一个元素
             cur++;
             //把以后节点的左右节点入队（如果存在的话）
             if(current.left != null)
             {
                 queue.offer(current.left);
             }
             if(current.right != null)
             {
                 queue.offer(current.right);
             }
         }
         level++;//每遍历完一层level+1
     }
     return level;
  }
  public static void main(String[] args)
 {
    BiTree root = BiTree.buildTree();
    Deep deep = new Deep();
    System.out.println(deep.findDeep(root));
    System.out.println(deep.findDeep1(root));
    System.out.println(deep.findDeep2(root));  
 }
}

8.二叉树任意两个节点之间门路的最大长度

int maxDist(Tree root) { 
    //如果树是空的，则返回0  
    if(root == NULL) 
        return 0; 
    if(root->left != NULL) { 
        root->lm = maxDist(root->left) +1; 
    } 
    if(root->right != NULL) 
        root->rm = maxDist(root->right) +1; 
    //如果以该节点为根的子树中有最大的间隔，那就更新最大间隔  
    int sum = root->rm + root->lm; 
    if(sum > max) { 
        max = sum; 
    } 
 
    return root->rm > root->lm ? root->rm : root->lm; 
}  

9.二叉树层序遍历，进一步发问：要求每层打印出一个换行符

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        if (root == null) {
            return res;
        }
        queue.offer(root);
        while (queue.size() != 0) {
            List<Integer> l = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode temp = queue.poll();
                l.add(temp.val);
                if (temp.left != null) {
                    queue.offer(temp.left);
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                }
            }
            res.add(l);
        }
        return res;
}

10.怎么求一个二叉树的深度?手撕代码

public int
maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        int bigger = Math.max(left, right);
        return bigger + 1;
    }

11.二叉树 Z 字型遍历

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        LinkedList<TreeNode> l = new LinkedList<TreeNode>();
        boolean flag = true;
        if (root == null) {
            return res;
        }
        l.add(root);
        while (l.size() != 0) {
            flag = !flag;
            int size = l.size();
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < size; i++) {
                TreeNode temp = l.remove();
                list.add(temp.val);
                if (temp.left != null)
                    l.add(temp.left);
                if (temp.right != null)
                    l.add(temp.right);
            }
            if (flag) {
                Collections.reverse(list);
            }
            res.add(list);
        }
        return res;
    }

12.写一个函数，找到一个文件夹下所有文件，包含子文件夹

import
java.io.File;
public class
Counter2 {
    public static void main(String[] args) {
        //获得目标目录
        File
file = new File("D:");
        //获取目录下子文件及子文件夹
        File[]
files = file.listFiles();
        readfile(files);
       
    }
   
    public static void readfile(File[] files) {
        if
(files == null) {// 如果目录为空，间接退出  
            return; 
        }
        for(File
f:files) {
            //如果是文件，间接输入名字
            if(f.isFile()) {
                System.out.println(f.getName());
            }
            //如果是文件夹，递归调用
            else if(f.isDirectory()) {
                readfile(f.listFiles());
            }
        }
    }
}

链表

1.判断链表中是否呈现了环

单链表有环，是指单链表中某个节点的next指针域指向的是链表中在它之前的某一个节点，这样在链表的尾部造成一个环形构造。
// 链表的节点构造如下 typedef struct node { int data; struct node *next; } NODE;

最罕用办法：
定义两个指针，同时从链表的头节点登程，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的开端（next指向 NULL）都没有追上第一个指针，那么链表就不是环形链表。

通过应用STL库中的map表进行映射。首先定义 map<NODE *, int> m; 将一个 NODE * 指针映射成数组的下标，并赋值为一个 int 类型的数值。而后从链表的头指针开始往后遍历，每次遇到一个指针p，就判断 m[p] 是否为0。如果为0，则将m[p]赋值为1，示意该节点第一次拜访；而如果m[p]的值为1，则阐明这个节点曾经被拜访过一次了，于是就造成了环。

2.有一个链表，奇数位升序偶数位降序，如何将链表变成升序

public class OddIncreaseEvenDecrease {
    /**
     * 依照奇偶位拆分成两个链表
     * @param head
     * @return
     */
    public static Node[] getLists(Node head){
        Node head1 = null;
        Node head2 = null;
       
        Node cur1 = null;
        Node cur2 = null;
        int count = 1;//用来计数
        while(head != null){
            if(count % 2 == 1){
                if(cur1 != null){
                    cur1.next = head;
                    cur1 = cur1.next;
                }else{
                    cur1 = head;
                    head1 = cur1;
                }
            }else{
                if(cur2 != null){
                    cur2.next = head;
                    cur2 = cur2.next;
                }else{
                    cur2 = head;
                    head2 = cur2;
                }
            }
            head = head.next;
            count++;
        }
        //跳出循环，要让最初两个开端元素的下一个都指向null
        cur1.next = null;
        cur2.next = null;
       
        Node[] nodes = new Node[]{head1,head2};
        return nodes;
    }
   
    /**
     * 反转链表
     * @param head
     * @return
     */
    public static Node reverseList(Node head){
        Node pre = null;
        Node next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    
    /**
     * 合并两个有序链表
     * @param head1
     * @param head2
     * @return
     */
    public static Node CombineList(Node head1, Node head2){
        if(head1 == null || head2 == null){
            return head1 != null ? head1 :head2;
        }
        Node head = head1.value < head2.value ? head1 : head2;
        Node cur1 = head == head1 ? head1 : head2;
        Node cur2 = head == head1 ? head2 : head1;
        Node pre = null;
        Node next = null;
        while(cur1 != null && cur2 !=null){
            if(cur1.value <= cur2.value){//这里肯定要有=，否则一旦cur1的value和cur2的value相等的话，上面的pre.next会呈现空指针异样
                pre = cur1;
                cur1 = cur1.next;
            }else{
                next = cur2.next;
                pre.next = cur2;
                cur2.next = cur1;
                pre = cur2;
                cur2 = next;
            }
        }
        pre.next = cur1 == null ? cur2 : cur1;
       
        return head;
    }
}

3.随机链表的复制

public RandomListNode copyRandomList(RandomListNode head) {
 
    if (head == null)
        return null;
 
    RandomListNode p = head;
 
    // copy every node and insert to list
    while (p != null) {
        RandomListNode copy = new RandomListNode(p.label);
        copy.next = p.next;
        p.next = copy;
        p = copy.next;
    }
 
    // copy random pointer for each new node
    p = head;
    while (p != null) {
        if (p.random != null)
            p.next.random = p.random.next;
        p = p.next.next;
    }
 
    // break list to two
    p = head;
    RandomListNode newHead = head.next;
    while (p != null) {
        RandomListNode temp = p.next;
        p.next = temp.next;
        if (temp.next != null)
            temp.next = temp.next.next;
        p = p.next;
    }
 
    return newHead;
}

4.反转单链表

ListNode reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode* p;
        ListNode* q;
        ListNode* r;
        p = head;
        q = head->next;
        head->next = nullptr;//旧的头指针是新的尾指针 指向NULL
        while(q){
            r = q->next;//用来保留下一步要解决的指针
            q->next = p;//p q 交替解决 进行反转单链表
            p = q;
            q = r;
        }
        head = p;//最初的q必然指向NULL，p就成了新链表的头指针
        return head;
}

数组

1.二维数组顺时针旋转90度

倒着的第一列变第一行…

public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n/2; i++) {
            for (int j = i; j < n-1-i; j++){
                int temp = matrix[i][j];
                matrix[i][j] =matrix[n-1-j][i];
                matrix[n-1-j][i] =matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] =matrix[j][n-1-i];
                matrix[j][n-1-i] = temp;
            }
        }
}

2.一个数组，除一个元素外其它都是两两相等，求那个元素

因为数组中除了一个元素只呈现一次之外，其它的元素都呈现两次，如果把所有的数都异或，雷同的数字异或为0，最初只剩下呈现一次的数字，它和0异或，后果就是它自身。

 public static int find1From2(int[] a){
        int len = a.length, res = 0;
        for(int i = 0; i < len; i++){
            res= res ^ a[i];
        }
        return res;
}

3.找出数组中和为S的一对组合，找出一组就行

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

4.求一个数组中间断子向量的最大和

public int maxSubArray(int[] nums) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        if (nums == null || nums.length == 0) {
            return sum;
        }
        for (int i = 0; i < nums.length;i++) {
            sum += nums[i];
            maxSum = Math.max(maxSum, sum);
            if (sum < 0) {
                sum = 0;
            }
        }
        return maxSum;
}

5.寻找一数组中前K个最大的数

public static void TOPK(int[] data,int k){
        PriorityQueue<Integer> pq=new PriorityQueue<>(k);
        for (int i = 0; i < data.length; i++) {
            if(i<k){
                pq.offer(data[i]);
            }else{
                if(data[i]>pq.peek()){
                    pq.poll();
                    pq.offer(data[i]);
                }
            }
        }
        for (int i = 0; i < k; i++) {
            System.out.print(pq.poll()+" ");
        }
    }