Mysql索引入门

1. 什么是索引

   索引用于快速找出在某个列中有一特定值的行

2. 索引类型

   大多数MySQL索引(PRIMARY KEY、UNIQUE、INDEX和FULLTEXT)在B树中存储。只是空间列类型的索引使用R-树，并且MEMORY表还支持hash索引

3. 索引越多越好？

   • 数据的变更（增删改）都需要维护索引，因此更多的索引意味着更多的维护成本
   • 更多的索引意味着也需要更多的空间 （一本100页的书，却有50页目录？）
   • 过小的表，建索引可能会更慢
   • 频繁写入影响性能

4. 使用索引

   1 2 3

   like 'xxx%' -- 可以用索引 Like '%xxx%' -- 不能用索引 like '%xxx' -- 不能用索引

   1 2	<，<=，=，>，>=，BETWEEN，IN -- 可以用索引 <>，not in ，！=则不行 -- 不能用索引

   1 2 3

   SELECT `sname` FROM `t_stu` WHERE `age`=20; -- 会使用索引 SELECT `sname` FROM `t_stu` WHERE `age`+10=30; -- 不会使用索引！！因为所有索引列参与了计算 SELECT `sname` FROM `t_stu` WHERE `age`=30-10; -- 会使用索引

   1 2	SELECT `sname` FROM `stu` WHERE concat(`sname`,'abc') ='Jaskeyabc'; -- 不会使用索引,因为使用了函数运算,原理与上面相同 SELECT `sname` FROM `stu` WHERE `sname` =concat('Jaskey','abc'); -- 会使用索引

   1 2 3 4 5

   select * from dept where dname='jaskey' or loc='bj' or deptno=45 --如果条件中有or,即使其中有条件带索引也不会使用。换言之,就是要求使用的所有字段,都必须建立索引 可以通过union来替换or select * from dept where dname='jaskey' union select * from dept where loc='bj' union select * from dept where deptno=45

5. 什么样的字段适合建索引

   • 唯一性太差的字段不适合单独创建索引，即使频繁作为查询条件
   • 较频繁的作为查询条件的字段应该创建索引

6. 什么时候用复合索引

   where a = x and b =xx 是建立索引a，索引b，索引ab，索引ba？

   看区分度

7. 最左前缀原则

   复合索引（a,b,c），可以用到索引的情况是

   where a=x and b=x and c=x

   where a=x and b=x

   where a=x

   其余where条件都不能用到索引

8. order by 索引

   单独使用order by是不能用索引的，需要配合limit

   where+orderby时需要加复合索引，比如where a=x order by b,c需要加（a,b,c）索引

9. 当有多个索引，选择哪个

   mysql 会自动选择返回集合小的索引

10. 不要过早优化，除非仔细分析

    explain工具

