今天答了腾讯的笔试题，结果题目选错了都是C++的我也不是太会，以下是几道记忆比较深的题目。
选择题
三个人玩斗地主，地主有20张牌，两个农民有17张牌，问两个王同时在一个人手中的概率是多少？
Mysql数据库建立索引，复合索引中匹配where子句和select查询字段的最左匹配问题。
剩下的就是C++的题了，一路蒙下来直接提交。
简答题
第一道没来得及，第二道是这样：
给定一个由
{'A','B','C','D'}组成的字符串，给定D>C>B>A，求总的逆序数。要求时间复杂度为O(N)。
刚开始看这题，第一反应是使用冒泡排序直接出比较次数就行了，但是看见时间复杂度要求，就知道要用Hash了。
我的思路是：
对于一个中间状态，例如 "[_ _ _ _]D[_ _ _ _]"，D的逆序数只与后面出现的C、B、A的数量有关，因此，伪代码为：
INPUT = "DBCA"
ALPHA_COUNT = {'A' => 0， 'B' => 0， 'C' => 0， 'D' => 0 }
VISITED_COUNT = {'A' => 0， 'B' => 0， 'C' => 0， 'D' => 0 }
# 计算出每种字母出现的次数
FOR c IN INPUT
ALPHA_COUNT[c]++;
SUM = 0
FOR c IN INPUT
CASE c
'D': SUM += ALPHA_COUNT['C'] -VISITED_COUNT['C']
'C': SUM += ALPHA_COUNT['B'] -VISITED_COUNT['B']
'B': SUM += ALPHA_COUNT['A'] - VISITED_COUNT['A'];
'A':
ESAC
RETURN SUM
编程题
- 给定一个包含小写字母的字符串，例如
"abcdefghijklmnopqrstuvwxyzabcdefghi"，将它格式化成十六进制编辑器的排版样式,如下格式：
00000000 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 abcdefghijklmnop
00000010 77 78 79 80 81 82 83 84 85 86 61 62 63 64 65 66 qrstuvwxyzabcdef
00000020 67 68 69 ghi
整个排版非常规整，用printf即可完成，第一列的偏移使用printf的十六进制前导补0即可。
- 给定k，num1，num2，num3，求在2^k-1个节点形成的满BST中查找包含三个数字的最小子树根。
刚开始看这题，就知道可以利用满二叉树的特点直接计算出来公共根。典型的分治策略
DEF F(N, MIN, MAX，K)
IF MIN<=K<=MAX THEN RETURN ROOT
IF MAX < N THEN
#将根节点降级，在左子树查找
RETURN F(N + POW(K-2，2), MIN, MAX, K-1)
ELSE
#将根节点降级，在右子树查找
RETURN F(N - POW(K-2，2), MIN, MAX, K-1)
总结： 题目总体难度简单，主要亏在了选错C++了,对于会C++的同学应该是非常简单的。喔寄几的网页编程盲打要保持和加强，在C的pow函数耽误了时间，结果还是寄几写的pow函数。以后投简历一定看好是什么语言。基础很重要，刷题很重要，再加把劲！！！！！