Welcome to meizhangzheng's blog

• 数据结构-链表

  2017-02-01

  mzz

  数据结构  链表

  数据结构  链表
  • 目的
  • 一、数据结构
    • 1. 数组
    • 2. 链表(单/双/循环链)
      • 2.1 单项链表
      • 2.2 循环链 约瑟夫问题
      • 2.3 双向链表
      • 2.4 翻转链表
      • 2.5 深度拷贝带随机指针的链表
      • 2.6 两个链表相加
      • 2.7 LRU Cache
    • 参考

  目的

  程序 = 数据结构 + 算法
  

  了解数据结构、算法思想、优缺点、合理运用到项目中， 常见算法：

  一、数据结构

  了解各类数据结构在内存的存储模型。

  1. 数组

  graph TB;
  1;2;3;4;5;6
  

  连续分配的存储区域（连续的内存空间）
  
  如果没有足够连续分配的存储空间，则不能够成功常见数组对象。
  
  特性：随机查找速度快 O(1),插入效率低O（n)  --> Why？  移动个数
  

  2. 链表(单/双/循环链)

  2.1 单项链表

   data|next  ->   data|next ->  data|next
  

  可以是非连续的存储区域（了解3类链表特点）
  
  特性：顺序查找 O(n),插入、删除 O（1) 删除前需要查找  -->Why？ 移动个数
  
  扩展：实例：点餐服务 ------> 插入、删除效率高
  

  2.2 循环链 约瑟夫问题

  尾节点的 next 指向 第一个节点。

  2.3 双向链表

  指定节点： 删除O(1) （空间、时间互换）

  pre

  data

  next -> pre

  data

  next -> pre

  data

  next

  2.4 翻转链表

  1 -> 2 -> 3 ->4 => 4->3->2->1

  //理解 current.next = prev;   current节点指向prev; 即当前current: 2 -> 1  (如果current:2  prev:1) 
  // pre = current;   当前的current的位置保存的是pre。2->1
  class solution{
      public ListNode reverseNode(ListNode head)
      {
          if(head == null || head.next == null)
          {
              return head;
          }
          
          ListNode pre = head;
          ListNode current = head.next;
          pre.next = null; //pre 只表示一个节点
     
          //翻转模板1   （pre、current、next 3节点)
          while(current !=null)
          {
          	ListNode next = current.next;
              current.next = pre;
              pre = current; //包含所有节点
              current = next;
          }
          return pre;        
      }    
  }
  // https://leetcode.com/problems/reverse-linked-list/
  // 了解如何遍历链表、各节点内容
  

  • 1 -> 2 -> 3->4 -> 5 => 1-> 4->3->2->5

    

  // 哨兵节点
  class solution{
      public ListNode reverseNode(ListNode head,int left, int right)
      {
          //校验
          if(head == null ||left >=right)
          {
              return head;
          }
          //哨兵节点，便于节点找到该节点并返回
          ListNode dummy = new ListNode(-1);
          dummy.next = head; //dummy 表示最新节点
          head = dummy;//都是最新值
          
          //保留之前
          for(int i =1 ;i<left;i++)
          {
              head = head.next;
          }      
          
          //保留之前节点变量
          ListNode pre =head;
          //保留m 起始点，便于指向后面未翻转的节点
          ListNode mNode = head.next;
          ListNode nNode = mNode;//翻转 n节点变量 2->3->4->5
  		ListNode postN = nNode.next; //当前节点： 2-> 3
          for(int i=left;i<right;i++)
          {
              ListNode next = postN.next;// next 节点
  			postN.next = nNode; //翻转后:  3-> 2 ->3 ...
              nNode = postN;//当前n节点
  			postN = next;//遍历：下一节点           4
          }
          
          //2节点指向最后未翻转节点
          mNode.next =postN;
          pre.next = nNode;
          
          return dummy.next;   
      }
  }
  

  2.5 深度拷贝带随机指针的链表

  

  /*
  // Definition for a Node.
  class Node {
      int val;
      Node next;
      Node random;
  
      public Node(int val) {
          this.val = val;
          this.next = null;
          this.random = null;
      }
  }
  */
  //了解多节点链表
  

  • 基于 HashMap 实现 映射关系

  //https://leetcode-cn.com/problems/copy-list-with-random-pointer
   public Node copyRandomList(Node head) {
       if(head == null) {
           return null;
       }
       Map<Node, Node> map = new HashMap<Node, Node>();
       Node newHead = head;
       while (newHead != null) {
           if (!map.containsKey(newHead)) {
               Node node = new Node(newHead.val);
               map.put(newHead, node);
           }
           if (newHead.random != null) {
               Node random = newHead.random;
               if (!map.containsKey(random)) {
                   Node copyRandom = new Node(random.val);
                   map.put(random, copyRandom);
               }
               map.get(newHead).random = map.get(random);
           }
           newHead = newHead.next;
       }
       newHead = head;
       while (newHead != null) {
           Node next = newHead.next;
           map.get(newHead).next = map.get(next);
           newHead = newHead.next;
       }
       return map.get(head);
   }
  

  • 基于链表本身实现

  class Solution {
      public Node copyRandomList(Node head) {
          if (head == null) {
              return null;
          }
          copy(head);
          copyRandom(head);
          return split(head);
      }
      public void copy(Node head) {
          Node node = head;
          while(node != null) {
              Node copy = new Node(node.val);
              copy.next = node.next;
              node.next = copy;
              node = copy.next;
          }
      }
      
      public void copyRandom(Node head) {
          Node node = head;
          while(node != null && node.next != null) {
              if (node.random != null) {
                  node.next.random = node.random.next;
              }
              node = node.next.next;
          }
      }
      
      public Node split(Node head) {
          Node result = head.next;
          Node move = head.next;
          while(head != null && head.next != null) {
              head.next = head.next.next;
              head = head.next;
              if (move != null && move.next != null) {
                  move.next = move.next.next;
                  move = move.next;
              }
          }
          return result;
      }
  }
  

  2.6 两个链表相加

  

  //考虑问题要全面（多种情况）
  // 1. 长度不等  2.进位  3.除法 与 取模 
  /**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode() {}
   *     ListNode(int val) { this.val = val; }
   *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   * }
   */
  class Solution {
      
      public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
          if (l1 == null) {
              return l2;
          }
          if (l2 == null) {
              return l1;
          }
          int carry = 0;
          ListNode head = new ListNode(-1);
          ListNode pre = head;
          while (l1 != null && l2 != null) {
              int number = l1.val + l2.val + carry;
              carry = number / 10;
              ListNode node = new ListNode(number % 10);
              pre.next = node;
              pre = pre.next;
              l1 = l1.next;
              l2 = l2.next;
          }
          while (l1 != null) {
              int number = l1.val + carry;
              carry = number / 10;
              ListNode node = new ListNode(number % 10);
              pre.next = node;
              pre = pre.next;
              l1 = l1.next;
          }
          while (l2 != null) {
              int number = l2.val + carry;
              carry = number / 10;
              ListNode node = new ListNode(number % 10);
              pre.next = node;
              pre = pre.next;
              l2 = l2.next;
          }
          if (carry != 0) {
              ListNode node = new ListNode(carry);
              pre.next = node;
          }
          return head.next;
      }
  }
  
  

  2.7 LRU Cache

  最少使用被淘汰算法： 基于双向链表（便于查找上一个节点和下一个节点），HashMap作为缓存；

  将最新的数据放在尾节点，达到最大值时，如果要插入数据，则移除头结点数据并重新指向头结点，然后插入尾结点数据。（也可将最新数据插入头结点，删除尾结点）

  

  /**
   * Your LRUCache object will be instantiated and called as such:
   * LRUCache obj = new LRUCache(capacity);
   * int param_1 = obj.get(key);
   * obj.put(key,value);
   */
  class LRUCache {
      private class CacheNode {
          CacheNode prev;
          CacheNode next;
          int key;
          int value;
          public CacheNode(int key, int value) {
              this.key = key;
              this.value = value;
              this.prev = null;
              this.next = null;
          }
      }
       
      private int capacity;
      private Map<Integer, CacheNode> valNodeMap = new HashMap();
      //自定义头结点、尾结点（哨兵结点，便于新增和删除很少使用的结点）
      private CacheNode head = new CacheNode(-1, -1);
      private CacheNode tail = new CacheNode(-1, -1);
   
      public LRUCache(int capacity) {
          this.capacity = capacity;
          tail.prev = head;
          head.next = tail;
      }
       
      public int get(int key) {
          if (!valNodeMap.containsKey(key)) {
              return -1;
          }
          CacheNode current = valNodeMap.get(key);
          current.prev.next = current.next;
          current.next.prev = current.prev;
          moveToTail(current);
          return valNodeMap.get(key).value;
      }
       
      public void put(int key, int value) {
          if (get(key) != -1) {
              valNodeMap.get(key).value = value;
              return;
          }
           
          if (valNodeMap.size() == capacity) {
              valNodeMap.remove(head.next.key);
              head.next = head.next.next;
              head.next.prev = head;
          }
       
          CacheNode insert = new CacheNode(key, value);
          valNodeMap.put(key, insert);
          moveToTail(insert);
      }
       
      private void moveToTail(CacheNode current) {
          current.prev = tail.prev;
          tail.prev = current;
          current.prev.next = current;
          current.next = tail;
      }
  }
  

  参考

  «算法图解»

  • ”程序员小灰“ 公众号 (推荐)

  约瑟夫问题

  • 网课（腾讯课堂）
  Read All

  ---

