被老板炒了？被马子甩了？被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 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&lt;T1.VAL ORDER BY VAL DESC),RID=(SELECT TOP 1 ID FROM TREENODE T2 WHERE T2.VAL&gt;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&lt;@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 ID=@NOWIDSELECT @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
[解决办法]
顶楼上&#183;&#183;&#183;&#183;
[解决办法]
学习.
[解决办法]
学习了！ 
 
[解决办法]
学习.
[解决办法]
伤的不轻啊 看来
[解决办法]
每天回帖即可获得10分可用分！小技巧：
[解决办法]
学习了，。！
[解决办法]
学习了~
[解决办法]
学习了
[解决办法]
好好学习，天天有钱赚
[解决办法]
学习.
[解决办法]

[解决办法]
学习。
[解决办法]
压力很大
[解决办法]
..........
[解决办法]
路过看看
[解决办法]

[解决办法]
惭愧啊，我连思路都没有。
搞了几年开发，却连些基本基础的底层东西都不了解。
[解决办法]
    我是冲标题来的 。。。。
[解决办法]
LZ不是标题党
[解决办法]

[解决办法]
学习。
[解决办法]
看 看
[解决办法]
学习。。。好贴，帮顶
[解决办法]
恭喜鸭子。

我已死。。
[解决办法]
技术贴，标题很技术，内容更技术。
[解决办法]
什么情况？
[解决办法]
我还以为出了什么事
[解决办法]
看不太懂 我是打酱油的
[解决办法]
SQL就能写出这个 我Java都写不出来，晕呀！悲哀了！！
[解决办法]
好厉害的鸭子，可惜是李钢家的
[解决办法]
标题党。。。。。。。
[解决办法]
还以为是时事贴
[解决办法]
学习.
[解决办法]
学习，其实我是来看lz怎么被甩的
[解决办法]
不被甩才怪
[解决办法]


凑凑热闹
------解决方案-------------------- 
 
亢奋。
[解决办法]
C/C++ code7788
[解决办法]
冲标题来的路过~
[解决办法]

[解决办法]
来10分
[解决办法]
每天回帖即可获得10分可用分！
[解决办法]
楼主ID有意思
[解决办法]
呵呵，这么好的点子，实在不易。支持一个先
[解决办法]
探讨
惭愧啊，我连思路都没有。
搞了几年开发，却连些基本基础的底层东西都不了解。

[解决办法]

[解决办法]
sql文盲飘过。。。
顺便膜拜lz！！！
[解决办法]
晕，看不懂啊

[解决办法]
强人啊。看不懂
[解决办法]
探讨
每天回帖即可获得10分可用分！小技巧：

[解决办法]
看不懂
[解决办法]
的，大的子
[解决办法]
dddddddddddddddddd
[解决办法]
~~~
[解决办法]
cun cui shi lai xue xi de!
[解决办法]
探讨
强人啊。看不懂

[解决办法]
强人啊。看不懂
[解决办法]
没分了
[解决办法]
  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 www.ningbofashionfair.cn
  BSTreeNode *m_pRight; // right child of node
};

我用了个取巧的办法，直接UPDATE+子查询了，反正最后就是要排序对吧，从大到小排出来就对了。。。TOP 1+ORDER BY解决战斗。。。。。。。
[解决办法]
楼主标题党。


不过内容挺实在。
[解决办法]
学习了~~~~~~~~~~~~~~
[解决办法]
MARK,学习学习~

[解决办法]
冲标题来的。。。
[解决办法]
我也来学习学习
[解决办法]
学习 压力大很
------解决方案--------------------  
持续跟踪中。。
[解决办法]
会做题的鸭子，鸭子中的战斗机，oh yeah！
[解决办法]
探讨

学习 压力大很

[解决办法]
题目智慧，内容也智慧，一个字，好
[解决办法]
膜拜下强人
[解决办法]
学习下
[解决办法]
脑袋乱码处理中
[解决办法]
Y被踢了
[解决办法]
让我如何是好啊
[解决办法]
我帮你！@
[解决办法]
学习。。。
[解决办法]
SQL code第六题用列来做CREATE TABLE #TB(NUM INT,SUMNUM INT)DECLARE @I INTSELECT @I=0while @I&lt;10BEGIN    INSERT INTO #TB VALUES(@I,0)    SELECT @I=@I+1ENDWHILE exists(SELECT b.num FROM #TB B where SUMNUM&lt;&gt;(SELECT COUNT(*) FROM #TB A where A.sumnum=b.num))BEGIN    DECLARE @NUM INT    DECLARE CUR CURSOR FOR SELECT NUM FROM #TB    OPEN CUR    FETCH NEXT FROM CUR INTO @NUM    WHILE @@fetch_status=0        BEGIN            UPDATE #TB SET SUMNUM=(SELECT COUNT(*) FROM #TB A WHERE A.SUMNUM=B.NUM) FROM #TB B WHERE B.NUM=@NUM            FETCH NEXT FROM CUR INTO @NUM        END    CLOSE CUR    DEALLOCATE CURENDSELECT * FROM #TBDROP TABLE #TB

被老板炒了？被马子甩了？被C罗涮了？

热点推荐