三叉树求最大路径和
二叉树的最大路径和
LeetCode 124.二叉树的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
输入：root = [-10,9,20,null,null,15,7]输出：42解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
代码实现：
class Solution { int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } public int maxGain(TreeNode node) { if (node == null) { ...
Kafka学习之路
架构
Producer：消息⽣产者，向 Kafka Broker 发消息的客户端。
Consumer：消息消费者，从 Kafka Broker 取消息的客户端。Kafka支持持久化，生产者退出后，未消费的消息仍可被消费。
Consumer Group：消费者组（CG），消费者组内每个消费者负责消费不同分区的数据，提⾼消费能⼒。⼀个分区只能由组内⼀个消费者消费，消费者组之间互不影响。所有的消费者都属于某个消费者组，即消费者组是逻辑上的⼀个订阅者。
Broker：⼀台 Kafka 机器就是⼀个 Broker。⼀个集群(kafka cluster)由多个 Broker 组成。⼀个 Broker 可以容纳多个 Topic。
Controller：由zookeeper选举其中一个Broker产生。它的主要作用是在 Apache ZooKeeper 的帮助下管理和协调整个 Kafka 集群。
Topic：可以理解为⼀个队列，Topic 将消息分类，⽣产者和消费者⾯向的是同⼀个 Topic。
Partition：为了实现扩展性，提⾼并发能⼒，⼀个⾮常⼤的 Topic 可以分布到多个 Broke ...
波形排列的字符串
题目描述
输入一个宇符串s和正整数numRows，对宇符串s按规则进行波形排列，然后按规则输出新的宇符串。
波形排列规则如下：
1.波峰和波谷的宽度固定为3;
2.波形高度为rowNums;
3.从左到右，从下到上排列rowNums个宇符，从在到右排列3个宇符，从下到上rowNums个字符，以此类推。
宇符串输出规则：
从上到下逐行读取，每行从左到右读取。
例如，输入“ABCDEFGHIJKLMNOPQ”3,则排列形状如下： E F G M N O D H L PA B C I J K Q输出"EFGMNODHLPABCIJKQ"
代码实现
class Solution{ public String convert(String str, int numRows){ int len = str.length(); if(len < 3)return str; int i = 0; String[] waves = new String[ ...
LeetCode 59.螺旋矩阵II
螺旋矩阵II
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
输入：n = 3输出：[[1,2,3],[8,9,4],[7,6,5]]
方法：模拟
算法思路：
定义当前上下左右边界t,b,l,r，初始值num = 1，迭代终止值tar = n * n；
按顺序填入空矩阵，填完一条边时，边界要收缩。
以num <= tar作为循环条件，而不是l < r || t < b，以防n为奇数时，矩阵中心数字无法填充。
代码实现：
class Solution { public int[][] generateMatrix(int n) { int[][] ans = new int[n][n]; int l = 0, t = 0, r = n - 1, b = n - 1; int tar = n * n; int num = 1; while(num <= tar){ ...
邻接表
邻接表
形如1一>3这样的式子是推导式，说明结论1可以推导出结论了。
显然这样的推导式具有传递性：
如果1一>3且3一>5，那么肯定满足1一>5。
现在给出n个推导式，你需要输出结论C能够推导出多少个不同的结论。
显然任何结论都可以推导出自己。
输入描述：第一行输入两个整数n和c，含义如题意所述。接下来n行，每行输入两个整数x，y，表示一个推导式x->y，可能会出现重复的推导式。（1 <= n <= 10^5)，（1 <= x,y,c <= 10000）输出描述：输出一个整数，表示结论c能推导出的不同结论的数目。示例1:输入：5 11 21 33 94 28 1输出：4说明：根据推导式1一>2，1一>3，3一>9，可以判断出结论1可以推出结论2，3，9，加上本身总共4个结论。
代码实现
算法思路：
建立哈希表edges，记录每个数字所能推导的结论。
建立队列que，记录起始结论以及后续推导出的结论。
建立HashSet集合res，记录最终答案。
建立哈希表，去除重复，以防循环推导。
import java. ...
LeetCode 28.实现strStr()
实现strStr()
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
输入：haystack = "sadbutsad", needle = "sad"输出：0解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。
方法：KMP算法
算法思路：
构建next数组。next数组是前缀表，记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。
int i = 1; //i，j两个指针int j = 0;int[] next = new int[n];while (i < n) { if (needle.charAt(i) != needle.charAt(j) && j != 0) { j = next ...
卷积运算
卷积运算
卷积神经网络使用卷积操作来提取特征，卷积一般包含以下几个概念：
输入：一个m∗nm*nm∗n大小的矩阵，是一个二维数组，是图像的数据信息。
卷积核：一个k∗lk*lk∗l大小的矩阵，是一个二维数组，kkk，lll为奇数，保证卷积核有一个中心。
卷积操作：将卷积核的中心对准输入的某个元素，两个矩阵的重合区域中的对应元素相乘后求和，得到输出数组中对应元素的数据。
输出：将卷积核滑动过程的卷积结果按照顺序放入一个二维数组中，即图像卷积的输出。
滑动步长：卷积核每次滑动的距离，本题中为1。
本题中，当输出中元素小于0时要变更为0，当输出中的元素大于255时要变更为255。
输入：第一行为M、N、K、L，后为图像矩阵和卷积矩阵。5 6 3 31 1 1 1 1 11 2 2 2 2 12 3 3 1 2 21 2 2 3 4 55 6 6 6 3 41 10 11 20 11 8 1输出：31 41 42 42 41 3152 84 84 69 74 5165 107 109 79 106 9891 137 139 138 145 161118 154 157 165 118 1 ...
Redis学习之路
redis
基本概念：Redis（Remote Dictionary Server），即远程字典服务，是基于内存的（Mysql基于硬盘），Key-Value数据库，是NoSQL（非关系型数据库）。
支持的数据类型
Key仅支持String类型，而Value支持多种类型：
String：采用类似数组的形式储存。
List：双向链表实现。
Hash：基于拉链法实现，储存时将index和00000011相与，去最后两位，以防超出限制。
Set：不重复的集合。
Sorted Set：多了一个权重参数score，集合内元素能够按score进行排列。
持久化
RDB（Redis DataBase）：把目前redis内存中的数据，生成一个快照（RDB文件），保存在硬盘中，如果发生事故，redis可以通过RDB文件，进行文件读取，并将数据重新载入内存中，是一种全量备份。
可手动触发（save命令、bgsave——会fork一个子进程去执行）
可自动触发（配置文件写入save m n，代表m秒内发生n次变化，会自动执行bgsave）。
AOF：记录之后所有对redis数据进行修改的 ...
LeetCode 494.目标和
目标和
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
输入：nums = [1,1,1,1,1], target = 3输出：5解释：一共有 5 种方法让最终目标和为 3 。-1 + 1 + 1 + 1 + 1 = 3+1 - 1 + 1 + 1 + 1 = 3+1 + 1 - 1 + 1 + 1 = 3+1 + 1 + 1 - 1 + 1 = 3+1 + 1 + 1 + 1 - 1 = 3
0 - 1背包
算法思路：
要使表达式结果为target，可将式子分为加法部分plus和减法部分neg，根据neg = sum - plus和plus - neg = target可得，plus = (target + sum) / 2。问题就转化为 ...