• 数据结构之红黑树

  2017-02-01

  mzz

  数据结构  树

  数据结构  树
  • 目的
  • 一、数据结构
    • 1. 红黑树
      • 1.2 基础特性

  目的

  程序 = 数据结构 + 算法
  

  了解数据结构、算法思想、优缺点、合理运用到项目中， 常见算法：

  一、数据结构

  1. 红黑树

  1.1 应用

  平衡二叉树变种， HashMap 与 红黑树

  1.2 基础特性

  

  性质1. 结点是红色或黑色。 [3]

  性质2. 根结点是黑色。 [3]

  性质3. 所有叶子都是黑色。（叶子是NIL结点） [3]

  性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）

  性质5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。(不是指连续节点，指的所有路径，从根节点到叶子) [3]

  Read All

  ---

• 数据结构之树

  2017-02-01

  mzz

  数据结构  树

  数据结构  树
  • 目的
  • 一、数据结构
    • 1. 树
      • 1.1 基础

  目的

  程序 = 数据结构 + 算法
  

  了解数据结构、算法思想、优缺点、合理运用到项目中， 常见算法：

  一、数据结构

  1. 树

  1.1 基础

  

  节点高度：节点到叶子节点最长路径；

  节点深度：根节点到节点经历边的个数；

  节点层次：节点深度 + 1；

  节点的度：含有子节点个数；

  树高度：根节点高度；

  树的度：最大节点的度。

  树是一种特殊的图。每个节点只有一个父节点，且不能形成环。
  实例：家谱
  
  最小生成树：n个顶点的连通图中选择n-1条边，构成权值之和最小的连通子图，被称为最小生成树。
  

  Read All

  ---

