首先说一下：这个题是在网上看的，老题了，属于经典题目那样，至于是不是微软的，可能是，可能不是，但是目的是为了锻炼基础，巩固算法。至于我给的答案，虽然是我推敲了之后发的，但能力有限，并不代表是最好的，也是发到博客上和朋友们一起思考，看看如何优化到最好，这才是学习的过程，而不是单纯为了题目，所以，大家可以考虑下，过一段时间我再贴代码，高手或者看过的直接飘过即可。
大部分情况都不会写到O(n2)，而且题目也很简单，所以代码就不直接贴出来了。不算很难的东西：）
(1)一个整数数列，元素取值可能是0—65535中的任意一个数，相同数值不会重复出现。0是例外，可以反复出现。
请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻。
注意：
- 5个数值允许是乱序的。比如： 8 7 5 0 6；
- 0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4；
- 0可以多次出现；
- 复杂度如果是O(n2)则不得分。
(2)设计一个算法，找出二叉树上任意两个结点的最近共同父结点，复杂度如果是O(n2)则不得分。
(3)一棵排序二叉树，令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
(4)一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。复杂度最好是O(n)，如果是O(n2)则不得分。
(1)首先先对非0的数字进行排序，然后检查插值是否为0，如果为0，则不操作，否则与0的个数相减，最后判断0的个数是否大于0。这里排序我用了二叉排序树，这样能够一次读取之后排序并记录0的个数并把0排除在外。然后再先序遍历得到有序列，每个节点（除了第一个）与前一个节点的数字相减再减1（思考），如果等于0，就是连续的，大于0，看看有几个0可以用，比如等于1，我们还有1个0可以用，就OK，最后看看我们用了几个0。我的不是答案，只是探讨，也是巩固基础，可能还有更好的排序方式。
First#region First
namespace Practice
…{
//创建一个二叉排序树
public class TreeNode
…{
public int data;
public TreeNode leftNode;
public TreeNode rightNode;
}
class Program
…{
static int zeros = 0;
static TreeNode root;
static bool isFirst = true;
static int LastNumber = 0;
static void Main(string[] args)
…{
int[] numbers = …{ 8, 7, 5, 6, 9 };
BuildSortedTree(numbers);
bool isTrue = Checker(root);
Console.WriteLine(isTrue);
Console.ReadKey();
}
static void BuildSortedTree(int[] numbers)
…{
//创建第一个节点
TreeNode node = new TreeNode();
node.data = numbers[0];
node.leftNode = null;
node.rightNode = null;
root = node;
//读取每个数并排序，不包括0，记录下0的个数
for (int i = 1; i < numbers.Length; i++)
…{
if (numbers[i] != 0)
…{
CreateNode(node, numbers[i]);
}
else
…{
zeros++;
}
}
}
static TreeNode CreateNode(TreeNode node, int data)
…{
if (node == null)
…{
node = new TreeNode();
node.data = data;
node.leftNode = null;
node.rightNode = null;
return node;
}
if (data > node.data)
…{
node.rightNode = CreateNode(node.rightNode, data);
}
else
…{
node.leftNode = CreateNode(node.leftNode, data);
}
return node;
}
static bool Checker(TreeNode node)
…{
if (zeros == 4)
…{
return true;
}
if (node != null)
…{
Checker(node.leftNode);
Console.WriteLine(node.data);
if (isFirst)
…{
LastNumber = node.data;
isFirst = false;
}
else
…{
int diff = node.data - LastNumber - 1;
zeros = zeros - diff;
LastNumber = node.data;
}
Checker(node.rightNode);
}
//如果0还没有用完
if (zeros >= 0)
…{
return true;
}
else
…{
return false;
}
}
}
}
#endregion
(2)这一题有一点复杂，首先我们需要找到两个节点的最小路径，这样我们才能够知道如何直接就寻找到这两个节点，并用堆栈来记录下路径，然后我们通过对比最小路径，看看从何处开始分叉，分叉的地方即是最短的父节点。这里有几个地方有点难写：（第一，最短路径，第二，记录后是堆栈，还得反转。最短路径遍历1-2次可获得，我用的2次，没有优化，比较忙，然后反转堆直接转换成链表去反转的，用的.NET的库，本身写起来也不难，也是O(n/2)。所以复杂度是O(n+n/2)=O(n)。
Second#region Second
namespace TreeFinder
…{
public class TreeNode
…{
public int data;
public TreeNode leftChild;
public TreeNode rightChild;
//用队列保存节点路径
public Stack<int> road = new Stack<int>();
//判断是否已经找到该节点，否则不继续保存
public bool isFinded = false;
}
class Program
…{
static TreeNode treeNode;
static int[] numbers = …{ 4, 2, 1, 3, 9, 7, 12, 5, 6, 11, 18, 14, 20 };
static TreeNode emptyNode = new TreeNode();
static bool isFinded = false;
static void Main(string[] args)
…{
emptyNode.data = -1;
CreateTree();
TreeNode node1 = new TreeNode();
TreeNode node2 = new TreeNode();
node1.data = 11;
node2.data = 6;
//FindFarther(null, treeNode, node1, node2);
node1.road = FindShortRoad(treeNode, node1, -1);
isFinded = false;
node2.road = FindShortRoad(treeNode, node2, -1);
Queue<int> path = FindFarther(node1, node2);
TreeNode node = FindNode(treeNode, path);
Console.WriteLine(node.data);
Console.ReadKey();
}
//找父节点
static TreeNode FindNode(TreeNode node, Queue<int> path)
…{
while (path.Count > 0)
…{
int side = path.Dequeue();
if (side == 1)
…{
node = node.rightChild;
}
else if(side == 0)
…{
node = node.leftChild;
}
}
return node;
}
//找最短的路径
static Stack<int> FindShortRoad(TreeNode root, TreeNode node1, int rl)
…{
if (root != null && !isFinded)
…{
node1.road.Push(rl);
if (root.data == node1.data)
…{
isFinded = true;
return node1.road;
}
node1.road = FindShortRoad(root.leftChild, node1, 0);
node1.road = FindShortRoad(root.rightChild, node1, 1);
if (!isFinded)
…{
node1.road.Pop();
}
}
return node1.road;
}
static void PrintRoad(TreeNode node)
…{
while (node.road.Count > 0)
…{
Console.WriteLine(node.road.Pop());
}
}
//找父节点
static Queue<int> FindFarther(TreeNode node1, TreeNode node2)
…{
int count = Math.Abs(node1.road.Count-node2.road.Count);
Queue<int> path = new Queue<int>();
//弹出大的那一边，也可以不弹出，自选
if (node1.road.Count > node2.road.Count)
…{
PopupMore(node1, count);
}
else if(node1.road.Count < node2.road.Count)
…{
PopupMore(node2, count);
}
//变成链表并反转
List<int> node1List = node1.road.ToList();
List<int> node2List = node2.road.ToList();
node1List.Reverse();
node2List.Reverse();
for (int i = 0; i < node1List.Count && i < node2List.Count; i++)
…{
if (node1List[i] == node2List[i])
…{
path.Enqueue(node1List[i]);
}
else
…{
break;
}
}
return path;
}
static void PopupMore(TreeNode node, int count)
…{
while (count > 0)
…{
node.road.Pop();
count–;
}
}
//创建树
static void CreateTree()
…{
treeNode = new TreeNode();
treeNode.data = numbers[0];
treeNode.leftChild = null;
treeNode.rightChild = null;
TreeNode node = treeNode;
for (int i = 1; i < numbers.Length; i++)
…{
node = CreateNode(node, numbers[i]);
}
}
//创建节点
static TreeNode CreateNode(TreeNode node,int data)
…{
if (node == null)
…{
node = new TreeNode();
node.data = data;
node.leftChild = null;
node.rightChild = null;
return node;
}
if (data > node.data)
…{
node.rightChild = CreateNode(node.rightChild, data);
}
else
…{
node.leftChild = CreateNode(node.leftChild, data);
}
return node;
}
}
}
#endregion
(3)我们可以算出我们需要的值，最大值和最小值之和的一半，得到这个值之后，我们直接找节点，如果值比节点值大，就向右找，否则向左找，找到最后的尾部的节点后，比较尾部节点和父节点的绝对值即可（注：例如找17这个节点，找到18和14，然后14右子树喂15，会找到18这个节点，然后去找18右节点，这里就说17在14和18之间的区间里，然后找到尾部就是最靠近17的，同时还要判断父节点和子节点谁更接近）。
Third#region Third
static TreeNode FindNearNode(TreeNode farther,TreeNode root, int data)
…{
if (data > root.data && root.rightChild != null)
…{
root = FindNearNode(root,root.rightChild, data);
}
else if (data < root.data && root.leftChild != null)
…{
root = FindNearNode(root,root.leftChild, data);
}
else if (data == root.data)
…{
return root;
}
else
…{
if (Math.Abs(farther.data - data) < Math.Abs(root.data - data))
…{
return farther;
}
else
…{
return root;
}
}
return root;
}
#endregion
(4)最后一题，我们可以先计算N+1的值，然后将所有的值放到一个Hash表里（元素都不重复），这可以说不叫遍历，可以让用户输入，反正最后我们得到了hash表，然后我们遍历一次1-N，得到每个数的另一半，如N+1-当前的数，然后在hash里找这个数是否存在即可（O（1））。
Last#region Last
namespace FindNumbers
…{
class Program
…{
static int[] numbers = …{ 1, 2, 3, 4, 5, 10, 29, 14, 39, 71, 200, -39, 72, 11 };
static int number = 0;
static Dictionary<int, int> dNumbers;
static void Main(string[] args)
…{
int count = 0;
number = numbers.Length + 1;
AddToDictionary();
for (int i = 0; i < numbers.Length; i++)
…{
int temp = number - numbers[i];
if (dNumbers.ContainsKey(temp))
…{
count++;
}
}
Console.WriteLine(“Numbers is “ + count/2);
Console.ReadKey();
}
static void AddToDictionary()
…{
dNumbers = new Dictionary<int,int>();
for (int i = 0; i < numbers.Length; i++)
…{
dNumbers.Add(numbers[i], numbers[i]);
}
}
}
}
#endregion
= End of buffer =
先支持你下再说。。。
[b]@lfdeng[/b]
难得你今天这么有雅兴啊。。哈哈。。
(4)两数的和为N+1，那不只有{1，N},{2，N – 1},{3，N – 2},…
结果直接就是(N – 1)/2，（当N为奇数）；N/2，（当N为偶数）
[b]@lfdeng[/b]
呵呵，最主要要注意的是，1.无序,2.数字不可能连续,{1,100,1000}。不简单，当然也不难。
原来题目都没看懂，呵呵
用一个数组或字典，什么都好，关键是方便查找
然后遍历数列，取一个元素e，在建立的数组A中找N+1-e
如果能找到，count++
如果找不到，将e存入数组，A[e]=e
遍历一次就行了，count是结果。
对了，如果能找到，去掉那个值，A[e]=0
(3) 计算min，不停的找左结点，找出最小值
计算max，不停的找右结点，找出最大值
f=(max + min)/2;
node = root;
AverageNode = FindAverage(null, node, f);
/* 判断结点是否为空的步骤省略。。。 */
/* FindAverage(Node, Node, int) */
FindAverage(Node BiggerParent, Node node, int f)
{
if (f <= node.Value)
{
if(node.HasLeftNode())
{
FindAverage(node, node.Left, f);
}
else
{
return node;
}
}
else
{
if(node.HasRightNode())
{
FindAverage(BiggerParent, node.Right, f);
}
else
{
return BigParent;
}
}
}
怎么排版这么难看。。。
(2) 遍历一次二叉树，用回溯法找出2个结点的路径，如{left, right, right, left, right}和{left, right, left, left, right}
比较2个路径开始的相同部分{left, right}，按这个路径就能找到共同的父结点。
其实来说应该不算很难，但是细节的很多地方还是要注意的。
我一直在想第一个问题,从昨天到现在.
应该有一个不用排序的方法,仅仅从基本运算中就能找到答案.
有点卡壳~~~~~
不是我的强项,汗.
[b]@Estyle[/b]
算法也不是我的强项，所以最近在看这些题，当开拓思路啦。。：）
刚才倒是总结出第一个问题的规律了, 但是要应用这个规律, 代码里面要遍历两次那5个数字, 失败.
重新想~~~
PS: 规律是, 看每个元素减去他们的非零平均值的差的绝对值的合.
如果没有0, 这个数字必须是6.
如果有1个0, 这个数字必须是小于6, 或者等于6但是没有任何一个元素等于它们的非零平均值.
如果是2个0, 这个数字必须小于4.67.
如果是3个0, 这个数字必须小于或等于4.
如果是4个或者5个0, 必连续.
这个方法等问题在于, 平均值要先遍历一次加总后才算得出来.
[b]@Estyle[/b]
和我开始的想法差不多，不过我用的不是非零平均值，而是最小值。
唉, 想不出来.
还是排序简单, 只要最大的和最小的数字的差的绝对值不超过4, 无论有多少个0, 都是连续的.
其实不用排, 只要遍历一次找一找最大和最小的数就OK.
@lfdeng
最开始我也想的是最小值, 后来发现最小值要先查一遍才能找到, 于是就用平均值了.
PS: 居然过了一天才又想起, 平均值也要先查一遍~~~
[b]@Estyle[/b]
你的那个数学的观点很有意思，呵呵。
[b]@soundbbg[/b]
我可是给你讲过这个观点哦，你不是没听明白吧。。。
[b]@lfdeng[/b]
别人是小于某个数值好吧..
[b]@GuoJing[/b] “这里有几个地方有点难写：第一，最短路径，第二，记录后是堆栈，还得反转。”
既然需要反转，为什么要用堆栈？队列不是挺好吗
[b]@lfdeng[/b]
最短路径和迷宫类似，用堆栈保留路径，你用队列能保留路径吗？上一步走的路径就先被弹出了。。
[...] 几道微软面试的算法题 [...]