题解:LeetCode第163场周赛(推箱子没写出来)

我好菜啊,100coin都拿不到的一场,伤心。

第四题,有点难顶。先把前三题的解答写了,回头再自己写了后,补上第四题。

第一题:

就先把二维数组展平,循环移位后,在整回去,很自然就想到numpy里有个reshape,那就用一下吧,list转np,操作后再转回来。

第二题:

这一题就是一个二叉树的BFS,也叫层次遍历来着。

用一个FIFO队列,先把root压到队尾,然后每次把队首的节点弹出来,如果有left,right,就更新val值后压回去,直到队列为空即可,查询的话不用遍历二叉树,用个set保存一下所有值就好了。

第三题:

稍加思索后可以发现,只要先算出所有数的和,根据其%3的余数讨论一下就好了:

如果余数为2:

1.去掉1个余2的最小数(如果存在)。

2.去掉两个余1的最小数(如果存在)。

当然1和2肯定至少存在一种情况。

如果余数为1:

1.去掉1个余1的最小数(如果存在)。

2.去掉两个余2的最小数(如果存在)。

当然1和2肯定至少存在一种情况。

所以按每个数%3的余数分个组,排序一下,讨论一下余2还是余1,就好了。

似乎还是动态规划来的明白,而且好想一点?

dp[i][m]表示前i个数余数为m的最大和,


本文为我原创

本文禁止转载或摘编

-- --
  • 投诉或建议
评论