• 数据结构

  2017-02-01

  mzz

  数据结构  栈  队列

  数据结构  栈  队列
  • 目的
  • 一、数据结构
    • 1. 栈
      • 1.1 括号验证
      • 1.2 最小栈
      • 1.3 最大区间
      • 1.4 两个栈实现队列
    • 2. 队列
    • 5.散列表
    • 6.图
    • 7.有向图
    • 8.无向图
    • 9.树

  目的

  程序 = 数据结构 + 算法
  

  了解数据结构、算法思想、优缺点、合理运用到项目中， 常见算法：

  一、数据结构

  1. 栈

  调用栈： 后进先出（先进后出）
  调用栈可能很长，需要占用很多的内存     --->竖着的 长方形
  不能用于查找
  
  优化：采用循环、尾递归
  
  扩展：思考代码中方法名称、参数名称 存放的位置
  
  实例：递归算法、函数调用（JVM)、深度优先遍历、两个栈实现一个队列、实现括号验证
  

  1.1 括号验证

  // https://leetcode-cn.com/problems/valid-parentheses/
  //括号验证 :  遍历字符， （[{ 入栈，)]} 时，出栈校验   
  class Solution {
      public boolean isValid(String s) 
      {
          if(s == null || s.length()==0)
          {
              return true;
          }
          Stack<Character> stack = new Stack<>();
          for(char c:s.toCharArray())
          {
                          
              if(c=='(' || c=='[' || c=='{')
              {
                  stack.push(c);
              }
              if(c ==')')
              {
                  if(stack.isEmpty() || stack.pop()!='(')
                  {    
                      return false;
                  }
              }
              if(c ==']')
              {
                  if(stack.isEmpty() || stack.pop()!='(')
                  {    
                      return false;
                  }
              }
              if(c =='}')
              {
                  if(stack.isEmpty() || stack.pop()!='{')
                  {    
                      return false;
                  }
              }
          }
          
          return stack.isEmpty();
      }
  }
  // 注意： 
  /**
   *  1. 基础用法: String.toCharArray()、length() 需要加括号。
   *  2. 栈初始化: Stack<Character> stack = new Stack<>()
   *  3. 最后一步： stack.isEmpty();       // [
   *	4. 校验（先自查 ）
   */
  

  1.2 最小栈

  // 取出栈内最小值。   思路： 同时操作两个栈，同时入栈、同时出栈。   =》 取栈 最大
  class MinStack {
  
      /** initialize your data structure here. */
      Stack<Integer> stack;
      Stack<Integer> minStack;
      public MinStack() {
          stack = new Stack<>();
          minStack = new Stack<>();
  
      }
      
      public void push(int val) {
          stack.push(val);
          if(minStack.isEmpty() || val < minStack.peek())
          {
              minStack.push(val);
          }
          else
          {
              minStack.push(minStack.peek());
          }
      }
      
      public void pop() {
         minStack.pop();
         stack.pop();
      }
      
      public int top() {
         return stack.peek();
      }
      
      public int getMin() {
          return minStack.peek();
      }
  }
  
  /**
   * Your MinStack object will be instantiated and called as such:
   * MinStack obj = new MinStack();
   * obj.push(val);
   * obj.pop();
   * int param_3 = obj.top();
   * int param_4 = obj.getMin();
   */
  

  1.3 最大区间

  class MaxSection {
  
      //int[] numbers ={5,2,3,4,1}
      public int getMax(int[] numbers)
      {
          //如果数据为空
          if(numbers==null ||numbers.length ==0)
          {
              return 0;
          }
          
          //保存的是索引
          Stack<Integer> stack = new Stack<>();
          int max=0;
          int[] sum = new int[numbers.length+1];
  
          for(int i = 1;i<numbers.length;i++)
          {
              sum[i] = sum[i-1]+numbers[i-1];
          }
          
          for(int i=0;i<numbers.length;i++)
          {
              while(!stack.isEmpty() && numbers[i]<numbers[stack.peek()])
              {
                  int index = stack.pop();
                  int left = i;
                  int right =i;
                  if(stack.isEmpty())
                  {
                      left = 0;
                  }else
                  {
                      left = index;
                  }
                  max = Math.max(max,numbers[index] * (sum[right]-sum[left])));
              }
              stack.push(i);
          }
          
          //最后一部分数据都是  从小到大排列,则未取完
          while(!stack.isEmpty())
          {
              int index = stack.pop;
              int left = numbers.length;
              int right = numbers.length;
              if(stack.isEmpty())
              {
                  left = 0;
              }else
              {
                  left = index;
              }
              max = Math.max(max,numbers[index] * (sum[right]-sum[left])));
          }
          retrun max;
      }
  }
  

  1.4 两个栈实现队列

  1. 分成两段： 第一个栈存新来的数据，第二个栈则取；

  2. 当第二个栈没有数据时，则从第一个栈，取出数据，放置到第二个栈（新来的数据在最上面 ）。
  3. 当要队列取数是，则从第二个栈取数。

  2. 队列

  实例：公交车站，排队等车、系统中各个资源管理、消息缓冲区管理、广度优先搜索
  特点：先进先出
  

  5.散列表

   定义：根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访  	  问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
   
   内部机制： 实现、冲突、散列函数
  
   散列函数：
      <1.它必须是一致的（同一输入，输出结果相同）
      <2.它应将不同的输入映射到不同的数字 ** （没有冲突的情况） 很难
  
     （1）散列函数很重要（最理想的情况：将键均匀映射到散列的不同位置）
     （2）散列的链表不能太长，影响查询效率
     
     构造方法：
     	（1）直接定址法（关键码本身和地址之间存在某个线性函数关系时，散列函数取为关键码的线性函数，即：H(key)=a*key+b，a、b均为常数。）  查找表较小且连续，不常用
     	（2）除留余数法（通过选择适当的正整数p，按计算公式H(K)=K mod p来计算关键码K的散列地址。
  ）  常用：Integer等数据类型 源码中hashcode
  	（3）平方取中法（将关键码K平方，取K^2中间几位作为其散列地址H(K)的值。
  ）
  	（4）随机数法（采用随机函数作为散列函数H(Key)=random(Key)，其中random为随机函数。）
          当关键码长度不等时，采用该方法较恰当。
          
      解决Hash冲突的处理方法：
      （1）再hash
      （2）缓冲区
      （3）开放定址法(从发生冲突位置的下一个位置开始寻找空的散列地址。发生冲突时，线性探测下一个散列地址是：Hi=(H(key)+di)%m，（di=1,2,3...,m-1）)
      （4）拉链法()
      
   实例： HashTable、HashMap、加密算法、查找、海量数据处理
  
      <1.模拟映射关系 -->将散列用于查找 （通过姓名查询电话号码）
      <2.防止重复（投票站投票，不允许1人多投）
      <3.将散列用于缓存（网站缓存，不用每次请求服务器）
  
  性能：
  
      1.较低的填充因子（散列包含的元素个数/位置总数）
      2.良好的散列函数（各个语言内置有散列函数）
  

  6.图

  图有节点和边组成。
  
  概念： 邻接表、邻接矩阵、邻接点、度
  

  7.有向图

  有方向，单向关系
  

  8.无向图

  无方向
  

  9.树

  树是一种特殊的图。
  实例：家谱
  
  最小生成树：n个顶点的连通图中选择n-1条边，构成权值之和最小的连通子图，被称为最小生成树。
  

  扩展：二叉树、B-树、B+树、红黑树、堆、伸展树。

  Read All

  ---

