力扣-删除二叉搜索树中的节点

RECOMMEND

一、题目描述: 给定一个无重复元素的有序整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中的每个区间范围 [a,b] 应该按如下格式输出: - "a->b" ,如果 a != b - "a" ,如果 a == b 示例 示例 1: >输入:nums = [0,1,2,4,5,7] 输出:["0->2","4->5","7"] 解释:区间范围是: [0,2] --> "0->2" [4,5] --> "4->5" [7,7] --> "7" 示例 2: >输入:nums = [0,2,3,4,6,8,9] 输出:["0","2->4","6","8->9"] 解释:区间范围是: [0,0] --> "0" [2,4] --> "2->4" [6,6] --> "6" [8,9] --> "8->9" 示例 3: >输入:nums = [] 输出:[] 示例 4: >输入:nums = [-1] 输出:["-1"] 示例 5: >输入:nums = [0] 输出:["0"] 提示: >0 <= nums.length <= 20 -231 <= nums[i] <= 231 - 1 nums 中的所有值都 互不相同 nums 按升序排列 二、解答 分析 解题思路: 1. 遍历整个数组,当相邻的数只相差1时,构成一个区间。 2. 当相邻的数相差大于1时,开始一个新的区间。 3. 当判断开始一个新的区间时,我们需要保存前面的区间。 4. 保存一个区间需要两个值分别记录区间开始的值,当前数的前一个数的值。 5. 唯一值得注意的是处理边界问题。 >时间复杂度:O(n),其中 n 为数组的长度。我们只需要遍历一次数组即可。 空间复杂度:O(1)。只需要常数空间存放若干变量。 代码 ```cpp class Solution { public List<String> summaryRanges(int[] nums) { int length = nums.length; List<String> result = new ArrayList<>(); if(length == 0){ return result; } int start = nums[0]; int now = nums[0]; int i = 1; for(;i < length;i++){ if(now + 1 == nums[i]){ now++; } else{ result.add(start == now?String.valueOf(start):start+"->"+now); start = now = nums[i]; } } result.add(start == now?String.valueOf(start):start+"->"+now); return result; } } ``` > 执行用时:7 ms, 在所有 Java 提交中击败了82.54%的用户 内存消耗:36.9 MB, 在所有 Java 提交中击败了53.76%的用户 改进 1. 因为当前数的前一个数的值,我可以通过当前的下标来获取,所以该值完全没有必要记录,所以可以省略该值 2. 省略该值之后,我只要通过下标来判断即可,所以在循环里,我只要判断前一个数加一与当前值不相等即可 ```java public List<String> summaryRanges(int[] nums) { int length = nums.length; List<String> result = new ArrayList<>(); if(length == 0){ return result; } int start = nums[0]; int i = 1; for(;i < length;i++){ if(nums[i - 1] + 1 != nums[i]){ result.add(start == nums[i - 1]?String.valueOf(start):start+"->"+nums[i - 1]); start = nums[i]; } } result.add(start == nums[i - 1]?String.valueOf(start):start+"->"+nums[i - 1]); return result; } ``` 这样做的好处就是节省了一定的空间。 三、官方解答 官方给出的题解也是一次遍历,但是是用双指针的方法,也就是使用维护下标low 和 high 分别记录区间的起点和终点,和我的大致思想也差不多。 ```cpp class Solution { public List<String> summaryRanges(int[] nums) { List<String> ret = new ArrayList<String>(); int i = 0; int n = nums.length; while (i < n) { int low = i; i++; while (i < n && nums[i] == nums[i - 1] + 1) { i++; } int high = i - 1; StringBuffer temp = new StringBuffer(Integer.toString(nums[low])); if (low < high) { temp.append("->"); temp.append(Integer.toString(nums[high])); } ret.add(temp.toString()); } return ret; } } ``` > 参考: > 1、[题目](https://leetcode-cn.com/problems/summary-ranges/) > 2、[官方解答](https://leetcode-cn.com/problems/summary-ranges/solution/hui-zong-qu-jian-by-leetcode-solution-6zrs/) >本文首发于CSDN,作者:lomtom 原文链接:**[https://blog.csdn.net/lomtom/article/details/112306554](https://blog.csdn.net/lomtom/article/details/112306554)** 个人网站:**[https://lomtom.top](https://lomtom.top)**,公众号:**博思奥园**,同步更新。 你的支持就是我最大的动力。 ![](https://img-blog.csdnimg.cn/20200405094243147.png)
2021-01-10
一、题目描述: 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 示例 示例 1: > **输入:** [7,1,5,3,6,4] 输出: 7 > **解释:** 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 =5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 > 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。 示例 2: > **输入:** [1,2,3,4,5] 输出: 4 > **解释:** 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 > 注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。 > 因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。 示例 3: > **输入:** [7,6,4,3,1] 输出: 0 > **解释:** 在这种情况下, 没有交易完成, 所以最大利润为 0。 提示: > 1 <= prices.length <= 3 * 10 ^ 4 > 0 <= prices[i] <= 10 ^ 4 二、解答 分析 整个算法的精髓就是:**在最低点买入,在最高点卖出。** 恩,这钱真好赚。 而我们要做的就是找出n天当中的低谷和高谷。 例如七天中:7,1,5,3,6,4,找出低谷:1、3,高谷:5、6 ![](https://img-blog.csdnimg.cn/20201108183309769.pngpic_center) 所以,问题可以继续抽象成,我在数组中找到极小值与极大值 最终,我们可以用后一个是否比前一个小来判断,如果小我就卖出,并且在后一天买入。 这样带来的问题是,如果我最后持续上升 那么我就没办法卖出了(因为我通过后一天是否比前一天小来判断是否卖出),所以在最后再卖出一次。 >时间复杂度:O(n),其中 n 为数组的长度。我们只需要遍历一次数组即可。 空间复杂度:O(1)。只需要常数空间存放若干变量。 代码 ```cpp class Solution { public int maxProfit(int[] prices) { int sum = 0; int length = prices.length; if(length == 0){ return 0; } int temp = prices[0]; int i = 1; for(;i < prices.length;i++){ //后一天是否比前一天小 if(prices[i] < prices[i - 1]){ //计算获得的利润 sum += prices[i - 1] - temp; //重新买入 temp = prices[i]; } } //再卖出一次 sum += prices[i - 1] - temp; return sum; } } ``` > 执行用时:1 ms, 在所有 Java 提交中击败了99.54%的用户 > 内存消耗:38 MB, 在所有 Java提交中击败了96.68%的用户 三、官方解答 官方有两种:一种是动态规划,另一种是贪心算法(比我的更简洁) 贪心: ```cpp class Solution { public int maxProfit(int[] prices) { int ans = 0; int n = prices.length; for (int i = 1; i < n; ++i) { ans += Math.max(0, prices[i] - prices[i - 1]); } return ans; } } ``` > 参考: > 1、[题目](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/) > 2、[官方解答](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/)
2020-11-08
一、场景引入 前提背景 在某些场景下,例如淘宝京东这样海量的数据,高访问量的场景,无疑对数据库造成了相当大的负载,同时对于系统的稳定性和扩展性提出很高的要求。 而单个服务器所能够提供的服务以及负载都是有限的。 所以,为了系统的问题,以及较快的响应速度或处理能力,在数据库方面就有了集中解决方案,**分库分表,读写分离**,这些都能在一定程度上有效地减小单台数据库的压力。 而本文就是从读写分离角度来一探究竟。 实现原理 主要理解以下三个点就差不多了: **1、主机负责写操作** **2、从机负责读操作** **3、从机自动从主机中同步数据** 然而,我们对于一个新的东西,我们就要提出我们的哲学三问: ~~我是谁?我在那?我要干嘛?~~ **是什么?为什么?怎么做?** 1、什么是读写分离 读写分离,基本的原理是让主数据库处理事务性增、改、删操作(INSERT、UPDATE、DELETE),而从数据库处理SELECT查询操作。数据库复制被用来把事务性操作导致的变更同步到集群中的从数据库。 2、为什么要读写分离呢? 因为数据库的“写”(写10000条数据到oracle可能要3分钟)操作是比较耗时的。 但是数据库的“读”(从oracle读10000条数据可能只要5秒钟)。 所以读写分离,解决的是,数据库的写入,影响了查询的效率。 3、什么时候要读写分离? 数据库不一定要读写分离,如果程序使用数据库较多时,而更新少,查询多的情况下会考虑使用,利用数据库 主从同步 。可以减少数据库压力,提高性能。当然,数据库也有其它优化方案。memcache 或是 表折分,或是搜索引擎。都是解决方法。 4.主从复制、读写分离的基本设计 在实际的生产环境中,对数据库的读和写都在同一个数据库服务器中,是不能满足实际需求的。无论是在安全性、高可用性还是高并发等各个方面都是完全不能满足实际需求的。因此,通过主从复制的方式来同步数据,再通过读写分离来提升数据库的并发负载能力。 > 取自:[读写分离的实现原理及使用场景](https://blog.csdn.net/belalds/article/details/82655786) **这里使用docker进行数据库的安装,docker的优势以及就怎么安装docker就不多做赘述了,感兴趣的可以去翻一下我以前的文章。** 一、安装mysql 这里只安装了一个主机(master),一个从机(slave) ``` docker run --name mysql-master -p 33061:3306 -e MYSQL_ROOT_PASSWORD=123456 -d mysql:5.7 --character-set-server=utf8mb4 --collation-server=utf8mb4_unicode_ci docker run --name mysql-salve -p 33062:3306 -e MYSQL_ROOT_PASSWORD=123456 -d mysql:5.7 --character-set-server=utf8mb4 --collation-server=utf8mb4_unicode_ci ``` 二、配置同步 为什么? 如果不进行同步的配置,那么从机无法获取主机的数据,最终就会导致同步失败。 1、配置主机用户 ``` grant replication slave on *.* to 'lomtom'@'%' identified by '123456' ``` 2、修改配置文件 在从机中的配置文件加入以下参数。 1. 主机 ``` log-bin = /var/lib/mysql/binlog server-id =1 binlog-do-db =lomtomdb ``` 2. 从机 ``` server-id =2 ``` 1、修改配置文件(以master为例) ``` Copyright (c) 2014, 2016, Oracle and/or its affiliates. All rights reserved. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License, version 2.0, as published by the Free Software Foundation. This program is also distributed with certain software (including but not limited to OpenSSL) that is licensed under separate terms, as designated in a particular file or component or in included license documentation. The authors of MySQL hereby grant you an additional permission to link the program and your derivative works with the separately licensed software that they have included with MySQL. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0, for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA The MySQL Server configuration file. For explanations see http://dev.mysql.com/doc/mysql/en/server-system-variables.html [mysqld] log-bin = /var/lib/mysql/binlog server-id =1 binlog-do-db =lomtomdb pid-file = /var/run/mysqld/mysqld.pid socket = /var/run/mysqld/mysqld.sock datadir = /var/lib/mysql log-error = /var/log/mysql/error.log By default we only accept connections from localhost bind-address = 127.0.0.1 Disabling symbolic-links is recommended to prevent assorted security risks symbolic-links=0 ``` 2、拷贝(主从都需要拷贝,以master为例) 如果服务器有vi编辑器,直接使用vi编辑器即可。 ``` docker cp mysql.cnf mysql-master:/etc/mysql/mysql.conf.d/ ``` 3、重启mysql ``` docker restart mysql-master ``` 4、查看是否配置成功 ``` show master status; ``` 如果出现以下数据即为成功。 ![](https://img-blog.csdnimg.cn/20210107122208680.png) 5、在从机(slave)中配置主机(master) ``` 1、配置主机信息 change master to master_host='192.168.43.236',master_port=33061,master_user='lomtom',master_password='123456',master_log_file='binlog.000001',master_log_pos=154; 2、查看从机状态 show slave status; SLAVE_IO_RUNNING ,SLAVE_MYSQL_RUNNING两个值为YES即为正确启动,否则自己根据下方的错误提示修改配置 ``` 三、测试 在第一个数据库(master)创建我们配置的数据库,然后随意修改该数据库的数据,刷新slave,数据同步成功。 四、注意 1、因为在配置当中指定了数据库(lomtomdb),也就是`binlog-do-db`参数,所以从机只会同步主机中的lomtomdb数据库,其他数据库不同步。 2、修改配置文件时,`log-bin`参数所指定的目录一定是要mysql能够操作的文件,也就是说,如果你指定了其他目录,请给予mysql操作权限。 >参考: >[读写分离的实现原理及使用场景](https://blog.csdn.net/belalds/article/details/82655786) >[江南一点雨](https://mp.weixin.qq.com/s/R89aCCFvCvudLp6FUn2JjQ) >本文首发于CSDN,作者:lomtom 原文链接:**[https://blog.csdn.net/qq_41929184/article/details/112306554](https://blog.csdn.net/qq_41929184/article/details/112306554)** 个人网站:**[https://lomtom.top](https://lomtom.top)**,公众号:**博思奥园**,同步更新。 你的支持就是我最大的动力。
2021-01-07
一、swagger是什么? swagger是一种基于Rest 风格的api文档开发工具,我们常常应用于前后端分离项目,解决由于前后端分离导致的数据接口不一致问题,有效的减少前端程序员与后端程序员的打斗次数。 swagger自己是这样介绍swagger的: 1. Swagger是一组功能强大且易于使用的API开发人员工具套件,适用于团队和个人,可在整个API生命周期(从设计和文档到测试和部署)中进行开发。 2. Swagger由开放源代码,免费和市售工具共同组成,它使任何人(从技术工程师到街头智能产品经理)都可以构建每个人都喜欢的惊人API。 3. Swagger由SmartBear Software构建,后者是团队软件质量工具的领导者。SmartBear落后于软件领域的一些知名企业,包括Swagger,SoapUI和QAComplete。 ![](https://img-blog.csdnimg.cn/20201002212241455.png) 二、使用swagger 1、引入依赖 在`pom.xml`文件中加入依赖 ```cpp <!--swagger2--> <dependency> <groupId>io.springfox</groupId> <artifactId>springfox-swagger2</artifactId> <version>2.7.0</version> </dependency> <dependency> <groupId>io.springfox</groupId> <artifactId>springfox-swagger-ui</artifactId> <version>2.7.0</version> </dependency> ``` 2、配置 主要从这几个方面来配置swagger > 1、配置swagger配置 > 2、配置swagger扫描 > 3、配置swagger2设置分组 > 4、实体类设置 2.1、配置swagger配置 首先若要使用swagger需要在配置文件上加上`@EnableSwagger2`注解,使用swagger2生效。 以下就是最简单的配置方法 ```cpp @Configuration @EnableSwagger2 public class SwaggerConfig { @Bean public Docket docket(Environment environment){ return new Docket(DocumentationType.SWAGGER_2).apiInfo(apiInfo()); } /** * 配置swagger信息 */ public ApiInfo apiInfo(){ return new ApiInfo( "教科文", "即使再小的帆也能远航", "1.0", "urn:tos", new Contact("lomtom", "", "lomtom@qq.com"), "Apache 2.0", "http://www.apache.org/licenses/LICENSE-2.0", new ArrayList<>()); } } ``` 如果你不知道ApiInfo的字段含义,我们可以查看他的构造方法,里面分别是它所代表的含义,这个相信会一点英文的都能够看得懂。 而ApiInfo并没有自己属性的set方法,所以我们只能使用构造方法来进行注入。 ```cpp 1、ApiInfo构造方法 public ApiInfo(String title, String description, String version, String termsOfServiceUrl, Contact contact, String license, String licenseUrl, Collection<VendorExtension> vendorExtensions) { this.title = title; this.description = description; this.version = version; this.termsOfServiceUrl = termsOfServiceUrl; this.contact = contact; this.license = license; this.licenseUrl = licenseUrl; this.vendorExtensions = Lists.newArrayList(vendorExtensions); } 2、其中的Contact构造方法 public Contact(String name, String url, String email) { this.name = name; this.url = url; this.email = email; } ``` 此时无需配置其他的我们也可以直接使用swagger。 打开[http://localhost:8080/swagger-ui.html](http://localhost:8080/swagger-ui.html). 在我的项目里一共有三个Controller:`LoginController、RegisterController、OssController` ![](https://img-blog.csdnimg.cn/20201002222742819.png) 其中1、红色框框内就是我配置的一些信息,而标注的①②③是我自己的`controller`,额外的④是默认的`controller`,也就是我们访问出错的`/error`页面 ![](https://img-blog.csdnimg.cn/20201002223044875.png) 2.2、配置swagger扫描 若我们在开发中不想看到默认的controller或者需要隐藏其他的controller,我们可以使用以下配置 ```cpp @Bean public Docket docket(Environment environment){ return new Docket(DocumentationType.SWAGGER_2) .apiInfo(apiInfo()) .select() //指定要扫描的包 .apis(RequestHandlerSelectors.basePackage("com.lomtom.website")) //过滤路径 //.paths(PathSelectors.ant("/admin/**")) .build(); } ``` 其中,apis参数中RequestHandlerSelectors一共有五种配置: ```cpp //1、basePackage:指定要扫描的包 //2、any():扫描全部 //3、none():都不扫描 //4、withClassAnnotation():类上的 //5、withMethodAnnotation():方法的 ``` 而.paths(PathSelectors.ant("/admin/**")),指的是我只扫描`/admin/`路径下的所有请求。 2.3、配置swagger2设置分组 当我们在实际的开发中,一个项目往往由多个开发人员共同协作完成的,而swagger恰好可以在这方面解决这一问题。 ```cpp @Bean public Docket docket1(Environment environment) { return new Docket(DocumentationType.SWAGGER_2) .groupName("ou"); } @Bean public Docket docket2(Environment environment) { return new Docket(DocumentationType.SWAGGER_2) .groupName("yang"); } ``` 我们再在原来的基础上加上两个Docket,当然实际中我们需要配置的往往不会这么简单,这里只是举例说明。 可以看到,在原来的分组中多了两个组,这样我们的程序员就可以只查看自己的负责的接口了。 ![](https://img-blog.csdnimg.cn/20201002224135724.png) 2.4、实体类设置 我们可以在实体类中对我们的model对象进行一些说明。`@ApiModel`对实体类的说明,` @ApiModelProperty`对类的属性的说明。 ```cpp @Data @TableName("admin_user") @ApiModel("管理员用户类") public class AdminUserEntity { @TableId(type = IdType.AUTO) private Long id; @ApiModelProperty("用户名") private String userName; private String password; private Date creatTime; } ``` 除此之外: **swagger的常用API** 1. api标记 Api 用在类上,说明该类的作用。可以标记一个Controller类做为swagger 文档资源,使用方式: ```cpp @Api(value = "/user", description = "Operations about user") ``` 2. ApiOperation标记 ApiOperation:用在方法上,说明方法的作用,每一个url资源的定义,使用方式: ```cpp @ApiOperation( value = "Find purchase order by ID", notes = "For valid response try integer IDs with value <= 5 or > 10. Other values will generated exceptions", response = Order, tags = {"Pet Store"}) ``` 3. ApiParam标记 ApiParam请求属性,使用方式: ```cpp public R save(@RequestBody @ApiParam(value = "save user", required = true) User user) ``` 4. ApiResponse ApiResponse:响应配置,使用方式: @ApiResponse(code = 400, message = "Invalid user supplied") 5. ApiResponses ApiResponses:响应集配置,使用方式: @ApiResponses({ @ApiResponse(code = 400, message = "Invalid Order") }) 6. ResponseHeader 响应头设置,使用方法 @ResponseHeader(name="head1",description="response head conf") 例如:我在我的上传文件的controller上加上注解说明 ```cpp @Api(tags = "OSS管理") @RestController public class OssController { @ApiOperation("获取上传图片的api凭证") @GetMapping("/oss/upload") protected R poliocy(HttpServletRequest request, HttpServletResponse response) { } } ``` 这样就可以对我们的接口进行中文说明。 ![](https://img-blog.csdnimg.cn/20201002225133390.png) 2.5、接口测试 swagger还为程序员提供了接口的测试功能,例如:测试login接口,填上需要的信息,点击下方的`Try it out`进行测试。 ![](https://img-blog.csdnimg.cn/20201002225438341.png) 从显示的数据中可以清晰地到看到我们所需要的信息:请求地址、请求头、请求体、状态码、回应头信息。 ![](https://img-blog.csdnimg.cn/20201002225639935.png) 三、拓展 这里有这样一个问题,也常常会作为面试题出现: ```cpp 问题:怎么使swagger在开发环境下使用,发布时不使用? ``` 答:需要建立好几个`springboot`配置文件,例如`application.yml`、`application-pro.yml`、`application-dev.yml`,分别用于默认、部署后、开发的环境中。在`application.yml`指定当前使用的是哪一个 ```yml spring: profiles: active: dev ``` 然后,再在swagger配置中配置,如果当前环境使用的是dev的配置文件,就是用`enable(flag)`,来关闭swagger功能。 这样就能使项目上线后不暴露接口,有效的提高安全性。 ```cpp @Bean public Docket docket(Environment environment){ Profiles profiles = Profiles.of("dev"); boolean flag = environment.acceptsProfiles(profiles); return new Docket(DocumentationType.SWAGGER_2) .groupName("lomtom") .apiInfo(apiInfo()) .enable(flag); } ``` > 总的来说,swagger是一个很好用的api文档工具,并且上手难度不高,最关键的是能减少前后端程序员的打斗次数,你值得拥有。 > > [1、swagger 介绍及两种使用方法](https://blog.csdn.net/weixin_37509652/article/details/80094370)
2021-01-04
**每天一个小知识**,不定期更新 <hr style=" border:solid; width:100px; height:1px;" color=000000 size=1"> (文章目录) <hr style=" border:solid; width:100px; height:1px;" color=000000 size=1"> 一、问题 事情是这样的,由于我最近在刷题,刷到这样一道题: ```cpp 你是产品经理,目前正在带领一个团队开发新的产品。 不幸的是,你的产品的最新版本没有通过质量检测。 由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。 实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。 示例: 给定 n = 5,并且 version = 4 是第一个错误的版本。 调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以,4 是第一个错误的版本。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/first-bad-version ``` 乍一看,题目是挺简单的。 直接采用二分法就可以立马解决。 于是我潇潇洒洒的写下 ```java public class Solution extends VersionControl { public int firstBadVersion(int n) { int left = 1, right = n; while(left < right){ int mid = (right + left) / 2; if (isBadVersion(mid)){ right = mid; } else { left = mid + 1; } } return left; } } ``` 也许,你看到我的代码,你会想没错啊!!! 自己也会这样写。 是的在我之前所有的二分法都是这样写的。 当我满怀信心的点了提交,然而 ```cpp 运行失败: Time Limit Exceeded 测试用例:2126753390 1702766719 ``` ?????????Why 二、分析 **须知:`Integer`都有自己的表示范围,他有定义`MAX_VALUE`和`MIN_VALUE`** ```cpp /** * A constant holding the minimum value an {@code int} can * have, -2<sup>31</sup>. */ @Native public static final int MIN_VALUE = 0x80000000; /** * A constant holding the maximum value an {@code int} can * have, 2<sup>31</sup>-1. */ @Native public static final int MAX_VALUE = 0x7fffffff; ``` **,当我们的数超过他所规定的最值时,Integer将无法表示。** 因此在我们上述算法中, 1. left <= `MAX_VALUE`和 right <= `MAX_VALUE`是肯定的 2. 但是left+right <= `MAX_INT` 我们无法确定,所以会造成栈溢出。 那么知道问题所在,我们怎么修改我们的代码呢? 我们可以使用 ```cpp int mid = left + (right - left) /2; ``` 来代替 ```cpp int mid = (right + left) / 2; ``` 他们最后的结果都是一致的,却能够有效的避免栈溢出问题。 三、结论 所以在我们使用二分法时,我们可以使用`left + (right - left) /2`来代替`(right + left) / 2`,来避免栈溢出。 > 参考: > [1、为什么left +(right-left)/ 2不会溢出?](https://stackoverflow.com/questions/27167943/why-leftright-left-2-will-not-overflow) > [2、第一个错误的版本](https://leetcode-cn.com/problems/first-bad-version)

CONTACT ME

You can contact me in the following ways

Copyright © 2019-2020 Made with love By LomTom | 湘ICP备19023870号 | 经历风雨 666 天 6 小时 6 分 6 秒