恋上算法与数据结构笔记

Algorithm

发布日期: 2022-10-12

更新日期: 2024-04-20

文章字数: 3.6k

阅读时长: 16 分

阅读次数:

链表

结构

public class ListNode{
    int value;
    ListNode next;
    ListNode(int x){
        value = x;
    }
}

删除节点

思路:链表只能获取每个节点的值和它的下一个节点删除节点(对外)只需要删除这个数据

将要删除的节点的下一个节点的数据覆盖到该节点
让该节点指向下一个节点的下一个节点

public void deleteNode(ListNode node){
    node.value = node.next.value;
    node.next = node.next.next;
}

反转链表

递归

每次用reverseList(head.next)获取从下一个节点开始反转之后的链表
让head的下一个节点指向head
让head指向空

public ListNode reverseList(ListNode head){
    if(head == null || head.next == null) return head;//空链表或只有一个节点
    
    ListNode newHead = reverseList(head.next);//从head.next开始反转，得到的newHead相当于图片中红框部分。
    head.next.next = head;//head.next为4，将4的next指向5
    head.next = null;//使5的next指向null
    return newHead;
}

迭代

创建一个新空链表newHead
让head节点指向newHead
让newHead指向head节点
让head指向下一个节点
循环直到head指向空

public ListNode reverseList2(ListNode head){
    if(head == null || head.next == null) return head;
    
    ListNode newHead = null;
    while(head != null){
        ListNode temp = head.next;
        head.next = newHead;
        newHead = head;
        head = temp;
    }
    return newHead;
}

环形链表-快慢指针

定义两个指针一个跑得快一个跑得慢
如果有环形链表快指针和慢指针一定会有时刻重合(快的一定会追上慢的)
如果不是环形链表快的一定会先指向null

public boolean hasCycle(ListNode head){
    if(head == null || head.next == null) return head;
    
    ListNode slow = head;
    ListNode fast = head.next;
    
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow) return true;
    }
    
    return false;
}

二叉树

二叉搜索树

元素必大于左子树上的任何元素, 小于右子树上的任何元素

public class Node<E>{
    E element;
    Node<E> parent; //父节点
    Node<E> left; //左子节点
    Node<E> right; //右子节点
}

添加节点

找到父节点
创建新节点
将节点插入空位

public void add(E element){
    //添加的节点为根节点
    if(root == null){
        root = new Node<>(element, null);
        size++;
        return;
    }
    
    //添加的节点不是根节点
    //找到父节点
    Node<E> node = root;
    Node<E> parent = root;//保存最后一个找到的节点
    int cmp;//保存最后一次比较的结果
    
    while(node != null){
        cmp = compare(element, node.element);
        
        parent = node;
        
        if(cmp > 0){
            node = node.right;
        }
        else if(cmp < 0){
            node = node.left;
        }
        else{//相等
            //不允许相等：两种方法 1.忽略(chosen) 2.覆盖
            //允许相等：合并入上面的一种情况
            return;
        }
    }
    
    Node<E> newNode = new Node<>(element, parent);
    //插入方向
    if(cmp > 0){
        parent.right = newNode;
    }
    else{
        parent.left = newNode;
    }
    size++;
}

删除节点

删除节点为叶子节点：直接删除
度为1的节点：用子节点替代原节点位置
度为2的节点：用此节点的前驱节点或后继节点代替此节点

注：如果一个节点的度为2，那么它的前驱、后继节点的度只可能是0或1

private void remove(Node<E> node){
    if(node == null) return;
    
    size--;
    
    if(node.left != null && node.right != null){//度为2
        //找到前驱节点
        Node<E> p = preccessor(node);
        //用前驱节点的值覆盖度为2的节点的值
        node.element = p.element;
        //删除前驱节点
        node = p;
    }
    
    //删除node
    Node<E> replacement = node.left != null ? node.left : node.right;
    
    if(replacement != null){//node是度为1的节点
        //更改parent
        replacement.parent = node.parent;
        //更改parent的left\right指向
        if(node.parent == null){
            root = replacement;
        }else if(node == node.parent.right){
            node.parent.right = replacement;
        }else{
            node.parent.left = replacement;
        }
    }else{//node是叶子节点
        if(node.parent == null){
            root = null;
        }else if(node == node.parent.right){
            node.parent.right = null;
        }else{
            node.parent.left = null;
        }
    }
}

