【每日算法Day 30】六月回顾总结

回顾

六月上旬，跟着高淇老师的课程学着手写一个简易的ORM框架，框架主要做了两件事：1. 获取目标数据库的表信息并自动生成POJO类源代码到项目下；2. 根据用户（开发者）提供的POJO对象进行增删改，根据提供的SQL进行查询，封装查询的结果到对应的POJO对象并返回单个POJO或List<POJO>。其中涉及到JDBC、数据库连接池、Java反射、IO流、设计模式（模板方法、简单工厂模式、单例模式、原型模式）、Java集合框架等知识。

六月下旬，入门了Spring MVC开发流程。包括xml的配置（Maven pom.xml管理依赖、web.xml配置DispatcherServlet与过滤器、spring-servlet.xml配置DispatcherServlet的实例）、使用@Controlller @RequestMapping的跳转方式、Spring MVC的数据绑定，以及使用EL+JSTL在jsp视图中取出处理后的数据并返回给浏览器。

算法方面，上旬做的算法题目是leetCode的每日一题，说实话东一榔头西一棒子也不够系统。其中值得注意的点有：

1. 限制运算方式求1+2+…+n：不能使用循环可转为递归，不能使用条件判断可以使用短路（或try catch），不过实际意义可能不大。不过俄罗斯农民乘法结合移位却能实现快速乘法。
2. 新21点：动态规划结合反序求解。
3. 除自身外数组元素的乘积：数组前缀和前缀积后缀和后缀积有时能有预想不到的意义和效果。
4. 并查集的构造、路径压缩。
5. 回文数：对数字的逆序翻转可以用不断地取余和除10再逆向实现。
6. 每日温度、下一个更大元素：单调栈的使用。
7. 无重复字符的最长子串：滑动窗口与哈希数组的使用。

下旬开始按照分类来做，包括的点有：

1. 数组中：在按特定要求移动（删除）数组元素时双指针的使用，两次分块翻转相当于平移数组，数组本身也可以用作哈希（在某些限制使用O(n)额外空间且取值范围有限的的情况下可以考虑自身用作哈希）。Arrays.euqals(arr1,arr2) Arrays.hashCode(arr)的使用。
2. 字符串：滚动哈希匹配子串，字符串按字典序排序与公共前缀的关系，唯一字符（数量）与哈希数组的关系，验证同构字符串（或字符串数组）需要使用map正反各来一次，字母异位词使用hash数组统计字符出现次数再比较两个数组是否相等。动态规划或中心扩展寻找最长回文子串。
3. 算术：在处理多种状态的输入并且不同状态下同一输入会有不同结果时构造确定有限状态机(Deterministic Finite Automaton)可以避免复杂的条件选择语句。Integer.parseInt(String, int base)可以选择进制来转换。字符串模拟乘法，先按位乘再整理。
4. 二叉树的前中后序遍历的递归、迭代写法，层次遍历的迭代写法，与路径相关的值传递时要复制一份值传递，使用迭代写法时，可以将值与节点封装在一起入栈。BST或普通二叉树的LCA（最低公共祖先问题）。

接下来的计划

• 七月份：
  • 使用上午的时间按照公开课学完SSM之Mybatis和Spring初阶入门，能照葫芦画瓢做一个完整的小项目。
  • 下午的时间刷剩余分类的基础算法题。包括回溯、动态规划、链表、二分查找、矩阵、DFS和BFS、栈和堆、位操作、拓扑排序、随机、图、并查集、字典树。
  • 晚间复习数据库知识，学习MySQL和Redis。
• 八月份：
  • 上午阅读《互联网轻量级框架整合开发》，从原理层面强化对之前学习的SSM的理解，同时也学习更多前面公开课里没有的知识，深入各组件开发。
  • 下午的话，前半个月按照分类刷一遍进阶算法题，同时强化对各分类基础思维的理解；后半个月学习Github某高星算法项目作者的GitBook。此外，把《剑指Offer》剩余的部分过一遍补充上来，后面不论秋招进度如何一有空就要保持二刷重点250题。
  • 晚间对照JavaGuide查漏补缺，巩固各项基础。完善简历，准备面试。