- 博客(938)
- 资源 (10)
- 收藏
- 关注
RSS订阅
原创 数据结构与算法总结
目录数据结构数组链表栈队列树图哈希表字符串算法排序查找位运算动态规划回溯算法分治法贪婪算法深度优先算法广度优先算法字符串数学数据结构数组leetcode https://blog.csdn.net/xushiyu1996818/article/details/81186534链表lee...
2019-04-02 10:33:27
482
2
原创 leetcode-063-不同路径2
否则网格 (i,j) 可以从网格 (i−1,j) 或者 网格 (i,j−1) 走过来，因此走到该格子的方法数为走到网格 (i - 1, j) 和网格 (i, j - 1)的方法数之和，即 dp[i, j] = dp[i - 1, j] + dp[i, j - 1]。第 1 行的格子只有从其左边格子走过去这一种走法，因此初始化 dp[0][j] 值为 1，存在障碍物时为 0。如果网格 (i,j) 上有障碍物，则 dp[i][j] 值为 0，表示走到该格子的方法数为 0；解法1（成功，0ms，极快）
2023-07-02 22:01:40
631
原创 leetcode-061-旋转链表
然后再向后移动到null，得到rightTail。然后rigthtail.next指向head，leftTail.next指向null即可。先获取链表的长度，然后从头部移动length-k-1次，得到head，leftTail，rightHead，解法1（成功，0ms，极快）
2023-07-02 21:49:51
467
原创 leetcode-060-排列序列
常见的做法是：代入一个具体的数值，认真调试。把候选数放在一个 有序列表 里，从左到右根据「剩下的数的阶乘数」确定每一位填谁，公式 k / (后面几位的阶乘数) 的值 恰好等于候选数组的下标；如果 k 小于等于这一个分支将要产生的叶子结点数，那说明所求的全排列一定在这一个分支将要产生的叶子结点里，需要递归求解。一句话题解：以下给出了两种方法，思路其实是一样的：通过 计算剩余数字个数的阶乘数，一位一位选出第 k 个排列的数位。由于这里考虑的是下标，第 k 个数，下标为 k - 1，一开始的时候，k--。
2023-07-02 19:40:32
521
原创 leetcode-059-螺旋矩阵2
如果 left<right 且 top<bottom，则从右到左填入下侧元素，依次为 (bottom,right−1) 到 (bottom,left+1)，以及从下到上填入左侧元素，依次为 (bottom,left) 到 (top+1,left)。填完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，进入下一层继续填入元素，直到填完所有元素为止。可以将矩阵看成若干层，首先填入矩阵最外层的元素，其次填入矩阵次外层的元素，直到填入矩阵最内层的元素。
2023-06-10 20:13:47
644
原创 leetcode-058-最后一个单词的长度
从最后一个字母开始继续反向遍历字符串，直到遇到空格或者到达字符串的起始位置。遍历到的每个字母都是最后一个单词中的字母，因此遍历到的字母数量即为最后一个单词的长度。由于字符串中至少存在一个单词，因此字符串中一定有字母。首先找到字符串中的最后一个字母，该字母即为最后一个单词的最后一个字母。题目要求得到字符串中最后一个单词的长度，可以反向遍历字符串，寻找最后一个单词并计算其长度。解法1（成功，1ms，较慢）
2023-06-09 22:34:31
59
原创 leetcode-057-插入区间
然后,再看右边,这里有个情况,就是 当intervals[i][0] > newInterval[1]说明newInterval没有和任何区间重合,比如intervals = [[1,3],[6,9]], newInterval = [4,5],直接插入即可.首先,左边,当newInterval[0] > intervals[i][1]说明没有和该区间没有重叠部分,继续遍历下一个区间,比如intervals = [[1,3],[6,9]], newInterval = [2,5]下面就要考虑重叠情况了。
2023-06-08 23:54:07
386
原创 leetcode-052-n皇后2
回溯的具体做法是：依次在每一行放置一个皇后，每次新放置的皇后都不能和已经放置的皇后之间有攻击，即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上。显然，每个皇后必须位于不同行和不同列，因此将 N 个皇后放置在 N×N 的棋盘上，一定是每一行有且仅有一个皇后，每一列有且仅有一个皇后，且任何两个皇后都不能在同一条斜线上。为了降低总时间复杂度，每次放置皇后时需要快速判断每个位置是否可以放置皇后，显然，最理想的情况是在 O(1) 的时间内判断该位置所在的列和两条斜线上是否已经有皇后。
2023-06-07 20:15:36
540
原创 leetcode-051-n皇后
我们可以先不考虑每一个皇后之间不能相互攻击的条件，如果要求每行只能放一个皇后，我们能否穷举出所有的放置方法？对于每一个格子进行计算分析能不能放置皇后，最后的代码实现会跳过这些格子，把皇后放在合法的位置上。具体的，在每一个位置放置皇后，然后调用 backtrack 函数，进入下一行进行穷举进行判断。因为我们是一行一行从上向下放置皇后，所以下方，左下方和右下方不会有皇后（还没放皇后）。因为我们的逻辑是每一行只放一个皇后，所以这个皇后的左边和右边不需要进行检查了。N 皇后问题也是一个暴力穷举的问题。
2023-05-31 23:14:03
395
原创 leetcode-047-全排列2
但是这个相等条件有两种可能 一种是，1 1‘ 2，也就是选择完1之后再选择第二个1，两个元素虽然重复，但是第二个元素是前一个元素的下一层，这时是没有问题的。另一种是之前的 同层 分支已经有 1 1‘ 2了，这次的选择是 1‘ 1 2。那就说明是重复分支。具体区分的办法是 nums[i-1] 的used状态是被选择的，那么说明当前的nums[i] 是 nums[i-1]的下一层路径。否则如果 nums[i-1] 的状态是没被选择的，那么说明当前 的nums[i] 是nums[i-1] 同层路径。
2023-05-20 16:45:55
78
原创 leetcode-045-跳跃游戏2
以此类推，不断地在到达当前步的边界 end 前更新下一步能够到达的最远距离nextMaxEnd 作为下一步的边界，更新途中一旦到达当前步的边界 end，就表示当前步已经贪心地走完了，必须跳下一步了，step++，并且下一步能够到达的最远边界我们已经在之前比较出来了，直接更新即可：end = nextMaxEnd。到这里，其实就可以明白为什么不用遍历终点了，因为边界 end 有可能是终点，那 end 一旦到了终点其实也就到了，但是我们的代码逻辑是到达 end 就得步数加一，其实这是没必要的。
2023-05-14 14:51:59
78
原创 leetcode-043-字符串相乘
如果num 1和num 2都不是0，则可以通过模拟「竖式乘法」的方法计算乘积。从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。这道题中，被乘数是num 1，乘数是num 2。num1[i] x num2[j] 的结果为 tmp(位数为两位，"0x""0x", "xy""xy" 的形式)，其第一位位于 res[i+j]，第二位位于 res[i+j+1]。该算法是通过两数相乘时，乘数某位与被乘数某位相乘，与产生结果的位置的规律来完成。需要注意的是，num 2。
2023-05-14 11:37:17
58
原创 leetcode-040-组合总和2
很容易想到的方案是：先对数组 升序 排序，重复的元素一定不是排好序以后相同的连续数组区域的第 11 个元素。也就是说，剪枝发生在：同一层数值相同的结点第 22、33 ... 个结点，因为数值相同的第 11 个结点已经搜索出了包含了这个数值的全部结果，同一层的其它结点，候选数的个数更少，搜索出的结果一定不会比第 11 个结点更多，并且是第 11 个结点的子集。这里我们使用和第 39 题和第 15 题（三数之和）类似的思路：不重复就需要按 顺序 搜索， 在搜索的过程中检测分支是否会出现重复结果。
2023-05-08 22:48:19
643
原创 leetcode-037-解数独
尝试去填充数组，只要行，列， 还有 3*3 的方格内 出现已经被使用过的数字，我们就不填充，否则尝试填充。声明布尔数组，表明行列中某个数字是否被使用了， 被用过视为 true，没用过为 false。我们尝试填充，如果发现重复了，那么擦除重新进行新一轮的尝试，直到把整个数组填充完成。类似人的思考方式去尝试，行，列，还有 3*3 的方格内数字是 1~9 不能重复。数独首先行，列，还有 3*3 的方格内数字是 1~9 不能重复。如果填充失败，那么我们需要回溯。初始化布尔数组，表明哪些数字已经被使用过了。
2023-05-07 17:49:37
79
原创 leetcode-035-搜索插入位置
情况 1：如果当前 mid 看到的数值严格小于 target，那么 mid 以及 mid 左边的所有元素就一定不是「插入元素的位置」，因此下一轮搜索区间是 [mid + 1..right]，下一轮把 left 移动到 mid + 1 位置，因此设置 left = mid + 1；说明：上面的两点中，「情况 2」其实不用分析得那么细致， 因为只要「情况 1」的区间分析是正确的，「情况 2」一定是「情况 1」得到的区间的反面区间。根据示例，分析题目要我们返回的「插入元素的位置」是什么。
2023-05-06 23:29:10
475
原创 leetcode-030-串联所有单词的子串
初始化 differ 时，出现在窗口中的单词，每出现一次，相应的值增加 1，出现在 words 中的单词，每出现一次，相应的值减少 1。窗口移动时，若出现 differ 中值不为 0 的键的数量为 0，则表示这个窗口中的单词频次和 words 中单词频次相同，窗口的左端点是一个待求的起始位置。不同的是第 438 题的元素是字母，而此题的元素是单词。然后进行回溯，对每个下标，进行dfs，碰到dict[index][i]为true的，wordsNum[i]--，如果回溯到wordsNum全为0，代表全部对应。
2023-05-06 22:40:59
77
原创 leetcode-027-移除元素
如果左指针 left 指向的元素等于 val，此时将右指针 right 指向的元素复制到左指针 left 的位置，然后右指针 right 左移一位。如果赋值过来的元素恰好也等于 val，可以继续把右指针 right 指向的元素的值赋值过来（左指针 left 指向的等于 val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于 val 为止。如果右指针指向的元素不等于 val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；解法1（成功，0ms，极快）
2023-05-05 23:11:04
732
原创 leetcode-025-k个一组翻转链表
特殊情况，当翻转部分长度不足 k 时，在定位 end 完成后，end==null，已经到达末尾，说明题目已完成，直接返回即可。初始需要两个变量 pre 和 end，pre 代表待翻转链表的前驱，end 代表待翻转链表的末尾。翻转链表，然后将三部分链表连接起来，然后重置 pre 和 end 指针，然后进入下一次循环。经过k此循环，end 到达末尾，记录待翻转链表的后继 next = end.next。需记录翻转链表前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来。解法1（成功，0ms，极快）
2023-05-05 22:58:18
55
原创 leetcode-024-两两交换链表中的节点
用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHead 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 newHead.next。如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。两两交换链表中的节点之后，新的链表的头节点是 dummyHead.next，返回新的链表的头节点即可。将链表根据节点的位置分成链表1和链表2，原来的变成12121，然后再合并，2121。
2023-05-02 01:43:30
645
原创 leetcode-018-四数之和
在确定第一个数之后，如果 nums[i]+nums[n−3]+nums[n−2]+nums[n−1]<target，说明此时剩下的三个数无论取什么值，四数之和一定小于 target，因此第一重循环直接进入下一轮，枚举 \textit{nums}[i+1]nums[i+1]；在确定前两个数之后，如果 nums[i]+nums[j]+nums[n−2]+nums[n−1]<target，说明此时剩下的两个数无论取什么值，四数之和一定小于 target，因此第二重循环直接进入下一轮，枚举 nums[j+1]。
2023-05-01 12:54:58
544
原创 leetcode-016-最接近的三数之和
同时判断 sum 与 target 的大小关系，因为数组有序，如果 sum > target 则 end--，如果 sum < target 则 start++，如果 sum == target 则说明距离为 0 直接返回结果。根据 sum = nums[i] + nums[start] + nums[end] 的结果，判断 sum 与目标 target 的距离，如果更近则更新结果 ans。在数组 nums 中，进行遍历，每遍历一个值利用其下标i，形成一个固定值 nums[i]
2023-04-25 21:28:13
75
原创 leetcode-012-整数转罗马数字
这个思路相对比较简单，因为题目中说输入在 1 ~3999 的范围内，所以我们把 1 到 9，10 到 90，100 到 900，1000 到 3000 对应的罗马数字都表示出来，最后对于任何输入，我们要做的就是把找到的罗马数字组合起来即可。比如输入是 2359，我们找到 2000，300，50，9 对应的罗马数字为 MM，CCC，L，IX，组合后得到结果为 MMCCCLIX。然后根据算法，将1,5,10对应的char拼接成对应的字符串。1994，这样，每位分别处理，1000,900,90,4。
2023-04-23 22:56:20
61
原创 leetcode-009-回文数
这里需要注意的一个点就是由于回文数的位数可奇可偶，所以当它的长度是偶数时，它对折过来应该是相等的；当它的长度是奇数时，那么它对折过来后，有一个的长度需要去掉一位数（除以 10 并取整）。如果是奇数的话，最中间的数字就在revertNum 的最低位上，将它除以 10 以后应该和 x 相等。将最低的数字加到取出数的末尾：revertNum = revertNum * 10 + y。每次进行取余操作 （ %10），取出最低的数字：y = x % 10。通过取整和取余操作获取整数中对应的数字进行比较。
2023-04-20 21:19:01
361
原创 leetcode-006-N 字形变换
对于其他行：两个公差为 2 * (n − 1) 的等差数列交替排列，首项分别是 i 和 2 * n − i − 2。解决方案为：模拟这个行索引的变化，在遍历 s 中把每个字符填到正确的行 res[i]。对于第一行和最后一行：公差为 2 * (n − 1) 的等差数列，首项是 i。对于本题，我们可以不失一般性的将规律推导为「首项」和「公差公式」。res[i] += c： 把每个字符 c 填入对应行 s_is。i += flag： 更新当前字符 c 对应的行索引；解法1（成功，7ms，较快）
2023-04-19 22:38:00
404
原创 Docker理论总结
开源的应用容器引擎，基于 Go 语言开发容器是完全使用沙箱机制,容器开销极低Docker就是容器化技术的代名词Docker也具备一定虚拟化职能docker文档。
2023-04-09 02:40:27
374
原创 Docker使用总结
132装的物理机，里面的tomcat容器端口8080，不能通过192.168.163.132:8080进行访问，需要进行端口映射，8000和8080进行映射，这样，192.168.163.132:8000即可访问，会转发给容器内部的8080端口。查看docker版本，能够看到是否安装成功，注意，里面会有docker客户端和服务端的信息，都安装了，默认客户端直连本机的服务端。脚本执行完毕，退出子shell，回到当前shell。查看当前运行的容器，可以看到tomcat的容器id，端口映射，最后执行的命令。
2023-04-09 02:38:24
1218
1
原创 Spring Cloud Nacos使用总结
重启Nacos服务，此时之前所创建的Namespace+Group+DatalD将全部消失，因为这些数据是保存在之前Nacos内嵌的derby数据库中，现在使用的是本地的MySql数据库，此时我们可以添加配置测试，在查看数据库nacos_config中的config_info表，此时就会有新添加的配置内容。`prefix` 默认为 `spring.application.name` 的值，也可以通过配置项`spring.cloud.nacos.config.prefix`来配置。这个就是负载均衡功能。
2023-03-26 23:13:54
1918
1
原创 Spring Cloud Nacos基础
官方网站home用户手册什么是 NacosNacos 致力于帮助您发现、配置和管理微服务。Nacos 提供了一组简单易用的特性集，帮助您实现动态服务发现、服务配置管理、服务及流量管理。相当于注册中心+配置中心Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。Nacos 是构建以“服务”为中心的现代应用架构(例如微服务范式、云原生范式)的服务基础设施。服务（Service）是 Nacos 世界的一等公民。Nacos 支持几乎所有主流类型的“服务”的发现、配置和管理。
2023-03-26 23:12:10
1461
原创 Dubbo集群容错负载均衡
服务路由其实就是路由规则，它规定了服务消费者可以调用哪些服务提供者，Dubbo 一共有三种路由分别是：条件路由 ConditionRouter、脚本路由 ScriptRouter 和标签路由 TagRouter。最常用的就是条件路由，我们就分析下条件路由。条件路由是两个条件组成的，是这么个格式[服务消费者匹配条件] => [服务提供者匹配条件]，举个例子官网的例子就是。
2022-11-19 22:22:16
339
原创 Dubbo服务调用过程
今天的调用过程我再总结一遍应该差不多了。首先客户端调用接口的某个方法，实际调用的是代理类，代理类会通过 cluster 从 directory 中获取一堆 invokers(如果有一堆的话)，然后进行 router 的过滤（其中看配置也会添加 mockInvoker 用于服务降级），然后再通过 SPI 得到 loadBalance 进行一波负载均衡。这里要强调一下默认的 cluster 是 FailoverCluster ，会进行容错重试处理，这个日后再详细分析。
2022-11-19 22:21:29
3254
原创 Dubbo的服务引用过程
相信分析下来整个流程不难的，总结地说无非就是通过配置组成 URL ，然后通过自适应得到对于的实现类进行服务引入，如果是注册中心那么会向注册中心注册自己的信息，然后订阅注册中心相关信息，得到远程provider的 ip 等信息，再通过netty客户端进行连接。并且通过directory和cluster进行底层多个服务提供者的屏蔽、容错和负载均衡等，这个之后文章会详细分析，最终得到封装好的invoker再通过动态代理封装得到代理类，让接口调用者无感知的调用方法。
2022-11-19 22:21:13
491
原创 Dubbo的服务暴露过程
总的而言服务暴露的过程起始于 Spring IOC 容器刷新完成之时，具体的流程就是根据配置得到 URL，再利用 Dubbo SPI 机制根据 URL 的参数选择对应的实现类，实现扩展。通过 javassist 动态封装 ref (你写的服务实现类)，统一暴露出 Invoker 使得调用方便，屏蔽底层实现细节，然后封装成 exporter 存储起来，等待消费者的调用，并且会将 URL 注册到注册中心，使得消费者可以获取服务提供者的信息。
2022-11-19 22:20:23
4654
原创 Dubbo的SPI机制
首先我们得先知道什么叫 SPI。SPI (Service Provider Interface)，主要是用来在框架中使用的，最常见和莫过于我们在访问数据库时候用到的接口了。你想一下首先市面上的数据库五花八门，不同的数据库底层协议的大不相同，所以首先需要定制一个接口，来约束一下这些数据库，使得 Java 语言的使用者在调用数据库的时候可以方便、统一的面向接口编程。数据库厂商们需要根据接口来开发他们对应的实现，那么问题来了，真正使用的时候到底用哪个实现呢？从哪里找到实现类呢？
2022-11-19 22:19:29
701
原创 Dubbo基础
RPC，Remote Procedure Call 即远程过程调用，远程过程调用其实对标的是本地过程调用，本地过程调用你熟悉吧？想想那青葱岁月，你在大学赶着期末大作业，正在攻克图书管理系统，你奋笔疾书疯狂地敲击键盘，实现了图书借阅、图书归还等等模块，你实现的一个个方法之间的调用就叫本地过程调用。你要是和我说你实现图书馆里系统已经用了服务化，搞了远程调用了，我只能和你说你有点东西。
2022-11-19 22:03:07
52752
原创 Kafka高级特性
可以通过实现 org.apache.kafka.clients.consumer.internals.PartitionAssignor 接口来实现。
2022-10-24 10:26:43
12570
原创 Kafka基础
kafka是一个流式数据处理平台，他具有消息系统的能力，也有实时流式数据处理分析能力，只是我们更多的偏向于把他当做消息队列系统来使用。消息系统：kafka与传统的消息中间件都具备系统解耦、冗余存储、流量削峰、缓冲、异步通信、扩展性、可恢复性等功能。与此同时，kafka还提供了大多数消息系统难以实现的消息顺序性保障及回溯性消费的功能。存储系统：kafka把消息持久化到磁盘，相比于其他基于内存存储的系统而言，有效的降低了消息丢失的风险。这得益于其消息持久化和多副本机制。
2022-10-24 10:24:43
11797
原创 ZooKeeper与Dubbo总结
ZooKeeper与集群与一致性协议总结。Zookeeper与统一配置管理。ZooKeeper基本概念总结。ZooKeeper与分布式锁。ZooKeeper实战总结。
2022-10-17 10:00:01
251563
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人