遍历

前序遍历(`Preorder Traversal`)

访问顺序: 根节点, 前序遍历左子树, 前序遍历右子树(类似dfs)

//递归
public void preorderTraversal(){
     preorderTraversal(root);
}
private void preorderTraversal(Node<E> node){
    if(node == null) return;
    //访问操作
    preorderTraversal(node.left);
    preorderTraversal(node.right);
}

中序遍历(`Inorder Traversal`)

访问顺序: 中序遍历左子树, 根节点, 中序遍历右子树(或左右互换)

特性: 访问后数据为升序(如先访问右子树则为降序)

//递归
public void inorderTraversal(){
     inorderTraversal(root);
}
private void inorderTraversal(Node<E> node){
    if(node == null) return;
    inorderTraversal(node.left);
    //访问操作
    inorderTraversal(node.right);
}

后序遍历(`Postorder Traversal`)

访问顺序: 后序遍历左子树, 后序遍历右子树, 根节点

//递归
public void postorderTraversal(){
     postorderTraversal(root);
}
private void postorderTraversal(Node<E> node){
    if(node == null) return;
    postorderTraversal(node.left);
    postorderTraversal(node.right);
    //访问操作
}

层序遍历(Lever Order Traversal)

访问顺序: 从上到下从左到右访问(类似于bfs)

思路: 队列

将根节点入队
循环执行:
1. 将队头节点a出队并访问
2. 将a的左子节点入队
3. 将a的右子节点入队

public void levelOrderTraversal(Node<E> root){
    if(root == null) return;
    
    Queue<Node<E>> queue = new Queue<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        Node<E> node = queue.poll();
        //访问node
        if(node.left != null) queue.offer(node.left);
        if(node.right != null) queue.offer(node.right);
    }
}

树的高度

//递归
public int height(){
     return height(root);   
}

private int height(Node<E> node){
    if(node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

//迭代(层序遍历)
//思路: 每层最后一个访问完后队列中元素数量即下一层元素数量
public int height(){
    if(root == null) return;
    
    int height = 0;
    int rowSize = 1;
    
    Queue<Node<E>> queue = new Queue<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        Node<E> node = queue.poll();
        rowSize --;
        
        if(node.left != null) queue.offer(node.left);
        if(node.right != null) queue.offer(node.right);
        if(rowSize == 0){
            rowSize = queue.size;
            height ++;
        }
    }
    
    return height;
}

判断完全二叉树(利用层序遍历)

树为空否
左右都非空将子节点入队
左空右非空否
左非空右空或左右都空之后节点应均为叶子节点否则为否

public boolean isComplete(){
    if(root == null) return false;
    
    boolean leaf;
    Queue<Node<E>> queue = new Queue<>();
    
    queue.offer(root);
    while(!queue.isEmpty()){
        Node<E> node = queue.poll();
        if(leaf && !node.isLeaf) return false;
        
        if(node.left != null) queue.offer(node.left);
        else if(node.right != null) return false;
        
        if(node.right != null) queue.offer(node.right);
        else leaf = true;
    }
    
    return true;
}

反转二叉树

只要保证遍历到每个节点并交换均可

中序遍历需注意遍历完左子树交换后传入另一子树（仍为左子树）

eg.层序遍历（迭代）：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue nodes;
        nodes.push(root);

        while (!nodes.empty())
        {
            TreeNode * node = nodes.front();
            if(node != NULL){
                TreeNode * temp = node->left;
                node->left = node->right;
                node->right = temp;
                nodes.push(node->left);
                nodes.push(node->right);
            }
            nodes.pop();
        }
        
        return root;
    }
};

