被老板炒了？被马子甩了？被C罗涮了？被李刚撞了？喝酒伤身，来做题发泄吧。该怎么处理
日期：2014-05-18 浏览次数：20713 次
被老板炒了？被马子甩了？被C罗涮了？被李刚撞了？喝酒伤身，来做题发泄吧。
刚上论坛，看到一行变绿了的字
横空出世，席卷Csdn：记微软等100题系列数次被荐
进去一看，乖乖，所有公司的面试算法题都是从这里来的？那就做呗，反正打游戏也是玩，做题也是玩，别的公司总不会因为你游戏玩的好招你当高层的，我打算有空了想玩游戏了就一道一道做，管它做的对不对呢，好歹也算见过这题了。
在SQL版，当然要用SQL来解，T-SQL应该也算门语言对吧。
废话少说，第一题开始：
1.把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树 节点的数据结构如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
我用了个取巧的办法，直接UPDATE+子查询了，反正最后就是要排序对吧，从大到小排出来就对了。。。TOP 1+ORDER BY解决战斗。。。。。。。
------解决方案--------------------
2.设计包含min函数的栈。
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
我的解法，加了一列。
我只用了索引的排序功能，没用统计信息，应该不算犯规吧。。。。
刚上论坛，看到一行变绿了的字
横空出世，席卷Csdn：记微软等100题系列数次被荐
进去一看，乖乖，所有公司的面试算法题都是从这里来的？那就做呗，反正打游戏也是玩，做题也是玩，别的公司总不会因为你游戏玩的好招你当高层的，我打算有空了想玩游戏了就一道一道做，管它做的对不对呢，好歹也算见过这题了。
在SQL版，当然要用SQL来解，T-SQL应该也算门语言对吧。
废话少说，第一题开始：
1.把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树 节点的数据结构如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
我用了个取巧的办法，直接UPDATE+子查询了，反正最后就是要排序对吧，从大到小排出来就对了。。。TOP 1+ORDER BY解决战斗。。。。。。。
- SQL code
IF OBJECT_ID('TreeNode') IS NOT NULL DROP TABLE TreeNode
GO
CREATE TABLE TREENODE (
ID INT NOT NULL UNIQUE
,VAL INT
,LID INT
,RID INT
)
/*
10
/ \
6 14
/ \ / \
4 8 12 16
*/
INSERT INTO TREENODE
SELECT 10,10,6,14 UNION ALL
SELECT 6,6,4,8 UNION ALL
SELECT 14,14,12,16 UNION ALL
SELECT 4,4,NULL,NULL UNION ALL
SELECT 8,8,NULL,NULL UNION ALL
SELECT 12,12,NULL,NULL UNION ALL
SELECT 16,16,NULL,NULL
SELECT * FROM TREENODE
/*
ID VAL LID RID
----------- ----------- ----------- -----------
10 10 6 14
6 6 4 8
14 14 12 16
4 4 NULL NULL
8 8 NULL NULL
12 12 NULL NULL
16 16 NULL NULL
*/
UPDATE T1 SET
LID=(SELECT TOP 1 ID FROM TREENODE T2 WHERE T2.VAL<T1.VAL ORDER BY VAL DESC)
,RID=(SELECT TOP 1 ID FROM TREENODE T2 WHERE T2.VAL>T1.VAL ORDER BY VAL ASC)
FROM TREENODE T1
SELECT * FROM TREENODE ORDER BY ID
/*
ID VAL LID RID
----------- ----------- ----------- -----------
4 4 NULL 6
6 6 4 8
8 8 6 10
10 10 8 12
12 12 10 14
14 14 12 16
16 16 14 NULL
*/
------解决方案--------------------
2.设计包含min函数的栈。
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
我的解法，加了一列。
我只用了索引的排序功能，没用统计信息，应该不算犯规吧。。。。
- SQL code
IF OBJECT_ID('MYSTACK') IS NOT NULL DROP TABLE MYSTACK
GO
CREATE TABLE MYSTACK(
ID INT IDENTITY(1,1)
,VAL INT
,MINVAL INT
,PRIMARY KEY(
ID DESC
)
)
GO
IF OBJECT_ID('MYPUSH') IS NOT NULL DROP PROCEDURE MYPUSH
GO
CREATE PROCEDURE MYPUSH(@VAL INT)
AS
BEGIN
DECLARE @MINVAL INT
SELECT TOP 1 @MINVAL=VAL FROM MYSTACK
INSERT INTO MYSTACK(VAL,MINVAL)
SELECT @VAL,CASE WHEN @VAL<@MINVAL OR @MINVAL IS NULL THEN @VAL ELSE @MINVAL END
END
GO
IF OBJECT_ID('MYPOP') IS NOT NULL DROP PROCEDURE MYPOP
GO
CREATE PROCEDURE MYPOP
AS
BEGIN
DECLARE @NOWID INT,@NOWVAL INT
SELECT TOP 1 @NOWID=ID,@NOWVAL=VAL FROM MYSTACK
DELETE FROM MYSTACK WHERE ID=@NOWID
SELECT @NOWVAL
END
GO
IF OBJECT_ID('MYMIN') IS NOT NULL DROP PROCEDURE MYMIN
GO
CREATE PROCEDURE MYMIN
AS
BEGIN
SELECT TOP 1 MINVAL FROM MYSTACK
END
GO
MYPUSH 7
GO
MYPUSH 4
GO
MYPUSH 5
GO
SELECT * FROM MYSTACK
GO
MYMIN
GO
MYPOP
GO
MYPOP
GO
MYMIN
GO
------解决方案--------------------
xue xi
------解决方案--------------------
顶楼上····
------解决方案--------------------
学习.
------解决方案--------------------
学习了！
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
