被老板炒了？被马子甩了？被C罗涮了？被李刚撞了？喝酒伤身，来做题发泄吧。该怎么处理

被老板炒了？被马子甩了？被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解决战斗。。。。。。。

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

------解决方案--------------------
顶楼上····

------解决方案--------------------
学习.

------解决方案--------------------
学习了！

被老板炒了？被马子甩了？被C罗涮了？被李刚撞了？喝酒伤身，来做题发泄吧。该怎么处理

相关推荐