Articles

• 二叉树

  Sep 23, 2020
  二叉树的简单介绍 二叉树的定义 二叉树是(n>=0)个节点的有限集合，他或者(n==0)时为空树，或者（n>0时）由一个根节点及两颗互不相交的分别称为跟的左子树和右子树的二叉树组成。 2 二叉树的遍历 2.1 前序遍历 递归实现的算法分析 前序遍历二叉树的递归定义为：若二叉树为空树则遍历结束，否则 1. 访问根节点 2. 前序遍历根节点的左子树 3. 前序遍历根节点的右子树 ———————————————— 算法实现 ————————————– public class Tree { private class Bitree<T>{ T data; Bitree lchild; Bitree rchild; public Bitree(T data,Bitree lchild,Bitree rchild){ this.data = data; this.lchild = lchild; this.rchild = rchild; } } private void preorder(Bitree bt){ //设置递归终止条件 if (bt==null){ return; } //输出 跟节点 System.out.println(bt.data); //前序遍历左子树 preorder(bt.lchild); //前序遍历右子树 preorder(bt.rchild); } } 2.

• 命令模式

  Sep 21, 2020
  命令模式的简单介绍 1 命令模式的介绍 1.1 命令模式的结构

• 哈希检索

  Sep 19, 2020
  哈希检索算法的深度学习 1 相关概念的理解 1.1 哈希检索 概念： 哈希检索技术的初衷是组织理想状态的检索表。检索表的理想状态是：把记录的关键字值与记录在检索表中的存储位置建立起某种一对一的关系，这种一对一的关系可以用关键字的一个函数h(key)来表示，这样不必进行关键字与给定值的比较，而是直接依据给定的关键字值来直接计算得到记录在检索表中的存储地址。 哈希函数（散列函数、杂凑函数）：反应关键字与存储位置一对一关系的函数h(key) 哈希检索技术必须解决的两个问题 （1）如何选择一个计算简单且地址冲突尽可能少的哈希函数； （2）在出现地址冲突时采用什么办法解决冲突 1.2 哈希函数的构建方法 直接定址法：h(key) = a*key + b 数字分析法：提前知道关键字值的集合，分析关键字集合的分布情况，确定散列函数； 平方取中法：先求出关键字的平方，然后取中间几位作为哈希地址； 折叠法 除留余数法：h(key) = key % p 余取整法 随机数法：h(key) = random(key) 2 地址冲突的消解策略 2.1 开放地址法 把哈希表中的空位置向处理地址冲突开放，具体的做法是，当发生地址冲突时，从发生地址冲突的那个位置开始，使用某种方法在哈希表中形成一个探查序列。 2.1.1 线性探查法 线性探查法是开放地址法消除地址冲突的一种最简单的探查方法。他把表长为m的哈希表看成是循环表，若发生地址冲突的位置地址为d，则依次探查d+1, d+2, …,直到找到一个空闲位置为止。 公式：（地址）d = (h(key)+i)%m ， 其中i=1,2,…,m-1 缺点：线性探查法易造成堆积现象。 2.1.2 平方探查法 平方探查法也称为二次探查法。在发生地址冲突时，依次探查位置d+i，其中i取 1^2,-1^2,2^2,-2^2,…, 公式：d = (h(key)+i^2)%m,d = (h(key)-i^2)%m 和中心扩展法相同，以地址冲突的位置，分别向两边去寻找空地址。

• LinkedList以及栈的深度理解

  Sep 11, 2020
  算法背景:给定一个只包括 ‘(‘，’)‘，’{‘，’}‘，’[‘，’]’ 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 1 首先了解LinkedList的底层实现 1.1 LinkedList的底层实现 LinkedList的底层是基于 双向链表 实现，使用Node存储链表节点信息。源码如下 private static class Node<E> { E item; Node<E> next; Node<E> prev; } 每个链表都存储了first和last指针； transient Node<E> first; transient Node<E> last; 2 设计算法，实现上面的需求 2.1 算法的实现 public static boolean isValid(String s) { int n = s.length(); if (n % 2 == 1) { return false; } Map<Character, Character> pairs = new HashMap<Character, Character>() {{ put(')', '('); put(']', '['); put('}', '{'); }}; Deque<Character> stack = new LinkedList<Character>(); for (int i = 0; i < n; i++) { char ch = s.

• Xml字符编码规范

  Sep 11, 2020
  xml字符编码规范 < <(小于) > >(大于) & &(和) ' ‘(单引号) " “(双引号)