换零钱

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

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

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的状态。

May 1, 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