左神专题
左神说：被火车撞了都不能忘记的算法
最大值窗口 https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/ class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums == null || k < 1 || nums.length<k) return new
左神的算法课笔记整理
简介：本文包含了 递归行为时间复杂度、快速排序的空间复杂度、堆排序、排序算法稳定性、工程中的综合排序算法、有关排序小知识 递归行为 递归行为时间复杂度 快速排序的空间复杂度 O(logN) ←原因是储存断点，二分再释放的过程，有多少个二分点，就需要多少的存储空间 堆排序 堆：完全二叉树 大根堆：任何一个子树的最大值都是这个子树的头部 插入操作：按照从左到右顺
左神算法课笔记（二）：链表、栈和队列、递归Master公式、哈希表、有序表
单向链表 双向链表 单链表、双链表最简单的面试题 1、单链表和双链表如何反转 package class02;import java.util.ArrayList;public class Code01_ReverseList {public static class Node {public int value;public Node next;public Node(int
左神算法：环形单链表的约瑟夫问题（Java版）
本题来自左神《程序员面试代码指南》“环形单链表的约瑟夫问题”题目。 题目 据说，著名犹太历史学家 Josephus 有过以下故事： 在罗马人占领乔塔帕特后，39 个犹太人与Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自杀，然后再由下一个人重新报 1，报数到
左神算法：生成窗口最大值数组（Java版）
本题来自左神《程序员面试代码指南》“生成窗口最大值数组”题目。 题目 有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。 例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时： 窗口数组 最大值 [4 3 5] 4 3 3 6 7 54 [
左神算法：找到二叉树中符合搜索二叉树条件的最大拓扑结构（Java版）
本题来自左神《程序员代码面试指南》“找到二叉树中符合搜索二叉树条件的最大拓扑结构”题目。 题目 牛客OJ：找到二叉树中符合搜索二叉树条件的最大拓扑结构 给定一棵二叉树的头节点head，已知所有节点的值都不一样，返回其中最大的且符合搜索二叉树条件的最大拓扑结构的大小。 例如，二叉树如图 3-19 所示。 其中最大的且符合搜索二叉树条件的拓扑结构如图3-20 所示。 这个拓扑结构节点
左神算法：遍历二叉树的神级方法（Morris遍历 / 线索二叉树）
本题来自左神《程序员代码面试指南》“遍历二叉树的神级方法”题目。 题目 给定一棵二叉树的头节点 head，完成二叉树的先序、中序和后序遍历。如果二叉树的节点数为N，则要求时间复杂度为O(N)，额外空间复杂度为O(1)。 题解 之前的题目已经剖析过如何用递归和非递归的方法实现遍历二叉树，但是很不幸，之前所有的方法虽然常用，但都无法做到额外空间复杂度为O(1)。这是因为遍历二叉树的递归方
左神算法：二叉树的序列化和反序列化（Java版）
本题来自左神《程序员代码面试指南》“二叉树的序列化和反序列化”题目。 题目 二叉树被记录成文件的过程叫作二叉树的序列化，通过文件内容重建原来二叉树的过程叫作二叉树的反序列化。给定一棵二叉树的头节点head，已知二叉树节点值的类型为32 位整型。请设计一种二叉树序列化和反序列化的方案，并用代码实现。 题解 本文提供两套序列化和反序列化的实现，供读者参考。 方法一：通过先序遍历实现序列
左神算法：如何较为直观地打印二叉树（Java版）
本题来自左神《程序员代码面试指南》“如何较为直观地打印二叉树”题目。 题目 二叉树可以用常规的三种遍历结果来描述其结构，但是不够直观，尤其是二叉树中有重复值的时候，仅通过三种遍历的结果来构造二叉树的真实结构更是难上加难，有时则根本不可能。 给定一棵二叉树的头节点head，已知二叉树节点值的类型为32 位整型，请实现一个打印二叉树的函数，可以直观地展示树的形状，也便于画出真实的结构。
左神算法：加强堆的实现（Java）
为什么要有加强堆？ Java中的PriorityQueue（优先级队列）就是系统提供的堆实现，那么为什么还要手动去实现？ 假如现在你手里有一个堆，里面存着一些元素，用户此时说要改变元素的排序指标且要求高效，怎么办？用系统实现的堆，你是不是只能把堆中的元素拿出来再重新去调整。 此时你的用户又想删除堆中的某一个元素，你要怎么删除指定元素又能保证堆结构呢？系统提供的堆是不是无能为力，或者说系统提供
左神算法基础class3—题目13复制含有随机指针节点的链表
左神算法基础class3—题目13复制含有随机指针节点的链表 1.题目:复制含有随机指针节点的链表2.分析3.核心代码（1）生成题设链表（2）加入新节点（3）复制新节点的值及rand指针（4）分离拷贝的部分 4.完整代码 1.题目:复制含有随机指针节点的链表 【题目】 一种特殊的链表节点类描述如下： public class Node { public int value; pu
左神算法基础class3—题目12单向链表按某值划分成左边小、中间相等、右边大的形式
左神算法基础class3—题目12单向链表按某值划分成左边小、中间相等、右边大的形式 普通版：单向链表按某值划分成左边小、中间相等、右边大的形式（不用考虑稳定性且额外空间复杂度为O(n)）1.分析2.核心代码（1）链表的生成及添加元素（2）把链表放入数组中（3）荷兰国旗排序（4）把数组放回链表中 3.完整代码4.输出结果 进阶版：单向链表按某值划分成左边小、中间相等、右边大的形式（考虑稳定性
左神算法基础class3—题目11判断一个链表是否为回文结构（不同额外空间复杂度的三种方法）
左神算法基础class3—题目11三种方法判断一个链表是否为回文结构 题目：判断一个链表是否为回文结构方法一：利用堆栈结构(额外空间复杂度O(n))（1）分析（2）核心代码①头节点初始化②初始化链表数据③比较栈和链表是否相同 （3）完整代码 方法二：利用快慢指针和堆栈结构（额外空间复杂度O(n/2)）（1）分析（2）核心代码快慢指针 （3）完整代码 方法三：利用快慢指针和逆序一半链表（额外空
左神算法基础class3—题目10打印两个有序链表的公共部分
左神算法基础class3—题目10打印两个有序链表的公共部分 1.题目2.分析3.核心代码(1)链表的建立(2)外排过程 4.完整代码5.输出结果 1.题目 【题目】 给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。 2.分析 打印链表的公共部分类似外排方式（外排不了解的请点击查看算法流程3），原理如下：设置两个指针分别指向链表1和链表2的第一个数，比
左神算法基础class3—题目9在行列都排好序的矩阵中找数
左神算法基础class3—题目9在行列都排好序的矩阵中找数 1.题目2.分析3.核心代码4.完整代码5.输出结果 1.题目 【题目】 给定一个有M*N的整型矩阵matrix和一个整数num，matrix的每一行和每一 列都是排好序的。实现一个函数，判断K是否在matrix中。 例如：{{1,3,5,6},{2,5,7,9},{4,6,8,10}} 如果num为7，返回true；如
左神算法基础class3—题目7反转单向和双向链表
左神算法基础class3—题目7反转单向和双向链表 题目1：反转单向链表1.分析2.核心代码3.完整代码4.输出结果 题目2：反转双向链表1.分析2.核心代码3.完整代码4.输出结果 题目1：反转单向链表 【要求】 如果链表长度为N，时间复杂度要求为O(N)，额外空间 复杂度要求为O(1) 1.分析 反转单向链表可以使用迭代法，需要三个指针分别记录前一个节点，当前节点和后一
左神算法基础class3—题目8之字形打印矩阵c++实现
左神算法基础class3—题目8之字形打印矩阵c++实现 1.题目2.分析3.核心代码（1）A、B点的更新（2）打印A、B之间的数字 4.完整代码5.输出结果 1.题目 给定一个矩阵matrix，按照“之”字形的方式打印这个矩阵，例如：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16。“之”字形打印的结果为：1 2 5 9 6 3 4 7 10 13
左神算法基础class3—题目6旋转正方形矩阵
左神算法基础class3—题目6旋转正方形矩阵 1.题目2.分析3.核心代码4.完整代码5.输出结果 1.题目 【题目】 给定一个整型正方形矩阵matrix，请把该矩阵调整成 顺时针旋转90度的样子。 【要求】 额外空间复杂度为O(1)，不使用辅助数组。 2.分析 分析：题目给定的是正方形矩阵，考虑把矩阵看成回字形结构，由外到内按层进行旋转，先外层后内层。与题目5思路相同
左神算法基础class3—题目5转圈打印矩阵
左神算法基础class3—题目5转圈打印矩阵 1.题目2.分析3.核心代码4.完整代码5.输出结果 1.题目 给定一个整型矩阵matrix，请按照转圈的方式打印它。 例如： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 打印结果为：1，2，3，4，8，12，16，15，14，13，9，5，6，7，11， 10 【要求】 额外空间复杂度为O(1)。
左神算法基础class3-2—题目3仅用栈结构实现队列结构
左神算法基础class3-2—题目3仅用栈结构实现队列结构 1.题目2.分析3.核心代码4.完整代码5.输出结果 1.题目 如何仅用栈结构实现队列结构？ 2.分析 栈本身是先进后出的结构，要想实现先进先出队列的作用就需要两个栈，把一个栈先倒到另一个栈内再pop出来。 （1）设计两个栈，一个命名为push、一个为pop。把数据输入push栈，把从pop栈输出的数据作为队列的输出
左神算法笔记（十八）——平衡搜索二叉树
搜索二叉树 搜索二叉树：对于搜索二叉树的任何一个节点，左子树的值都比节点小，右子树的值都比他大。 TreeMap中，跟HashMap中一样可以提供key-value，同时会将key按照大小顺序排列。中间采用的就是搜索二叉树的知识。 具备平衡性的搜索二叉树： AVL树——平衡性最严格 任何一个节点的左子树和右子树高度差不大于1，复杂度还是O(logN)。导致调整非常频繁。 红黑树——平衡性
算法笔记——左神进阶（4）平衡搜索二叉树、累加和为定值最长子数组
搜索二叉树 搜索二叉树：对于搜索二叉树的任何一个节点，左子树的值都比节点小，右子树的值都比他大。 TreeMap中，跟HashMap中一样可以提供key-value，同时会将key按照大小顺序排列。中间采用的就是搜索二叉树的知识。 具备平衡性的搜索二叉树： AVL树——平衡性最严格 任何一个节点的左子树和右子树高度差不大于1，复杂度还是O(logN)。导致调整非常频繁。 红黑树——平衡性
左神算法：遍历二叉树的神级方法（Morris遍历 / 线索二叉树）
本题来自左神《程序员代码面试指南》“遍历二叉树的神级方法”题目。 题目 给定一棵二叉树的头节点 head，完成二叉树的先序、中序和后序遍历。如果二叉树的节点数为N，则要求时间复杂度为O(N)，额外空间复杂度为O(1)。 题解 之前的题目已经剖析过如何用递归和非递归的方法实现遍历二叉树，但是很不幸，之前所有的方法虽然常用，但都无法做到额外空间复杂度为O(1)。这是因为遍历二叉树的递归方
左神算法题系列：动态规划机器人走路
机器人走路 假设有排成一行的N个位置记为1~N，N一定大于或等于2 开始时机器人在其中的start位置上(start一定是1~N中的一个) 如果机器人来到1位置，那么下一步只能往右来到2位置； 如果机器人来到N位置，那么下一步只能往左来到N-1位置； 如果机器人来到中间位置，那么下一步可以往左走或者往右走； 规定机器人必须走K步，最终能来到aim位置(P也是1~N中的一个)的方法有多少种 给定四