立扣(LeetCode)go语言学习练习 存放我主要利用力扣学习go语言的练习内容
今天的题是简单题，但是却拖了我一个多小时
究其原因是因为我想的太复杂了，或者说没有把问题简化。对于匹配的问题，我的思路始终是以单向计数为准，相同则+1不同则-1，这意味着就需要考虑上一个字符，而且还要没有匹配完剩下的能不能组成一对等等问题。
结果到头来这些问题相当复杂，其实简化非常简单，就是利用正负两极的对称性，规定两个字符的极性，而且其实题干意思是只有L和R两个字符，因此直接规定就行，这样意味着只要回零就是一次对称了，直接计数即可。
而且我也吧问题想复杂了，本来需要考虑到上一个字符就比较复杂了，万一中途又换了方向，有还得去看这个方向究竟是左侧变成右侧，还是右侧截断，这让各种情况的考虑无休止地下去。
因此，即使是简单题，如果没有合适的思路简化问题，就无法顺利解决问题的。
今天这道题没啥技术含量(绝对不是因为打卡题太难了)，就是对应关系容易弄混注意一下
今天主要是二叉搜索树BST的内容，当初以为不简单但实际上通过之后可以说是相当水了。
应该是遇到的第二个二叉树的题目，连预定义的结构体都一模一样，即使是看起来写的很水的时间和空间复杂度居然都能超90%
这一次是一个字符串搜索的东西，这时让我联想到了之前做数组实现的循环链表的时候的关键是取模。这个字符串提取出第一个其实也是遍历的过程，可以很容易想到用链表实现，但是总所周知动态分配的链表效率一般。
此时就想到了用数组实现链表，毕竟从输入就能确定链表的长度，这样就事先了只需要访问和索引数组就能随机访问的链表，预期效率会不错。
提交之后想不到效率这么高，空间复杂度都直接100%我是没想到的，但是时间复杂度是44%，原因应该是遍历了两遍。但是除了第一遍计数第二遍提取想不到什么好的思路了，可能用冒泡或者搜索树之类的方法可以做到一次遍历之后就能得出结果，而且我有些怀疑那些用链表做的速度也是差不多的。
更好的方法就没有啥思路了（不想看题解）
只要难度上升到了中等难度就能让我想个半天了，但是这个可以说是想的最久的。应该说是想的完整性中比较久的，之前的大多是经过其他人讨论或者题解的点拨才想明白的。
这次我在这个树当中找到了一些隐含的规律，虽然很清楚这种规律只适用于这种题的特殊情况，但是很有用。这是我第一次接触关于树的题型。
问题就在于首先递归访问，递归一般用在一些具有规律的重复性操作中，这些操作可以是定义一些变量，判断一些分支，其实可以看成一个大范围的for循环但又不太一样。
例如这里的每个节点的访问具有递归的潜在特性；其次是每次的反向访问，我立即就想到了用取模特性我就可以很快利用一个自增数作出自动反向的特性，而后就是怎么在同一层同时遍历这些节点，因为随着树的分支逐渐深入，看起来同一层的节点其实存在于许多不同的但是相同深度的子树当中，换句话说，这些“相邻”的节点是无法互相感知到的，因此直接在逐个访问是不现实的。
后面想到了用数组动态增加的方式，我就能在逐个访问子树的时候依次加上去，这样在一个数组看起来是一次性访问的，其实是在不同的循环内逐个添加进去的。
但是这里引入了新的问题，就是必须要确保子节点的访问顺序和这一层的访问顺序是一致的，例如这一层是从左到右，那么下一层访问也是从左到右，反之亦然。否则，就会出现每个树的节点左右颠倒，彻底毁了这个树，同步这一点其实还简单，因为只需根据方向确定读取顺序就行。
但是最大的问题是一致的遍历方向就导致这个数组在下一次循环就需要反过来访问了，因为方向发生了变化。
经过这些细节的反复整理总结之后，并且基于广度优先搜索的**，最终得出了一个最终方案。就是利用栈先入后出的特性来装这些被遍历的节点，而每个子节点的访问依旧是根据当前访问方向，这样只要保证每个循环访问这个数组都是后入先出就行了，这样就形成了有规律的一整个函数，那么，接下来只需要在合适的地方开始递归这个函数就行了。递归的本质就是套娃，在函数内部调用自己，而数组容器就是横跨这些函数之间的桥梁。
之后又经过了一些细节整理，包括先预先分配最大容量，而后再按需裁剪的方式来提高数组的访问效率，但是显然这样更占内存，在树很深的时候会更糟，而且递归由于其特性，上层函数的局部变量是没有释放的（因为压根没离开作用域），这样导致比单纯用for的内存开销更大。
提交结果执行时间是0ms，但是内存是19%，可以看到预分配数组占用很大了，毕竟裁剪也并不会让那部分多出来的空间直接释放，但是鉴于这是自己独立思考出来的算法，还是觉得颇有成就感的。
这道题其实到最后也是没想出来，和同学讨论了一天也难以出结果，到后面才看了一会题解。
这时才了解到这种题型就是“动态规划”，甚至这还是一道经典例题。其实题干里面的爬楼梯这个举例我一直觉得不太好，虽然最后不影响理解题干，不过那种跨两台阶只要最终台阶的体力，而且有些台阶甚至是花费0看起来有点离谱了，但是如果稍微拓展一下，例如放在不同节点路由的最短路由搜索中突然就变得形象了，毕竟对于计算机而言点对点只是一个结果罢了，就和我们常识中的拾级而上很不一样。
所谓动态规划，包含三个最重要的结构：最优子结构、边界、状态转移公式
对应到这道题，最优子就是最小阶梯代价，边界就是从第0或1级开始到结束，状态转移就是可选方案有跨1级或跨0级。
后面当我理解里面数组的用法之后就意识到了其中的巧妙之处，特别是如何利用数组逐个堆积的原理，巧妙地保证了前两个数组一定是最优的两个方案，这样只要每次只从前两个之间进行比较，就会自动淘汰掉其他的方案，直到边界吧最终的比较结果摆出来就是最优解了，可谓是巧妙。
因为状态转移公式是恒定了，因此我们无需关心之前阶梯是怎么走的，只需知道前两个阶梯均拥有到达这个阶梯的机会，而这两个阶梯又是基于这个原则必定是前面的最优解，因为最优解会随着下一阶的进入发生变化，因此我们平等地看到分别到达这一级的方案，并再次计算出这一阶的最优解，直到阶梯用完，当前最优解即为全题最优解。