跳跃表

redis中的sorted-set正是一种基于此原理的数据结构,可是为啥不用二叉树呢?它们之间的区别在哪里?

二叉查找树需要维持平衡,一般不用AVL,维护的代价比收益会大,只对查找有要求的情况下AVL优于红黑树.而一般使用红黑树的应用场景非常多.redis之所以不用,是因为redis是内存数据库,其设计理念就是要节省内存,跳表虽然空间复杂度是On但是可以通过调参来降低内存消耗.而且在并发环境下,跳表需要更新的部分比较少,需要加锁的地方也比较少,所以不同线程竞争锁的代价就少了.性能也就会比红黑树高了.

小米9月20日笔试题第二题,只过了91%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <iostream>
#include <vector>
#include <numeric>
#include <limits>
#include <cstring>
using namespace std;
const int MAXN = 100005;
bool divide(int a[], int n, int m, int tag) {
	for (int i = 0; i < n; ++i) {
		if (a[i] > tag) {
			return false;
		}
	}
	int sum = a[0];
	int cnt = 1;
	for (int i = 1; i < n; ++i) {
		if (sum + a[i] > tag) {
			sum = a[i];
			++cnt;
			if (cnt > m) {
				return false;
			}
		}
		else {
			sum += a[i];
		}
	}
	return true;
}
int a[MAXN];
int main(int argc, char** argv) {
	int n, m;
	while (cin >> n >> m) {
		int sum = 0;
		for (int i = 0; i < n; ++i) {
			cin >> a[i];
			sum += a[i];
		}
		int num;
		if (sum % m == 0) {
			num = sum / m;
		}
		else {
			num = sum / m + 1;
		}
		int res = -1;
		for (int i = num; i <= sum; ++i) {
			if (divide(a, n, m, i)) {
				res = i;
				break;
			}
		}
		cout << res << endl;
	}
	return 0;
}

参考https://blog.csdn.net/javazejian/article/details/72772461

数据库原理

1.MYISAM与InnoDB搜索引擎原理

MyIsam引擎使用B+树作为索引结构,叶子节点data域存放的是数据记录的地址.索引文件和数据文件是分开的,索引文件只存放索引,数据文件只存放数据,其索引方式是非聚集的.

InnoDB引擎也是使用B+树作为索引结构.但是它的主键索引也就是一级索引是与数据放在一个文件中的.其索引结构是聚集索引,因为数据本身的物理顺序与索引的逻辑顺序相同.为此,innoDB建表要求一定要有主键.

网络编程:

ISO模型与协议

1.应用层有哪些协议?

Telnet,FTP,HTTP,SNMP,DNS等等

Http1.0:需要使用Keep-alive参数来告知服务器端需要建立一个长连接

Java基础系列

Java中的Map接口有诸多实现,参考,一般会从效率,键值对的保存及呈现次序,对象的保存周期,映射表如何在多线程程序中工作以及判定”键”等价的策略等方面来考虑它们之间的区别.

题目描述：

00:00到23:59时间内时针和分针重合了几次?(00:00到11:59呢)

解题思路：

先找到时针和分针可以比较的相同度量,即每秒走多少度.然后再根据这个角速度来求时针和分针相遇后时针走了多少度.

概念

图片讲得已经非常清楚了，TP90指标越小，说明在所有的请求中占90%的请求的响应时间都很小，所以一般说3个9，4个9，9越多说明指标的要求越高。

2803. The Max

题目意思很简单，不说了，第一反应就是先进行排序，还要注意数据的范围是大于int的，所以要用long long。

725. Split Linked List in Parts

题目意思很简单，给你一串链表，将其分成k个链表。前面链表的长度要大于后面链表的长度。比如说长度为10分成3部分就是[4,3,3]