哈希
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()+" ");
}
}