笔记1 用两个栈实现队列 1、进栈时候进入第一个栈内 2、出栈时将栈1的内容再次压入栈2中，即正向 3、如果栈2没有元素，弹栈需要栈1进栈 4、如果栈2有元素，即上一次进栈元素没有全部弹栈，直接弹栈 packageesay.jz9用两个栈实现队列;​importjava.util.Stack;​publicclassSolution{  Stack<Integer>stack1=newStack<Integer>();  Stack<Integer>stack2=newStack<Integer>();&n...

数字在升序数组中出现的次数 描述 给定一个长度为n的非降序数组和一个非负数整数k，要求统计k在数组中出现的次数 解析 排序数组的查找问题首先考虑二分法 使用二分法找到左右边界的位置，然后长度一减即可 解题思路： 排序数组的查找问题首先考虑使用二分法解决，其可将遍历法的线性级别时间复杂度降低至对数级别 算法流程： 1、初始化：声明i,j双指针分别指向array数组左右两端 2、循环二分：设m=(i+j)/2为每次二分的中点（"/"代表向下取整除法，因此恒有i≤m1、当array[m]>array[j]时：m一定在左排序数组中，即旋转点x一定在[m+1,j]闭区间内，因此执行i=m+1 ...

RabbitMQ 整合RabbitMQ / 使用RabbitMQ 1、引入ampq场景，RabbitAutoConfiguration就会自动生效 2、给容器中自动配置了 RabbitTemplate、AmqpAdmin、CachingConnectionFactory、RabbitMessagingTemplate 所有的属性都是在 @EnableConfigurationProperties(RabbitProperties.class) @ConfigurationProperties(prefix="spring.rabbitmq") publicclassRabbitProperti...

JZ55二叉树的深度 描述 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度，根节点的深度视为1。 方法1递归 思路： 最大深度是所有叶子节点的深度的最大值，深度是指树的根节点到任一叶子节点路径上节点的数量，因此从根节点每次往下一层深度就会加1。因此二叉树的深度就等于根节点这个1层加上左子树和右子树深度的最大值。而每个子树我们都可以看成一个根节点，继续用上述方法求的深度，于是我们可以对这个问题划为子问题，利用递归来解决： 终止条件：当进入叶子节点后，再进入子节点，即为空，没有深度可言，返回0. 返回值：每一级按照上述公式，返...

JZ61扑克牌顺子 描述 现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。 有如下规则： 1.A为1，J为11，Q为12，K为13，A不能视为14 2.大、小王为0，0可以看作任意牌 3.如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。 4.数据保证每组5个数字，每组最多含有4个零，数组的数取值为[0,13] 具体做法： 将nums数组依次装入set集合，遇到0则返回装下一个元素，出现重复元素则返回false，并在其中记录max，min，最终max-min>=5的都不是顺子； 代码 packageesay.JZ61扑克牌...

定时任务 文档 1.实现方案 1、Timer 2、线程池 3、mq的延时队列 4、QUARTZ 1.搭配cron表达式使用 2.支持年，spring不支持年 3.在周几的位置，quartz的周1是2，spring的周1是1 4. spring框架的定时任务 springboot默认定时任务框架不是QUARTZ，如果需要使用引入即可 2.cron表达式 1.语法 语法：秒分时日月周年（spring不支持年，所以可以不写） http://www.quartz-scheduler.org/documentation/quartz-2.3.0/tutorials/crontrigger...

买卖股票的最好时机(一) 描述 假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益 1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天 2.如果不能获取到任何利润，请返回0 3.假设买入卖出均无手续费 解法一：暴力(常规大循环解决) 思路步骤： 最显而易见的解法，当然可能并不是最优的解法 声明变量ans=0存放最终答案 两层for循环，分别找到数组中最大的差值，表示利润最大化 比较并更新ans的值 返回ans即为答案 代码 intans=...

JZ65不用加减乘除做加法 描述 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、、/四则运算符号。 数据范围：两个数都满足-10\len\le1000−10≤n≤1000 进阶：空间复杂度O(1)O(1)，时间复杂度O(1)O(1) 方法一：位运算非递归（推荐使用） 思路： 由于题目禁止我们使用+，-，，/运算符，我们需要通过位运算来实现加法。我们需要通过循环迭代两个变量实现，一个变量指代进位，一个变量指代非进位。 位运算中两数进行异或运算可以提供两数加和后二进制非进位信息，位运算中的两数进行与运算的结果可以提供两数加和后的二进制进位信息。因此我们将两数与运算的结果进行循环左...

JZ66构建乘积数组 描述 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]（除A[i]以外的全部元素的的乘积）。程序中不能使用除法。（注意：规定B[0]=A[1]A[2]...A[n-1]，B[n-1]=A[0]A[1]...A[n-2]） 对于A长度为1的情况，B无意义，故而无法构建，用例中不包括这种情况。 方法1 思路 矩阵中由对角线1将其分成了上三角和下三角。我们先看下三角，如果我们累乘的时候，B[1]是在B[0]的基础上乘了新增的一个A[0]，B[2]是在B[...

JZ68二叉搜索树的最近公共祖先 描述 给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。 1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先. 2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值 3.所有节点的值都是唯一的。 4.p、q为不同节点且均存在于给定的二叉搜索树中。 数据范围: 3<=节点总数<=10000 0<=节点值<=10...

JZ69跳台阶 描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 数据范围：1\leqn\leq401≤n≤40 要求：时间复杂度：O(n)O(n)，空间复杂度：O(1)O(1) 方法1递归 思路 题目分析，假设f[i]表示在第i个台阶上可能的方法数。 逆向思维。如果我从第n个台阶进行下台阶，下一步有2中可能，一种走到第n-1个台阶，一种是走到第n-2个台阶。 所以f[n]=f[n-1]+f[n-2]，那么初始条件了，f[0]=f[1]=1。 所以就变成了：f[n]=f[n-1]+f[n-2],初始值f[0]=1,...

JZ71跳台阶扩展问题 描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。 数据范围：1\len\le201≤n≤20 进阶：空间复杂度O(1)O(1)，时间复杂度O(1)O(1) 方法1动态规划 思路： 对于最后一级台阶，我们可以由倒数第二级台阶跳1步，也可以由倒数第三级太极跳两步，即f(n)=f(n−1)+f(n−2)+...+f(n−(n−1))+f(n−n)=f(0)+f(1)+f(2)+...+f(n−1)f(n)=f(n-1)+f(n-2)+...+f(n-(n-1))+f(n-n)=f(0)+f(...

JZ73翻转单词序列 描述 牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder.aamI”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“Iamanowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？ 数据范围：1\len\le100\1≤n≤100 进阶：空间复杂度O(n)\O(n)，时间复杂度O(n)\O(n)，保证没有只包含空格的字符串 思路 1.将字符串按照空格进行分割，返回一个数组 2.对数组进行反...

JZ79判断是不是平衡二叉树 描述 输入一棵节点数为n二叉树，判断该二叉树是否是平衡二叉树。 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树 平衡二叉树（BalancedBinaryTree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 思路 左右两个子树的高度差的绝对值不超过1 左右两个子树都是一棵平衡二叉树 代码 packageesay.JZ79判断是不是平衡二叉树; classTreeNode{ intval=0; TreeNodeleft=null; TreeNoderight=null; public...

JZ81调整数组顺序使奇数位于偶数前面(二) 描述 输入一个长度为n整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。 方法1 思路： 既然要把所有的奇数放在数组前面，所有的偶数放在数组后面，那可以统计奇数在原数组中出现了多少次，这样就可以找到二者的分界线。有了分界线以后，前面就是奇数，后面就是偶数，可以利用两个指针分别指向二者的开头，遇到一个元素就添加到相应位置，然后指针移动。（该方法保证了相对位置不变） 代码 ...

JZ82二叉树中和为某一值的路径(一) 代码 packageesay.JZ82二叉树中和为某一值的路径1; importjava.util.; classTreeNode{ intval=0; TreeNodeleft=null; TreeNoderight=null; } publicclassSolution{ / 描述 给定一个二叉树root和一个值sum，判断是否有从根节点到叶子节点的节点值之和等于sum的路径。 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点 2.叶子节点是指没有子节点的节点 3.路径只能从父节点到子节点，不能从子节点到父节点 4.总节点数...

JZ4二维数组中的查找 描述 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 [[1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15]] 给定target=7，返回true。 给定target=3，返回false。 进阶：空间复杂度O(1)O(1)，时间复杂度O(n+m)O(n+m) 思路 利用该二维数组的性质： 每一行都按照从左到右递增的顺序排序， 每一列都按照从上到下递增的顺序排序 改变个说...

JZ7重建二叉树 描述 给定节点数为n的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6} 提示: 1.vin.lengthpre.length 2.pre和vin均无重复元素 3.vin出现的元素均出现在pre里 4.只需要返回根结点，系统会自动输出整颗树做答案对比 具体做法： step1：先根据前序遍历第一个点建立根节点。 step2：然后遍历中序遍历找到根节点在数组中的位置。 step3：再按照子树的节点数将两个遍历的序列分割成子数组，将子数组送入函数建立子树。 st...

JZ8二叉树的下一个结点 描述 给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。 示例: 输入:{8,6,10,5,7,9,11},8 返回:9 解析:这个组装传入的子树根节点，其实就是整颗树，中序遍历{5,6,7,8,9,10,11}，根节点8的下一个节点就是9，应该返回{9,10,11}，后台只打印子树的下一个节点，所以只会打印9 具体做法： step1：首先先根据当前给出的结点找到根节点 step2：然后根节点调用中序遍历 step3：将中序遍历结果存储下来 step4：最终拿当前结点匹配是否...

JZ12矩阵中的路径 描述 请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 思路 我们看到他是从矩形中的一个点开始往他的上下左右四个方向查找，这个点可以是矩形中的任何一个点，所以代码的大致轮廓我们应该能写出来，就是遍历矩形所有的点，然后从这个点开始往他的4个方向走，因为是二维数组，所以有两个for循环，代码如下 publicbooleanhasPath(char[][]matrix,Str...