Java数据结构第四讲-树/递归/Hash

void InOrderNonRecursive(TreeNode root){
  if (root == null) {
    return;
  }
  Stack s = new Stack();
  while(true){
    while (root !=null) {
      s.push(root);
      root = root.left;
    }
    if (s.isEmpty()) {
      break;
    }
    root = (TreeNode) s.pop();
    System.out.println(root.val);
    root = root.right;
  }
}

void PreOderNonRecursive(TreeNode root){
  if (root == null) {
    return;
  }
  Stack s= new Stack();//使用栈保存将要遍历的结点
  while(true){
    while (root !=null) {
      System.out.println(root.val);
      s.push(root);
      root = root.left;
    }
    if (s.isEmpty()) {
      break;
    }
    root = (TreeNode) s.pop();
    root = root.right;
  }
}
递归后序遍历：
void PostOrder(TreeNode root){
  if (root!= null) {
    PostOrder(root.left);
    PostOrder(root.right);
    System.out.println(root.val);
  }
}
层序遍历：
void LevelOrder(TreeNode root){
  TreeNode temp;
  Queue q= new ArrayBlockingQueue(0);
  if (root == null) 
    return;
  q.add(root);
  while (!q.isEmpty()) {
    temp = (TreeNode) q.remove();
    System.out.println(temp.val);
    if (temp.left != null) {
      q.add(temp.left);
    }
    if (temp.left != null) {
      q.add(temp.right);
    }
  }
  q.clear();
}

public class BinarySearchTree {
  private Node tree;
  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if (data < p.data) p = p.left;
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }
  public static class Node {
    private int data;
    private Node left;
    private Node right;
    public Node(int data) {
      this.data = data;
    }
  }
}

public void insert(int data) {
  if (tree == null) {
    tree = new Node(data);
    return;
  }
  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
      return;
      }
      p = p.left;
    }
  }
}