eg.前序遍历（递归）

public TreeNode invertTree(TreeNode root){
    if(root == null) return root;
    
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

重构二叉树

前序遍历 + 中序遍历

class Solution {
public:
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        if(preorder.size() == 0 || inorder.size() == 0) return NULL;
        TreeNode * root = new TreeNode(preorder[0]);
        
        int i;
        for (i = 0; i < inorder.size(); i++)
        {
            if(inorder[i] == preorder[0]) break;
        }
        
        vector leftpreorder((preorder.begin() + 1), (preorder.begin() + i + 1));
        vector rightpreorder((preorder.begin() + 1 + i), (preorder.end()));
        vector leftinorder((inorder.begin()), (inorder.begin() + i));
        vector rightinorder((inorder.begin() + 1 + i), (inorder.end()));
        root->left = buildTree(leftpreorder, leftinorder);
        root->right = buildTree(rightpreorder, rightinorder);

        return root;
    }
};

后序遍历 + 中序遍历
前序遍历 + 后序遍历 + 真二叉树（节点的子节点数为0或2）

前驱节点

概念：中序遍历时的前一个节点
思路：在二叉搜索树中即为前一个比它小的节点

左子树非空时为左子树中最大节点

左子树空父节点非空时向上找父节点直到node在parent右子树中

否则无前驱节点

private Node<E> predecessor(Node<E> node){
    if(node == null) return null;
    
    //前驱节点在左子树当中(left.right.right.right...)
    Node<E> p = node.left;
    if(p != null){
        while(p.right != null){
            p = p.right;
        }
        return p;
    }
    
    //从父结点、祖父节点中寻找前驱节点
    while(node.parent != null && node == node.parent.left){
        node = node.parent;
    }
    
    //node.parent == null(没有前驱节点)
    //node == node.parent.right(前驱节点即父节点)
    return node.parent;
}

后继节点

与前驱节点相反

右子树非空时为右子树中最小节点

右子树空父节点非空时向上找父节点直到node在parent左子树中

否则无后继节点

将上述代码中left改成right，right改成left即可

AVL树

原因：分析二叉搜索树增删查复杂度均与由树高决定

如从小到大添加节点会退化成链表
平衡：节点数相同时，左右子树高度越接近树就越平衡
平衡因子：某节点左右子树高度差

性质

每个节点的平衡因子只可能是1， 0， -1 否则为失衡
每个节点的左右子树高度差不超过1
增删改的时间复杂度为O(logn)

分析

添加元素时父节点不可能失衡其他所有祖先节点都可能失衡

排序

堆排序

原地建堆

重复执行以下步骤直到堆中元素为1

将堆顶元素与堆底元素交换
将堆大小-1

将堆顶元素下滤

while(heapSize > 1){
    swap(0, --heapSize);
    
    siftDown(0);
}

并查集

Quick Find

find O(1) 找到节点父节点

union O(n) 让左边与集合内所有元素指向节点指向右边父节点

for(int i = 0; i < parents.length; i++){
    parents[i] = i;
}

//父节点就是根节点
public int find(int v){
    return parents[v];
}

//将v1的所有元素嫁接到v2的父节点上
public void union(int v1, int v2){
    int p1 = find(v1);
    int p2 = find(v2);
    if(p1 == p2) return;
    
    for(int i = 0; i < parents.length; i++){
        if(parents[i] == p1){
            parents[i] = p2;
        }
    }
}

public boolean isSame(int v1, int v2){
    retrun find(v1) == find(v2);
}

Quick Union

find O(logn) 找到节点根节点

union O(logn) 让左边根节点指向右边根节点

//不断向上,直到找到根节点
public int find(int v){
    while(v != parents[v]){
        v = parents[v];
    }
    return v;
}

//将v1的根节点嫁接到v2的根节点上
public void union(int v1, int v2){
    int p1 = find(v1);
    int p2 = find(v2);
    if(p1 == p2) return;
    
    parents[p1] = p2;
}

