¶LeetCode-algorithms20:Valid Parentheses

¶Problem:

• Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
• An input string is valid if:

  • Open brackets must be closed by the same type of brackets.

  • Open brackets must be closed in the correct order.

¶LeetCode-algorithms2:Add Two Number

• Problem :

  • You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

  • You may assume the two numbers do not contain any leading zero, except the number 0 itself.

  • Example : Input: （2 --> 4 --> 3）+ (5 --> 6 --> 4) ; output : 7 --> 0 --> 8 ; Cause 342 + 465 = 807

¶栈结构

¶概念解释：

• 对栈结构的理解生活中有个很类似的例子 – 叠盘子：最先洗好的盘子放在最下面，然后一个一个往上叠加；取盘子用的时候也是从上面开始取用，不会从中间抽一个盘子出来。
• 基于这种场景，再类比栈的特点：先进后出，后进先出；只允许在栈顶进行入栈，出栈操作； 和前面的数组以及链表不同，栈结构是一种操作受限的结构，从王争的《数据结构和算法之美》的栈一章节里面，看到这样一句话:特定的数据结构是对特定场景的抽象，这样结合栈的实际使用场景就能更好地理解栈结构。

¶栈实现

• 基于数据和链表都可以实现栈结构，前者称为顺序栈，后者称为链式栈；

• 联想到数组和链表的特性，数组初始化时容量固定，适用于元素数量固定的场景，不需要进行扩容，避免产生更高的开销；

• 链式栈不存在容量的限制，在需要自动扩容的不定长栈场景中可以采用这种实现。

¶链表相关实操

¶概述

• 在链表的操作中，理解链表指针的概念很重要；C语言的指针代表的意思是对象的内存地址，在Java对应的概念则是引用；将对象赋值给变量 ，实际是将对象的内存地址赋值给了变量，用来定位对象在内存中的位置。
• 为了更深入地理解这些概念和链表结构，通过：反转单链表，合并有序单链表，检测链表环，删除链表倒数第N个节点这四个实践场景来加深印象。

¶反转单链表

• 给定链表 a -> b -> c -> d-> e ，反转成 e -> d-> c-> b-> ->a ,并返回头节点

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

  static class Node { Object value = null; Node next; public Node(Object value) { this.value = value; } } //反转单链表 public void reverseLinkList(Node head){ Node first = new Node(null); first.next = head; while(true){ if(head.next == null){ break } Node move = head.next; Node moveNext = head.next.next; //修改指针引用 head.next = moveNext; move.next = first.next;//链接到第一个非空节点 first.next = move; // move 成为第一个非空节点 } //输出 while(first.next!=null){ printf(first.next.value + " ---> ") first = first.next; } printf("null"); }

• 最开始想到的思路是：

  • 先记录尾节点，将头节点一次移动一个位置

  • 当前头节点移动至链表尾部时，再次循环将新的头节点移动到链表尾部

¶链表

¶概念

• 在数据结构中，链表也是常用的基本数据结构，节点持有指向其他节点的前后引用，一次来定位和查找元素，这种特性也导致链表在访问指定元素时，需要进行一次O(n)遍历；根据存储方式的不同，可以简单划分为三类基础链表:单链表，双链表，循环链表。
• 单链表：
  • 每个节点只具备向后的指针引用，最后一个节点指向null
• 双链表:
  • 每个节点都具备向前，向后的引用，指向各自的前驱，后继节点；头节点的前驱节点指向null；尾节点的后继节点指向null
• 循环链表：
  • 循环单链表： 在单链表的基础上，尾节点的next指向头节点
  • 循环双链表：在双链表的基础上，头节点的前驱节点指向尾节点；尾节点的后继节点指向头节点；

¶链表的存储特点

