基础数据结构

一、Trie

someone read like tree, from retrieval is also corrent.

Trie 树，又叫字典树、前缀树（Prifix Tree）、单词查找树或键树，是一种多叉树结构。

字典树的性质

根结点（Root）不包含字符，除根节点外的每一个节点都仅包含一个字符
从根节点到某一节点路径上所经过的字符连接起来，即为该节点对应的字符串；
任意节点的所有字节点所包含的字符串都不相同

Use cases : 自动补全、拼写检查、IP 路径（最长前缀匹配）、T9（九宫格）打字预测、词频统计（节省内存）

模板

常用 method

addWord(String word)
search(String word)
searchPrefix(String prefix)

208 实现 Trie (前缀树)open in new window

// 定义 TrieNode 数据结构
class TrieNode {
  TrieNode[] children;
  boolean isWord;
  public TrieNode() {
    children = new TrieNode[26];
  }
}
class Trie {
		// 成员变量 root
    public Trie() {
			// 初始化 root
    }
    
  	// 此处注意：root 不包含任何字符！
    public void insert(String word) {

    }
    
    public boolean search(String word) {

    }
    
    public boolean startsWith(String prefix) {

    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

211 添加与搜索单词 - 数据结构设计open in new window

class WordDictionary {

    public WordDictionary() {

    }
    
    public void addWord(String word) {

    }
    
    public boolean search(String word) {

    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

212 单词搜索 II（困难）open in new window

class Solution {
    public List<String> findWords(char[][] board, String[] words) {

    }
}

二、Union Find 并差集

动态连接（Dynamic connectivity）的问题，什么是Union Find？

并查集是一种树形的数据结构，用于处理不交集的合并（union）及查询（find）问题。

Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。

Union：将两个子集合并成同一个集合。

模板

class DSU {
  int[] parent;
  public DSU(int N) {
    parent = new int[N];
    for (int i = 0; i < N; i++) parent[i] = i;
  }
  public int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }
  public void union(int x, int y) {
    parent[find(x)] = find(y);
  }
}

Improved with size(weighted)

class DSU {
  int[] parent;
  // 记录组中元素数量
  int[] size;
  public DSU(int N) {
    parent = new int[N];
    size = new int[N];
    for (int i = 0; i < N; i++) parent[i] = i;
    // 初始化为 1
    Arrays.fill(size, 1);
  }
  public int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }
  
  // 小树挂到大树上
  // 元素数量少的赋给元素数量多的使其平衡，高度不变
  public void union(int x, int y) {
    int rootX = find(x), rootY = find(y);
    if (rootX == rootY) return;
    if (size[rootX] <= size[rootY]) {
      parent[rootX] = rootY;
      size[rootY] += size[rootX];
    } else if (size[rootX] > size(rootY)) {
      parent[rootY] = rootX;
      size[rootX] += size[rootY];
    }
  }
}

Improved with ranked

使用 rank 来优化，rank 代表数的高度或深度。高度低的树向高度高的树合并。

class DSU {
  int[] parent;
  // 记录深度
  int[] rank;
  public DSU(int N) {
    parent = new int[N];
    rank = new int[N];
    for (int i = 0; i < N; i++) parent[i] = i;
    Arrays.fill(rank, 1);
  }
  public int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }
  public void union(int x, int y) {
    int rootX = find(x), rootY = find(y);
    if (rank[rootX] < rank[rootY]) {
      parent[rootX] = rootY;
    } else if (rans[rootX] > rank[rootY]) {
      parent[rootY] = rootX;
    } else { // 相等时需要维护深度,X 贴给 Y，Y 深度加一
      parent[rootX] = rootY;
      rank[rootY]++;
    }
  }
}

305. Number of Islands 2

547. 省份数量open in new window

class Solution {
    public int findCircleNum(int[][] isConnected) {

    }
}

128. 最长连续序列open in new window

class Solution {
    public int longestConsecutive(int[] nums) {

    }
}
class DSU {
  int[] parent;
  int[] size;
  
  public DSU(int N){
    
  }
  
  public int find(int x) {
    
  }
  