优化

基于Quick Union优化

可能出现树不平衡,退化至链表,使find=O(n)

基于size的优化

元素少的嫁接到元素多的

sizes = new int[capacity];
for(int i = 0; i < sizes.length; i++){
    sizes[i] = 1;
}

public void union(int v1, int v2){
    int p1 = find(v1);
    int p2 = find(v2);
    if(p1 == p2) return;
    
    if(sizes[p1] < sizes[p2]){
        parents[p1] = p2;
        sizes[p2] += sizes[p1];
    }
    else{
        parents[p2] = p1;
        sizes[p1] += sizes[p2];
    }
}

基于rank的优化

矮的树嫁接到高的树

ranks = new int[capacity];
for(int i = 0; i < sizes.length; i++){
    ranks[i] = 1;
}

public void union(int v1, int v2){
    int p1 = find(v1);
    int p2 = find(v2);
    if(p1 == p2) return;
    
    if(ranks[p1] < ranks[p2]){
        parents[p1] = p2;
    }
    else if(ranks[p1] > ranks[p2]){
        parents[p2] = p1;
    }
    else{
        parents[p1] = p2;
        ranks[p2] += 1;
    }
}

路径压缩(基于Quick Union-rank优化)

在find时使路径上所有节点指向根节点

public int find(int v){
    while(v != parents[v]){
        parents[v] = find(parents[v]);
    }
    
    return v;
}

路径分裂

使路径上的每个节点指向它的祖父节点

public int find(int v){
    while(v != parents[v]){
        int p = parents[v];
        parents[v] = parents[parents[v]];
        v = p;
    }
    
    return v;
}

路径减半

是路径上每隔一个节点就指向其祖父节点

public int find(int v){
    while(v != parents[v]){
        parents[v] = parents[parents[v]];
        v = parents[v];
    }
    
    return v;
}

泛型

public class GenericUnionFind<V>{
    public Mao<V, Node<V>> nodes = new HashMap<>(){
        public void makeSet(V v){
            if(nodes.containsKey(v)) rerurn;
            nodes.put(v, new Node<>(v));
        }
        
        private Node<V> findNode(V v){
            Node<V> node = node.get(v);
            if(node == null) return null;
            while()
        }
    }
}

搜索

广度优先搜索 (Breadth First Search)

以与初始节点的距离大小为顺序遍历

思路：用队列将初始节点加入队列之后每取出一个节点就将此节点的子节点放入队列已加入过的节点忽略

private void bfs(Vertex<V, E> beginVertex){
    Set<Vertex<V, E>> visitedVertices = new HashSet<>();
    Queue<Vertex<V, E>> queue = new LinkedList<>();
    queue.offer(beginVertex);
    visitedVertices.add(beginVertex);
    while(!queue.isEmpty()){
        Vertex<V, E> vertex = queue.poll();
        System.out.println(vertex.value); //遍历
        
        for(Edge<V, E> edge : vertex.outEdges){
            if(visitedVertices.contains(edge.to)) continue;
            queue.offer(edge.to);
            visitedVertices.add(edge.to);
        }
    }
}

深度优先搜索 (Depth First Search)

每次走到最大距离然后往回退走下一条路的最大距离

递归

思路：递归，每次遍历该节点的子节点（子节点又会遍历自己的子节点

private void dfs(Vertex<V, E> vertex, Set<Vertex<V, E>> visitedVertices){
    System.out.println(vertex.value); //遍历
    visitedVertices.add(vertex)
    
    for(Edge<V, E> edge : vertex.outEdges){
        if(visitedVertices.contains(edge.to)) continue;
        dfs(edge.to, visitedVertices);
    }
}

迭代

思路: 利用栈先将第一个节点加入栈中

弹出顶上的节点,打印节点
选择此节点的一条边的to节点(未被加入过的)
将此节点和to节点加入栈中
重复上述操作直到栈为空