public void delete(int data) {
  Node p = tree; // p指向要删除的节点，初始化指向根节点
  Node pp = null; // pp记录的是p的父节点
  while(p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  if (p == null) return; // 没有找到
  //要删除的节点有两个子节点
  if (p.left != null && p.right != null) {//查找右子树中最小节点
    Node minP = p.right;
    Node minPP = p; // minPP表示minP的父节点
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    p.data = minP.data; // 将minP的数据替换到p中
    p = minP; // 下面就变成了删除minP了
    pp = minPP;
  }
  //删除节点是叶子节点或者仅有一个子节点
  Node child; // p的子节点
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;
  if (pp == null) tree = child; // 删除的是根节点
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

private static void buildHeap(int[] a, int n) {
  for (int i = n/2; i >= 1; --i) {
    heapify(a, n, i);
  }
}
private static void heapify(int[] a, int n, int i) {
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}

排序操作： //n表示数据的个数，数组a中的数据从下标1到n的位置。

public static void sort(int[] a, int n) {
  buildHeap(a, n);
  int k = n;
  while (k > 1) {
    swap(a, 1, k);
    --k;
    heapify(a, k, 1);
  }
}

public class AcNode {
  public char data; 
  public AcNode[] children = new AcNode[26]; //字符集只包含a~z这26个字符
  public boolean isEndingChar = false; //结尾字符为true
  public int length = -1; //当isEndingChar=true时，记录模式串长度
  public AcNode fail; //失败指针  相当于KMP中失效函数next数组
  public AcNode(char data) {
    this.data = data;
  }
}

public int f(int n){
  if(n==1) return 1;
  if(n==2) return 2;
  //hasSolvedList可以理解为一个Map，key是n，value是f(n)
  hasSolvedList.containsKey(n){
    return hasSolvedList.get(n);
  }
  int ret =f(n-1)+f(n-2);
  hasSolvedList.put(n,ret);
  return ret;
}//王争这道题没写好，他的本意是记忆化递归

int f(int n){
    int ret = 1;
    for (int i = 2; i <= n; ++i) {
      ret = ret + 1;
    }
    return ret;
  }
  f(n) = f(n-1)+f(n-2) ->
  int f(int n){
    if (n == 1) return 1;
    if (n == 2) return 2;
    int ret = 0;int pre = 2;int prepre = 1;
    for (int i = 3; i <= n; ++i) {
      ret = pre + prepre;
      prepre = pre;
      pre = ret;
    }
    return ret;
  }

long findRootReferrerId(long actorId) {
  Long referrerId = select referrer_id from [table] where actor_id = actorId;
  if (referrerId == null) return actorId;
  return findRootReferrerId(referrerId);
}

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

void TowersOfHanoi(int n,char frompeg,char topeg,char auxpeg){
  /*如果仅有一个圆盘，直接移动，然后返回*/
  if(n==1){
    syso("Move disk 1 from peg"+frompeg+"to peg"+topeg);
    return;
  }
  /*利用c作为辅助，将A柱最上面的n-1个圆盘移动到B柱*/
  TowersOfHanoi(n-1, frompeg, topeg,auxpeg)；
  /*将余下的圆盘从A柱移动C柱*/
  syso("Move disk 1 from peg"+frompeg+"to peg"+topeg);
  /*利用A柱作为辅助，将B柱上的n-1个圆盘移到C柱*/
  TowersOfHanoi(n-1, auxpeg,topeg,frompeg)；
}

int Fact(int n){
  //基本情形：当参数为0或1时，返回1
  if (n==1) {
    return 1;
  }else if (n == 0) {
    return 1;
  }else {
    return n*Fact(n-1);
  }
}

public class 实现一组数据集合的全排列 {
      public void printAllSort(int[] arr) {
        if (arr == null || arr.length == 0) {
          return;
        }
        if (arr.length == 1) {
          System.out.println(arr[0]);
        }
        List<List<Integer>> result = _printAllSort(arr);
        int count=0;
        for (List list : result) {
          count++;
          System.out.println(list+" 第"+count+"种");
        }
      }
      private List<List<Integer>> _printAllSort(int[] tmpArr) {
        // 结束条件
        List<List<Integer>> result = new ArrayList<>();
        if (tmpArr.length == 2) {
          List<Integer> subList = new ArrayList<>();
          List<Integer> subList2 = new ArrayList<>();
          subList.add(tmpArr[0]);
          subList.add(tmpArr[1]);
          subList2.add(tmpArr[1]);
          subList2.add(tmpArr[0]);
          result.add(subList);
          result.add(subList2);
          return result;
        }
        // 当前层处理
        for (int i = 0; i < tmpArr.length; i++) {
          // 顺序拿出一个参数，其余交给下一层处理
          int tmp = tmpArr[i];
          int[] arr = new int[tmpArr.length - 1];
          int offset = 0;
          for (int j = 0; j < tmpArr.length; j++) {
            if (i != j) {
              arr[offset] = tmpArr[j];
              offset++;
            }
          }
          List<List<Integer>> nextLevelResult = _printAllSort(arr);
          // 处理下一层结果（当前值加到结果的前面、后面）
          for (List<Integer> nextList : nextLevelResult) {
            List<Integer> appendList = new ArrayList<>();
            appendList.add(tmp);
            appendList.addAll(nextList);
            result.add(appendList);
          }
        }
        return result;
      }
    }//[1, 2, 3, 4] 第1种  [1, 2, 4, 3] 第2种  [1, 3, 2, 4] 第3种  [1, 3, 4, 2] 第4种  [1, 4, 2, 3] 第5种  [1, 4, 3, 2] 第6种

//方法1：暴力法 使用递归
public int climbStairs(int n) {
  return climb_Stairs(0, n);
}
public int climb_Stairs(int i, int n) {
  if (i > n) {
    return 0;
  }
  if (i == n) {
    return 1;
  }
  return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
}//时间复杂度：O(2^n)

public class 记忆化递归 {
  public int climbStairs(int n) {
    int memo[] = new int[n + 1];
    return climb_Stairs(0, n, memo);
  }
  public int climb_Stairs(int i, int n, int memo[]) {
    if (i > n) {
      return 0;
    }
    if (i == n) {
      return 1;
    }
    if (memo[i] > 0) {
      return memo[i];
    }
    memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
    return memo[i];
  }
}

public class 动态规划求解爬楼梯 {
  public int climbStairs(int n) {
    if (n == 1) {
      return 1;
    }
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
      dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
  }
}

int hash(Object key){
  int h = key.hashCode();
  return (h ^ (h >>> 16)) & (capitity -1); //capicity表示散列表的大小
} 
public int hashCode(){
  int var1 = this.hash;
  if(var1 == 0 && this.value.length > 0){
    char[] var2 = this.value;
    for(int var3 = 0; var3 < this.value.length; ++var3) {
      var1 = 31 * var1 + var2[var3];
    }
    this.hash = var1;
  }
  return var1;
}

public class HashTable {
  private int tSize;
  private int count;
}
public class HashTableNode {
  private int blockCount;
  private ListNode startNode;//维护的线性表
}
public class 基于散列表解决冲突的散列表 {
  public final static int LOADFACTOR = 20;
  public static HashTable createHashTable(int size) {
    HashTable h = new HashTable();
    //count默认设置为0；
    h.settSize(size / LOADFACTOR);
    for (int i = 0; i < h.gettSize(); i++) {
      h.getTable()[i].setStartNode(null);
    }
    return h;
  }
  public static int hashSearch(HashTable h, int data) {
    ListNode temp;
    temp = h.getTable()[Hash(data, h.gettSize())].getStartNode();
    while (temp != null) {
      if (temp.getVal() ==data) {
         return 1; 
      }
      temp = temp.getNext();
    }
    return 0;
  }
  //散列函数
  public static int Hash(int data, int gettSize) {
    int h = data; /* data.hashCode(); */
    return (h ^ (h >>> 16)) & (gettSize - 1); // capicity表示散列表的大小
  }
}

public class LRU缓存淘汰算法{
  private ListNode head; //最近最少使用，类似列队的头，出队
  private ListNode tail; //最近最多使用，类似队列的尾，入队
  private Map<Integer, ListNode> cache;
  private int capacity;
  public LRU缓存淘汰算法(int capacity){
    this.cache = new HashMap<>();
    this.capacity = capacity;
  }
  public int get(int key) {
    ListNode node = cache.get(key);
    if (node == null) {
      return -1;
    } else {
      moveNode(node);//把该数据移动到链表尾部
      return node.value;
    }
  }
  public void put(int key, int value) {
    ListNode node = cache.get(key);
    if(node != null){
      node.value = value;
      moveNode(node);//把该数据移动到链表尾部
    } else{//缓存满了，移除链表的头结点
      removeHead();
      addNode(new ListNode(key, value));
    }
    cache.put(key, node);
  }
  private void removeHead() {
    if (cache.size() == capacity) {
      ListNode tempNode = head;
      cache.remove(head.key);
      head = head.next;
      tempNode.next = null;
      if (head != null)
        head.prev = null;
    }
  }
  private void addNode(ListNode node) {
    if (head == null)
      head = tail = node;
    else
      addNodeToTail(node);
  }
  private void addNodeToTail(ListNode node) {
    node.prev = tail;
    tail.next = node;
    tail = node;
  }
  //移动数据到链表尾部 分类讨论：第一种要移动的结点是头结点；第二种直接为尾节点，无需处理；第三种为链表中的结点
  private void moveNode(ListNode node){
    if (head == node && node != tail){
      head = node.next;
      head.prev = null;
      node.next = null;
      addNodeToTail(node);
    } else if (tail == node){
    } else {
      node.prev.next = node.next;
      node.next.prev = node.prev;
      node.next = null;
      addNodeToTail(node);
    }
  }
}

LinkedHashMap<Long, String> unchecked = new LinkedHashMap<Long, String >(20, .75F, true) {
     @Override
     protected boolean removeEldestEntry(Map.Entry<Long, String> eldest){
         //什么时候执行LRU操作
         return this.size() > 20;
     }
 };