面试题
二叉树
非递归实现二叉树遍历
节点:
class Node(object):
value = 0
left = None
right = None
前序遍历
def func(root):
s = []
p = root
while s or p is not None:
while p is not None:
print p.value
s.append(p)
p = p.left
if s:
p = s.pop()
p = p.right
中序遍历
def func(root):
s = []
p = root
while s or p is not None:
while p is not None:
s.append(p)
p = p.left
if s:
p = s.pop()
print p.value
p = p.right
后序遍历
def func(root):
s = []
p = root
b = None
s.push(root)
while s:
p = s[-1]
# 只有这个节点没有子节点，或者这个节点右节点被访问过，或者这个节点没有右节点且左节点被访问过，这个节点才可以被访问
if (p.left is None and p.right is None) or (
b == p.right or (b == p.left and p.right is None)):
print p.value
s.pop()
b = p
else:
if p.right:
s.push(p.right)
if p.left:
s.push(p.left)
排序
快速排序
#include<stdio.h>
void quickSort(int a[],int left,int right) {
int i = left;
int j = right;
int temp = a[left];
if(left >= right)
return;
while(i != j) {
while(i < j && a[j] >= temp)
j--;
if(j > i)
a[i] = a[j];//a[i]已经赋值给temp,所以直接将a[j]赋值给a[i],赋值完之后a[j],有空位
while(i < j && a[i] <= temp)
i++;
if(i < j)
a[j] = a[i];
}
a[i] = temp;//把基准插入,此时i与j已经相等R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
quickSort(a, left, i - 1);/*递归左边*/
quickSort(a, i+1, right);/*递归右边*/
}
int main()
{
int a[9]={8,2,6,12,1,9,5,5,10};
int i;
quickSort(a,0,8);/*排好序的结果*/
for(i=0;i<8;i++)
printf("%4d",a[i]);
getchar();
return 0;
}
def qsort(a, left, right):
i = left
j = right
temp = a[i]
if left >= right:
return
while i != j:
while i < j and a[j] >= temp:
j -= 1
if j > i:
a[i] = a[j]
while i < j and a[i] <= temp:
j += 1
if i < j:
a[j] = a[i]
a[i] = temp
qsort(a, left, i -1)
qsort(a, i + 1, right)
其他问题
算法题
给一个长度为 n 的字符串，找出其中最长的回文串长度。
解法一：暴力
效率： n^3
解法二：字符串翻转，最长公共子序列
效率：n^2
解法三：Manacher
效率：n
工程题
假设我们有一个敏感词词库，1000万个词，如何判断一个词是否是敏感词，如何判断一句话中是否有敏感词。
布隆过滤器
