1、可以讲一下红黑树吗？用在什么地方，有什么优点？
红黑树也是自平衡的二叉查找树。
红黑树定义和性质
- 性质1：每个节点要么是黑色，要么是红色。
- 性质2：根节点是黑色。
- 性质3：每个叶子节点是黑色。
- 性质4：每个红色结点的两个子结点一定都是黑色。
- 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
(值得提醒注意的是，在Java中，叶子结点是为null的结点。)
前面讲到红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色
作用：当在10亿数据中只需要进行10几次比较就能查找到目标时，查找时算法时间复杂度为O(log n)。
2、跳表
这种带多级索引的链表，就是跳表
跳表的查询时间复杂度可以达到O(logn)
二分查找依赖数组的随机访问，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找了吗？而实际上，我们只需要对链表稍加改造，就可以实现类似“二分”的查找算法，这种改造之后的数据结构叫作跳表（Skip List）
缺点：耗内存（因为要重复分层存节点），可以调参数来降低内存消耗，和那些平衡树结构达到差不多。
假如一直往原始列表中添加数据，但是不更新索引，就可能出现两个索引节点之间数据非常多的情况，极端情况，跳表退化为单链表，从而使得查找效率从 O(logn) 退化为 O(n)。那这种问题该怎么解决呢？
完全重建索引，我们每次插入数据后，都把这个跳表的索引删掉全部重建，重建索引的时间复杂度是多少呢？因为索引的空间复杂度是 O(n)
我们在原始链表中随机的选 n/2 个元素做为一级索引是不是也能通过索引提高查找的效率呢？
3、两数之和
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
4、三数之和
class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList();
int len = nums.length;
if(nums == null || len < 3) return ans;
Arrays.sort(nums); // 排序
for (int i = 0; i < len ; i++) {
if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
int L = i+1;
int R = len-1;
while(L < R){
int sum = nums[i] + nums[L] + nums[R];
if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
while (L<R && nums[L] == nums[L+1]) L++; // 去重
while (L<R && nums[R] == nums[R-1]) R--; // 去重
L++;
R--;
}
else if (sum < 0) L++;
else if (sum > 0) R--;
}
}
return ans;
}
}
5、布隆过滤器
6、讲几个排序算法，为什么快速排序不稳定？
- 选择排序：从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
- 冒泡排序：从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。
- 插入排序：每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。
- 希尔排序： 对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。
- 归并排序：归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来
- 快速排序：通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。复杂度为 O(NlogN)。
- 堆排序：堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。
选择排序，希尔排序，堆排序，快速排序等都是不稳定的排序算法。
稳定性：待排序的序列中有两元素相等,排序之后它们的先后顺序不变
如果只是单纯数字，那么稳不稳定都没啥影响，如果有关联关系，比如主键是有关联到其他信息
快排算法改进
1、 切换到插入排序
因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。
2、 三数取中
最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。
3、 三向切分
对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。
三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。
7、LeetCode之实现IndexOf()
8、哈希
哈希函数的特点：
- 确定性
- 哈希碰撞
- 不可逆性
- 混淆特性
常见的哈希函数
- MD5
- SHA-1
- MD4
解决散列冲突问题
- 开放寻址法
- 有线性探测方法（按顺序地往后一个一个找，看有没有空闲的位置）
- 二次探测（使用二次探测进行探测的步长变成了原来的“二次方）
- 双重散列（不仅要使用一个散列函数，而是使用一组散列函数 ，先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置）
- 链表法（每个位置对应一条链表，所有散列值相同的元素都放到相同位置对应的链表中）
9、字节、字、位、比特之间的关系
1 Byte（B）= 8 bit；
1 Kilo Byte（KB） = 1024B；
1 MB = 1024 KB；
1 GB = 1024 MB；
1 TB = 1024 GB；
1 PB = 1024 TB；
10、100以内的质数
public void primeNumberTest() {
for (int i = 2; i <= 100; i++) {
boolean flag = true;
for (int j = 2; j <= Math.sqrt(i); j++) { //Math.sqrt(i)平方根
if (i % j == 0) {
flag = false;
break;
}
}
if (flag) {
System.out.print(i + ",");
}
}
}
11、bfs和dfs倒背如流
public void bfs(TreeNode root) {
if (root == null) return;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode poll = q.poll();
if (poll.left != null) q.add(poll.left);
if (poll.right != null) q.add(poll.right);
}
}
}
public void dfs(TreeNode root) {
if (root == null) {
return;
} else {
minDepth(root.left);
minDepth(root.right);
}
}
12、判断字符串是否是回文字符串
public boolean isPalindrome(String s) {
if (s == null || s == "" || s.length() == 1) return false;
int length = s.length();
char[] chars = s.toCharArray();
for (int i = 0; i < length / 2; i++) {
if (chars[i] != chars[length - i - 1]) {
return false;
}
}
return true;
}
13、手写代码求二叉树的左视图
二叉树的左视图就是从二叉树左边看这棵树，你能看到的结点
【解决思路】
- 首先，“每行第一个数”，让我们想到这是层序遍历的变形。
- 用 size 记录当层的结点数，循环访问时用 child 记录下一层的结点数，当 i = 0 时，是当层第一个结点。
public void LeftView(TreeNode node) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(node);
//设置 size 和 child 两个标记，child在循环中会变，size不会变，作为循环条件
//第一层只有根节点1个，所以size = 1
int size = 1;
//记录孩子数
int child;
while (!queue.isEmpty()) {
//初始化孩子数为 0
child = 0;
for (int i = 0; i < size; i++) {
TreeNode node1 = queue.poll();
// i = 0,说明是该层第一个结点
if (i == 0) {
System.out.println(node1.val);
}
if (node1.left != null) {
queue.offer(node1.left);
child++;
}
if (node1.right != null) {
queue.offer(node1.right);
child++;
}
}
size = child;
}
}
【右视图】
有了以上的思路，右视图也就迎刃而解，因为右视图就是输入每行的最后一个结点呀！
也就是当 i = size -1,改动一行代码就行
网友评论