Posts

最大矩形 题目描述 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。 示例 1： 输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] 输出：6 解释：最大矩形如上图所示。 示例 2： 输入：matrix = [] 输出：0 示例 3： 输入：matrix = [[“0”]] 输出：0 示例 4： 输入：matrix = [[“1”]] 输出：1 示例 5： 输入：matrix = [[“0”,“0”]] 输出：0 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximal-rectangle 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 对于每个单元格，维护从上往下的连续的1的个数 遍历所有单元格，对于每个单元格，计算从左往右的连续的1的个数作为长，再从下往上遍历该列，以列的步数作为宽，维护长取最小值，求面积维护答案 code func maximalRectangle(matrix [][]byte) int { for i := 0; i < len(matrix); i++ { for j := 0; j < len(matrix[i]); j++ { matrix[i][j] = matrix[i][j] - 48 } } // 维护行上的连续1的个数 for i := 0; i < len(matrix); i++ { for j := 1; j < len(matrix[i]); j++ { if matrix[i][j] !...

分割数组的最大值 题目描述 给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法使得这 m 个子数组各自和的最大值最小。 示例 1： 输入：nums = [7,2,5,10,8], m = 2 输出：18 解释： 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。 示例 2： 输入：nums = [1,2,3,4,5], m = 2 输出：9 示例 3： 输入：nums = [1,4,4], m = 3 输出：4 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/split-array-largest-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 对数组维护前缀和 二分枚举答案，对于每个答案，二分查找区间和划分验证 code func splitArray(nums []int, m int) int { // 特殊处理 if len(nums) == 1 { return nums[0] } var l, r int var ans int = 0 // 维护前缀和数组 sum := make([]int, len(nums)+1) for i := 0; i < len(nums); i++ { l = max(l, nums[i]) r += nums[i] sum[i+1] = sum[i] + nums[i] } // 特殊处理 if m == 1 { return sum[len(sum)-1] } ans = sum[len(sum)-1] // 二分枚举答案 for l < r { mid := l + (r-l)/2 k, last := 0, 0 ok := true isans := true for k < m { // 二分查找区间和划分 p := sort....

和为K的子数组 题目描述 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1 : 输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。 说明 : 数组的长度为 [1, 20,000]。 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/subarray-sum-equals-k 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 思路 思路一： 前缀和，枚举 做一次前缀和，对于第i个数，枚举子数组nums(j,i)，其中j<i 复杂度O(n^2) 思路二： 前缀和，hash 做一次前缀和，并且把前缀和的值保存到hash中记次数 对于目标整数k，可以表示为k=sum(j)-sum(i)，其中i<j，因此sum(i)=sum(j)-k 对于第j个数，查找sum(i)=sum(j)-k在hash中的次数，累加即为结果 例如1，2，3，4，5；目标数k=9 前缀和为1，3，6，10，15； 当j=3时（下标以0开始），sum(i)=sum(3)-k=10-9=1，因此需要找到数组中前缀和为1的次数，为1 当j=4时，sum(i)=sum(4)-k=15-9=6，因此需要找到前缀和为3的次数，为1 因此结果为2 code func subarraySum(nums []int, k int) int { sum :=make([]int,len(nums)+1) cnt :=make(map[int]int,len(nums)+1) var ans int cnt[0]++ for i:=0;i<len(nums);i++ { sum[i+1]=sum[i]+nums[i] ans += cnt[sum[i+1]-k] cnt[sum[i+1]]++ } return ans }

第12章 TCP传输控制协议 12.1.1 通信消息差错的解决办法： 差错校正码 自动重传请求ARQ 12.1.2 重传和重复 重传 处理分组丢失和错误分组的办法是重传分组直到正确接收。发送方发送分组后，等待一个ACK，接收方发送ACK来确认自己收到分组。 可能出现的问题： 发送方等待多长时间ACK ACK丢失 分组收到但出错 重复 在分组中携带序列号，接收方通过序列号判断该分组是否重复 12.1.2 滑动窗口 分组窗口：已发送但还未收到ACK的分组集合 滑动窗口：对于上图中，当收到分组4的ACK后，窗口向右滑动，表示分组7可以被发送 12.1.3 窗口控制 流量控制：当接收方慢于发送方时，控制发送方降低发送速率。 两种方法： 基于速率：指定发送方的发送速率，发送方发送速率不会超过该值 基于窗口：接收方动态调整窗口大小以通知发送方发送速率 拥塞控制：发送发减低速率以保证不会压垮与接收方之间的网络 12.1.4 超时重传 如何设置超时重传的时间？ 统计分组的往返时间，取稍大于平均值。 12.2.1 TCP模型 tcp提供面向连接的，可靠字节流服务 面向连接：tcp在进行数据交互之前，需要建立TCP连接。 字节流：UDP是面向报文的，即应用层交付多长报文，UDP照样发送。TCP面向字节流，即TCP将应用层交付的数据看成无结构的字节流，当发送时，会维护缓冲区，如果交付的数据太长，则划分为多段多次发送；如果交付数据太短，则等待累计到足够的字节再发送。由于TCP会拆分或累计，则会导致数据是没有边界的，当缓冲区够大，可能一次性收到发送方发送的多段数据，这也是TCP拆包和粘包出现的原因。 12.2.2 TCP可靠性 序列号：表示每个分组的第一个字节在整个数据流中的字节偏移。比如序列号为301，该报文共100个字节，则表示该报文第一个字节序号为301，最后一个为400，且下一个分组的序号应为401。 检验和：包括头部、应用数据、IP头部字段。对于无效的校验和，接收方丢弃该报文，不发送ACK。 重传计时器：为一个窗口设置一个重传计时器，当ACK到达时更新。 ACK：累积确认，指示字节号N的ACK表示所有直到N的字节都收到。 12.2.3 TCP头部和封装 IP数据报封装： TCP头部： 头部特殊字段： URG：紧急 ACK：确认，在连接建立后通常开启 PSH：推送，未使用？ RST：重置连接，连接取消 SYN：初始化序列号，通常是随机选择的 FIN：发送方结束发送 第18章 TCP的连接与终止 18.2 连接的建立与终止 建立连接： 客户端发送SYN报文段，并随机生成初始序号。图中为1415531521 服务端发送SYN报文段，并随机生成初始序号，确认号设置为客户端的SYN+1。图中SYN为1823083521 客户端发送ACK报文段，确认好设置为服务端的SYN+1。 对于初始序号的选择，随机生成，每隔4ms+1。目的是防止在网络中被延迟的分组重传后，接收方做出错误的处理。 终止连接： 由于TCP是全双工，即支持数据在两个方向上流动的，发送一个FIN仅代表着这个方向上没有数据流动，因此终止连接时，每个方向都必须单独关闭 客户端发送FIN报文段，主动关闭 服务端发送ACK报文段，确认号为客户端FIN序号+1 当服务端发送FIN报文段 客户端发送ACK报文段，确认号为服务端FIN序号+1 连接超时： 在ubuntu中查看系统变量...

GC 版本迭代 v1.1 STW v1.3 Mark STW v1.5 三色标记 v1.8 混合写屏障 三色标记 不变性条件，写屏障 如何标记，gcmarkerbits，0表示白色对象，1表示灰色或黑色对象。p中wbBuf和gcw以及全局workbuf来表示标记队列 对象元信息，查找到对象分配内存的span gc触发时机 分配内存时，当前已分配内存与上次内存比较 sysmon每2min检查执行一次 调用runtime.gc强制执行 三色标记 传统的标记-清除需要长时间STW以完成标记和清扫的过程，三色标记用于改进减小STW的时间。 三色标记中将对象分为三种类型： 白色：可能存活的对象，在初始阶段所有对象为白色，在标记完成后，所有的白色对象视为垃圾 灰色：确认存活的对象，但其引用了白色对象，因此要对灰色对象进行递归扫描 黑色：确认存活的对象，扫描完成的对象，根对象可达 三色标记过程： 初始时所有对象为白色 将根对象标记为灰色，根对象包括运行栈中的对象以及全局对象 对所有灰色对象进行扫描，将灰色对象引用的对象标记为灰色，并将该灰色对象标记为黑色 重复上述过程，直到没有灰色对象 标记结束后，程序中只有黑色对象和白色对象，黑色对象为确认存活的对象，白色对象为垃圾 三色不变性 当三色标记的标记过程是STW时，可以确保标记过程的正确性，但STW要消耗大量时间。但如果将三色标记的标记过程和用户代码并发执行，则可能出现对象丢失. 三色标记正确性被破坏，如下图，B对象本不该回收的对象，由于引用的改变，导致其被回收了。 图来自https://golang.design/under-the-hood/zh-cn/part2runtime/ch08gc/barrier/ 使得三色标记正确性被破坏的两个条件： 黑色对象引用了白色对象 灰色对象达到白色对象的未访问过的路径被破坏，即黑色对象引用的白色对象，但灰色对象无法找到一条路径到达该白色对象 当上述两个条件同时满足时，三色标记就可能丢失对象。 想要使得三色标记正确，就必须破坏上述条件中的任意一个条件，因此三色标记不变式： 强三色不变式：黑色对象不能指向白色对象，只能指向灰色或黑色对象。该不变式破坏了两个条件。 弱三色不变式：黑色对象执行的白色对象，必须存在一条从灰色对象经过零个或多个白色对象可达该白色对象的路径。 屏障 Dijkstra插入写屏障 当某一对象的引用被插入到已经标记为黑色的对象中，需要将其标记为灰色对象。 将有存活可能的对象标记为灰色，以满足强三色不变式。 // Dijkstra 插入屏障 // slot表示旧指向的对象，ptr表示新指向的对象 func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) { // 将新指向的对象标记为灰色 shade(ptr) *slot = ptr } 特点： 可能产生部分黑色对象的垃圾，需要在下一次GC中回收 对于栈上的对象，使用插入写屏障后耗费大量性能，因此不在栈上开启插入写屏障。 由于在栈上不开启插入写屏障，因此当栈上的黑色对象指向了白色的对象时，因为没有屏障，因此白色对象会被错误回收。因此插入写屏障在标记结束后，会STW并再次重新扫描栈。 Yuasa删除写屏障 起始时，STW将整个栈的可达对象标记为黑色，将所有可达对象在灰色保护下...