Microsoft笔试

1 Shortening Sequence

描述

There is an integer array A1, A2 ...AN. Each round you may choose two adjacent integers. If their sum is an odd number, the two adjacent integers can be deleted.

Can you work out the minimum length of the final array after elaborate deletions?

输入

The first line contai......

数据结构拾遗(0)

最近忙着9月份的校招,所以最近一直在复习数据结构相关知识。其实从2013年开始就断断续续的学习清华大学MOOC数据结构这门课程。

课程的内容是用C++写的,也花了一段时间改写成C#,已经放在github上Data Structure 最近也做了一些复习,算作拾遗。

0 Time cost

一个合格的程序猿基本的一点是能够明确自己所写的算法的时间复杂度。

常数$O(1)$

ordinaryElement 从集合中筛选非最大和非最小元素

ordinaryElement(S[],n)

any three elements x,y and z belong to S,

sor......

百度实习生招聘笔试题

1 描述

给两个二叉树,判断第二个二叉树是否为第一棵二叉树的字数,并且二叉树节点的值没有重复的。

二叉树节点定义:

typedef struct tnode{

int val;

struct tnode* left;

struct tnode* right;

};

int isSubtree(tnode* root1, tnode* root2)

{

//todo

}

2 解题思路

在题意中有一个二叉树节点没有重复,则可以考虑到二叉树重建的实现:任意一个二叉树,给定二叉树[先序|后序] && 中序即可重建这棵二叉树,LeetCode上有相关的题目。

+ ......

KMP算法详解

串匹配算法描述

文本串 T 长度为$m$, 模式串 P 长度为$n$。需要做到以下几点

Detection: P 是否出现

Location: 首次出现的位置

Counting: 出现的次数

Emumeration: 出现在哪里

其中第二条是最重要的,解决好第二条问题,3、4两问都能顺利解决。

蛮力算法

自左向右,以字符为单位,依次移动模式串,知道某个位置发现匹配。

version #1

public int Match(string t,string p){

int n=t.Length;

int m=p.Length;

int i=0;

int......

Huffman编码树实现

定义

在Huffman编码树是基于加权最短路径树,具体定义见:Huffman Tree

实现过程

输入各个字符已经相应的字符权重

构建Huffman编码树节点向量

在向量中查找权重最小的两个节点,新建一个新的节点,其左右子树是两节点,权重为两个子树权重之和

添加到向量中,并删除两个字数

重复3-4,直到只有一个节点

注意点

查找两个最小节点的采用的是 Divide and Conquer ,算法复杂度为(logN), 如果采用遍历的方法算法复杂度达(2n). 将向量均分成两部分,分别求得每个部分的最小的两个Tuple1(Min1, Min2),和Tuple2(Min......