依葫芦画瓢写一个
第一题解得比较烂,bug太多就不贴了,总体思路是
1.将其他用户的徽章和自己要出的徽章放在一个视图里,做成一个in 和一个out的列的视图里,id为0的行是自己,且in为空
例如
user_idin out
0
德国
2
德国 虎
2.递归找出所有能换到所缺徽章的路径(不关心徽章个数)
3.最后检查用户id,个数是否正确。
第二题(偷懒直接copy评委的评语了)
先找出所有雷的坐标,然后在算出雷周围的坐标,分组后计数。这些坐标中可能也包括了雷点。
最后用所有坐标集合和上述两个做外连接算出要拼接的字符(数字或地雷或空格),用Wm_Concat拼成一串。
Wm_Concat里面的顺序是不受控制的,应该用LISTAGG更好。
在计算地雷邻居坐标的时候,和8行的小集合做了笛卡尔积,比起和所有坐标的集合做笛卡尔积的方法更加高效。
这一题如果去掉正则,用LISTAGG代替wm_concat效率会更好。
附加题
思路(继续copy):
本解法试图将连续的空位分片,找出其中可以确定的,遍历剩下的成片空位的组合,如果组合中的空位总数=未分配雷数,则可能为答案, 对其进行校验。
步骤:
1.求出连续的空格
2.根据数字找出能够确定是雷的空格
3.根据第2步和第1步结果求出确定的连续的雷
4.根据第3步结果求出确定的不是雷的空格
5.根据第4步和第一步结果求出确定的连续的不是雷的空格
6.遍历并校验剩下的不确定的连续空格的组合
求连续空格的部分之前连9*9的都弄不出来,后来做了一些优化:
posn 为pos的相邻空格
例如
1 2 3
4 5 6
都是空格
对于5的话有(5,1) , (5,2), (5,3), (5,4), (5,6)
用min或max函数将数据量减到最小留下 (5,1) 或者(5,6)
Rl AS
(SELECT Pos, MIN(Ps) Posn/*减少递归路径*/
FROM (SELECT *
FROM Ra
WHERE Vn = ' '
OR Ps IS NULL)
WHERE v = ' '
GROUP BY Pos),
Rg AS
(SELECT Pos, MAX(Ps) Posn /*减少递归路径*/
FROM (SELECT *
FROM Ra
WHERE Vn = ' '
OR Ps IS NULL)
WHERE v = ' '
GROUP BY Pos),
Re AS
( /* 求出相关联的块的集合*/
SELECT DISTINCT Connect_By_Root(Pos) Root, Pos
FROM Rl
START WITH Sign((SELECT COUNT(*) FROM Rl WHERE PosPosn)) IN (1, 0) /*判断从左上角还是右下角开始*/
AND (PosPRIOR Pos
UNION ALL
SELECT DISTINCT Connect_By_Root(Pos) Root, Pos
FROM Rg
START WITH Sign((SELECT COUNT(*) FROM Rl WHERE PosPosn)) = -1 /*判断从左上角还是右下角开始*/
AND (Pos > Posn /*从右下角的块或者单独的块开始*/
OR Posn IS NULL)
CONNECT BY PRIOR Pos = Posn
AND Pos < PRIOR Pos)
示例图
4*4的连续空格,矩形是比较理想的情况
Rl
→
|