11. Case Study

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

    CREATE TABLEt_cms_comment` ( id bigint(20) NOT NULL AUTO_INCREMENT, content text, create_time timestamp(3) NOT NULL DEFAULT CURRENT_TIMESTAMP(3), platform_id int(11) DEFAULT NULL, update_time timestamp(3) NOT NULL DEFAULT CURRENT_TIMESTAMP(3) ON UPDATE CURRENT_TIMESTAMP(3), target_type varchar(30) DEFAULT NULL, target_id bigint(20) DEFAULT NULL, content_type varchar(30) DEFAULT NULL, interaction_type varchar(30) DEFAULT NULL, user_id bigint(20) DEFAULT NULL, variety varchar(255) DEFAULT NULL, variety_id bigint(20) DEFAULT NULL, create_user bigint(20) DEFAULT NULL, deleted int(11) DEFAULT NULL, update_user bigint(20) DEFAULT NULL, audit_state varchar(30) DEFAULT NULL, author_type varchar(30) DEFAULT NULL, is_top bit(1) DEFAULT NULL, top_priority bigint(20) DEFAULT NULL, audit_user bigint(20) DEFAULT NULL, audit_time timestamp NULL DEFAULT NULL, re_audit_user bigint(20) DEFAULT NULL, PRIMARY KEY (id) ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

    select * from t_cms_comment where create_time < ‘2017-11-09 10:00:00’ and variety_id=5 and variety=’studio’ order by top_priority desc ,create_time desc, id desc limit 200 — 怎么加索引？

    • where create_time < ‘2017-11-09 10:00:00’ and variety_id=5 and variety=’studio’
    • order by : top_priority desc ,create_time desc, id desc
    • where + order by 复合索引，如果不行，优先考虑对sort建立索引，因为sort比较耗性能
    • 可能索引：(top_priority+create_time+id), (create_time+varierty_id),(variety_id)

1.后端整体服务

整体服务分层

1. 前端页面渲染
2. 业务逻辑层
3. 服务层

我们使用的技术包括：

开发：配置管理，服务发现，远程调用，网关，日志追踪

监控：prometheus监控，apm性能管理

部署：docker，k8s, ansible

基础组件：mysql，redis，mqtt，rabbitmq

2. 服务管理

1. 配置管理

• 代码配置分离

  我们通过git集中化进行配置管理，配置和程序代码分离，即做到一份程序，多份配置，多处部署

  

• 实时刷新配置

  通过springcloud-bus项目，我们可以实时动态热更新运行中的程序配置，避免修改配置需要重新打包发布

  

• 配置获取

  通过域名conf.jinyi999.cn/{项目名称}/{环境} 获取应用相应环境的配置，比如http://conf.jinyi999.cn/ytx-sso/k8s或者sso项目k8s环境的配置

  

  ​

2. 服务注册发现

• 传统服务管理问题

  传统服务通过域名管理，通过nginx代理服务域名，需要管理nginx和后端服务关系，在微服务时代，服务量级会不断增加，通过传统的nginx管理服务十分不便。比如新增节点，减少节点，都需要对nginx进行重新配置。通过获取服务信息也十分困难不便

• 服务发现好处

  服务发现的好处在于，可以零编码的对所以服务进行动态管理，获取服务信息，如服务ip，端口，监控状态等。我们使用的是eureka进行服务发现管理。

  

• 服务发现模型

  服务发现本身需要保证服务的分布式高可用，所以服务发现本身相对比较复杂。在分布式CAP理论基础上，eureka服务发现使用了AP模型，在网络出现问题时，保证了服务的可用性，牺牲了一致性

• eureka高可用

  我们部署了三台eureka服务，三个节点两两相互备份，保证服务的高可用性，任意一个节点挂了都不会影响服务的可用性

  

• 统一管理各自语言服务：包括java服务，nodejs服务，go服务，并且可以不断扩张

3.远程调用

• 远程调用简称RPC，在我们微服务体系中，我们选用了http作为远程调用协议（后续可以升级为gRpc等方式）。在springcloud体系中，我们使用了feign通过ribbon来进行远程调用。ribbon封装了httpclient或者okhttp，通过eureka获取服务地址并做负载均衡。我们使用了okhttp进行访问，提高http访问效率

• 重试机制

  远程调用需要考虑重试，比如由于网络超时、服务不稳定等原因造成访问失败。ribbon提供的重试机制为：对于所有GET幂等请求进行重试，重试方式是本机重试或者重新选取一个节点重试。相关配置为：

  1 2 3 4 5 6 7 8

  ribbon: MaxAutoRetries: 1 #本机重试一次 MaxAutoRetriesNextServer: 1 #重新选举一台重试 okhttp: enabled: true #使用okhttp eureka: registry-fetch-interval-seconds: 5 #5s从注册中心获取一次服务信息

4.网关

在微服务时间，服务数量相对传统单体应用会增加许多。我们通过统一的网关服务zuul代理访问所有的服务。

• 网关好处

  统一服务入口，避免客户端调用不同服务

  统一日志管理

  统一监控

  统一权限控制

  统一流量控制

  通过网关，我们可以做很多工作，后续如蓝绿发布，a/b test等

5.日志追踪

在单体应用时代，所有服务日志在一个应用中，而在微服务时代，一次请求涉及多个服务，日志追踪就变的十分重要。我们使用springcloud-sleuth组件进行日志追踪管理，所有日志都会有一个traceid，当进行远程调用时，该traceid会被传递到下游服务。我们的日志样例如下：

1
2
3
4
5

2017-09-01 16:09:56.828  INFO [zuul-server,e3459faf4e4115d8,e3459faf4e4115d8,false] 9 
--- [nio-8041-exec-1] c.y.f.base.filter.RequestLoggingFilter   : 
After request [method=POST,After request [uri=/api/user-center/device/save;payload={"deviceToken":"dd6f96fb3a9c10e6f9087d5ab5291e37",
"deviceId":"CC2165D8-BADC-476F-8ED8-B71A04CC2E41","userId":9,"os":"IOS","appVersion":"1.5.0"}],
time=12(ms),code=200]

traceid=e3459faf4e4115d8，同时我们记录了每次请求的耗时和httpcode，方便排查问题

• zipkins

  zipkins是一个tracing可视化工具，通过zipkins，我们将所有服务调用链串联起来。

3. 部署

• 服务Docker化

所有服务使用docker打包集成，提高部署的持续集成、版本控制、可移植性、隔离性和安全性。

开发测试环境所有部署使用自动化，通过gitlab pipeline完成。单测，sonar检查，build，docker镜像部署，上传docker仓库，部署到k8s环境，全部自动化。线上环境部署通过ansible进行自动化

4. 监控

• 基于网关的统一监控

  微服务架构由于服务较为分散，造成监控不便，我们通过统一的网关收率监控对象，将所有数据存储到prometheus中，通过grafana进行图表绘制以及报警。有任何错误可以在10s内进行报警

• springboot 服务监控

我们所有的微服务使用springboot框架开发，集成了actuator模块，自动暴露了/health，/metrics等接口，通过springboot-admin模块，我们集成了eureka获取了所有模块的列表，通过每个模块的/health，/metrics接口获取模块信息。
springboot-admin模块页面如下:

通过springboot-admin，我们可以实时观察到每个模块是否存活，健康状态

每个模块的内容包括：模块信息，调用情况，环境变量，调用情况

比较有用的是模块信息，比如启动时间，内存占用等。

• docker 监控

使用cadvisor+prometheus监控docker容器状态,可以获取所有机器和服务的的cpu，内存，磁盘等使用信息

一般系统都会访问外部系统，比如请求支付，会员卡，营销等各种系统，有时候一次请求需要访问多个下游系统，这种情况下失败是避免不了的。这里总结了几个注意事项

1. 访问下游系统必须设置超时时间，一般设置3s，不同业务系统需要进行相应调整
2. 访问下游系统qps必须控制，不能给下游系统压力过大
3. 幂等操作：访问下游失败了，可能是由于网络超时，下游系统已经处理成功。这个时候有两种方式
   1. 下游提供查询接口，通过查询判断是否处理成功
   2. 下游提供幂等接口，通过幂等号多次请求下游，下游保证操作幂等
4. 一次请求需要访问多个下游，如果保证多个下游的数据一致性

• 通过分布式事务，比较重，而且需要各个下游支持分布式事务接口，比较难实现。
• 通过二阶段事务方式访问各个下游，要求也是下游系统需要支持二阶段事务协议，也比较难实现。
• 简单依次访问各个下游，如果某个下游访问失败了，可以进行的操作是：
  • 简单重试n次，一般是3次。优点是简单，缺点是如果n次不成功，之前访问的系统无法回滚。
  • 如果n次不成功，有效的方案是落异步任务，然后通过任务无限次重试。优点是可以保证最终一致性。缺点是开发成本大，而且需要下游系统支持幂等。如果下游系统不支持幂等怎么办？我们可以自己为下游系统记录幂等信息，比如我们自己记录一个流水表，记录各个下游系统是否访问成功了。如果成功了就不再访问了
  • 如果落异步任务成本太高，怎么办？暂时没想到什么好方法，我能想到的就是客户端不断重试调用服务端。

文中的“我”，其实不是一个单纯的角色，它可能会包含多层含义，不管是我作为一个团队的管理者，还是我作为一名技术团队的普通员工，都会对自己的团队有一些期许，一些定义，一些要求，而这就是今天我们要谈论的话题。希望这些思考能够对管理者或者求职者有些帮助。

团队的首先组成就是人，那我理想中的技术团队中的人应该是怎样的呢？作为团队的负责人，其实对于人这方面的把关我一直是非常严格的，对于进入到我团队里的成员，通常需要有以下品质，这就是我对技术人的理解。

1.好奇心。

你为什么做技术？一些人是为了糊口，一些人只是不知道自己能做什么，而另外一群人，则是因为好奇心，对未知领域的探索，用技术来做很多神奇的事情，例如炫酷的动画？碉炸的算法？人工智能？游戏？物理引擎？漂亮惊艳的页面？想想你是不是因为这些技术而义无反顾的冲入编程大军的。我觉得这种编程才能持续的做下去，而不是捞一笔就走的心态，或者想着靠编程实现财务自由。有些同学在做技术一段时间之后，会开始迷茫，我觉得这时候回过头去看看你的初衷非常重要，如果你的初衷是平庸的，那我觉得你不适合做这行，如果是你的初衷是用技术探索应用价值，那我觉得你可以顺着这个思路想一想你的现在的价值点在何处？对于这个问题，前几天我发的一个朋友圈挺有代表性，这里贴出来：

2.持之以恒的学习。

我面试的时候通常会特别关注这一点，有时候如果实在看不到一个人对于持续学习的热情，我甚至直接生硬的问对方，“你业余时间会做些什么跟技术相关的事情”，然后得到的回答，通常是“看书”“看论坛”“看源码”。其实这就是敷衍了事了，这些事情只是一个程序员最基本的一些学习方法，我其实想知道的是，你是如何“持续学习”的，你看过一篇文章之后，对于其中涉及的一些知识点，你如何去强化？如何去实践？甚至如何引入到工作中来？你的工作或者是项目都做得平平无奇，那你看书看论坛都是在看什么呢？看了之后又解决了什么问题？

3.分析解决问题的方式。

最基本的，你在遇到技术难题的时候，如何解决？google？爆栈网？这些是最基本的，你如何判别一个解决方案的正确性？你如何一步一步分析问题？如何debug你的代码？然后，解决问题之后，你做了什么思考？是否是你的知识面有问题，需要系统补充下某个方面的技术点？你是否研究了它周边的知识？写一篇博客，备忘顺便分享给网友？这里又涉及到知识管理的方面。总之每次遇到问题其实都是一次对你的知识面的扩充时机，最终这些都会变成你的经验。在工作多年之后，这些潜移默化的知识会让你能够快速对一个问题作出判断，会在你脑海中形成一套体系，帮助你快速分析和解决问题，不管是你的方向是架构师，还是业务leader，都需要这些能力。

通常，你做事的方式态度，就决定了你的未来。

为什么我们需要一个团队中的成员具备这些素质？最终目的都是通过这些细节发现一个人的潜力：好奇心决定了你能在技术这条道路上走多久；学习方式决定了你能够在这条道路上越走越高；而解决问题的方式则决定了你能否形成方法论，成为一位真正的资深工程师。

除了上述的三点，对于团队中的人，作为一名普通员工，我还期望有这些关键字：

• 乐于分享，让我可以被动扩充知识面；
• 和善真实，不为人情世故操心专心做个写代码的美男子；
• 牛逼哄哄，让我大开眼界的牛人那是最好不过的，光听那些名词就足够我出去吹半天了，对于开阔思路视野有奇效；

人满足需求了，接着讲我理想中的团队是什么样的第二部分：事。

1.团队是否在朝着一个更好的方向成长？

我见过很多团队，基本没有“管理”。所谓管理，不是说有个老大管着你，指挥你做这个做那个，而是你这个团队是否有“目标”“规划”“预期”。就如最近面试的一些比较优秀的同学一样，他非常关注我们团队的“管理”，会提出一堆关于此方面的问题，这就是他对团队的一种期许，你的团队是单纯的实现业务？还是有所规划？你理想中的团队架构是如何的？人员分配如何？技术栈如何？规范如何？流程如何？现在有何不足，作何改进？这些其实就是对“管理”的拷问。一个有管理思路的团队，经得起这些拷问。而这些拷问，其实关注点主要就是你的团队是在健康成长，还是放养或者原地踏步？如果进入没有方向的团队，恐怕自身的成长也不会有大的进步。

2.团队做事方式是否规范？

近一年，我对团队管理最大的方法论也是指导方针，就是规范化。这里的规范化有几种含义。

• 代码规范，这个不用多说，最基本也是最容易达成的，方法可以有eslint等，加上定期的代码review，以及团队内的规范文档等。
• 方法规范，如何引入新技术？多人开发如何进行？如何保障代码可用性？如何保障发布安全？如何有效利用日志？等等，这些问题都需要形成方法论，有一套流程来保障。例如引入新技术，我们需要 调研试用 - 产出优劣报告 - 产出脚手架 - 多人review脚手架 - 分享+文档 - 新项目试验 - 问题总结分享 - 优化 - 全面投入使用，过程中会要求一些产出，目的都是为了评估好优劣，并且形成一套规范，而不是随意引入一些不可控的技术。上面提及的其他问题，我们都会形成自己的一套规范，落地分享和文档，跟踪执行。这就是团队规范的方法论。
• 流程规范，一个需求如何产生？如何评估其用户价值和可行性？如何进入开发手中？如何排期？是否有完善的项目管理流程？测试发布如何进行？一个团队的开发如果是乱哄哄没有标准秩序的话，开发会很累，这些其实是项目经理的职责，从开始对需求的把关，到产品经理的把关，到交互视觉把关，到技术方案排期评估，到联调跟进测试发布。做好不易，做不好大家就会很累。

规范化的最终目的，一个是提高开发效率，另一个是确保团队开发的可持续性，减少“坑”出现的几率。这些问题通常是创业公司技术团队的通病。

3. 共同成长和价值定位

以我团队为例，最近在做一个事情，全公司公用组件的开发，这个事情我不准备让负责架构的同学去做，我将其分解为两部分： 架构组的事情：制定组件规范，制定脚手架，把关代码质量，出标准组件的实例，推动计划进行，文档和组件索引网站等。 业务组的事情：根据架构组的周边和规范分工实现组件。

我希望通过这样的分工达成两件事情：架构组发挥其作用让事情朝着正确的方向前进；业务组的每位同学都能知道一个标准组件是怎样产出的，都了解npm是如何管理组件的，组件的周期维护是如何的，更通过严格的review通过制度来让大家共同成长。 可以看到这件事情的三个意义：一，让大家共同成长；二，大家各司所致，找到自己在整件事情中的价值定位；三，事情本身推动了团队开发效率，这是其最基本的价值。

作为一个个人，其实对团队的期望大体还有：

• 有足够的挑战，有机会接触各种问题并解决以此获得经验积累。
• 团队认可我的价值，而不是把我当成工具来使用。
• 团队有足够的成长空间，对自己有个清晰的定位。

结语

其实今天还跟大家讲，为什么做分享，很难做一些方法论或者是管理思路的分享？一个是因为还不够成熟，大家都在摸索；另一个重要的原因是，很多方法论其实就是一句话或者几句话，更重要的是执行到位，否则说出来都会很虚，但是团队到了一定阶段之后，一定要有目标和方法论，否则还是原始的行军状态，大家都会迷茫，内耗也会非常高。其实这些总结也是挺虚的，但是算是我内心对团队和人的一些见解。

问题

前端同学和我在讨论什么功能应该放在后端完成，什么工作应该放在前端完成。

想法

• 传统的开发模式是后端负责业务逻辑，然后通过模板填充数据的方式返回html给前端显示，前端就只要负责样式设计即可。这种模式的缺点是后端太重，既要负责业务，又要负责显示，前端样式改了，后端也要跟着改，整体效率低下。
• 随之产生的是前后端分离开发模式，即MVC，目的是解决后端负责数据和业务，前端负责显示，通过Controller进行衔接。但是同样有个问题，即Controller的工作范围，如果和以往一样，controller负责将所有业务数据封装完成，View就是简单的显示数据，这样的好处相比原有的模式只是在于后端不用知道前端样式，只负责返回数据，而模板渲染的工作放到了前端。
• 那是不是前端就只是负责显示数据？我觉得不应该这样的，前端也是应该有相应的业务逻辑存在的。那哪些业务逻辑应该放在前端，哪些必须放在后端，其实很难定义。有些业务必须放在后端，比如数据校验，安全分析，权限控制这些是要放在后端。但是有些业务是两边都可以做的，比如菜单栏显示，菜单栏里面的数据如果是固定的，那这个数据应该维护在前端还是后端，其实前后端都可以。

解决

我觉得针对这个问题我的思路是两点

• 从整体最优的角度去思考问题，从开发成本，维护成本角度看，放在哪里是最优的。
• 前后端开发语言的特点考虑，前端出现的优势就是快速开发，相比后端java，js更加轻，开发效率更高，所以我个人建议是将一些独立的业务逻辑移到前端，而不是放在后端。而后端java的优势在于性能，安全，强大的框架以及各种成熟的中间件，所以相对复杂的业务流程需要放到后端。

结论

• 后端注重数据，前端注重展示，有时候边界不是特别清晰，需要从整体考虑收益，而不是单从前端或者后端角度考虑问题。

• left join，right join，inner join，select in

  最基本的sql语句，连表查询性能并没有想得那么差。尽量避免大表连小表的操作。

• 锁

  mysql的锁有很多类，主要区别在于两点

  • 锁粒度
  • 互斥性

  mysql有一下几类锁

  1. Shared and Exclusive Locks：读写锁
  2. Intention Locks：意向锁：表或者行级别锁
     1. SELECT … LOCK IN SHARE MODE IS锁。读锁
     2. SELECT … FOR UPDATE IX锁。写锁
  3. 行级锁：用于锁定某一行数据，粒度
  4. gap索引: 范围锁，a gap between index records, or a lock on the gap before the first or after the last index record。在read_repeatable级别有效，read_commited无效
  5. Next-Key Locks: 行锁+gap锁，在read_repeatable级别有效，read_commited无效
  6. Insert Intention Locks: 插入索引

• 事务

  • 隔离级别
    • READ UNCOMMITTED
    • READ COMMITTED 阿里云默认，性能好些。不适用gap锁。在扫描数据的时候，会自动释放不符合条件的行锁
    • REPEATABLE READ innodb默认级别，mvcc，使用next-key lock
    • SERIALIZABLE 串行化
  • Locking Reads
    • share mode：SELECT … LOCK IN SHARE MODE。共享读锁
    • exclusive mode：SELECT … FOR UPDATE。排他锁

• 索引：

  1. 聚簇索引：索引和数据一起存储，读取效率高
  2. 二级索引：存储聚簇索引，读两次磁盘
  3. 主键uuid vs auto_increment bigint：二级索引存的是主键值，uuid太大。读取磁盘速度慢。索引不连续

1. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

1
2
3
4

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

1
2
3
4

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

Answer:

for each time i with price = prices[i], we should find the minimum prices whose time j < i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

func MaxProfit(prices []int) int {
	min := math.MaxInt32
	max := 0
	for _, x := range prices {
		temp := x - min
		if temp > max {
			max = temp
		}
		if x < min {
			min = x
		}
	}

	return max
}

2. Best Time to Buy and Sell Stock II

Say you have an array for whichthe ith elementis the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may completeas many transactions as you like (ie, buy one and sell one share of the stockmultiple times). However, you may not engage in multiple transactions at thesame time (ie, you must sell the stock before you buy again).

Example：

Input: [7, 1, 5,3, 6, 4]

Output: 7

Input: [7, 6, 4,3, 1]

Output: 0

Answer:

since we can do many transaction as we want, then we just need find every close valley and peak in the curve.

1
2
3
4
5
6
7
8
9
10

func MaxprofileWithMultitransaction(prices []int) int {
	profile := 0
	for i := 1; i < len(prices); i++ {
		if prices[i] > prices[i-1] {
			profile += prices[i] - prices[i-1]
		}
	}

	return profile
}

3.Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Answer:

DP problem, prof[i] is the max profile with up to r transactions before time i.

m = max profile with up to r-1 transaction and prices[i] as buying price in the next transaction at time i

prof[i] = max(prof[i-1],prices[i]+m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

if prices == nil || len(prices) <= 0 {
		return 0
	}

	n := len(prices)
	prof := make([]int, n, n)
	for r := 0; r < 2; r++ {
		m := prof[0] - prices[0]
		for i := 1; i < len(prices); i++ {
			m = max(m, prof[i]-prices[i])
			prof[i] = max(prof[i-1], prices[i]+m)
		}
	}

	return prof[n-1]

4.Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Answer:

DP problem

1
2

prof[r][i] = max(prof[r][i-1],prices[i]+m) // max(profile with no transaction at time i,profile with transaction at time i)
m = max(m,prof[r-1][i-1]-prices[i]) // max profile with r-1 transaction at time i-1 and buying price = prices[i]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

// MaxProfitWithKTransactionDP 动态规划版本
// prof[r][j] 表示j时刻，最多r次交易可以获得的最大收益
// m = max(prof[r-1][j-1]-prices[j],m) 表示r-1笔交易情况下，j-1时刻的收益减去j时刻的价格的最大值
// m意义是基于r-1笔交易收益为prof[r-1][t]的前提下，找到一个低点买入，即需要找到一个时刻t，使得prof[r-1][t-1]-prices[t]值最大，这样才能在后续高点卖出，是的整体收益最大化
// 由于交易笔数k可能比较大，远远大于prices的长度，即这样交易笔数不在重要，只要有价差就可以买入卖出，所以当k>len(prices)/2时，可以直接退化至任意笔操作
func MaxProfitWithKTransactionDP(k int, prices []int) int {
	if prices == nil || len(prices) <= 0 {
		return 0
	}

	if k > len(prices)/2 {
		return quickSlove(prices)
	}

	n := len(prices)
	prof := make([][]int, k+1, k+1)
	for i := 0; i < k+1; i++ {
		prof[i] = make([]int, n, n)
	}

	for r := 1; r <= k; r++ {
		m := prof[r][0] - prices[0]
		for i := 1; i < len(prices); i++ {
			prof[r][i] = max(prof[r][i-1], prices[i]+m)
			m = max(m, prof[r-1][i-1]-prices[i])
		}
	}

	return prof[k][n-1]
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func quickSlove(prices []int) int {
	profile := 0
	for i := 1; i < len(prices); i++ {
		if prices[i] > prices[i-1] {
			profile += prices[i] - prices[i-1]
		}
	}
	return profile
}

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment