4. 动态规划

①. 动态规划（Dynamic Programming）

示例场景：实现一个动态规划算法来解决最长递增子序列（LIS）问题。

import React, { useState } from "react";

function longestIncreasingSubsequence(nums) {
  if (nums.length === 0) return 0;

  const dp = new Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

function DynamicProgrammingComponent() {
  const [nums, setNums] = useState("");
  const [lisLength, setLisLength] = useState(0);

  const handleCalculate = () => {
    const numArray = nums.split(",").map(Number);
    const lis = longestIncreasingSubsequence(numArray);
    setLisLength(lis);
  };

  return (
    <div>
      <h2>动态规划 - 最长递增子序列</h2>
      <input
        type="text"
        placeholder="输入数字，用逗号分隔"
        value={nums}
        onChange={(e) => setNums(e.target.value)}
      />
      <button onClick={handleCalculate}>计算LIS长度</button>
      <p>LIS长度: {lisLength}</p>
    </div>
  );
}

function App() {
  return (
    <div>
      <h1>动态规划 - 最长递增子序列</h1>
      <DynamicProgrammingComponent />
    </div>
  );
}

export default App;

②. 平衡二叉搜索树（AVL 树）

示例场景：实现一个 AVL 树，并提供插入、查找和删除功能。

import React, { useState } from "react";

class AVLNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

class AVLTree {
  constructor() {
    this.root = null;
  }

  getHeight(node) {
    return node ? node.height : 0;
  }

  getBalanceFactor(node) {
    return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
  }

  updateHeight(node) {
    if (node) {
      node.height =
        1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
    }
  }

  rotateRight(y) {
    const x = y.left;
    const T2 = x.right;

    x.right = y;
    y.left = T2;

    this.updateHeight(y);
    this.updateHeight(x);

    return x;
  }

  rotateLeft(x) {
    const y = x.right;
    const T2 = y.left;

    y.left = x;
    x.right = T2;

    this.updateHeight(x);
    this.updateHeight(y);

    return y;
  }

  insert(node, value) {
    if (!node) {
      return new AVLNode(value);
    }

    if (value < node.value) {
      node.left = this.insert(node.left, value);
    } else if (value > node.value) {
      node.right = this.insert(node.right, value);
    } else {
      return node; // Duplicate values not allowed
    }

    this.updateHeight(node);

    const balanceFactor = this.getBalanceFactor(node);

    if (balanceFactor > 1) {
      if (value < node.left.value) {
        return this.rotateRight(node);
      } else {
        node.left = this.rotateLeft(node.left);
        return this.rotateRight(node);
      }
    }

    if (balanceFactor < -1) {
      if (value > node.right.value) {
        return this.rotateLeft(node);
      } else {
        node.right = this.rotateRight(node.right);
        return this.rotateLeft(node);
      }
    }

    return node;
  }

  delete(node, value) {
    if (!node) {
      return node;
    }

    if (value < node.value) {
      node.left = this.delete(node.left, value);
    } else if (value > node.value) {
      node.right = this.delete(node.right, value);
    } else {
      if (!node.left && !node.right) {
        return null;
      } else if (!node.left) {
        return node.right;
      } else if (!node.right) {
        return node.left;
      }

      const minNode = this.findMinNode(node.right);
      node.value = minNode.value;
      node.right = this.delete(node.right, minNode.value);
    }

    this.updateHeight(node);

    const balanceFactor = this.getBalanceFactor(node);

    if (balanceFactor > 1) {
      if (this.getBalanceFactor(node.left) >= 0) {
        return this.rotateRight(node);
      } else {
        node.left = this.rotateLeft(node.left);
        return this.rotateRight(node);
      }
    }

    if (balanceFactor < -1) {
      if (this.getBalanceFactor(node.right) <= 0) {
        return this.rotateLeft(node);
      } else {
        node.right = this.rotateRight(node.right);
        return this.rotateLeft(node);
      }
    }

    return node;
  }

  findMinNode(node) {
    while (node.left) {
      node = node.left;
    }
    return node;
  }

  search(node, value) {
    if (!node) {
      return null;
    }

    if (value < node.value) {
      return this.search(node.left, value);
    } else if (value > node.value) {
      return this.search(node.right, value);
    } else {
      return node;
    }
  }

  inorderTraversal(node, result = []) {
    if (node) {
      this.inorderTraversal(node.left, result);
      result.push(node.value);
      this.inorderTraversal(node.right, result);
    }
    return result;
  }
}

function AVLTreeComponent() {
  const [avlTree, setAvlTree] = useState(new AVLTree());
  const [value, setValue] = useState("");
  const [searchResult, setSearchResult] = useState(null);

  const handleInsert = () => {
    const valueInt = parseInt(value, 10);
    if (!isNaN(valueInt)) {
      avlTree.root = avlTree.insert(avlTree.root, valueInt);
      setAvlTree(new AVLTree(avlTree.root)); // Create a new instance to trigger re-render
      setValue("");
    }
  };

  const handleDelete = () => {
    const valueInt = parseInt(value, 10);
    if (!isNaN(valueInt)) {
      avlTree.root = avlTree.delete(avlTree.root, valueInt);
      setAvlTree(new AVLTree(avlTree.root)); // Create a new instance to trigger re-render
      setValue("");
    }
  };

  const handleSearch = () => {
    const valueInt = parseInt(value, 10);
    if (!isNaN(valueInt)) {
      const node = avlTree.search(avlTree.root, valueInt);
      setSearchResult(node ? "找到" : "未找到");
    }
  };

  return (
    <div>
      <h2>AVL树</h2>
      <input
        type="number"
        value={value}
        onChange={(e) => setValue(e.target.value)}
      />
      <button onClick={handleInsert}>插入</button>
      <button onClick={handleDelete}>删除</button>
      <button onClick={handleSearch}>查找</button>
      <p>查找结果: {searchResult}</p>
      <h3>树内容（中序遍历）</h3>
      <ul>
        {avlTree.inorderTraversal(avlTree.root).map((value, index) => (
          <li key={index}>{value}</li>
        ))}
      </ul>
    </div>
  );
}

function App() {
  return (
    <div>
      <h1>AVL树</h1>
      <AVLTreeComponent />
    </div>
  );
}

export default App;

③. 斐波那契堆

示例场景：实现一个斐波那契堆，并提供插入、查找最小值和删除最小值功能。

import React, { useState } from "react";

class FibonacciHeap {
  constructor() {
    this.min = null;
    this.numNodes = 0;
  }

  insert(value) {
    const node = {
      value,
      degree: 0,
      child: null,
      parent: null,
      left: null,
      right: null,
      mark: false,
    };
    if (!this.min) {
      this.min = node;
      node.left = node;
      node.right = node;
    } else {
      node.left = this.min;
      node.right = this.min.right;
      this.min.right = node;
      node.right.left = node;
      if (node.value < this.min.value) {
        this.min = node;
      }
    }
    this.numNodes++;
  }

  findMin() {
    return this.min ? this.min.value : null;
  }

  extractMin() {
    if (!this.min) return null;

    const min = this.min;
    let child = min.child;
    let nextChild;

    while (child) {
      nextChild = child.right;
      child.left = this.min.left;
      child.right = this.min.right;
      this.min.left.right = child;
      this.min.right.left = child;
      child.parent = null;
      child = nextChild;
    }

    if (min === min.right) {
      this.min = null;
    } else {
      this.min = min.right;
      this.consolidate();
    }

    this.numNodes--;
    return min.value;
  }

  consolidate() {
    const maxDegree = Math.floor(Math.log2(this.numNodes)) + 1;
    const degreeTable = new Array(maxDegree).fill(null);

    let current = this.min;
    do {
      let degree = current.degree;
      while (degreeTable[degree]) {
        const other = degreeTable[degree];
        if (current.value > other.value) {
          [current, other] = [other, current];
        }
        this.link(other, current);
        degreeTable[degree] = null;
        degree++;
      }
      degreeTable[degree] = current;
      current = current.right;
    } while (current !== this.min);

    this.min = null;
    for (let i = 0; i < maxDegree; i++) {
      if (degreeTable[i]) {
        if (!this.min || degreeTable[i].value < this.min.value) {
          this.min = degreeTable[i];
        }
      }
    }
  }

  link(child, parent) {
    child.left.right = child.right;
    child.right.left = child.left;
    child.parent = parent;
    if (!parent.child) {
      parent.child = child;
      child.left = child;
      child.right = child;
    } else {
      child.left = parent.child;
      child.right = parent.child.right;
      parent.child.right = child;
      child.right.left = child;
    }
    parent.degree++;
    child.mark = false;
  }
}

function FibonacciHeapComponent() {
  const [fibHeap, setFibHeap] = useState(new FibonacciHeap());
  const [value, setValue] = useState("");
  const [minValue, setMinValue] = useState(null);

  const handleInsert = () => {
    const valueInt = parseInt(value, 10);
    if (!isNaN(valueInt)) {
      fibHeap.insert(valueInt);
      setFibHeap(new FibonacciHeap(fibHeap.min, fibHeap.numNodes)); // Create a new instance to trigger re-render
      setValue("");
    }
  };

  const handleExtractMin = () => {
    const min = fibHeap.extractMin();
    setMinValue(min);
  };

  return (
    <div>
      <h2>斐波那契堆</h2>
      <input
        type="number"
        value={value}
        onChange={(e) => setValue(e.target.value)}
      />
      <button onClick={handleInsert}>插入</button>
      <button onClick={handleExtractMin}>提取最小值</button>
      <p>提取的最小值: {minValue !== null ? minValue : "无"}</p>
      <h3>堆内容</h3>
      <ul>
        {fibHeap.inorderTraversal().map((value, index) => (
          <li key={index}>{value}</li>
        ))}
      </ul>
    </div>
  );
}

function App() {
  return (
    <div>
      <h1>斐波那契堆</h1>
      <FibonacciHeapComponent />
    </div>
  );
}

export default App;

④. 布隆过滤器（Bloom Filter）

示例场景：实现一个布隆过滤器，并提供插入和查找功能。

import React, { useState } from "react";

class BloomFilter {
  constructor(size, hashFunctions) {
    this.bitArray = new Array(size).fill(false);
    this.hashFunctions = hashFunctions;
  }

  add(item) {
    for (const hashFunction of this.hashFunctions) {
      const index = hashFunction(item) % this.bitArray.length;
      this.bitArray[index] = true;
    }
  }

  contains(item) {
    for (const hashFunction of this.hashFunctions) {
      const index = hashFunction(item) % this.bitArray.length;
      if (!this.bitArray[index]) {
        return false;
      }
    }
    return true;
  }
}

const hashFunctions = [
  (str) => str.split("").reduce((acc, char) => acc + char.charCodeAt(0), 0),
  (str) =>
    str
      .split("")
      .reduce((acc, char, i) => acc + char.charCodeAt(0) * (i + 1), 0),
  (str) =>
    str
      .split("")
      .reduce((acc, char, i) => acc + char.charCodeAt(0) * (i + 2), 0),
];

function BloomFilterComponent() {
  const [bloomFilter, setBloomFilter] = useState(
    new BloomFilter(100, hashFunctions)
  );
  const [item, setItem] = useState("");
  const [containsResult, setContainsResult] = useState("");

  const handleAdd = () => {
    bloomFilter.add(item);
    setItem("");
  };

  const handleContains = () => {
    const result = bloomFilter.contains(item);
    setContainsResult(result ? "可能包含" : "不包含");
  };

  return (
    <div>
      <h2>布隆过滤器</h2>
      <input
        type="text"
        value={item}
        onChange={(e) => setItem(e.target.value)}
      />
      <button onClick={handleAdd}>添加</button>
      <button onClick={handleContains}>检查</button>
      <p>检查结果: {containsResult}</p>
    </div>
  );
}

function App() {
  return (
    <div>
      <h1>布隆过滤器</h1>
      <BloomFilterComponent />
    </div>
  );
}

export default App;

在 React 中使用平衡二叉搜索树（AVL 树）、斐波那契堆、布隆过滤器和动态规划。这些数据结构和算法在解决各种问题时非常有效，特别是在处理高效查找、堆操作、集合成员检查和优化问题时。