Sa1L

昨天尝试解决 leetcode 周赛题，发现第二题有点意思，但是想了半天没想到解决方式。阅读题解时了解到有一个算法很适合解决这个问题，叫 Z 函数（扩展 KMP），听大佬讲解没听明白，只能多去查查资料，花时间去理解，最后看了几遍代码才明白 Z 函数是编写逻辑和用法。以下来梳理一下 Z 函数（扩展 KMP） 定义和设计思路直接去OI看,以下是 Z 函数的 golang 实现 // Z-function func calculateZFunction(s string) []int { length := len(s) z := make([]int, length) // 初始化两个变量 left 和 right，表示当前 Z 值已经计算出来的区间的左右边界 left, right := 0, 0 for i := 1; i < length; i++ { // 如果当前字符在已经计算出来的 Z 值区间内，那么可以直接得到它的 Z 值 if i <= right { z[i] = min(right-i+1, z[i-left]) } // 通过比较字符来计算 Z 值 for i+z[i] < length && s[z[i]] == s[i+z[i]] { z[i]++ } // 更新 Z 值已经计算出来的区间的左右边界 if i+z[i]-1 > right { left, right = i, i+z[i]-1 } } return z } 以下是解决3029....

练习动态规划解题时，碰到一个题可以以很巧妙的数学计算解决，写个文档记录下。 题是leetcode.62 不同路径，要求算出一个 m*n 的网格中从左上角格子到右下角格子的路径总数。正常解法是动态规划，从第一个格子开始计算有多少个路径，再依次向下计算。这题也可以使用数学的计算方法二项式系数解决. 概念和在线计算工具： 二项式系数概念 二项式系数计算器 二项式系数计算解法： // binom 计算二项式系数，即从n个元素中不重复地选择k个元素的方式数。 func binom(n int, k int) int { if k == 0 { // 递归的基础情况：C(n, 0) 总是等于 1。 return 1 } // 递归情况：基于前一个值（将 k 减 1）来计算，并根据选择第 k 个元素的方式数进行调整。 return (n - k + 1) * binom(n, k-1) / k } // uniquePaths 计算从 m x n 网格的左上角到右下角的唯一路径数， // 限制条件是你只能向下或向右移动。 func uniquePaths(m int, n int) int { // 需要的总移动次数是向下 (m-1) 次和向右 (n-1) 次，总共 (m+n-2) 次移动。 // 我们使用 binom 函数来计算这些移动组合的唯一方式数。 // 使用 min(m-1, n-1) 来优化计算，利用组合数的性质 C(n, k) = C(n, n-k)。 return binom(m+n-2, min(m-1, n-1)) } 正常动态规划解法： func uniquePaths(m int, n int) int { // 初始化动态规划数组 dp := make([]int, n) // 将数组的每个元素初始化为1 for i := 0; i < n; i++ { dp[i] = 1 } // 从第二行开始，计算每个格子的路径数 for i := 1; i < m; i++ { // 从第二列开始，计算每个格子的路径数 for j := 1; j < n; j++ { // 当前格子的路径数等于上方格子的路径数加左方格子的路径数 dp[j] += dp[j-1] } } // 返回最后一个格子的路径数 return dp[n-1] } //该算法的时间复杂度为O(m*n)，空间复杂度为O(n)。

并查集 定义 并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。 顾名思义，并查集支持两种操作： 合并（Union）：合并两个元素所属集合（合并对应的树） 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合 定义来源：https://oi-wiki.org/ds/dsu/ 链接里包含并查集在C++和python的实现，以下为golang实现方式 实现 type UnionFind struct { parent []int //根节点记录数组，下标为子节点，值为根节点下标 size []int //子集中数量，可以按需设计，比如改成height } //初始化并查集 func NewUnionFind(n int) *UnionFind { parent := make([]int, n) size := make([]int, n) for i := 0; i < n; i++ { parent[i] = i size[i] = 1 } return &UnionFind{parent: parent, size: size} } //向并查集放入新关系 func (uf *UnionFind) Union(u, v int) { rootX, rootY := uf.Find(u), uf.Find(v)//查找要关联的两个节点的根节点 if rootX == rootY { //一致表明添加过，所以不再重新添加，size也不用更新 return } if uf....