• 和数组不同，链表由于通过节点之间的引用来进行定位，所以并不要求使用物理连续的内存空间进行数据存储，可以比较好地利用碎片空间；
• 在对链表中的数据进行插入和删除操作时，只需要改变相邻节点的引用，插入删除的复杂度都是O(1)
• 而在遍历上，三种结构的链表最坏时间复杂度都是O(n）

¶链表结构之间的对比

• 单链表与双链表：

  • 单链表只能进行向后查找，与之相比，再进行查找指定元素再进行删除这样的操作场景上，单链表定位到指定元素进行删除时，还需要重新遍历一次定位被删除元素的前驱节点，将该节点的引用指向被删除节点的后继节点；而双链表虽然在定位元素的时间复杂度上和单链表一样，但是进行删除时，可以通过被删除节点的向前指针找到前驱节点，直接改变相邻节点的引用，不需要再进行一次遍历

¶Ioc 概览

• ¶Bean 属性定制:

  • Spring 框架提供了一系列用于定制 Bean 的接口, 主要是 Bean 生命周期相关的回调方法（ Lifecycle Callbacks ）

    ---

    ¶生命周期相关的回调方法:

    • 为了和Spring 对Bean 的管理相互影响，可以通过实现 InitializingBean 和 DisposableBean 接口，分别定义 Bean 的 afterPropertiesSet() 和 desyory() 方法，指定在Bean 属性设置完成和 Bean 销毁时的动作

    • 在Spring 的内部，是通过接口 BeanPostProcessor 的实现类执行相关回调方法的，因此如果你想实现任何 Spring 没有提供的生命周期相关的动作，可以通过实现 BeanPostProcessor 接口来完成。

    • 初始化回调

      • afterPropertiesSet() ：在Bean 所有必须的属性设置完成之后进行一些其他的初始化工作；

      • 但是并不推荐继承 InitializingBean 接口来实现这一回调方法，因为会和Spring 的代码相耦合；建议通过 @PostConstruct 注解 ， 或者指定对象的初始化方法

        1 2 3 4 5 6 7 8

        <bean id = "exampleInitBean" class = "examples.ExampleBaen" init-method = "init"> // xml 格式的配置元数据，指定 init-method 方法，作为初始化回调 public class ExcepleBane{ public void init{ //初始化回调 } }

    • 生命周期结束回调

      • destory() ： Bean 销毁方法

      • 同样为了避免和 Spring 代码过度耦合，建议使用 @PreDestory 注解，或者在配置元数据中指定销毁方法，在中指定 destory-method 指向的方法作为 Bean 生命周期销毁时的回调。

        1 2 3 4 5

        <bean id ="exampleInitBean" class="examples.ExampleBaen" destory-method="cleanup"> //指定 destory-method 方法作为生命周期结束回调 public void cleanup(){ //销毁动作 }

¶一学一记：数组

¶概述:

• 数组是一种比较常见的基础数据结构，存储相同的数据类型，支持通过下标(index)进行随机访问，也是一种线性表结构，存储数据的是一块内存连续的空间。

¶概念解释:

• 线性表 : 数据最多只具备向前向后两个方向的，可以想到链表，队列也是一样的结构

• 随机访问实现：

  • 因为数据在内存中需要的是一块连续的内存空间，而且数据中存储着相同的数据类型，这意味着每一个数据的在内存中的长度都是一致的，假设:

    • int[] a= new int[10] , 在计算机中分配到的内存空间如下所示 :

    • 

    • 将1000作为这个数组的起始地址(base_address),int类型长度为4字节(data_size),假设我们要查找a[5]位置的元素，计算方式就是:

    • $$
      a[5] Address = baseAddress + 5 * dataSize = 1000 + 20 = 1020
      $$

    • 数组在内存空间寻址公式就是这样，从基地址出发，将需要计算的偏移量乘以数据类型长度，得到该偏移量下的内存地址，即确定了元素在内存中的位置

• 数组的缺点：

  • 低效的插入，删除 ：

    • 根据数据的存储特性，为了维护数组内存空间的物理连续性，当从数组中删除一个元素时，需要将该元素之后的元素都向前移动一位；在这种情况下，如果是进行头节点的删除，需要将剩下的所有元素位置都进行一次移动，在数量较大时显得很低效。

    • 插入—可优化场景：考虑到之前了解到的最好和最坏时间复杂度，如果是仅作为数据存储的无序数组，在进行数据的插入时，可以不进行数据的移动，而是通过将插入数据直接替换该索引位置数据，将被替换数据插入到尾部降低整体的操作时间复杂度:

    • $$
      往数组a的i位置插入X，temp = a[i]; a[i] = X ;a[n] = temp
      $$

    • 当然了这是假设数组有剩余空间的情况下可以直接这么处理，如果没有剩余空间还是得先进行整体数据的移动移动，在插入数据，ArrayList 的扩容就是基于这种方式实现的

    • 删除—可优化场景：数组的删除操作一定会导致内存空间的不连续，因此在没有要求每次删除都必须马上将数组空间空闲出来的情况下，可以对需要删除的数据进行标记，不触发真正的删除；等到数组空间不足，需要清理数据的时候再一次性将需要删除的数据清除，进行一次数据的移动，大大节省了操作时间，这种先将数据标记，然后进行数据清理的思路，和JVM的标记-回收算法类似。

• 数组的起始下标为何从0开始？

  • 从合理性性的角度来说，根据我们刚才使用的数组内存寻址公式: bas_address + index * data_size ,数组中第一个元素的位置就是 base_address ,如果 index 从1开始，意味着这个计算公式要变成 base_address + (index-1) * data_size ，增加了一次运算操作，这次操作是可以避免的，以提高效率和节省CPU资源。

• 二维数组的寻址公式:

  • 1 2 3

    int[m][n] a; a[i][j] = base_adddress + (i*n + j)*data_size; // 即定位二维数组的某个数组的元素地址，需要加上该数组之前的内存空间长度，再计算自身索引条件下查找元素的内存地址

小结：

• 数组是一种支持随机访问的线性表结构，它在连续的内存空间中存储着相同类型的数据
• 一维数组的寻址公式为 : 基地址 + 偏移量*数据类型长度
• 数组的插入，删除元素操作效率较低，在不考虑数组数据有序性的前提下：
  • 插入:往数组i位置插入元素X，可以将a[i]元素放置数组尾部，X放置在a[i]位置，这样操作的时间复杂的降低为O(1)
  • 删除:如果数组空间充足，对于需要删除的数据可以先进行删除状态标记，等到需要腾出数据空间的时候，再对这些数据进行一次性删除，节省了多次删除的数据移动操作，提高了执行效率

¶一学一记：代码时间/空间复杂度

¶代码的复杂度分析

• 时间复杂度:

  • 概念解释：代码的执行时间复杂表示的是一段代码的执行时间随数据规模增长的变化趋势**(它并不是表示具体的代码时间)，也叫做**渐进式时间复杂度

  • 分析时间复杂度方法：

    • 只关注循环最多的代码 ： 一段代码的最大时间复杂度会由运行时间最长—也即时间复杂度最大的那段代码决定，因此分析一段代码的时间可以只关注的

      循环最多的那段代码的时间复杂度

    • 加法法则 ： 总复杂度等于量级最大的那段代码的时间复杂度：类似于木桶效应，一段代码的总时间复杂度是内部多段代码执行时间复杂度之和，但是最能够代表复杂度趋势的还是量级最大的那段代码的执行时间复杂度

    • 乘法法则：嵌套代码的时间复杂度等于内外代码复杂度的乘积 : 嵌套循环了 n*n 的代码总时间复杂度就是O(n^2)

¶Spring 框架指引文档阅读笔记(一)

¶概述

​ 现如今Java Web 开发者们基本都绕不开 Spring框架( 这里的Spring框特指Spring Framework的Web开发框架，以下以 Spring Web框架代替 )这个话题，基于主流市场要求的影响，无论是对于Spring Web 框架足够足够推崇抑或是单纯为了混口饭吃，都会实际学习和使用 Spring Web 框架，本人属于后者，搭上了J2EE开发的大船，因此基本离不开Spring Web 框架。

​ 虽然在学习和工作中对于Spring Web 框架的使用比较多，但了解的东西还是比较片面，不够系统化，当有人让我描述一下Spring Web 框架的时候，组织不出合适的语言。因此以更加了解Spring Web 框架的结构和特性，更好地使用它为目的，一边阅读Spring 指引文档，一边尝试借由实践去产生自己的理解，希望技能能更上一层楼。

¶Spring 文档(Version 5.2.4 RELEASE)

• 总览:

  • Spring 的含义:

    • 英文翻译的话就是春天的意思，记得有人解释过Spring 系列框架的诞生带来了 Java 企业级应用开发的春天。

    • 过去在提到 Spring Framework 的时候，人们更多的是指 Spring Web 框架本身。而发展到现在，已经基于 Spring Web 框架构建起了一个庞大的生态体系，现在提到 Spring Framework的话，则指代了Spring 家族的诸多项目。

      Spring Framework ：提供 DI，事务管理，web 开发，数据访问和消息等核心支持

      Spring Boot ： 提供了快速构建 Spring 项目的固定配置

      Spring Cloud: 为公共模式构建的分布式应用提供给了一系列工具集，利于构建微服务

      Spring Security: 通过全面可扩展的授权和认证保护应用程序

      …

    • Spring Web 框架内部划分成诸多模块，TODO

¶Redis 学习笔记(一)

¶简述.

• Redis (Remote Dictionary Server) ，是一个基于内存的高性能Key-Value数据库；支持多种丰富的数据类型，而且由于纯内存访问和优秀的单线程架构，所以具备很高的响应性。支持主从模式，在单机多机环境下分别支持哨兵和集群搭建高可用环境。

¶Redis 优点：

• 访问速度快： Redis 将数据保存在内存中，存取速度比较可观；并且可以定期通过异步操作将数据库数据持久化到本地磁盘，作为灾难恢复和数据转移的准备。

• 支持丰富的数据结构： Redis 大受欢迎的原因还在于它提供了丰富的数据结构:string,hash,list,set,zset,Pub/Sub,Geo等，可以很大程度上直接满足业务场景的需求。

• 丰富的特性：

  • 支持简单的发布订阅

  • Key过期策略：在缓存一致性问题中可以提供帮助

  • 事务特性

  • 支持多DB:16个，从0开始

  • 原子计数

  • Session 共享

  • 分布式锁

    …