随笔记录

算法-二叉树-序列化&反序列化

2022-4-11 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /** * 二叉树的序列化与反序列化 * * @Author jiucaiyuan 2022/4/11 22:57 * @mail services@jiucaiyuan.net */ public class SerializeAndDeserializeTree { /** * 先序遍历-序列化...

阅读全文>>

评论(0) 浏览(581)

算法-二叉树-最低公共祖先

2022-4-11 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; /** * <pre> * 【问题】给定二叉树的两个节点node1和node2，找到他们最低公共祖先 * 【概念】最低公共祖先：两个节点往root节点的链路，第一个相交的节点 * 【思路】 * </pre> * * @Author jiucaiyuan ...

阅读全文>>

评论(0) 浏览(601)

算法-二叉树-判断满二叉树

2022-4-10 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree; /** * <pre> * 【问题】判断一棵树是满二叉树(Full Binary Tree) * 【概念】满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。 * 也就是说，如果一个二叉树的深度为K，且结点总数是(2^k) -1 ，则它就是满二叉树。 * (一棵满二叉树的每一个结点要么是叶子结点，要么它有两个子结点，但是反过来不成立， * 因为完全二叉树也满足这个要求，但不是满二叉树) * 【思路】获得二叉...

阅读全文>>

评论(0) 浏览(646)

算法-二叉树-判断完全二叉树

2022-4-10 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /** * <pre> * 【问题】判断一棵树是完全二叉树(Complete Binary Tree) * 【概念】完全二叉树：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部（树只有最后一层可能出现不满，只能是右下角缺少子树） * 【思路】通过二叉树的宽度优先遍历，判断 * >...

阅读全文>>

评论(0) 浏览(1368)

算法-二叉树-判断搜索二叉树

2022-4-10 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree; import java.util.Stack; /** * <pre> * 【问题】判断一棵树是否是搜索二叉树（Binary Search Tree），（又：二叉搜索树，二叉排序树） * 【概念】搜索二叉树：树的左子树比头结点小，右子树比头结点大（左子<头<右子） * 【思路】通过二叉树的中序遍历，判断树中节点一直是升序的，不出现降序即可 * </pre> * * @Author jiucaiyuan 2022/4/10 16:42 ...

阅读全文>>

评论(0) 浏览(561)

算法-二叉树-宽度优先遍历&树宽度

2022-4-10 diaba 笔试题

package com.jiucaiyuan.net.algrithm.tree; import java.util.HashMap; import java.util.LinkedList; import java.util.Queue; /** * 二叉树的宽度优先遍历（求一个二叉树的宽度） * 使用辅助工具队列LinkedList，压入队列，出队时进行访问 * * @Author jiucaiyuan 2022/4/9 23:15 * @mail services@jiucaiyuan.net */ public class TreeMax...

阅读全文>>

评论(0) 浏览(558)

算法-二叉树遍历

2022-4-9 diaba 数据结构

package com.jiucaiyuan.net.algrithm.tree; import java.util.Stack; /** * 二叉树的遍历（前序、中序、后续遍历）递归+非递归 * * @Author jiucaiyuan 2022/4/9 22:16 * @mail services@jiucaiyuan.net */ public class PreInPostTraversal { /** * 先序遍历-非递归 */ public static void preOrderUnRecur(Nod...

阅读全文>>

评论(0) 浏览(515)

算法-链表-找两个单项链表首个相交节点

2022-4-9 diaba 算法

package com.jiucaiyuan.net.algrithm.linked; import java.util.HashSet; import java.util.Set; /** * <pre> * 【问题】找到两个单项链表第一个相交节点 * 【解题思路】 * case1：两个无环链表相交 * 把长链表长出来部分先走完，然后两个链表一起走，如果发现两个链表当前节点相同，则该节点即是所找 * case2：两个有环链表相交 * 入环节点是否相同 * 相同：按照两个无环链表的查找思路，以入环节...

阅读全文>>

评论(0) 浏览(504)

算法-链表-找到单链表入环节点

2022-4-7 diaba 笔试题

问题 判断一个单链表是否存在环，如果存在返回入环节点 要求 时间复杂度O(N)，空间复杂度O(1) 方案 快慢指针：从头结点开始，快指针一次走两步，满指针一次走一步，如果这两个指针相遇后，快指针回到头结点，两个指针一起开始走，每次走一步，再次相遇的节点即是入环节点 代码 package com.jiucaiyuan.net.algrithm.linked; import java.util.HashSet; import java.util.Set; /** * 【问题】...

阅读全文>>

评论(0) 浏览(598)

算法-链表-复制带随机指针的链表

2022-4-5 diaba 算法

package com.jiucaiyuan.net.algrithm.linked; import java.util.HashMap; /** * 【问题】复制带有随机指针节点的链表 * 【要求】时间复杂度O(N)，空间复杂度O(1) * 【思路】如果不是空间复杂度O(1)的限制，可以使用Map，暂存新老节点之间的关系， * 然后再补齐rand字段，但是有O(1)限制，所以在克隆出新节点时，放到该节点之后， * 变成注入这个结构：1——>1`——>2——>2`——>3——>3`——>4——>4`——>5——&g...

阅读全文>>

评论(0) 浏览(562)

算法-链表-是否为回文

2022-4-5 diaba 算法

package com.jiucaiyuan.net.algrithm.linked; import java.util.Stack; /** * 【问题】给定一个单项链表的头结点head，请判断该链表是否是回文结构 * 【例子】 * 1——>2——>1，返回true * 1——>2——>2——>1，返回true * 15——>6——>15，返回true * 1——>2——>3，返回false * 【要求】时间复杂度O(N)，空间复杂度O(1) * 【思路】快慢指针，快指针走到末尾，慢指针走到终点...

阅读全文>>

评论(0) 浏览(524)

算法-基数排序

2022-4-2 diaba 算法

package com.jiucaiyuan.net.algrithm.sort; import java.net.InetSocketAddress; /** * <pre> * 基数排序 * 根据数据特点进行排序，而非基于比较 * 时间复杂度O(N*logN) 空间复杂度O(1) * </pre> * Created by jiucaiyuan on 2022/4/1. */ public class RadixSort { public static void radixSort(int[] arr) {...

阅读全文>>

评论(0) 浏览(534)

算法-堆排序扩展排序几乎有序数组

2022-4-1 diaba 算法

package com.jiucaiyuan.net.algrithm.sort; import java.util.PriorityQueue; /** * <pre> * 堆排序扩展 * 一个几乎有序的数组， * 几乎有序是指，如果把数组排好顺序的话， * 每个元素移动的距离可以不超过k，这个k相对于数组来说比较小， * 请选择合适的排序算法针对这个数组进行排序 * * 时间复杂度O(N*logk) 空间复杂度O(k) * * </pre> * Created by jiucaiyuan ...

阅读全文>>

评论(0) 浏览(576)