- 博客(55)
- 收藏
- 关注
RSS订阅
3原创 动态开点线段树
对于在线数据且数据量大，无法离散化，则无法实现构造线段树。那么此时可以动态开点线段树，即在modify和qurey时来创建节点。事先只需要构建一个根节点即可。此外一个节点的左右子节点无法根据u≪1u\ll1u≪1以及u≪1∣1u\ll1|1u≪1∣1，所以在定义节点时需要定义节点的左右子节点。其余的pushup，pushdown，modify以及query都与传统线段树类似。例题732. 我的日程安排表 III当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k
2022-05-20 16:27:25
502
原创 秒杀活动开发
活动模型创建PromoModelpackage com.miaoshaproject.service.model;import org.joda.time.DateTime;import java.math.BigDecimal;public class PromoModel { private Integer id; // 秒杀活动状态 1表示还未凯斯 2表示进行中 3表示已结束 private Integer status; // 秒杀活动名称
2022-05-07 15:47:18
168
原创 交易模块开发
创建交易领域模型OrderModelpackage com.miaoshaproject.service.model;import java.math.BigDecimal;// 用户下单的交易模型public class OrderModel { // 交易号 2022050500128 private String id; // 购买的用户id private Integer userId; // 购买的商品id private Integ
2022-05-07 15:28:05
298
原创 商品模块开发
领域模型ItemModelpackage com.miaoshaproject.service.model;import org.hibernate.validator.constraints.NotBlank;import javax.validation.constraints.Min;import javax.validation.constraints.NotNull;import java.math.BigDecimal;public class ItemModel {
2022-05-07 15:07:07
635
原创 用户模块开发
核心领域模型：UserModelpackage com.miaoshaproject.service.model;import org.hibernate.validator.constraints.NotBlank;import javax.validation.constraints.Max;import javax.validation.constraints.Min;import javax.validation.constraints.NotNull;public class
2022-05-07 14:45:14
564
原创 简单秒杀项目简介
通过使用SpringBoot快速搭建前后端分离的电商基础秒杀项目。项目中会通过应用领域驱动型的分层模型设计方式去完成用户otp注册、登陆、查看、商品列表、进入商品详情以及倒计时秒杀开始后下单购买的基本流程。电商秒杀项目简介：1、商品列表页获取秒杀商品列表2、进入商品详情页获取秒杀商品详情3、秒杀开始后进入下单确认页下单并支付成功使用SpringBoot完成基础项目搭建使用IDEA+Maven搭建SpringBoot开发环境。引入依赖pom.xml(后续项目所需的所有依赖)包括springb
2022-05-06 23:18:28
795
原创 拓扑排序判断有向图中是否有环
拓扑排序的工程意义拓扑排序是对一个有向图构造拓扑序列，解决工程是否能顺利进行的问题。构造时有222种结果：此图全部顶点被输出：说明说明图中无「环」存在， 是 AOV 网（有向无环图）没有输出全部顶点：说明图中有「环」存在，不是 AOV 网主要思想遍历所有入度为000的节点，并由该节点刷新其指向节点的度，即将其指向节点的入度减111，当该节点入度为000，将其加入队列。最后查看所有节点的入度是否为000，如果全部为000，说明该网络是有向无环图。例题LeetCode.207 课程表你这个学
2022-02-24 14:25:39
3357
原创 桶排序+抽屉原理
桶排序桶排序定义 桶排序是一种基于分治思想、效率很高的排序算法，理想情况下对应的时间复杂度为O(n)O(n)O(n)。桶排序算法的实现思路是：将待排序序列中的元素根据规则分组，每一组采用快排、插入排序等算法进行排序，然后再按照次序将所有元素合并，就可以得到一个有序序列。 为了使桶排序更加高效，我们需要做到这两点：在额外空间充足的情况下，尽量增大桶的数量使用的映射函数能够将输入的NNN个数据均匀的分配到KKK个桶中桶排序时间复杂度分析 1. 什么时候最快：当输入的数据可以均
2022-02-23 23:04:57
386
原创 二叉树中的递归问题
二叉树中的递归问题二叉树中的递归问题有时可以转化为树形DP问题LeetCode124. 二叉树中的最大路径和 路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次 。该路径至少包含一个节点，且不一定经过根节点。路径和是路径中各节点值的总和。 给你一个二叉树的根节点 root ，返回其最大路径和 。思路 树形DP：对于某个节点vvv，以该节点作为最近邻公共祖先时，通过该节点的最大路径和为：v.val+f(v.lef
2022-02-18 23:41:27
149
原创 股票买卖问题
股票买卖问题主要分成以下四个逐步进阶的版本最多进行一次交易可以进行无数次交易最多进行两次交易最多进行kkk次交易最多进行一次交易LeetCode121. 买卖股票的最佳时机 给定一个数组 pricespricesprices，它的第iii个元素prices[i]prices[i]prices[i]表示一支给定股票第iii天的价格。 你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中
2022-02-18 22:59:17
245
原创 树状数组+离散化
树状数组+离散化树状数组的优点树状数组的实现例题LeetCode327. 区间和的个数树状数组的优点快速修改某个数O(logn)O(logn)O(logn)快速求前缀和O(logn)O(logn)O(logn)对比原数组：修改某个数O(1)O(1)O(1)求前缀和O(n)O(n)O(n)对比前缀和数组修改某个数O(n)O(n)O(n)求前缀和O(1)O(1)O(1)树状数组的实现原理看博客：主要就是使用二进制思想，将原数组分成块状，进而对其进行修改和求和主要两个操作：
2022-02-10 17:28:14
684
原创 KMP中的最小循环节
首先对next数组的理解：表示模块串的以第个字符结尾的子串中，前缀和后缀相同的最长字符串长度为。那么可以得出模块串的最小循环节长度为。证明如下：模板题：LeetCode459.重复的子字符串给定一个非空的字符串 ，检查是否可以通过由它的一个子串重复多次构成。思路：根据以上分析，若字符串可被多个子串重复构成，那么不为0，且。综上代码如下：class Solution { public boolean repeatedSubstringPattern(String s) {
2022-02-09 15:56:37
398
原创 算法经典题：串联所有单词的子串
LeetCode30.串联所有单词的子串给定一个字符串和一些 长度相同 的单词 。找出中恰好可以由中所有单词串联形成的子串的起始位置。注意子串要与中的单词完全匹配，中间不能有其他字符 ，但不需要考虑中单词串联的顺序。提示： s 由小写英文字母组成 words[i]由小写英文字母组成思路：定义。因为各个单词长度相同，所以可以根据单词长度将划分成个候选序列。例如：，，那么可以将其分成的候选序列为，每次只在候选序列中寻找答案。同时考虑的话，需要用到滑动串口，记录各个单词出现的次数..
2022-01-16 14:54:09
256
原创 算法经典题：查找和最小的 K 对数字
LeetCode373.查找和最少的K对数字给定两个以 升序排列 的整数数组和, 以及一个整数。定义一对值，其中第一个元素来自，第二个元素来自。请找到和最小的个数对。提示: 和均为升序排列 思路：设，。那么总共可以组成对数。因为两个数组有序。所以以下各个数对的和也是有序的。所以可以使用优先队列（小根堆）存每行的第一个数对和，每次弹出队首元素必然就是当前最小值，并将该行的下一个数对和存入优先队列即可。Java代码如下：class Solution {
2022-01-14 14:41:44
308
原创 算法经典题：二叉树中节点之和最大的路径
题目：剑指OfferⅡ051. 节点之和最大的路径路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。提示：树中节点数目范围是 思路：对于每个节点，求出左子树中从根节点出发的最大路径和left，右子树中从根节点出发的最大路径和right，然后以该.
2022-01-12 15:13:00
965
原创 记忆化搜索
递归的过程中，很多的结果都是被重复计算的，这样大大降低了算法的运行效果。记忆化搜索是在递归的过程中，将已经计算的结果保存下来，当之和的运算用到时直接取出结果，避免重复运算，所以大大提高了算法的执行效率。（以空间换时间）题目：AcWing901.滑雪给定一个行列的矩阵，表示一个矩形网格滑雪场。矩阵中第行第列的点表示滑雪场的第行第列区域的高度。一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前
2022-01-05 17:26:35
254
原创 算法经典题：1~n整数中1出现的次数
剑指Offer 43. 1~n整数中1出现的次数输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。限制：1 <= n <2^31思路：对每一次分别考虑：例如对abcdef这个数的c位进行考虑。首先取该位为1，那么ab可以取，def可以取，所以，然后对c进行分类讨论时，当ab取ab时，该位取不到1，所以此时解为0 时，当ab取ab时，该位取1，那么def只能取，所...
2021-12-26 14:46:19
247
原创 算法经典题：二叉搜索树和完全二叉树判断
二叉搜索树的中序遍历是有序的；完全二叉树：一棵深度为k的有n个结点的 二叉树 ，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与 满二叉树 中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。如何判断二叉搜索树：对二叉树进行中序遍历，如果前后两节点的值都满足：前一个节点的值小于后一个节点的值，那么该二叉树是二叉搜索树如何判断完全二叉树：对二叉树进行层序遍历一个节点如果存在右子节点，但是不存在左子节点，那么该二叉树必然不是完全二叉树 当确定叶子
2021-12-17 15:20:26
183
原创 算法经典题：链表内指定区间反转
NC21链表内指定区间反转描述将一个节点数为size的链表m位置到n位置之间的区间反转，要求时间复杂度，空间复杂度。例如：给出的链表为1→2→3→4→5→NULL,m=2,n=4,返回1→4→3→2→5→NULL.数据范围：链表长度0<size≤1000，0<m≤n≤size，链表中每个节点的值满足0≤∣val∣≤1000要求：时间复杂度，空间复杂度进阶：时间复杂度，空间复杂度 思路：使用虚拟节点指向头节点，循环找到需要反转的子链表的头尾节点的前一个位置。将之...
2021-12-16 21:10:35
922
原创 算法经典题：快慢指针+反转链表判断回文链表
剑指Offer II027.回文链表给定一个链表的头节点head，请判断其是否为回文链表。如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。提示：链表 L 的长度范围为[1, 105] 0<= node.val <= 9思路：首先使用快慢指针找到链表的中间节点，需要注意链表的长度是奇数还是偶数。然后将后半个链表进行反转。反转后，分别遍历前半部分和后半部分，判断每个节点的值是否相同。/** * Definition for singly-...
2021-12-16 19:40:49
884
原创 算法经典题：约瑟夫环
剑指offer62. 圆圈中最后剩下的数字0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。限制：1 <= n <= 10^5 1 <= m <= 10^6思路：用f(n,m)表示，每次删除第m个数字所剩下的那个数..
2021-12-15 21:23:18
578
原创 算法经典题：数组中的逆序对
剑指offer51. 数组中的逆序对在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。数据范围：0数组长度50000思路：借助归并排序。归并排序中有一步是比较前后两部分已排好序子数组的大小来合并这两个子数组。在每次前半部分的某个数大于后半部分的某个数时，那么前半部分该数后面的数都大于后半部分这个数，这些数与后半部分这个数都能组成一个逆序对。所以逆序对数量+mid-j+1。Java代码如下：class Soluti
2021-12-13 22:18:52
137
原创 算法经典题：判断是不是平衡二叉树
NC62判断是不是平衡二叉树输入一棵节点数为的二叉树，判断该二叉树是否是平衡二叉树。在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。注：空树是平衡二叉树数据范围：,树上节点的val值满足要求：空间复杂度，时间复杂度思路：首先使用DFS求出树的高度。然后使用该方法判断节点的两个子树的高度差是否小于等于1。...
2021-12-13 17:18:45
314
原创 算法经典题：两个链表生成相加链表
NC40两个链表生成相加链表假设链表中每一个节点的值都在 0 - 9之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表。数据范围：，链表任意值要求：空间复杂度，时间复杂度例如：链表 1为 9->3->7，链表 2为 6->3，最后生成新的结果链表为 1->0->0->0。思路：首先需要将各位对齐，即个位对齐个位，十位对齐十位...此时需要反转链表。链表反转后，对各位相加，需要一个进位标识符carry记录...
2021-12-12 14:20:02
99
原创 算法经典题：下一个序列
LeetCode31.下一个序列实现获取“下一个排列”的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须 原地 修改，只允许使用额外常数空间。提示：1 <= nums.length <= 100 0 <= nums[i] <= 100思路：首先从尾到头找到第一个下降的位置k，即该位置满足nums[k]>nums[k-1]，所有k之后的
2021-12-11 21:12:28
226
原创 算法经典题：Flood Fill算法
NC109岛屿数量描述给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。例如： 输入 [[1,1,0,0,0], [0,1,0,1,1], [0,0,0,1,1], [0,0,0,0,0], [0,0,1,1,1]] 对应的输出为3数据范围：01矩阵范围<=200*200思路：使用Flood Fill算法。遍历每个位置，当该位置为...
2021-12-11 15:05:49
281
原创 TreeMap按value排序
NC97字符串出现次数的TopK问题给定一个字符串数组，再给定整数，请返回出现次数前名的字符串和对应的次数。返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的ASCII值的大小关系。比如"ah1x"小于"ahb"，"231"<”32“。字符仅包含数字和字母。数据范围：字符串数满足，每个字符串长度，要求：空间复杂度，时间复杂度思路：将字符串数组存入TreeMap。...
2021-12-09 16:22:55
3405
原创 算法经典题：判断链表中是否有环以及环的入口位置
NC4判断链表中是否有环判断给定的链表中是否有环。如果有环则返回true，否则返回false。数据范围：链表长度，链表中任意节点的值满足要求：空间复杂度，时间复杂度思路1：哈希表（时空复杂度都是）:遍历链表，把每个节点存入哈希表，当出现重复的节点时，说明有环import java.util.*;/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode n.
2021-12-08 14:04:34
248
原创 算法经典题：LRU缓存机制
LeetCode146. LRU缓存机制运用你所掌握的数据结构，设计和实现一个LRU(最近最少使用) 缓存机制 。实现LRUCache类：LRUCache(int capacity) 以正整数作为容量capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达..
2021-12-06 22:30:28
312
转载 Linux学习记录
目录基础知识目录基本指令tmux+vimtmuxvim基础知识目录绝对路径:从根目录(/)开始描述相对路径:从当前位置开始描述的路径. 当前目录.. 上一级目录~/ 家目录基本指令ctrl c取消命令,并且换行ctrl u 清空本行命令tab 补全命令,如果补全不了,按两下,给出提示↑ 给出之前输入的命令ls 展出列...
2021-11-30 21:51:59
1148
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人