- 博客(170)
- 收藏
- 关注
RSS订阅原创 2171.拿出最少数目的魔法豆
请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少还有一颗 魔法豆的袋子）魔法豆的数目 相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。所有需要取出的魔法豆总数=前缀和+后缀和-beans[i]*(len-i-1)。i为排序后当前元素的下标。分析：如果最后非空袋子的魔法豆数量为x，因为袋子中无法添加豆子，所以原本比x小的，只能全部取出。给定一个 正整数 数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。先排序，做累加，即可得到前缀和与后缀和。
2024-01-21 12:06:04
498
原创 Spring源码之BeanNameGenerator
从图中可以看到，ComponentScans的属性为value，而value又包含了一个长度为4的AnnotationAttributes的数组。这里正是在上面配置类中使用的注解ComponentScans和Configuration，其中我们还使用了Configuration，但是其是作为ComponentScans的value属性而存在。因为上面的扫描的第一个注解为ComponentScans，它的value值是不被允许指定为bean的名称的。它的value值是可以指定bean的名称的。
2023-07-25 08:39:35
200
原创 799. 香槟塔
模拟：为了好模拟，先将poured这个数放到无限大，将poured杯的水全部倒入第一层的杯子里，那么第一个杯子装了poured杯的水，那么溢出的水也就是poured-1。如果dp[i][j]>1，那么肯定是要溢出的，溢出的水的量就是dp[i][j]-1，溢出的水去向分别是dp[i+1][j]和dp[i+1][j+1]。分析：可以将杯子的容量先扩大，就是将当前层的杯子看成无限大的容量，装再多的水也不会溢出，然后再把容量缩小为1份玻璃杯的体积。定义：dp[i][j]:表示第i行第j列杯子里的水量（可以大于1）
2022-11-20 11:01:03
181
1
原创 redis变慢原因记录
如果对操作系统有了解的话，应该知道，操作系统为了缓解内存不足对应用的影响，允许把一部分内存中的数据换出到磁盘上，等要使用的时候再换进来。从内存中换出到磁盘上的区域就是Swap。那么问题就在于，频繁的换入换出，也就是要频繁读写磁盘，这个速度相比于访问内存，是很慢的。尤其是对redis这种对性能要求极高、性能及其敏感的数据库来说。
2022-09-20 22:45:36
3173
原创 基于ReentrantLock的AQS源码解析（一）
众所周知：ReentrantLock可以是公平的也可以是非公平的。所谓公平：就是先来的肯定比后来的先获取到锁。也就是不能插队。所谓非公平：就是说，后来的可以比先来的先获取到锁，也就是说可以插队。以公平为例子进行讲解。我们知道，ReentrantLock 使用起来就向上面那样。一个lock一个unlock即可。首先看lock方法：继续跟进去，最后可以看到，调用的是acquire(1):acquire方法：重点从这里才开始，上面的都是依次跟就行。首先进行了一个if判断。第一个方法：tryAcq
2022-07-09 10:23:33
210
原创 406. 根据身高重建队列
题目链接分析：题目意思是要我们将一个数组 people[i] = {h,k}，放到一个位置，并且能保证，这个位置前面有k个h大于等于当前h的。首先说一下需要使用到的变量：res[][]：用来记录最终答案的二维数组vis[]：用来记录这个位置是否已经放置了元素count：用来记录前面有几个大于等于当前h的元素那么我们可以反过来想，首先找到一个最小的h，那么其它的h肯定比当前大，那么只需要考虑前面有k个位置就行，也就是说，当前这个放到第k+1个位置就行。（这里为了简单，先没考虑有相同的h）下面我们再考虑
2022-07-03 10:56:49
88
原创 leetcode 730. 统计不同回文子序列
题目链接思路一：动态规划（三维数组）分析：对于每个符合题目条件的回文串，一定是a、b、c、d中的某个字符开头和结尾的。那么可以将这四个字符开头当作一个状态。定义dp: dp[x][i][j]表示 以x开头和结尾 的并且字符串范围在s[i:j]中的回文子序列的个数。其中x表示abcd中的某个字符。首先初始化。对于长度为1的字符串肯定是回文。所以dp[x][i][i]=1，此时的x应该为s.charAt(i)。状态转移方程：最后的答案应该为以a、b、c、d四个字符结尾的范围是[0][len-1]的dp
2022-06-11 10:47:43
122
原创 leetcode 450. 删除二叉搜索树中的节点
题目链接思路：递归分析：删除root中值为key的节点，首先分为两步：第一步：找到值为key的节点第二步：删除值为key的节点完成第一步的方案：因为树为二叉搜索树，所以有左小右大的原则，可以在O(h)的时间复杂度内找到值为key的节点。（h为数的高度）具体做法是：root.val>key，代表值为key的节点在root的左子数里面，那么就递归从root的左子树中删除值位key的节点。root.val...
2022-06-04 11:49:10
1368
原创 leetcode115. 不同的子序列
题目链接思路：动态规划分析：确定dp数组的含义dp[i][j]：表示s中以为i-1结尾的字符串，有多少个子序列等于 以t中以j-1为结尾的字符串。递推公式：如果s[i-1]和t[j-1]相等这里还要分为两部分，将s[i-1]算进来，和不将s[i-1]算进来所以，dp[i][j]=dp[i-1][j-1] + dp[i-1][j].举例：s=“bagg” t=“bag”，s[3]和t[2]相等，但是要得到t，可以将s[3]算进来，也可以不将s[3]算进来，所以dp[i][j]等于两种情况
2022-05-23 10:59:23
78
原创 leetcode 467. 环绕字符串中唯一的子字符串
题目链接思路：一次遍历分析：1.只需要统计以当前字符结尾的子串。2.最后直接进行求和即可例如 “zab”，假设用r表示以当前字符结尾的环绕子串个数，当当前字符为’z’时，我们找到一个子串，r= 1，当当前字符为’a’,我们发现和’z’是连续的，r直接加1得，r= 2，而总的子串就有1 + 2 = 3， 当当前字符为’b’和前面的"za"构成连环绕连续，r再加1，r= 3，而总的环绕子串就有1 + 2 + 3 = 6，共6个。不过此时有个问题：假设当前字符结尾的字串，之前遍历有过和当前字符一样的字
2022-05-11 22:28:51
951
原创 leetcode 957. N 天后的牢房
题目链接思路一：位运算+模拟分析：规则说的很清楚，当前位置由左边和右边位置的值决定。首先我们可以先将数组转为int。将一个长度为8的数组转为int的代码如下：public int transferArrToNum(int[] cells){ int num = 0; for(int i=0;i<8;i++){ if(cells[i]==1){ //把1移动到相应位置，然后与num或运算，或运算就是将1加入到nu
2022-05-07 17:23:30
283
原创 leetcode 713. 乘积小于 K 的子数组
题目链接思路：双指针分析：题目要求连续子数组的乘积小于k，连续子数组，那么也就是从数组中取出一段乘积小于k。那么用一个指针指向这一段的左边，另一个指针来指向这一段的右边。左指针记为l，右指针记为r。累乘为seqr。答案记为res初始化 l=0,r=0,seqr=nums[r]；r=0表示的意思是以下标为0元素结尾的段。如果此时seqr满足条件，那么res = res + (r-l+1)如果此时seqr不满足，如果此时l=<r，那么将nums[l]移出去。然后计算res = res +
2022-05-05 10:24:06
445
原创 leetcode 297. 二叉树的序列化与反序列化
题目链接思路：层序遍历分析：普通得情况下，如果单独靠一种遍历序列（前序、中序、后序、层序），想要唯一确定一颗二叉树，是无法确定的。因为是如果一个节点左孩子没有，而有右孩子，此时，无法构造树的时候，无法区分这个孩子是左孩子还是右孩子。其他的情况也类似。所以在遍历的时候，如果某个孩子为null，那么我们可以用一个标志来表示。举例：如果是上面这种情况。层序遍历：1，2，3，4此时无法确定3是不是1的孩子。但是如果将层序遍历为：1，2，null，3，4，null，null，null，null这
2022-05-02 18:14:28
652
原创 leetcode 427. 建立四叉树
题目链接思路：递归+分治思路：题目给了我们两条规则。1.如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。2.如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值对于这两条规则，我们首先要判断网格内的值是否相同。根据相同或不相同，规则也说的很清楚要怎么处理。这里的judge函数就是用来判断网格的值是否相同。(x1,y1)表示网格左上角的点，(x2,y2)表
2022-04-29 10:57:45
175
原创 leetcode 210. 课程表 II（拓扑排序）
题目链接思路：拓扑排序（深搜）拓扑排序的定义：给定一个包含n个节点的有向图G，我们给出它的节点编号的一种排序，如果满足，对于图G中的任何一条有向边(u,v)，u都在排列中都出现在v的前面，那么就称该排列是图G的【拓扑排序】。根据这个定义，可以得出两个结论：存在拓扑排序的图，肯定是有向无环图。即存在拓扑排序的图，肯定不能有环。一个有向无环图，他的拓扑排序可能有好多种，例如所有节点都没有边，那么任意的编号排列都是一种拓扑排序。这个题目的意思就是求一个图的拓扑排序，前提是如果存在的话。首先：将题
2022-04-24 12:51:58
401
原创 leetcode 134. 加油站
题目链接思路：一次遍历分析：那么就从每个站点出发试试但是，开始的站点，肯定要满足能加的油肯定要大于等于去下一站要耗费的油量。即gas[i]>=cost[i]并且因为答案唯一，所以能加的油量肯定不是0即gas[i]!=0假设从x点出发，最远到了y，假设没有经过所有站点。那么下一次开始的点，不是x后的站点，而应该是y后面的站点。因为x和y中间的站点，已经走过了，已经判断了不行。代码：class Solution { public int canCompleteCircuit(
2022-04-22 11:28:40
358
原创 leetcode 396. 旋转函数
题目链接思路：迭代分析：手动模拟一下，其实可以找到规律首先，用sum记录一下F(0)，用k记录一下累加和简单模拟一下，找找规律nums = [4,3,2,6]F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6)F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2)F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3)F(1)与F(0)相比，可以看到，多了一个4，多了一个3，多了一个2，少
2022-04-22 11:14:59
1007
原创 leetcode 821. 字符的最短距离
题目链接思路一：双指针分析：如果里面只有一个和c相同的字符。那么很好处理，只要计算和这个字符的距离即可。如果里面有两个或两个以上。将第一个的下标记为p1，第二个的下标记为p2。当i<=p1的时候，最近的距离肯定是p1-i。当i>p1 && i<= (p1+p2)/2,最近的距离是res[i] = i-p1;当i>(p1+p2)/2，最近的距离是res[i]=p2-i;此时要更新两个指针。p2=p1p2更新为下一个与c相同的字符。代码：clas
2022-04-19 11:00:59
222
原创 leetcode 57. 插入区间
题目链接思路：模拟分析：情况1：要加的区间在最前面【】 [],[],[],[],[]…情况2：要加的区间，左边在最前面【[],[],[],…… 情况2.1：要加的区间，右边在某个区间里面【[],[],[],…[】]…… 情况2.2：要加的区间，右边不在任何区间里面… … 情况2.2.1：右边区间在最后【[],[],[],[],[],[],[],…】… … 情况2.2.2：右边区间在中间【[],[],[],[],】[],[],[],…情况3：要加的区间，左边不在最前面… 情况3.1：左边在
2022-04-18 13:35:53
286
原创 leetcode 386. 字典序排数
题目链接思路：递归分析：首先我们先不看n多大，把他当作无限大。那么肯定是1，10，11，12，13，，，，19，20，21，，，29可以看出，我们可以分为9层，每一层分别是1开头，2开头，3开头。。。。9开头然后在1开头后，后面又可以分为9层，10，12，13，14，，，，，19即又可以分为10份，即0开头，1开头，2开头，，，，，9开头，也就对应10，11，12，13，，，，，19。那么这里已经可以看出递归的规律了。就是每次将这一层的数字加入答案，然后将（这个数字+一个偏移量）*10
2022-04-18 10:21:03
100
原创 leetcode 385. 迷你语法分析器
题目链接思路：递归分析：这个题主要在于要看懂题目意思，这个NestedInteger对象里面就是套了一个NestedInteger对象。很明显，这是个嵌套的定义，那么我们可以用递归的思路来实现。从左到右遍历S。如果一开始是’[‘，那么后面肯定是一个列表，并且从这个字符开始，后面又是一个新的NestedInteger实例，继续解析后面的字符，如果遇到的是一个数字字符串，那么设置为val，然后继续后面走，如果后面还有，那么肯定又是一个嵌套的NestedInteger实例，一直到最后解析完，解析完就是
2022-04-15 12:40:01
382
原创 HashMap1.7 扩容产生环形链表
场景两个线程同时put，发现HashMap需要扩容。执行代码现场HashMap真正的resize是在transfer方法里面完成的。void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Ent
2022-04-12 11:10:04
1490
原创 leetcode 12. 整数转罗马数字
题目链接思路：哈希表分析：这里使用哈希表将题目提供的数值和字符对应起来，并且将特殊规则中的字符也对应起来。步骤：1.开始去用num和数值比较，找到最大的小于等于num的数值。2.计算所需要这个数值的个数。3.将这个值对应的字符所需要的个数加入到答案中。代码：class Solution { private static HashMap<Integer, String> map = new HashMap<>(); static { ma
2022-04-12 10:14:40
98
原创 leetcode 780. 到达终点
题目链接思路：反向计算分析：这个题目的解法很巧妙，这个题一读完，很容易让人想到一直去想如何从sx,sy去转换到tx,ty，这要尝试很多情况，(sx,sy)下一次就可以转到(sx+sy,sy)或(sx,sx+sy)，然后每次都有两种选择，并且tx,ty的范围到了109,这显然会超时。所以这里采用的时候从tx，ty倒退过来。想想看假设，(sx,sy)可以到达(tx,ty)那么最后一次转化肯定tx，ty中较小的那个肯定已经相等了，假设tx<ty，也就是说，最后一次转换之前，sx肯定等于了tx了
2022-04-11 11:42:23
101
原创 leetcode 357. 统计各位数字都不同的数字个数
题目链接思路：动态规划分析：用高中知识，要怎么开始去做呢？假设n=0。此时只有1个数字0，所以答案就是1。假设n=1，此时一共是[0,9]，10个数组，所以答案就是10。假设n=2首先考虑就是两位数的情况。填写第一位数字，第一位数字不能是0，其它均可，那么也就是9个，第二个数字可以填写0，但是不能和第一个数字一样，所以也是9个，所以两位数是99=81.再考虑一位数的情况。一位数的情况上面算过了，就是10。所以n=2，答案是99+10=91假设n=3首先考虑三位数的情况。一样，填
2022-04-11 11:01:09
152
原创 leetcode 29. 两数相除
题目链接思路：位运算+二分分析：这里采用得是：被除数/除数=商…余数不过这里的余数不是真正的余数，因为这里的余数不一定小于除数。但是这个是符合的。余数=被除数-（除数*商）；那么这次的余数，就可以当作下一次被除数，因为是没除尽的数字，所以下一次继续算，又可以得到商和余数直到某一次被除数大于了除数，就停下来。这里要注意两点：先看被除数和除数是否异号，要记录一下。将被除数和除数都弄成负数，因为前面符号是否异号已经记录下来，那就可以不考录符号带来的影响了，此时如果都弄成正数，那么对于int的最
2022-04-09 10:27:20
265
原创 leetcode 39. 组合总和
题目链接思路：深搜+回溯分析：因为每个数字都可以用多次，也就是说要找到所有的可行解，那么这里使用的是搜索+回溯的方法来解决。这里定义了dfs函数。第一个参数是：排好序的candidates。第二个参数是：当前需要凑出来的目标值。第三个参数是：当前从candidates数字开始遍历的下标。第四个参数是：candidates的长度。dfs：函数功能是查找[index.n-1]范围内，能凑出tar的组合。这里要注意，因为candidates中的元素都是正数，所以一旦最开始的元素就大于了tar，那
2022-04-08 13:21:12
112
原创 leetcode 146. LRU 缓存
题目链接思路：双向链表+哈希表分析：这是一个很经典的策略，很多缓存淘汰策略都是采用的这个。这里还要熟悉指针的操作。这个题目的意思就是：当键值对的个数没达到capacity的时候，那么就直接加入缓存。当键值对的个数达到了capacity的时候，那么就要淘汰一个键值对。这里存储键值对使用的是双向链表+哈希表。双向链表(DouList)的结构如下： class DouList{ //指向头节点 DouListNode head;
2022-04-07 18:38:32
461
原创 leetcode 19. 删除链表的倒数第 N 个结点
题目链接思路：快慢指针分析：倒数第N个节点，最简单的做法就是先数一下一共有几个节点，然后再去操作。这里是用的是利用一个先行指针，一个后行指针，他们之间的间隔就是n-1个节点，也就是说后行指针比先行指针慢n-1个节点。当先行指针到了最后一个节点的时候，那么后行指针就正好在第到数n+1个节点上。这样的好处在于不需要去计算一共多少个节点了。代码：/** * Definition for singly-linked list. * public class ListNode { * in
2022-04-07 10:51:40
401
原创 leetcode 1390. 四因数
题目链接思路：枚举+减枝分析：枚举数组中的每个数，然后找到其因数。如果只有四个，那么就将因素累加到答案中即可。并且每个大于等2的数字，有两个因数是不用判断的，就是1和自身。那么我们只需要发现，在[2,i*i]的去间找到了多于两个因数，那么就不用判断了，肯定不是。直觉告诉我们，只有四个因数的数肯定不多。并且，完全平方数肯定不可能是答案，因为完全平方数的因素总数一定是奇数。所以肯定排除。总结一下减枝的条件：因为数量大于了4个，直接跳出。完全平方数，直接跳出。代码：class Solut
2022-04-06 14:47:16
661
原创 leetcode 310. 最小高度树
题目链接思路：深搜分析：这个题目要找最小高度树，要达到最小高度，要处理的其实是最长路径，如果我们找到了最长的路径，那么只要取中间的节点当作根节点就是最小高度树，因为最长的路径被中分了，那么也就可以做到高度最小了。也就是说，在这个图里面找到一根最长的线，那么，你怎么折这根线使得折完以后，这根最长的线最短。那么肯定是对折，对吧。那么现在有两个问题：如果找到这个图里面的最长路径，也就是如何找到这根最长的线。找到最长路径后，如何找到这个路径的中点。**问题1：**我们可以这么想，把自身当作里面的一
2022-04-06 11:54:51
446
原创 leetcode 454. 四数相加 II
题目链接思路：分组+哈希表分析：四个树状A、B、C、D，将AB分为一组，CD分为一组。首先计算AB一共可以加出多少个不同的数字来，并且记录每个数字有多少种情况可以加出来。（记录在哈希表种）然后再计算0减去CD的值相加，并且去哈希表中找，看有几种情况。也就是将A+B记在哈希表中，然后在哈希表中寻找-（C+D），看有多少种情况，然后进行累加即可得到答案。代码：class Solution { public int fourSumCount(int[] nums1, int[] nums2,
2022-04-05 13:00:17
335
原创 leetcode 307. 区域和检索 - 数组可修改（树状数组）
题目链接思路：树状数组首先：直接用前缀和数组肯定是会超时的，假设每次修改的都是第一个数组，那么后面的每个前缀和都要修改，最坏情况下，就是O(n2)，显然就超时了，所以换个思路，使用树状数组。树状数组是一种可以维护序列前缀和的数据结构，并且：单点修改add(index,val)：在index位置上加上val，它的时间复杂度是O(log(n))前缀和prefixSum(index)：查询[0,index]范围内的累加和，它的时间复杂度是O(log(n))介绍一下树状数组这个数据结构：一个数组A
2022-04-05 09:55:38
271
原创 leetcode 18. 四数之和
题目链接思路：排序+双指针分析：首先排序，第一个是为了从小到大遍历每一个数，第二个是为了去重方便，排序完相同的数肯定是靠在一起的。第一：遍历第一个数，从小到大。第二：遍历第二个数，从小到大。第三：计算第一个数与第二个数的和，然后再计算与目标之的差距。第四：此时题目就变成了，从第二个数后面开始找两个数相加等于这个差距。此时因为是有序的，所以可以用双指针来查找。这里还可以减枝来提高效率。代码：class Solution { List<List<Integer>>
2022-04-03 10:18:14
553
原创 leetcode 3. 无重复字符的最长子串
题目链接思路一：前置指针分析：最长子串肯定是出现在某个字符与该字符上一次出现的位置中间这一段。我们用一个数组来记录每个字符上一次出现的位置，那么以这个字符结尾最长肯定是在它上一次出现的位置的后面一个位置到当前位置。并且这个题目里面的字符串都是ASSIC码表中的字符，我们用一个长度为128的数组last表示。last[i]=x：表示的是在ASSIC表中十进制是i的字符上一次在s中出现的下标是x。举例：“abcabcbb”i=0last[‘a’]=0;此时的前置指针默认为-1，因为前面没有a
2022-04-02 20:51:24
257
原创 leetcode 16. 最接近的三数之和
题目链接思路：排序+双指针分析：我们先排序，枚举第一个数a，然后第二个数b从第一个数后面第一个开始，第三个数c从最后一个数开始。记录此时的三数之和，拿这个三数之和与目标的差距 和 之前最接近的三数之和与目标的差距相比较。也就是拿a+b+c-tar 与 close-tar相比，如果前者更接近tar，那么就更新close。如果close等于tar，那么直接返回close，因为此时不可能有数字更接近了。如果此时的三数和 大于了tar，那么将第三个数左移。如果此时的三数和 小于了tar，那么
2022-03-31 14:42:16
478
原创 leetcode 2028. 找出缺失的观测数据
题目链接思路：模拟分析：这个题其实就是需要选n个在[1,6]范围内的数之和为tar。那么我们可以先记录一下 num=tar/n，remainder=tar%n.也就是说，num是这个n个数字接近的一个答案，但是n个num加起来可能还少了一点，就是说，tar可能不能整除n，所以我们再记录一下remainder，然后我们再将remainder个数+1就可以解决不能整除的问题。代码：class Solution { public int[] missingRolls(int[] rolls,
2022-03-27 11:31:44
528
原创 leetcode 395. 至少有 K 个重复字符的最长子串
题目链接思路：分治+逻辑分割分析：要求连续的字符串最长，并且组成字符串的每个字符出现的次数都不能小于k，那么我们可以反过来想。也就是说：字符串中的出现次数小于k的，肯定不会是答案。并且答案一定不会包含这个字符在内。那么我们统计一下字符串中每个字符出现的次数。然后找到出现出现次数少于k的，然后按照这个字符去切割这个字符串。代码：class Solution { //每次把在[left, right]中字符出现次数少于k的找出来，然后按照这个将字符串切割开，因为不可能包含这个字符
2022-03-26 14:21:22
700
原创 leetcode 220. 存在重复元素 III
题目链接思路一：滑动窗口+红黑树查找分析：这个题目意思简化一下就是两句话。第一：元素之差 小于等于 t第二：下标之差 小于等于 k那么这里提到了下标的距离，那么很容易想到这里可以用到滑动窗口，而且这个窗口的大小是k。这里t是大于等于0的，也就是说 nums[i]要满足第一个条件，必须存在 在 nums[i]-t到nums[i]+t范围内存在数字在窗口中。那么i从头遍历nums即可。但是这里有个问题，这么去判断窗口中有没有在范围nums[i]-t和nums[i]+1内的数字存在呢？如果我
2022-03-25 19:38:33
1317
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人