public void dfs(V begin){
    Vertex<V, E> beginVertex = vertices.get(begin);
    if(beginVertex == null) return;
    
    Set<Vertex<V, E>> visitedVertices = new HashSet<>();
    Stack<Vertex<V, E>> stack - new Stack<>();
    
    //初始化
    stack.push(beginVertex);
    visitedVertices.add(beginVertex);
    System.out.println(beginVertex.value);
    
    while(!stack.isEmpty()){
        Vertex<V, E> vertex = stack.pop();
        for(Edge<V, E> edge : vertex.outEdges){
            if(visitedVertices.contains(edge.to)) continue;
            
            stack.push(edge.from);
            stack.push(edge.to);
            visitedVertices.add(edge.to);
            System.out.println(edge.to.value);
            
            break; //拿到一条边后就结束循环
        }
    }
}

AOV网-拓扑排序 (`topologicalSort`)

作用: 使AOV网中每个活动的前去活动都排在该活动的前面

条件: 有向无环图

卡恩算法

思路:

将所有入度为零的节点值放入结果列表
将此节点从图中去除
重复操作,直到没有入度为零的节点

结果:

如果结束后列表中元素与定点总数相同,说明拓扑排序完成
如果结束后列表中元素个数小于定点总数,说明存在环,无法完成拓扑排序

缺点: 需将顶点从图中删除不符合设计原则

优化: 创建入度表,每次将节点值放入结果列表时将其所有outEdges对应to节点的入度减一,达成删除节点同效果.

细节优化:一开始入度就为零的节点不涉及入度修改,不用放入入度表

public List<V> topologicalSort(){
    List<V> list = new ArryList<>(); //结果列表
    Queue<Vertex<V, E>> queue = new LinkedList<>(); //入度为零的节点
    Map<Vertex<V, E>, Integer> ins = new HashMap<>(); //入度表
    //初始化 将初始入度为零的放入队列
    vertices.forEach((V v, Vertex<V, E> vertex) ->{
        int in = vertex.inEdges.size();
        if(in == 0){
            queue.offer(vertex);
        }else{
            ins.put(vertex, in);
        }
    });
    
    while(!queue.isEmpty()){
        Vertex<V, E> vertex = queue.poll();
        // 放入返回结果
        list.add(vertex.value);
        
        for(Edge<V, E> edge : vertex.outEdges){
            int toIn = ins.get(edge.to) - 1;
            if(toIn == 0){
                queue.offer(edge.to);
            }else{
                int.put(edge.to, toIn);
            }
        }
    }
}

mashimaro kumo

https://mashimarokumo.github.io/posts/lian-shang-suan-fa-yu-shu-ju-jie-gou-bi-ji/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 mashimaro kumo !

Study Algorithm

编辑器简单拓展

2022-11-17 Unity

Unity Study Unity Editor

my fist blog!!!!!!

2021-01-30 mashimaro kumo

恋上算法与数据结构笔记

链表

结构

删除节点

反转链表

递归

迭代

环形链表-快慢指针

二叉树

二叉搜索树

添加节点

删除节点

遍历

前序遍历(Preorder Traversal)

中序遍历(Inorder Traversal)

后序遍历(Postorder Traversal)

层序遍历(Lever Order Traversal)

树的高度

判断完全二叉树(利用层序遍历)

反转二叉树

重构二叉树

前驱节点

后继节点

AVL树

性质

分析

排序

堆排序

并查集

Quick Find

Quick Union

优化

基于Quick Union优化

基于size的优化

基于rank的优化

路径压缩(基于Quick Union-rank优化)

路径分裂

路径减半

泛型

搜索

广度优先搜索 (Breadth First Search)

深度优先搜索 (Depth First Search)

递归

迭代

AOV网-拓扑排序 (topologicalSort)

卡恩算法

前序遍历(`Preorder Traversal`)

中序遍历(`Inorder Traversal`)

后序遍历(`Postorder Traversal`)

AOV网-拓扑排序 (`topologicalSort`)