换零钱

用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)))))) ...

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

今天是2019年12月3号,我在ThoughtWorks已经13个月了。回顾下我这十三个月。 OneApp 第一个项目就是典型的大客户项目,Daimler OneApp,顾名思义,把所有能揉在一起的应用都揉在一起。第一次去客户现场是和另一个后端同事,当时是去商量两个模块,sCRM和IM,出发之前是两个人一起做两个模块。去了之后,就是和第三方的vendor商量接口,实际上就是甩活,看你如何把一些脏活累活扔给对方,这点恰恰是我的强项,但是我是个新人,所以第一轮商讨的时候,主力是另外一位同事,一轮谈下来,我就和同事商量:“要不这个IM你做吧,我做sCRM就好了。”,不得不说,同事在这方面真的软弱。后面的发展就是被灌输了BFF,契约测试两个基本贯穿了我几个项目的概念。 契约测试,这个是一个美好的理念,蹩脚的实现,残酷的现实。 BFF,一次性代码,帮前端包鸡包眼的代名词。 现在回想起来,也是神奇,sCRM我居然没有写一行实际代码,这也要感谢当时的TL,所以我整天的工作就是嘴炮,安抚前端,推动上游vendor。 好景不长,IM的同事把IM也交接给我了,整个项目最大的历练和成长也由此开始。与第三方无止境的扯皮。前一天晚上答应的事情,第二天就能完全不认。与此我也总结出了许多“经验” 不在客户面前说没把握的事 只说事情的表现,不帮第三方去猜原因 保留证据,并引导第三方犯上面的错 不要一次性要求第三方解决N个问题,抽一个,咬住不松口 多发问,少解释。除非是客户问你bug的原因,你能甩给第三方,但也要注意前面说的,不要去猜测第三方的原因。 戴姆勒项目后期就非常无趣了,没写代码没实际产出物被diss,小组效率被质疑,BA夹在小组和PM之间为难…… 总之,五月份左右,我下了Daimler OneApp项目 OTR 中间on beach了一个多月,无所事事,某天被RM拉过去“北京的TP点名要你上OTR,和他一起balabala”,同时也从Buddy口中听到了类似的声音。当时的我受宠若惊,TP,什么概念。上了OTR,才发现,原来不是这样,OTR想上契约测试,TP便问了OneApp的另外一个TL,得知我做过契约测试,并且处于on beach状态,就让我过去了。这个事情不知道怎么就变成TP点名要我了。扯淡的很。 反正上了OTR 一周,我就下项目了,原因很简单 我不喜欢写测试 我不喜欢帮别人写测试,擦屁股 我更不喜欢帮别人写契约测试 和PM说了之后,最开始是想在OTR其他组做,但是应该是“刺头”都不愿意要,便让我再次回到了on beach的状态。 IKEA 这个时间遇到了公司的组织架构变动,之前Daimler OneApp的同事找到我,问我愿不愿意以后分到华东,我当然无所谓啊。于是就答应了,然后永远“下周上项目”(预定人,最后还是上了IKEA项目,这个项目还挺像小公司的项目的,算半个从无到有,不停的推导重建,具体的回顾,我应该是写了另外一篇文章。 Starbucks 宜家下了之后,经历了项目黄掉,项目我看不上,项目看不上我,角色不合适,最后上了Starbucks,哦豁,又一个大客户项目。 这个项目我遇到的最大问题就是“没有赢得信任”,因为合作的人真的是有点蠢,我是真的不想理。...

December 3, 2019

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

Multipartform-Data

Part multipart/form-data 由许多块part组成,每一块之间由boundary分隔开 每一块都有自己的header Content-Disposition: form-data; name="user" //or Content-Disposition: form-data; name="user"; filenmae="image.png" 每一块都可以有一个可选的Content-Type字段,默认为text/plain,如果是文件类型,而且不知道其MIME,那么应该设置为application/octet-stream Content-Type: image/png 每一块的header和body之间都会有一个空行 每一行的结尾都应该用CRLF(\r\n) Tips 前端发来的filename不应该信任 name应该独一无二 name和filename都需要Percent-Encoding,应该避免Non-ASCII boundary boundary 应该放在Content-Type 中 Content-Type: multipart/form-data; boundary=abcedfghijk 每个part之间的分隔线由--,boundary,CRLF组成,每个part之前都需要放置一个。最后一个分割线需要加上--后缀。比如 --abced Content-Disposition: form-data; name="user" uservalue --abced Content-Disposition: form-data; name="file"; filenmae="image.png" Content-Type: image/png �PNG ffffff --abced-- 背景知识 Percent-Encoding,也叫做URL Encoding。https://en.wikipedia.org/wiki/Percent-encoding ...

September 15, 2019

我的这两年

今天是2018.10.22,可能是我在上海生活的最后一天,2016.02.16,我来到上海,那时的我还没有毕业,至于为什么来上海实习,其实没有为什么,就是觉得“年轻人应该出去走走”,至于为什么是上海而不是北京,广州……可能是上海,“魔都”这个称号真的是充满魔力。 找工作 来之前就沟通了三家还是四家面试,当时的我稚嫩的很,基础没有,经验没有,最擅长的就是面向Google编程,各种解决办法囫囵凑一块,总能解决问题,水平最差,热情最高。 第一家公司是闯奇,一家做积分墙业务的小公司,技术面试内容不大记得了,我只记得当时XYK给我很自豪的分享他对于redis ZSET的使用,以及原来用webmagic,后面又为啥弃用…… 当天上午面试,中午我就拖着箱子进公司了,成了CQASO项目组的第二名成员。 第二天就迎来了第三名成员,也是一名实习生(CYT)。 这说对我来说是最好的开头了。 开始工作 热情高涨的投入工作,XYK对我也是非常信任,经常夸我,让我觉得有点难堪(我这么弱……)。当然,这也鼓励着我往着好的方向发展。 几乎是一天发布N次,一周几个版本,更迭速度是我这几年来见过最快的,当时没多想,现在觉得CYT真奇才,前端真的牛的一逼,后端那样更迭,也能跟上。 技术上也是各种更新换代,开始抛弃祖传的xml配置,开始使用SpringBoot,开始使用MongoDB,集群,开始越来越多的使用lambda表达式(最开始XYK大规模使用的时候,我还觉得影响了代码可读性,后面,嗯,真香。),自学Kotlin,开始不囿于“怎么样才能搞定”,追求“为啥这样能搞定”。 抛开技术,产品也是全程参与,不得不说这个时期的小团队战斗力真的惊人,我也体验了一把”人人都是产品经理“。可以说CQASO,我也是有自己的感情在里面的,但是囿于当时我们的技术水平,我们只能在采集,整理,展示方面做到了自认非常不错的水平,最重要的数据背后的规律,我们确实没有什么好的办法,即便当时跟风上了Hadoop那一套,找了一些算法,效果也是不尽如人意。 厌倦 经过了7-8个月的开发,我们与竞品之间已经没有什么差距了,除了稳定性,不过事后复盘,稳定性的问题确实很大,很多用户都是经历了几次bug就跑掉了。老板开始对项目失去了信心,这个项目成了一个面子工程,用来彰显公司是一家高科技公司。开始了洗脑,早报那一套,我可能深受阶级斗争思想的荼毒,非常非常厌恶这一套,团队内部也开始有了抱怨,不得不说,抱怨是会传染的,特别是这种关系很融洽的小团队,到了17年2月,终于,团队散伙了。 再次找工作 这个时候的我,比较无知,但是想得很多,我开始向往大公司,觉得小公司随时有产品崩掉之后整各种幺蛾子的风险。一周投了好几十家,拉钩各种不匹配(觉得可能大部分是自动拒的,我没差到连面试都进不了),面试了两三家公司,收到offer的就只有什么值得买,当时看来,真的是梦想中的公司。 我是SMZDM老用户,特别喜欢这家公司 面试官问的问题都是我喜欢的问题(怎么解决一个问题,而不是哪个参数怎么配置 不再参与CRUD,而是参与集团内部基础设施和架构的研发 简直不要太美好,这次工资被压的比较低,个人感觉应该是比市场价少了20%,不管,开心就好。 纠结 进了SMZDM,才发现不是我想象中的那样 面试的leader马上要离职 300多人的技术规模,只有10来个是Java 整体技术水平怎么说呢,说出来就得罪人的水平 这就导致了内部基础设施和架构都搞不起来。(难度非常高,我做不到 还有一个小小的点是,我和面试我的leader都是非常强势且固执的人,当然我很尊重他(哈哈,Respect),但是两个人合作确实会有一些不愉快。 这导致了我进公司当天回家就写了一封邮件表示不合适 混乱 就这样开始了混的一年多,基本上做的东西都是,emm,怎么说呢,都是我不会跟人主动说的东西…… 技术变化可以说,基本没有,但是终于,被逼着开始看源码了,因为有些问题你压根搜不到任何解决方案,说的就是某些国内大厂的开源产品,管生不管养,文档全靠微信群,QQ群口口相传。 中间也间歇性踌躇满志,想离职,换个公司好好做点东西,但还是被持续性混吃等死给打败了。 //2018年12月17日晚上8点09分继续,毕竟我是一个很拖拉的人 等到离职才发现,我在SMZDM只做了这么一点东西,半成品(其实就是垃圾)CI,支付SDK(其实我觉得还行,但是还有改善的余地),配置中心(凑合能用,但是不算优秀),改了一下CAS,改了一下ES的Netty模块,对CAT有点头痛医头,脚痛医脚的修改。一年半(2017.03-2018.08)就只做了这么一点。实在是对不起公司。 在这里需要特别感谢我的领导LC,给与了我非常多的不应该的宽容。我感觉I don’t deserve it。 结束 2018年是我的本命年,可以说整一年都不太顺,年初出去玩,脚扭了。休息了整个3月,然后七月份,我爷爷重病去世,这是我第一次体会到,亲人离我而去,至今我还经常梦到我爷爷。这也让我意识到,过去的就已经过去了。等我再次回到上海,我已经不想继续上班了。其实现在回想,真的就是不想上班,所谓的一大堆理由,就是不想上班,我提出了离职,LC还是同意了我的离职,我何德何能,能让别人这样对待?7月底,我办完了离职流程,我突然就想回到武汉了。是的,突然就想回武汉了,所谓的理由都是假的,就是脑中冒出这么一个想法,然后践行了而已。 再次感谢我的领导,LC。以及我的各位SMZDM的同事,给与我的各种不应该的宽容。 回武汉 7月底离职,整个8月都在玩游戏。9月份投了小米云服务,没有做任何准备,电话面试的时候凭感觉侃侃而谈,然后挂掉了,很合理,我毫无怨言。 然后就放弃了整个9月,又开始了混吃等死的生活,BTW,合金装备5真的是一个非常非常棒的游戏。十月份,我再次开始了投简历,小米的IoT服务将我捞了起来,我又投了金山,海康,ThoughtWorks,还有两个不知名公司,金山面试我就知道自己挂了,海康面试非常简单,不知名公司中一个我觉得非常有把握,另外一个我压根瞧不上。IoT再次面试我觉得表现不错,TW的面试我也觉得还行。后来没想到两家小公司我都挂了(其中一家表现的对我非常认可),海康给的是童工合同,TW压价也厉害(多次打电话问最低多少完全不能接受)。 这里可以谈下小米IoT被挂掉的最后一次面试(第4次)。To be honest,让人非常不爽,问我overloads和override的区别,各种鸡毛蒜皮的问题。这里还是要说,WCNM,这种JB问题真的有意思嘛? 回到武汉 最后我来到了TW,一个外包公司,我在V2EX看到过几次TW的招聘帖,不管TW这边怎么吹,在我心中TW都是一家外包公司,但是我没得选了。 外包公司是原罪,但是To be honest,很多公司连外包公司都不如。 女朋友领导得知我去了TW,第一反应是"养老公司"。 不管怎么样,我进了这么一家养老公司。 我在来TW之前看了一些TW的差评。 会吹牛逼吗?会的话可以去TW,想学吹牛逼吗?想的话可以去TW。 可以说,这句非常贴切。 生活还得继续 入职TW也有一个多月了,当我一件一件的拆到女朋友从上海发来的包裹的时候,我开始意识到,我这辈子可能就和上海说再见了,我可能就在武汉买房,上班,结婚,生孩子,直到一生结束。 后记 我总是能开一个好头,然后后续乱七八糟…… 其实写了这么乱七八糟的一些,我也不知道我写了什么。 但是感谢XYK,CYT给我的鼓励和激励。...

October 22, 2018