  // 小树挂到大树上
  public void union(int x, int y) {
    
  }
  
  public int findMax() {
    
  }
}

三、Heap

四、栈，队列实现

栈（stack）

栈是限定仅在表尾进行插入和删除操作的线性表。栈又称为后进先出（Last In First Out）的线性表，简称 LIFO 结构。

队列（queue）

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出（First In First Out）的线性表，简称 FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

155. 最小栈

/**
 * two stack
 */
class MinStack {
		Stack<Integer> stack = new Stack<>();
 		Stack<Integer> minStack = new Stack<>();

    public MinStack() {

    }
    
  	// 如果为空或者比栈顶小则 push 进 minStack
    public void push(int val) {

    }
    
    // 如果移除的与 minStack 栈顶一样则同时移除
    public void pop() {

    }
    
    public int top() {

    }
    
    public int getMin() {

    }
}

/**
 * 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();
 */

/**
 * one stack
 */
class MinStack {
		Stack<int[]> stack = new Stack<>();
    public MinStack() {

    }
    
  	// 存入数组，数组第一个放自身，第二个与上一个第二个比较放入小的。
    public void push(int val) {

    }
    
    public void pop() {

    }
    
    public int top() {

    }
    
    public int getMin() {

    }
}

/**
 * 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();
 */

232. 用栈实现队列open in new window

225. 用队列实现栈open in new window

push heavy 情况
push O(1)
pop O(n)
pop heavy 情况
pop O(1)
push O(n)

/*
 * push heavy 情况
 * push     O(n)
 * pop、top O(1)
 */
class MyStack {
  	// 定义 q1， q2
  
    public void push(int x) {
			// 1. q1 为空放入 q1
      // 2. q2 不为空则全倒入 q1
      // 3. q1 不为空则全倒入 q2
    }
    
    public int pop() {
			// 检索并移除队列的头
    }
    
    public int top() {
			// 检索
    }
    
    public boolean empty() {
			// q1, q2 均为空则判空
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

/*
 * push heavy 情况
 * push     O(1)
 * pop、top O(n)
 */
class MyStack {
  	// 定义 q1， q2
  	Queue<Integer> q1 = new LinkedList<>();
    Queue<Integer> q2 = new LinkedList<>();
  	// 记录 top 数据
    int top；
    // 复杂度为 O(1)
    public void push(int x) {
			q1.offer(x);
      top = x;
    }
    
    public int pop() {
			// 检索并移除队列的头
      while (q1.size() > 1) {
        top = q1.poll();
        q2.add(top);
      }
      int value = q1.poll();
      Queue<Integer> tmp = q1;
      q1 = q2;
      q2 = tmp;
      return value;
    }
    
    public int top() {
			// 检索
      return top;
    }
    
    public boolean empty() {
			// q1, q2 均为空则判空
      return q1.isEmpty() && q2.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

622. 设计循环队列open in new window

// 使用数组实现循环队列
class MyCircularQueue {

    public MyCircularQueue(int k) {

    }
    
    public boolean enQueue(int value) {

    }
    
    public boolean deQueue() {

    }
    
    public int Front() {

    }
    
    public int Rear() {

    }
    
    public boolean isEmpty() {

    }
    
    public boolean isFull() {

    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

1381. 设计一个支持增量操作的栈open in new window

// 采用 lazy 操作
// 将需要加的 val 缓存到 inc 数组中，pop 操作的时候返回
class CustomStack {
		// 初始化最大 maxSize
  	// 初始化 inc 数组做缓存
  	// 初始化 stack 结构
    public CustomStack(int maxSize) {
			// 初始化 maxSize、inc
    }
    
    public void push(int x) {
			// 栈未满则 push
    }
    
    public int pop() {
			// 判断栈中元素数量
      // 小于零返回 -1
      // 大于零则
    }
    
    public void increment(int k, int val) {
			// 给缓存赋值
    }
}

/**
 * Your CustomStack object will be instantiated and called as such:
 * CustomStack obj = new CustomStack(maxSize);
 * obj.push(x);
 * int param_2 = obj.pop();
 * obj.increment(k,val);
 */

895. 最大频率栈open in new window

五、链表（上）反转 + 合并 + 找环

链表分为单链表、双链表、循环链表（有环）

链表的核心操作集有3种：插入、删除、查找

链表是由一组不必相连的内存结构（节点），按特定的顺序链接在一起的抽象数据结构

链表的基础知识是什么？

翻转链表
双指针合并链表
找环
删除 node
结构转换

206. 反转链表open in new window

// 方法1 interative 双指针
class Solution {
    public ListNode reverseList(ListNode head) {
  		ListNode newHead = null;
    	ListNode cur = head;
      while (cur != null) {
        ListNode next = cur.next;
        cur.next = newHead;
        // 	双指针同时后移
        newHead = cur;
        cur = next;
      }
      return newHead;
    }
}

// 方法2 recursive 递归
class Solution {
    public ListNode reverseList(ListNode head) {
			return reserve(head, null);
    }
  
  	private ListNode reserve(ListNode head, ListNode newHead) {
      if (head == null) return newHead;
      ListNode next = head.next;
      head.next = newHead;
      return reserve(next, head);
    }
}

92. 反转链表 IIopen in new window

25. K 个一组翻转链表open in new window（hard）

2. 两数相加open in new window

/**
 * 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; }
 * }
 */
 // 每个链表代表一个数字，相加向后进位
 // 373
 // 227
 // --------
 // 5901
// interative compact
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

    }
}


class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      // 定义虚拟头节点
      // 定义当前节点（因为后面要返回头节点）
      // 定义 carry 保存进位
			// 当 l1 或 l2 不为空 或者 carry == 1 一直循环
      		// 计算位数之和
      		// 与当前进位相加
      		// 定义节点
          // carry = val / 10
      		// 如果l1， l2不为空则下一为
          // cur 下一位
      
      // 返回头节点
    }
}

445. 两数相加 IIopen in new window

// 与2题一样，只不过使用 stack 反转链表顺序
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

    }
}

21. 合并两个有序链表open in new window

模板基础题，作为很多题目的 helper method

两种解法

常规解法注意最后剩余的一个数据
递归解法

// interative
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

    }
}