• 数据结构之堆

  2017-02-01

  mzz

  数据结构  堆

  数据结构  堆
  • 目的
  • 一、数据结构
    • 1. 堆
      • 1.2 基础特性
    • 2. 算法
      • 2.1 查找流中的中位数

  目的

  程序 = 数据结构 + 算法
  

  了解数据结构、算法思想、优缺点、合理运用到项目中， 常见算法：

  一、数据结构

  1. 堆

  1.1 应用

  堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

  1.2 基础特性

  • 堆中某个结点的值总是不大于或不小于其父结点的值；
  • 堆总是一棵完全二叉树
  • 插入、删除效率O(logn)

  2. 算法

  2.1 查找流中的中位数

  public class MediaFinder {
  
      public static void main(String[] args) {
  
          int[] nums = {1,2,3,4,5,6};
          int[] nums1 = {4,5,1,3,2,6,0};
  
          int[] ints = new MediaFinder().medianII(nums);
          int[] ints1 = new MediaFinder().medianII(nums1);
          for (int i : ints)
          {
              System.out.println(i);
          }
          System.out.println("nums 1 :");
          for (int i : ints1)
          {
              System.out.println(i);
          }
      }
  
      public int[] medianII(int[] nums) {
          int count = nums.length;
          PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(count, new Comparator<Integer>(){
              public int compare(Integer num1, Integer num2) {
                  return num2 - num1;
              }
          });
          PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(count);
          int[] answer = new int[count];
          int number = nums[0];
          answer[0] = number;
          for (int i = 1; i < count; i++) {
              if (nums[i] > number) {
                  minHeap.add(nums[i]);
              } else {
                  maxHeap.add(nums[i]);
              }
              if (Math.abs(maxHeap.size() - minHeap.size()) > 1) {
                  if (minHeap.size() > maxHeap.size()) {
                      maxHeap.add(number);
                      number = minHeap.poll();
                  } else {
                      minHeap.add(number);
                      number = maxHeap.poll();
                  }
              } else {
                  if (maxHeap.size() - minHeap.size() == 1 && maxHeap.peek() < number) {
                      minHeap.add(number);
                      number = maxHeap.poll();
                  }
              }
              answer[i] = number;
          }
          return answer;
      }
  }
  

  Read All

  ---

• Java 性能优化

  2017-01-31

  Java  性能优化

  Java  性能优化
  • Java 性能优化
    • 1 策略、方法、方法论
    • 2 操作系统性能监控

  Java 性能优化

  1 策略、方法、方法论

  1.1 性能问题现状
  1.2 性能分析的两种方法： 自顶向下和自底向上
  1.3 选择正确的平台并评估系统性能
  	1.3.1 选择正确的CPU框架
  	1.3.2 评估系统性能
  

  2 操作系统性能监控

  2.1 定义
  	性能监控、性能分析、性能优化
  2.2 CPU使用率
  

  Read All

  ---