单调栈
单调栈学习和使用
前言:今天来讲一下单调栈,它定义是非常简单的,首先栈是一种先进后出、后进先出的数据结构。而单调栈,就是说栈中的元素是严格单调递增或者递减的。它主要用来解决的问题:找到前一个或者后一个的最大或者最小元素。属于一种空间换时间的思想,通常用来把O(n^2)的时间复杂度降低到O(n)。
典型的做法:
假设我们是要找比当前元素大的元素,那么栈内的元素就是递增的(从栈顶往栈底方向)。
当元素大于栈顶的元素,就把栈顶的元素给替换成当前元素;
当元素小于等于栈顶元素,就直接入栈。
这样处理后,栈内就一直保持着一个从栈顶往栈底方向递增的单调栈。
注意:一般栈内储存的都是元素的下标而不是元素的值,因为下标可以直接找到值,而值不能直接找到下标。
所以如果是计算两个元素之间的距离的题目,储存值就没法算了。
因此单调栈里面说的单调性指的是下标对应的元素值单调的。
实例:LeetCode:739-每日温度123456789101112131415161718给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下 ...
并查集介绍和常用模板
并查集介绍和常用模板
前言:并查集(Union-find set 也叫Disjoint Sets)是图论里面一种用来判断节点之间是否连通的数据结构,学会使用它可以处理一些跟节点连通性的问题。它有两个很重要的方法:
Find(x):查找x的父元素
Union(x,y):将x,y两个对应的集合合并到一起
接下来我们先看一个例子,看看怎么判断节点之间是否相连,怎么把两个集合合并到一起:
先看第一个问题,怎么判断两个节点是否相连?
在上面这张图里面我们肉眼可以看到(0,1,2)是连在一起,(3,4)是连在一起,(5)是单独存在的,这也是前置客观存在的条件。
那么我们怎么判断0和3是不是连到一起了呢?思路是这样,我们把这三块看成是三个团队,(0,1,2)是一个团队,队长是0,(3,4)是一个团队,队长是3,(5)是一个团队,队长是5。判断逻辑是,两个元素的队长是相同的,就认为在一个团队里面。所以更加计算机化的语言描述是,三个集合,每个集合都有一个根节点,如果根节点是相同的,就是在一个集合里面。因此你要想到,我们需要存储每个节点对应的根节点,这样才能判断出两个节点是否在同一个集合内。
再 ...
leetcode-7022限制条件下元素之间的最小绝对差
leetcode-7022
这道题是358周赛的第三题,当时没做出来,后来弄明白了,记录一下。
#题目
限制条件下元素之间的最小绝对差
给你一个下标从 0 开始的整数数组 nums 和一个整数 x 。
请你找到数组中下标距离至少为 x 的两个元素的 差值绝对值 的 最小值 。
换言之,请你找到两个下标 i 和 j ,满足 abs(i - j) >= x 且 abs(nums[i] - nums[j]) 的值最小。
请你返回一个整数,表示下标距离至少为 x 的两个元素之间的差值绝对值的 最小值 。
示例 1:
12345输入:nums = [4,3,2,4], x = 2输出:0解释:我们选择 nums[0] = 4 和 nums[3] = 4 。它们下标距离满足至少为 2 ,差值绝对值为最小值 0 。0 是最优解。
示例 2:
12345输入:nums = [5,3,2,10,15], x = 1输出:1解释:我们选择 nums[1] = 3 和 nums[2] = 2 。它们下标距离满足至少为 1 ,差值绝对值为最小值 1 。1 是最优解。
示例 3:
12345输入:nu ...
leetcode53_最大子序和
leetcode53 最大子序和给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
进阶:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。
题解:
解法一:动态规划首先读完题目我们知道数组最少是一个元素,那么此时它的最大和就是这个元素,不管它是正负整数还是零.那么当变成两个元素的时候呢,我们分析一下:1.如果第二个元素是正整数,那一定会让最大和变大2.如果第二个元素是零的话,对最大和其实没有影响3.如果第二个元素是负数的话,那么最大和就是第一个元素和第二个元素中最大的那个负数,令dp[i]是数组nums的最大和推广到i个数的话1.如果dp[i - 1]是正数或或者0就加上去2.如果dp[i -1]是负数的话,就不加入,选第nums[i]为最大和然后我们根据这个条件列出状态转移方程,这里把零放入到第一种情况中,令dp[i]是数组nums的最大和$$dp[i]\begin{case ...
leetcode62_UniquePaths
leetcode62 Unique Paths一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
问总共有多少条不同的路径?
例如,上图是一个7 x 3 的网格。有多少可能的路径?
说明:m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2输出: 3解释:从左上角开始,总共有 3 条路径可以到达右下角。
向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右示例 2:
输入: m = 7, n = 3输出: 28
题解:这道题使用动态规划是比较好解决的,我们可以先设dp[m,n]为m,n的不同路径结果.我们根据题目分析后得出dp[1,1]是1dp[1,2]也是1dp[2,1]也是1
dp[2,2]往右边走的话其实就是dp[1,2],往下面走的话就是dp[2,1],所以dp[2,2] = dp[1,2] ...
leetcode6_Z-字形变换
leetcode-6 Z 字形变换
题目:将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时,排列如下:
L C I RE T O E S I I GE D H N之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:”LCIRETOESIIGEDHN”。
请你实现这个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);示例 1:
输入: s = “LEETCODEISHIRING”, numRows = 3输出: “LCIRETOESIIGEDHN”示例 2:
输入: s = “LEETCODEISHIRING”, numRows = 4输出: “LDREOEIIECIHNTSG”解释:
L D RE O E I IE C I H NT S G
思路:思路一: 一开始最初的想法就是构造一个二维数据然后按照题目的顺序 ...
刷题发现的一些编码技巧
刷题发现的一些编码技巧:
1.判断是否为偶数,奇数
不要再用 n % 2 == 0 是偶数, n % 2 != 0是奇数了。位运算可以更快,也更加优雅,
n & 1 == 1 就是奇数 n & 1 == 0 是偶数
2.char数组里面的元素替换成它的前一个字符
之前我都是这么写的:arr[j] = (char) (arr[j] - 1);
看见别人写的题解之后才发现可以这么写:arr[j]–
代码优雅很多,也更加简洁
大白话btree和b+tree
btree,b+tree都是些啥?作为一直后端程序猿,经常会看到好几个关于树的概念,平衡二叉树,二叉搜索树,avl树,btree,b+tree等等。没有弄清楚的时候,放到一起很容易弄混。今天咱们就来捣鼓捣鼓这几个名词,理解一下它们都是啥。本文会从二叉树由浅入深介绍到b+tree,,对于不同的树的插入删除先不谈,主要用于帮助不清楚概念的童鞋理解这些名词代表的什么样的数据结构,暂不涉及红黑树(这玩意要写起来篇幅有点长,下次可以单独出一篇)。
树:首先咱们来看看最基本的定义,之后讲的所有种类的树都是属于树这个大类里面:树(tree)是包含n(n>=0)个结点的有穷集,其中:(1)每个元素称为结点(node);(2)有一个特定的结点被称为根结点或树根(root)。(3)除根结点之外的其余数据元素被分为m(m≥0)个互不相交的集合T1,T2,……Tm-1,其中每一个集合Ti(1<=i<=m)本身也是一棵树,被称作原树的子树(subtree)。
然后一些树的基本概念(默认大家都学过了,不过照顾一下真没看过的列了几个简单的概念在下面,不会的请百度了解下 ...
布隆过滤器
最近做爬虫项目过滤重复的url的时候,了解到一个东西,叫布隆过滤器,然后也学习了一下,写下这篇博客记录一下.下面我们将分为几个专题来介绍布隆过滤器:1.什么是布隆过滤器;2.布隆过滤器的使用场景和缺陷;3.布隆过滤器java实现;4.guava中使用布隆过滤器;5.布隆过滤器的变体
1.什么是布隆过滤器? 首先我们得知道布隆过滤器的概念是什么,采自wiki百科:布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。tips:看完这个我们可以知道是一个叫布隆的人提出的一个用来检索一个元素是否在一个集合中的算法,效率高,性能好。
1.1 图解布隆过滤器很长的二进制向量(这里可以理解为很长的bit数组)一系列的随机映射函数(hash函数)
如图所示,将一个 ...
ScheduledExecutorService线程池挂掉的问题
导语:最近遇到一个问题,有个周期给业务方推送信息的功能,突然就没推送了。日志里面也没有查询到报错的信息,然后检查代码发现原来写这个推送功能用的是ScheduledExecutorService,再设定好执行时间,就会周期性去用ScheduledExecutorService的子线程来执行任务。
问题排查:问题的原因最后发现是某些配置修改了,导致运行推送任务的子线程在执行的时候回抛出异常,但是这个线程池是不打印子线程的异常信息的,所以日志里面根本看不到报错的信息。
测试例子:写一个简单方法,直接子线程就抛出异常,看看会不会打印堆栈信息:
1234567891011121314151617@Slf4jpublic class ScheduledExecutorServiceTest { public static Integer count = 0; public static void main(String[] args) { ScheduledExecutorService executorService = Executors.newS ...