学习笔记-字典序

嗯......没想到还真给做出来了。

虽然最后速度还是很慢，但好在使用的额外内存就只有一个int数组，所以空间复杂度还说得过去......但是leetcode的机器真的有点迷，本来我一堆额外的静态方法和变量，结果提交上去只用了35M，把所有静态方法和额外的代码删掉以后再提交，反而多了0.2M，执行时间也在80到120之间反复横跳。

结果已经远超预期了，本来觉得不看题解根本做不了，然后用字典序做了出来。字典序超时以后想尽各种办法优化，最后终于勉强进了200ms以内，通过了。

优化的过程中突然发现，所有可行的排列连在一起也是满足字典序中的“相邻”的。于是想到，没必要拘泥于字典序的规则，完全可以自己定义一个规则然后只枚举满足条件的排列。

最后还是没找到可以只枚举满足条件的排列的方法，但比起基于字典序的优化，已经好很多了。这是字典序优化后的代码，在我的机器上要用200ms左右:

然后这是新的代码，自己的机器上是100ms左右：

所以说那些长的要死还各种if嵌套的代码是不可取的，if多只能说明思路上就是错的，才要考虑更多例外的情况......

都说不要死磕一道题，但有的时候我在想，如果看到某道题脑海里就有了答案，那去做这道题还有什么意义可言吗......感觉那样就不是学习而是记忆了。记住某道题，或者某类题的答案，下次出现同类就可以轻松应对......目的是面试的话可以，但对自身思考问题的能力真的有提升吗。

这次的收获还是挺多的，比如学会了字典序，还有在思考不出结果时的正确做法。

简而言之，想不出办法不意味着智商低，知识量不够，仅仅只是理解不够深刻。字典序算法到底是怎么回事，我到现在还是没完全理解，但我依旧在理解字典序的过程中获得了灵感。

一开始想不通为什么后面要reverse一下，想不通为什么reverse可以代替排序......过了很久才明白，reverse对于这一次的调用确实没有任何意义，它是在为下一次调用做准备。

于是我明白了，要从更加宏观的角度去思考，单独去看某一行代码起到了什么作用，很多时候是看不出来的，减去这一行，看看最终的结果有什么变化，就可以知道它的真正作用了。

排序的方法暂时可以放一下了，还得用回溯接着磕这道题。