Algo array/list/slice 宁缺毋滥，只记复杂逻辑 两个全排列 func SliceUltimate() { demoSlice := []int{1, 3, 3, 2, 4} toDESC_next_permutation(demoSlice) toDESC_next_permutation(demoSlice) toDESC_next_permutation(demoSlice) toASC_next_permutation(demoSlice) toASC_next_permutation(demoSlice) toASC_next_permutation(demoSlice) //true [1 3 3 4 2] //true [1 3 4 2 3] //true [1 3 4 3 2] //true [1 4 2 3 3] //true [1 3 4 3 2] //true [1 3 4 2 3] } // 从最小到最大排列的一下排列 func toDESC_next_permutation(target []int) bool { n := len(target) i := n - 2 for i >= 0 && target[i] >= target[i+1] { i-- } if i < 0 { return false } j := n - 1 for j > i && target[j] <= target[i] { j-- } target[i], target[j] = target[j], target[i] for k, l := i+1, n-1; k < l; k, l = k+1, l-1 { target[k], target[l] = target[l], target[k] } return true } // 从最最大到最大排列的一下排列 func toASC_next_permutation(target []int) bool { n := len(target) i := n - 2 for i >= 0 && target[i] <= target[i+1] { i-- } if i < 0 { return false } j := n - 1 for j > i && target[j] >= target[i] { j-- } target[i], target[j] = target[j], target[i] for k, l := i+1, n-1; k < l; k, l = k+1, l-1 { target[k], target[l] = target[l], target[k] } return true }

评价人才的时候，只需要识别他特殊能力的一面，不需要全面评价一个人。 如何管理员工 第一，要树立企业目标，有一个整体方向，把员工凝聚起来。 第二，整个公司要有清晰的流程体系，研发、财务、供应链等各方面都要有。 第三，分配向劳动者倾斜。华为的财富在员工的脑袋里面，所以劳动分配四分之三，资本分配四分之一。 教育就是培养一个人。受培养和不受培养，人是不一样的。 每个人都有自学的能力，但还需要受到良好的培养。“自培"和"他培"要结合起来，不要同质化培养，要因才施教。 新加坡立国时，李光耀定了两个最重要的政策。一个是确定了官方语言为英文，连接了一个非常大的世界；另一个是确定了发展汉语，准确来说是发展普通话和简体字，这样就把两个大世界都连起来了。 我们要学习他，为了发展自己，连接更大的世界。（这一句不是任总说的，是我加上的。） 他说了一段话，发人深思。 “新人企业家的常见错误，就是认为结果是可预测的。如果我长期努力工作，就应该会得到某种成果。” “实际上，你的成果是不可预测的。你工作多么努力并不重要，重要的是你在做什么、与谁一起工作、以及在哪里工作。 " 他的意思是，很多人有一个思维误区：他们认为"努力"与"成果"是正比例关系，工作越努力，越可能获得好成果。 实际上根本不是这样，努力与成果之间，没有必然关系。 “你每天都会看到，那些赚最多钱的人，工作时间根本不长。而淘金者和商铺老板，努力工作一天，赚不到什么钱。 " 原因在于，现实世界是非线性的、非因果的，而人的思维是线性的、因果关系的，会不知不觉从单一的线性因素，去解读非线性关系。 举例来说，银行存款是线性的，存款越多，利息越多；股票是非线性的，投资多，可能回报多，也可能亏得多。我们不应该把存款的逻辑，用在股票市场这样的非线性系统。 你不断加大努力的程度，长时间工作、长期加班、没有个人生活，会带来成功吗？很可能不会，因为两者之间没有因果关系。 纳瓦尔的建议是： “重要的不在于你的努力程度，而在于仔细选择工作、人员和项目。” “真正有效的工作方式，不是铁人三项或马拉松，比拼谁坚持的时间长，而是短跑，当机会来临的时候冲刺，平时注意健康和休息。” “你要像狮子一样，看到猎物一跃而起，而不要牛一样，从早到晚劳作。” 不要在疲劳的时候写代码。敬业和专业精神，更多地体现在你的纪律性，而不是体现在投入的时间。 网页设计师的一个巨大错误，就是以为用户会仔细阅读页面。但是实际上，用户不阅读，只是扫描页面。 因为大多数用户只想完成某件事，而且是快速完成，不想了解任何不必要的内容。 长期计划属于臆测，没有人能够未卜先知。篇幅庞大的计划书最终都会成为文件柜里的化石。 你只需要决定这周要做什么，找出下一项最重要的任务，然后去做，不必去管全年计划。 无计划地工作看上去挺悬，但是盲目遵循不切实际的计划，后果更糟糕。 我做出创业产品后，最大的错误是在 Twitter、LinkedIn 和 Instagram 上发布演示，来寻找用户。 这好比在街道中央尖叫，以引起人们的关注。有时人们可能会停下来参与其中，但大多数情况下，这是没有效果的。 我经常看到人们不断寻找最好的笔记 App、最好的 Linux 发行版、提高生产力的最佳 AI 软件、最好的游戏引擎…… 这样做并不会提高你的效率，你永远找不到最好或最完美的设置。我的建议是，只要一样东西足够好、能完成工作，你就不妨坚持用下去。不要盯着工具，而要盯着你要完成的工作。 伟大的想法是锻造出来的，而不是创造出来的。没有完美的想法，所以不要想太多。只需选择一个想法，然后根据用户反馈不断改进它。 Ideas are cheap, execution is everything. Ideas can be pitched succinctly in one sentence: we help [x-type of people] do [what] so that [why]. 可以用一句话简洁地表达想法：我们帮助[x 类型的人]做[什么]，以便[为什么]。...