刚上论坛，看到一行变绿了的字
横空出世，席卷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 TreeNodeGOCREATE TABLE TREENODE (ID INT NOT NULL UNIQUE,VAL INT,LID INT,RID INT)/* 10 / \ 6 14 / \ / \4 8 12 16*/INSERT INTO TREENODESELECT 10,10,6,14 UNION ALLSELECT 6,6,4,8 UNION ALLSELECT 14,14,12,16 UNION ALLSELECT 4,4,NULL,NULL UNION ALLSELECT 8,8,NULL,NULL UNION ALLSELECT 12,12,NULL,NULL UNION ALLSELECT 16,16,NULL,NULL SELECT * FROM TREENODE/*ID VAL LID RID----------- ----------- ----------- -----------10 10 6 146 6 4 814 14 12 164 4 NULL NULL8 8 NULL NULL12 12 NULL NULL16 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 T1SELECT * FROM TREENODE ORDER BY ID /*ID VAL LID RID----------- ----------- ----------- -----------4 4 NULL 66 6 4 88 8 6 1010 10 8 1212 12 10 1414 14 12 1616 16 14 NULL*/------解决方案--------------------
2.设计包含min函数的栈。
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
我的解法，加了一列。
我只用了索引的排序功能，没用统计信息，应该不算犯规吧。。。。
- SQL code
IF OBJECT_ID('MYSTACK') IS NOT NULL DROP TABLE MYSTACKGOCREATE TABLE MYSTACK(ID INT IDENTITY(1,1) ,VAL INT,MINVAL INT,PRIMARY KEY(ID DESC))GOIF OBJECT_ID('MYPUSH') IS NOT NULL DROP PROCEDURE MYPUSHGOCREATE PROCEDURE MYPUSH(@VAL INT)ASBEGINDECLARE @MINVAL INTSELECT TOP 1 @MINVAL=VAL FROM MYSTACKINSERT INTO MYSTACK(VAL,MINVAL)SELECT @VAL,CASE WHEN @VAL<@MINVAL OR @MINVAL IS NULL THEN @VAL ELSE @MINVAL ENDENDGOIF OBJECT_ID('MYPOP') IS NOT NULL DROP PROCEDURE MYPOPGOCREATE PROCEDURE MYPOPASBEGINDECLARE @NOWID INT,@NOWVAL INTSELECT TOP 1 @NOWID=ID,@NOWVAL=VAL FROM MYSTACK DELETE FROM MYSTACK WHERE [email protected]SELECT @NOWVAL ENDGOIF OBJECT_ID('MYMIN') IS NOT NULL DROP PROCEDURE MYMINGOCREATE PROCEDURE MYMINASBEGINSELECT TOP 1 MINVAL FROM MYSTACKENDGOMYPUSH 7 GOMYPUSH 4GOMYPUSH 5GOSELECT * FROM MYSTACKGOMYMINGOMYPOP GOMYPOPGOMYMINGO
------解决方案--------------------
xue xi
------解决方案--------------------
顶楼上····
------解决方案--------------------
学习.
------解决方案--------------------
学习了！