// recursive
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
			if (list1 == null) return list2;
      if (list2 == null) return list1;
      if (list1 < list2) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
      } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
      }
    }
}

23. 合并K个升序链表open in new window (hard)

/**
 * 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 mergeKLists(ListNode[] lists) {

    }
}

141. 环形链表open in new window

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
// 采用快慢双指针方法
public class Solution {
    public boolean hasCycle(ListNode head) {
        
    }
}

142. 环形链表 IIopen in new window

// 从数学思路入手
// 快指针路程： a + (b + c) + b = 2b + a + c
// 慢指针路程： a + b

// 快指针距离 = 2 * (a + b) 两倍速度
// 2b + a + c = 2 * (a + b)
// c = a
public class Solution {
    public ListNode detectCycle(ListNode head) {
        
    }
}

287. 寻找重复数open in new window

// 此题有五种解法，感兴趣可以了解一下
// 快慢双指针为最优解
// 时间 O(1)
// 空间 O(1)
class Solution {
    public int findDuplicate(int[] nums) {

    }
}

// 暴力解法
// 时间 O(n)
// 空间 O(n)
class Solution {
    public int findDuplicate(int[] nums) {
			Set<Integer> seen = new HashSet<>();
      for (int num : nums)
        if (!seen.add(num)) return num;
      return -1;
    }
}

// 时间 O(n)
// 空间 O(1)
class Solution {
    public int findDuplicate(int[] nums) {
			for (int i = 0; i < nums.length; i++)
        // 将元素转换为下标
        int index = Math.abs(num[i]) - 1;
      	// 如果未被标记过则进行标记
        if (nums[index] > 0) nums[index] *= -1;
      	else return index + 1;
      return -1;
    }
}

// 时间 O(nlog2)
// 空间 O(1)
class Solution {
    public int findDuplicate(int[] nums) {
			Arrays.sort(nums);
      for (int i = 1; i < nums.length; i++)
        if (nums[i] == nums[i - 1]) return nums[i];
      return -1;
    }
}

五、链表（下）删除 + 复制 + 结构转换

203. 移除链表元素open in new window

还是两种解法

双指针解法
递归解法

class Solution {
    public ListNode removeElements(ListNode head, int val) {
			// dummy or sentinel 哨兵节点
    }
}

83. 删除排序链表中的重复元素open in new window

class Solution {
    public ListNode deleteDuplicates(ListNode head) {

    }
}

82. 删除排序链表中的重复元素 IIopen in new window

class Solution {
    public ListNode deleteDuplicates(ListNode head) {

    }
}

19.删除链表的倒数第 N 个结点open in new window

常规解法
双指针解法

1171. 从链表中删去总和值为零的连续节点open in new window

本题目融合多种经典知识

sum + prfixSum 的结合，prefixsum array 中相同 value 的两个点之间的 subarray 的 sum 必然为 0，我们在第一次做 prefixSum 的时候只保存最后一次相同的 value，这样在第二次遍历的时候可以直接跳过。

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
			// 哨兵
      ListNode dummy = new ListNode(0);
      dummy.next = head;
      // prfixSum and ListNode
      Map<Integer, ListNode> map = new HashMap<>();
      // 存入头节点
     	map.put(0, dummy);
      int prefix = 0;
      for (ListNode i = dummy; i != null; i = i.next) {
        prefix += i.val;
        map.put(prefix, i); // 相同 prefix 只保留最后一个
      }
      prefix = 0;
      for (ListNode i = dummy; i != null; i = i.next) {
        prefix += i.val;
        i.next = map.get(prefix).next;
      }
      return dummy.next;
    }
}

243. 最短单词距离open in new window

反转链表后判断是否一致

快慢指针快指针是慢指针的两倍快指针到头慢指针正好处于中心

class Solution {
	public boolean isPalindrome(ListNode head) {
    ListNode firstHalfEnd = endOfFirstHalf(head);
    // 翻转后的第二个链表
    ListNode secondHalfStart = reverse(firstHalfEnd.next);
    // 对比链表
    ListNode p1 = head;
    ListNode p2 = secondHalfStart;
    boolean result = true;
    while (result && p1 != null && p2 != null) {
      if (p1.val != p2.val) result = false;
      p1 = p1.next;
      p2 = p2.next;
    }
    // 翻转回去
    firstHalfEnd.next = reverse(secondHalfStart);
    return result;
  }
  
  // 利用快慢指针返回链表半中央的节点
  private ListNode endOfFirstHalf(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast.next != null || fast.next.next != null) {
      fast = fast.next.next;
      slow = slow.next;
    }
    return slow;
  }
  
  // 翻转链表
  private ListNode reverse(ListNode head) {
    // 短路操作
    if (head == null || head.next == null) return head;
    ListNode res = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return res;
  }
}

160. 相交链表open in new window

提前假设两个链表相交

计算出两个链表长度，截取长链表与短链表长度一致
利用数学公式两个链表都走完 abc 三段路程
a + c + b = b + c + a

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      // 使用临时节点，头节点需要保存
      ListNode tmpA = headA;
      ListNode tmpB = headB;
      while (tmpA != tmpB) {
        tmpA = tmpA == null ? headB : tmpA.next;
        tmpB = tmpB == null ? headA : tmpB.next;
      }
      return tmpA;
    }
}

138. 复制带随机指针的链表open in new window

426. 将二叉搜索树转化为排序open in new window

将二分查找树转换为双链表结构

public class Solution {
  public Node treeToDoubluList(Node root) {
    
  }
}

# 基础数据结构

# 一、Trie

# 模板

# 208 实现 Trie (前缀树)open in new window

# 211 添加与搜索单词 - 数据结构设计open in new window

# 212 单词搜索 II（困难）open in new window

# 二、Union Find 并差集

# 模板

# 305. Number of Islands 2

# 三、Heap

# 四、栈，队列实现

# 155. 最小栈

# 五、链表（上）反转 + 合并 + 找环

# 25. K 个一组翻转链表open in new window（hard）

# 23. 合并K个升序链表open in new window (hard)

# 五、链表（下）删除 + 复制 + 结构转换