字典顺序

字典顺序,实际上就是一个递增的顺序。字典为 \(dic\) ,可以得到:\(dic[n] 将 \(dic[n]\) 记为 \(d_n\) , \(dic[n+1]\) 记为 \(d_{n+1}\) ,相邻的两个元素,可能存在前N位相同的项(N可以为0),我们将前N项去掉。得到 \(S_n\) 和 \(S_{n+1}\) 。 由于是递增顺序,显而易见: \(S_n[0] 。 由于 \(S_n\) 的下一项是 \(S_{n+1}\) ,所以 \(S_n[1:]\) 的所有元素无法排列出比现有更大的组合。 \(S_n[1:]\) 为递减排列(即能排列出的最大值)。 同样的道理, \(S_{n+1}\) 的上一项是 \(S_n\) ,所以 \(S_{n-1}[1:]\) 的所有元素无法排列出比现有更小的组合。 \(S_{n+1}[1:]\) 为递增排列。 如果能排列出来,那与“ \(S_n\) 的下一项是 \(S_{n+1}\) ”相冲突 对于 \(S_n[0]\) 和 \(S_{n+1}[0]\) ,除了已经知道的 \(S_n[0] 。还有另外一个规律: \(S_{n+1}[0]\) 为 \(S_n\) 所有元素中 \(S_n[0]\) 的下一项。(依然是因为 \(S_n\) 的下一项就是 \(S_{n+1}\) ) 所以,整体的思路是:...

March 12, 2021

Leetcode#45 Jump Game II

给定一个数组,从下标为0开始,往右跳,下标对应的值表示其能跳的最远距离。求最少X步,能跳到最后一个元素? 简单思路 最近看SICP看的比较多,第一个想到的办法,就是递归。 对于数组\([a,a_1...a_n]\),找到能跳到最后的最小下标\(m\) 对于数组\([a,a_1...a_m]\),找到能跳到最后的最小下标\(l\) …… 当最后数组长度为1的时候,说明已经到头了 func jump(nums []int) int { return jumpIter(nums, 0) } func findMin(nums []int) int { for i := 0; i < len(nums); i++ { if i+nums[i] >= len(nums)-1 { return i } } return len(nums) - 1 } func jumpIter(nums []int, count int) int { if len(nums) == 1 { return count } return jumpIter(nums[:findMin(nums)+1], count+1) } 改进 在上面的算法中,从左到右, 很多位置(\(i\))能达到的最远距离(\(nums[i]+i\)),都被计算了多次。 就算是每个位置的最远距离缓存/保存起来,迭代次数并不会减少。 改进的思路,依然是从左往右遍历func jump(nums []int) int { if len(nums) == 1 { return 0 } var limit, next, steps int for i := 0; i <= limit; i++ { //从左到limit if i+nums[i] > next { //更新最大的next next = i + nums[i] } if i == limit { //如果已经移动到了limit steps++ limit = next //从0-limit之间选出最远的next if limit >= len(nums)-1 { //如果current-limit之间的最远距离已经达到目标 break } } } return steps } 整理一下...

November 27, 2020

换零钱

用100元来换若干面值的零钱(1,5,10,25,50),有多少种兑换方式? 思路 定义一个函数\(f(amount,coins)\),用来计算使用coins来换amount的方案数量。很容易得到,分为两种情况 使用零钱A(至少使用1次A) 不使用零钱A 情况1,至少使用1次A,coins来兑换amount 等价于 至少使用0次A,coins来兑换(amount-A) 等价于 coins来兑换(amount-A) ,可以表示为 f(amount-coins[0],coins) 情况2,不实用零钱A,可以从coins中移除掉A,表示为 f(amount,coins[1:]) 得到如下等式: f(amount,coins) = f(amount-coins[0],coins) + f(amount,coins[1:]) 递归退出 当可供使用的零钱列表coins已经为空 还需要兑换的金额amount为0,说明该路径兑换成功 amount不为0,说明兑换失败 coins不为空 当需要兑换的金额amount为负数的时候,说明该情况下兑换已经失败了。 amount非负,继续兑换 代码 func change(amount int, coins []int) int { if len(coins) == 0 { if amount != 0 { return 0 } else { return 1 } } if amount < 0 { return 0 } return change(amount-coins[0], coins) + change(amount, coins[1:]) } (define (change amount coins) (cond ((= 0 (length coins)) (if (= 0 amount) 1 0)) ((> 0 amount) 0) (else (+ (change (- amount (car coins)) coins) (change amount (cdr coins)))))) 推广 这个思路也可以放到另外一个子集问题上,找到集合(无重复元素,即SET)的所有子集。很容易得到:...

November 22, 2020

函数加法

如果不允许使用数值,只能使用函数(过程)。现在已经定义好0和+1操作了。 如何表示1、2、3?如何实现加法? (define zero (λ (f) (λ (x) x))) (define (add-1 n) (λ (f) (λ (x) (f ((n f) x))))) 代换出1 显然,0+1=1 (define one (add-1 zero)) 把zero带入add-1 (λ (f) (λ (x) (f ((zero f) x)))) 对 ((zero f) x) 做代换,1就出来了 (λ (f) (λ (x) (f x))) 代换出2 显然,1+1=2 (define one (add-1 one)) 把one带入add-1 (λ (f) (λ (x) (f ((one f) x)))) 对 ((one f) x) 做代换,2就出来了 (λ (f) (λ (x) (f (f x)))) 代换出…… 显然是不用代换了,我们很容易猜测到,用f的调用次数来表示数的大小。...

November 1, 2020

斐波拉契优化

简单直接的思路 在斐波拉契数列找到上任意两个相邻的数 \(a\), \(b\) ,做如下变化 \[\left\{\begin{matrix}&a_1=b \\&b_1=a+b\end{matrix}\right. \] 得到的新 \(a_1\) , \(b_1\) ,实际上就是 \(a\) , \(b\) 沿着斐波拉契数列滑动一位的结果。 我们将这种变换记为 \(fib\) ,变化\(n\)次,记为\(fib(n)\) 当初始 \(a=0,b=1\) 时,\(fib(n)\)的 \(a\) 值,就是斐波拉契数列的第 \(n\) 位。 增加复杂度 我们设计一个新的变换方式 \(T_{p,q}\) ,此处的 \(p\) , \(q\) 为常量。 \[\left\{\begin{matrix}&a_1=a*p+b*q \\&b_1=a*q+b*p+b*q\end{matrix}\right. \] 当\(\left\{\begin{matrix}p=0 \\q=1\end{matrix}\right.\) 时。记为\(T_{0,1}\) \[\left\{\begin{matrix}&a_1=a*0+b*1 \\ &b_1=a*1+b*0+b*1\end{matrix}\right. \Rightarrow \left\{\begin{matrix}&a_1=b\\ &b_1=a+b\end{matrix}\right. \] 显然,此时的\(T_{0,1}=fib\) 猜测 我们猜想,存在这样的情况,对于任意的\(T_{p,q}\) 都能找到新的常量\(m\), \(n\) ,满足以下要求。 \[T_{p,q}(2)=T_{m,n}(1) \] 证明 对于一组值\(a\) ,\(b\) 使用\(T_{p,q}\) 进行2次变换 \[T_{p,q}(1)\left\{\begin{matrix}&a_1=a*p+b*q \\&b_1=a*q+b*p+b*q\end{matrix}\right. \] \[T_{p,q}(2)\left\{\begin{matrix}&a_2=a_1*p+b_1*q \\&b_2=a_1*q+b_1*p+b_1*q\end{matrix}\right. \] 简单替换之后 \[T_{p,q}(2)\left\{\begin{matrix}&a_2=(a*p+b*q)*p+(a*q+b*p+b*q)*q \\&b_2=(a*p+b*q)*q+(a*q+b*p+b*q)*p+(a*q+b*p+b*q)*q\end{matrix}\right. \]...

November 1, 2020

Leetcode#44 Wildcard Matching

*代表任意长度的任意字符 ?代表任意字符 需要实现这个匹配逻辑。现在有字符串s和匹配模版p,要求判断p是否能完全匹配s 思路 从左到由遍历p,可以这样匹配 如果该字符为固定字符,就能找到这个字符在s中的所有下标 如果该字符为*,匹配任意长度0-MAX 如果该字符为?,匹配任意长度1 优化一下 ** = * ⇒ 匹配长度 0-MAX *? = ?* ⇒ 匹配长度1-MAX ab ⇒ 满足s.indexOf(a)+1 = s.indexOf(b) a?b ⇒ 满足s.indexOf(a)+2 = s.indexOf(b) a???b ⇒ 满足s.indexOf(a)+4 = s.indexOf(b) a*b ⇒ 满足s.indexOf(a) ≤ s.indexOf(b) a?b = a?b ⇒ 满足s.indexOf(a)+1 ≤ s.indexOf(b) 除了*,其他字符串都是长度固定的,所以我们可以将p视为用*连接的多个子字符串 str1*str2*str3*str4 需要满足, s.indexOf(str1)≤s.indexOf(str2)≤s.indexOf(str3)≤s.indexOf(str4) len(str1)+len(str2)+len(str3)+len(str4) ≤ len(s) 再经过一点点小优化,就成了这样子: func isMatch(s string, p string) bool { isChar := true maybe := []int{-1} limit := 1 for i:= range p { switch p[i] { case '*': isChar = false case '?...

October 26, 2020

Leetcode#42 Trapping Rain Water

如图所示,蓝色区域就是☔️积水区,现在需要计算这个值。 思路 以最高的柱子P为终点,从左L向P移动。 如果L右边的柱子L2的长度低于当前L的高度,那么在该柱子上可以累积array[L]-array[L2]的雨水量 如果L右边的柱子L2的长度大于等于当前L的高度,那么,L-L2实际上已经形成了一个池塘了 从L2开始往右寻找池塘,直至找到P 找到P之后,就不能这样找了,因为右边不存在可以与P形成池塘的柱子。所以,从最右边往左找,思路和上面一致。 代码 func trap(height []int) int { var trap, i, j, t, maxIndex int for i = 0; i < len(height); i = j { t = 0 for j = i + 1; j < len(height); j++ { if height[j] < height[i] { t += height[i] - height[j] } else { maxIndex = j trap += t break } } } for i = len(height) - 1; i > maxIndex; i = j { t = 0 for j = i - 1; j >= maxIndex; j-- { if height[j] < height[i] { t += height[i] - height[j] } else { trap += t break } } } return trap } ...

October 22, 2020

Leetcode#41 First Missing Positive

寻找缺失的正整数,这个思路非常有趣,将数组中的每个正整数都放在其自然顺序的下标位置中。即下标为0的放1,下标为1的放2,下标为2的放3……,重复的数和负数都不用理会,经过这么一番整理之后。数组应该看起来是这样的。 #x代表不等于其下标+1的值 #-代表任意值 1 2 3 4 x - - - #缺少5 x - - - - - - - #缺少1 1 2 3 4 5 6 7 8 #缺少9 #实际上,就是找出第一个不等于下标+1的值 代码如下 func firstMissingPositive(nums []int) int { size := len(nums) if size == 0 { return 1 } var index = 0 for index < size { value := nums[index] orderShouldBe := value - 1 //正数 && 小于等于长度 && 不在应该在的位置 && 应该在的位置不是现在的值 if value > 0 && value <= size && index !...

October 16, 2020

ThoughtWorks 1

我是2018年年底加入ThoughtWorks,招聘的原因在事后看来也很有意思,某大公司的某部门年底预算用不完,需要找点事做,所以就起了一个项目,TW就为这个项目招了一批人。 这个项目是一个大杂烩项目,把所有能揉在一起的应用都揉在一起。第一次去客户现场是和另一个后端同事,当时是去商量两个模块,A和B,出发之前商量是两个人一起做两个模块。去了之后,就是和第三方的vendor讨论接口,实际上就是甩活,看你如何把一些脏活累活扔给对方,这点恰恰是我的强项,但是我是个新人,所以第一轮商讨的时候,主力是另外一位同事,一轮谈下来,我就和同事商量:“要不这个B你做吧,我做A就好了……”,不得不说,和第三方打交道不强硬就等于吃亏。 于是我就开始了A开发,我在SMZDM没有参与业务开发长达两年,在TW的第一个项目,依然是没有开发任务,天天嘴炮,说服前端接受API,说服上游vendor修改接口。在这个过程中,被灌输了BFF和Contract Testing这两个概念。 契约测试,这个是一个美好的理念,蹩脚的实现,残酷的现实。 BFF,一次性代码,帮前端包鸡包眼的代名词。 到了项目后期,IM的同事下项目,我接手,和第三方对接,这个时候,历练和成长才由此开始。 与第三方无止境的扯皮。 讨论的时候:这个接口调一下就行了! 第二天实施:你们先调用A,再调用B,然后把xxx弄一下,不就行了吗? 讨论的时候:好的,没问题,那我们就这么改。 第二天实施:我们没答应,我的原意是回去研究下,我们研究结果是不可行…… 与此我也总结出了许多“经验”: 不在客户面前说没把握的事 只说事情的表现,不帮第三方去猜原因 保留证据,并引导第三方犯上面的错 不要一次性要求第三方解决N个问题,选择一个,咬住不松口 多发问,少解释。除非是客户问你bug的原因,你能甩给第三方,但也要注意前面说的,不要去猜测第三方的原因。 项目后期就非常无趣了,没写代码没实际产出物被diss,小组效率被质疑,BA夹在小组和PM之间为难…… 2019年5月,我下了这个项目。 小插曲 在on beach了一个多月之后,某天被RM拉过去“北京的TP点名要你上O项目,和他一起balabala”,同时也从Buddy口中听到了类似的声音。当时的我受宠若惊,TP,什么概念。上了O项目,才发现,原来不是这样,O项目想上契约测试,TP便问了之前项目的一个TL,得知我做过契约测试,并且处于on beach状态,就让我过去了。这个事情不知道怎么就变成TP点名要我了。扯淡的很。 反正上了O项目一周,我就主动要求下项目了,原因很简单 不喜欢写测试 尤其不喜欢契约测试 更加不喜欢帮别人写测试 更加更加不喜欢帮别人写契约测试 和PM说了之后,最开始是想在该Account下其他项目做,但是应该是我这种“刺头”没人愿意要,我便再次回到了on beach的状态。 ...

January 1, 2020

ThoughtWorks 2

在告别了上一个项目之后,公司迎来了组织架构变动,之前项目的同事找到我,问我愿不愿意以后分到华东,我当然无所谓啊,于是就答应了。然后持续了很久“下周上项目”(预定人),最后还是上了I项目,这个项目还挺像小公司的项目的,算半个从无到有,不停的推导重建。 入场的时候,再次提到了这是一个BFF,我心目中的BFF,是简单的/薄薄的一层,路由分发,接口聚合,数据mapping。显然,我认为和TW认为还是有差距的,公司的BFF就是在其他系统的API上堆砌出一个项目。 技术选择 Kotlin Spring Boot + Webflux + Reactor Mongodb + Redis 我觉得整体的选择还是挺不错的,这个项目最大的收获可能就是对Reactor的一系列了解了。 代码整体风格 这个项目做的事情其实特别简单,但是实现上真的是“非常Java”,这儿我又得黑一下Java了,我喜欢Kotlin,也喜欢Java,但是这个圈子真的是太老了。开口闭口就是分层,模块,内聚,耦合…… 一个6000行代码能搞定的事情,非得拖到16000行。 DDD 然后整体的结构是按照所谓的DDD来进行划分的,其实我不懂DDD,我也没有什么动力去深入了解DDD,可能有人会说,你对一个东西都不了解,怎么能下结论呢?道理其实很朴素。 当一个所谓的设计思路,设计理念,不能清晰,浅显地向他人解释解决了什么问题,带来了什么好处。那么我们可以认为这个玩意儿基本不会有任何好处,只是一个商业卖点而已。原因也很简单,这个思路,理念,都是需要人来落地的。 测试 由于这是我进TW第一次写代码,所以也体验到了写测试的“快感”,整体感觉也是偏负面的,怎么说呢,有点用,但又没啥屁用。这儿就不展开了,一句话:把底层全部mock掉之后的测试,只有面子上好看。 Ops 这次算是做了一次Devops,我还是对自己挺满意的。Ansible,Jenkins pipeline、Jenkins plugin develop、Gradle kts。基本上都碰了一遍,总体而言,都挺简单的。 比较可惜的是没有上Docker,K8s之类的,要不然我会更开心。😃 Other 其他方面,先来吐槽吧。 开发水平参差不齐,水平烂而不自知。这个是纯主观体验。还有就是理论大师,实现菜🐔。 BFF端地位低下,这是我长达3年的职业生涯里没有遇到过的。完全被前端牵着走。 项目管理不够实诚,从上项目之前的“永远下周上”,初期的的长时间shadow,到后期下项目之后让人待定。都有一种揩公司油的感觉。当然,这个跟我没什么利益冲突,我只是单纯觉得不太符合公司的调性。 最终我的解决方案都是 随便吧 我觉得都可以 那就这样吧 不得不说,在外包公司真的是很容易让人接受一切,毕竟都不是自己的项目。可能是没有产品的荣誉感? 我走后,哪管它洪水滔天 再说优点吧,同事关系比较融洽,轻松😉。体验了一些新玩意。 不过话说回来,我是一个负能量爆表的人,只要是我不吐槽的点,基本都是很不错的点。 后记 很难想象,这是我在TW工作最开心的一段经历了,甚至测试/敏捷实践,我也是从这个项目中从“完全没用”到“还有一点用”的想法转变。...

January 1, 2020