学习方法

  • 知识切片
  • 刻意练习
  • 反馈

基本功是区别业余选手和职业选手的根本
基础动作的分解训练和反复训练->最大的误区
算法题只做一遍是完全不够的
台球
网球一样
刻意联系－－过遍数(五毒神掌)　练习五遍！！！
练习缺陷和弱项
不爽,不舒服,枯燥 对了！你在成长

反馈
即时反馈
主动反馈
-高手代码
-第一视角
被动反馈
-code review

切题四件套

  1. Clarification 和面试官多确认几遍,确定自己的审阅题目的理解没有错
  2. possible solutions 考虑所有有可能额解法,以及它们相关的时间复杂度和空间复杂度

　compare(time/space) 比较时间复杂度和空间复杂度
　optimal(加强)

  1. Coding 多写
  2. Test cases 测试案例

五毒神掌
刷题第一遍
1.5 分钟:读题加思考
2.直接看解法:注意!多解法,比较解法的优劣
3.背诵.默写好的解法

刷题第二遍
马上自己写—LeetCode提交
多种解法比较.体会->优化

刷题第三遍
过了一天后,再重复做题
不同解答的熟练程度—专项训练

刷题第四遍
过了一周后再进行练习

刷题第五遍
面试前的恢复性训练

算法脑图.xmind

数据结构.xmind

学习前的环境准备
1.准备开发环境,vscode,idea，pycharm等,安装leetcode插件
2.两个常用的网站leetcode中文站和leetcode国际站
　在中文站上解答题目,查看答案,并且可以在国际站查看国际上的解答,因为两者讨论区的内容是不一样的

3.vscode使用指南　https://segmentfault.com/a/1190000017949680
4.goole code style 养成良好的代码规范　http://google.github.io/styleguide/　注意细节
5.使用五遍练习法,在进行第三遍和第四遍的时候,去国际站的leetcode的查看最高票的回答与自己相关的语言
6.指法和一些小操作

  • home和end 开头结尾
  • 选中单词,选中整行
  • 选中单词上下移动,选中整行上下移动
  • IDE的自动补全功能
  • 对IDE的Top Tips 做刻意联系,例如vscode

  • [ ] 学会自顶向下的编程方式,要像报纸一样,优先显示头版头条

    eg:

  1.   public boolean isPalindrome(String s) {
  2.         //主干逻辑
  3.         //1.filter out nunber & char
  4.         String filterS = filterOutNumberAndChar(s);
  5.         //2.reverse string and compare
  6.         return reverseStringAndCompare(filterS);
  7.     }
  9.     private boolean reverseStringAndCompare(String s) {
  11.         return s.equalsIgnoreCase(new StringBuilder(s).reverse().toString());
  12.     }
  14.     private String filterOutNumberAndChar(String s) {
  16.         return s.replaceAll("[^A-Za-z0-9]", "");
  18.     }

时间和空间复杂度

算法训练营(极客时间) - 图1

碰到递归问题,如何解决

将递归问题表示为递归状态树
例如斐波那契数列

0 ,1,1,2,3,5,8,13

  1. int fib(int n){
  2.     if(n<＝２) return n;
  3.     return fib(n-1)+fib(n-2)
  4. }

将他转换为递归状态图
image.png
所以菲波那切数列的递归算法的时间复杂为 2^n 因为数的每一层都是两个分叉。

主定理(递归问题的解决方案)

https://zhuanlan.zhihu.com/p/100531135　知乎
https://baike.baidu.com/item/%E4%B8%BB%E5%AE%9A%E7%90%86/3463232?fr=aladdin　百度百科

image.png

任何一个分治或者递归的函数都能算出它的时间复杂度
四种:
1.二分查找　O(logn)
2:二叉树的遍历　O(n) ——>简单思考:二叉树的遍历,每个节点都会遍历且仅仅遍历一遍
3.二维有序矩阵　O(n)
4.归并排序 nlogn

思考题:
1.二叉树的前序,中序和后序遍历的时间复杂度—->O(n),每个节点都会被访问到,且仅访问一次
2.图的遍历　O(n) 同理
3.搜索算法 DFS BFS (深度优先和广度优先)的时间复杂度 O(n)　同理
4.二分查找 O(logn)

数组,链表,跳表

当你申请一个数组的时候其实是计算机的内存管理器在内存中申请了一段连续的地址　
跳表在Redis中使用
LRUCache 使用了LinkedList
中心思想－－>升维度,空间换时间

加快链表的访问速度
1.简单优化,增加头尾指针,可以避免随机访问尾部数据慢的情况
2.升维,变为二维结构