一、数据库索引的实现原理

推荐阅读：MySQL索引背后的数据结构及算法原理

摘录：

• 数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。
• 设置索引要付出代价：一是增加了数据库的存储空间，二是在插入和修改数据时要花费较多的时间(因为索引也要随之变动)。

题目来源：LeetCode: 110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

概述：Python中这三种形式的定义相近，易于混淆，应注意区分.

1
2
3
4

Python中字典Dictionary、列表List、元组Tuple定义形式：
aDict={'a':1, 'b':2, 'c':3, 'd':4, 'e':5}
aList=[1,2,3,4,5]
aTuple=(1,2,3,4,5)

题目来源：LeetCode: 257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1
/ \
2 3
\
5
All root-to-leaf paths are:
[“1->2->5”, “1->3”]

思路

• 二叉树的遍历：先序遍历，递归调用
• 解决好走过路径的记录和回退
• C语言处理字符的操作不太便捷，试着用Python写这道题

时间复杂度：O(n), 空间复杂度O(logn)

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

思路

最初看到这个题目，觉得迭代加法取余的方式肯定是最low的，分析规律。

• 最终得到个位数，结果取值范围[0,9]
• 各位数累加的计算规律：dr(10)=10-9=1, dr(11)=11-9=2
• 但并不是对九取余的关系，因为mod(n, 9)的取值范围时[0, 8]
• 可以抽象为dr(n)=mod(n-1,9) + 1

时间复杂度：O(1), 空间复杂度O(1)

• 各位数累加的计算规律：12345=1x(9999+1)+2x(999+1)+3x(99+1)+4x(9+1)+5=(1x9999+2x999+3x99+4x9)+(1+2+3+4+5)

Given an integer, write a function to determine if it is a power of three.

Follow up:
Could you do it without using any loop / recursion?

思路

• 循环除3、取余，判定是否3的幂(与题目不建议使用循环、递归的思想不符)
• math函数，求log3(n)，判断是否为整数
• 转换为3进制，判断是否为10*形式的三进制数

方案2：时间复杂度：O(1), 空间复杂度O(1)

Power(x, n) | 实现幂运算

Implement pow(x, n).

思路1: 分治

恰如1+2+3+…+n的解决方案，pow(x,n)也可优化拆解

二分法：x^n = x^(n/2) * x^(n/2) * x^(n%2)
时间复杂度：O(logn), 空间复杂度O(1)

题目来源：LeetCode:67. Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = “11”
b = “1”
Return “100”.

思路

• 类似于大数大数加法操作，逐位进行操作。
• 每一位字符-‘0’得到的数字，累加后与2比较，来确定进位与否。
• 最高位的可能位1，或不存在，且只有计算结束时才能确定存在与否，动态分配内存方面应特殊对待。

设备、产品厂商列表

• 网络设备：华为、锐捷、思科
• 防火墙：天融信
• 安全产品：绿盟、启明星辰
• 软件产品：北信源

一、基本命令查看服务器状态

/proc/目录原理：硬件状态信息在启动的过程中装载到虚拟目录/proc下文件中。

proc文件系统是一个伪文件系统，它只存在内存当中，而不占用外存空间。它以文件系统的方式为访问系统内核数据的操作提供接口。