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

Reactor进阶功能

进阶功能和概念 操作符组合 为了让代码简洁,增加复用性,Reactor提供了一些模式来达到这些目的。操作符组合就是其中一种。 transform 就是将一部分操作链作为一个函数嵌到另一个publisher的操作中。 transform的函数在组装的时候就被调用,确定好操作链。 对于不同的订阅者来说,是同一个操作链。 compose 达到的效果和transform差不多,区别在于,compose的函数会在每次订阅的时候都被调用,实际上可以产生不同的操作链。 热源与冷源 冷源:如果没有被订阅,不会有操作发生(不会触发产生数据的操作) 热源:不管是否有订阅,都会立马开始有操作产生(产生数据) 在热源的某些情况下,后面订阅的订阅者只能收到它订阅之后产生的新元素。 just: 在组装的时候,直接获取值,并且重放给所有的订阅者 defer:可以将just转换成一个冷源,每次订阅都会触发其包装的请求 ConnectableFlux:广播到多个订阅者 将数据生成的操作推迟到订阅者的订阅时,可能不是我们需要的,我们更希望多个订阅者集合,然后触发订阅和数据生成。 publish,动态的将下游的请求转发到上游(回压),如果有一个下游(订阅者)的需求为0,那么就会停止对上游的请求。 replay,从第一个订阅者开始缓冲数据,可以配置时间、数量 ConnectableFlux提供了额外的函数来管理订阅者对上游源头的请求。 connect,手动的触发对上游源头的订阅 autoConnect(n),订阅者达到n之后,自动向上游订阅 refCount(n),当没有足够的订阅者的时候,会断开和上游的请求。当达到足够的订阅者数量的时候,会重新产生一个新的订阅到上游源头 refCount(int,Duration),对断开操作加上一个平缓的时间 批量操作 将一个流分成一批一批,有三个解决方案 grouping windowing buffering 使用Flux<GroupedFlux<T»分组 将一个流Flux<T>分割成多个批次,每一个批次(组)就是一个GroupedFlux<T>,可以使用key()来获取用来分割特定的key。 每一组都不是连续,因为只有groupBy函数获取到上游的值才能知道将它分到哪一组。 每个元素都必定有一个组 组里的元素可以来自上游不同的位置 不可能为空(为空的话,压根不会产生 一些限制: 分组的数量不能太大 每一组的消费要足够快 窗口滑动Flux<Flux<T» 可以从数量,时间,边界条件等因素来进行窗口滑动。 和groupBy的一个区别就是,窗口滑动是连续的,也是可以重叠的,上游的元素也可能被抛弃。windowWhile是一个比较奇特的滑动,支持传入一个predicate, 返回true,则开启一个window。 返回false, 如果当前存在window。则关闭这个window。 如果当前没有开启的window,那么生成一个空的window。 使用Flux<List<T»缓冲 和windowing类似,区别主要有两点 缓冲到Collection里,默认是List 不会产生空的容器(window会产生空的flux) ...

October 14, 2019