【github 自动部署】github实现自动部署

RECOMMEND

一、题目描述: 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 一般来说,删除节点可分为两个步骤: 首先找到需要删除的节点; 如果找到了,删除它。 说明: 要求算法时间复杂度为 O(h),h 为树的高度。 示例: >root = [5,3,6,2,4,null,7] > key = 3 >![](https://img-blog.csdnimg.cn/20210115133530614.png) >给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。 > >一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。 > ![](https://img-blog.csdnimg.cn/20210115133552237.png) >另一个正确答案是 [5,2,6,null,4,null,7]。 > ![](https://img-blog.csdnimg.cn/20210115133608480.png) 二、解答 分析 解题思路: 首先,这个题目可以根据删除的节点的左右节点来判断。 而找到该节点是非常简单的,因为这棵树是二叉搜索树,而二叉搜索树的特性,左节点的值一定小于该节点值,右节点的值一定大于该节点的值,所以直接搜索就可以找到该值。 所以重点在于怎么判断该节点的左右节点的情况。 大致可以分为四种: 1. 该节点没有左节点,也没有右节点 2. 该节点没有左节点,但有右节点 3. 该节点有左节点,但没有右节点 4. 该节点有左节点,也有右节点 第一种:对于第一种情况,直接将该节点删除即可。 第二种:对于第二种情况,直接删除节点,将左节点代替该节点。 第三种:对于第三种情况:直接删除节点,将右节点代替该节点。 第四种:对于第四种情况,又可以分为三种情况: 1. 该节点的左节点没有右节点,将左节点代替该节点。 2. 该节点的右节点没有左节点,将右节点代替该节点。 3. 对于都有的情况,为了保证二叉搜索树的结构,我们 ① :可以用该节点的左节点最右节点的值代替该节点;②:也可以用该节点的右节点的最左节点的值代替该节点。 >而对于最后的情况,也就是第四种情况的第三种情况, >需要注意 >①中,如果最右节点还有左节点,我们可以用最右节点的左节点的值代替最右节点所在的位置; >②中,如果最左节点还有右节点,我们可以用最左节点的右节点的值代替最左节点所在的位置。 **再一次总结归纳:** 其实,最后第四种情况的第三种就包括了前面所有的方面, 在找到该节点后: 1. 如果该节点的左节点不为空,我们用该节点的左节点最右节点的值代替该节点; 2. 否则,如果该节点的右节点不为空,我们可以用该节点的右节点的最左节点的值代替该节点。 3. 否则,将该节点置空。 找到该节点,非常容易,因为左节点的值一定小于该节点值,右节点的值一定大于该节点的值。 所以,从根节点开始遍历 1. 如果遍历到的节点的值大于该值,该值一定处于该节点的右子树,往右遍历即可。 2. 否则,如果遍历到的节点的值小于该值,该值一定处于该节点的左子树,往左遍历即可。 3. 否则,就是找到了该值,在进行上述操作即可。 >时间复杂度:O(h),其中 n 为树的高度。 代码 ```java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode deleteNode(TreeNode root, int key) { if(root!=null){ if(root.val == key){ if(root.left != null){ root.val = leftMax(root); root.left = deleteNode(root.left, root.val); } else if(root.right != null){ root.val = rightMin(root); root.right = deleteNode(root.right, root.val); } else { root = null; } }else if(root.val>key){ root.left = deleteNode(root.left,key); }else{ root.right = deleteNode(root.right,key); } return root; } return null; } public int rightMin(TreeNode root) { root = root.right; while (root.left != null) root = root.left; return root.val; } public int leftMax(TreeNode root) { root = root.left; while (root.right != null) root = root.right; return root.val; } } ``` > 执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗:39.2 MB, 在所有 Java 提交中击败了8.92%的用户 三、官方解答 ```java class Solution { /* One step right and then always left */ public int successor(TreeNode root) { root = root.right; while (root.left != null) root = root.left; return root.val; } /* One step left and then always right */ public int predecessor(TreeNode root) { root = root.left; while (root.right != null) root = root.right; return root.val; } public TreeNode deleteNode(TreeNode root, int key) { if (root == null) return null; // delete from the right subtree if (key > root.val) root.right = deleteNode(root.right, key); // delete from the left subtree else if (key < root.val) root.left = deleteNode(root.left, key); // delete the current node else { // the node is a leaf if (root.left == null && root.right == null) root = null; // the node is not a leaf and has a right child else if (root.right != null) { root.val = successor(root); root.right = deleteNode(root.right, root.val); } // the node is not a leaf, has no right child, and has a left child else { root.val = predecessor(root); root.left = deleteNode(root.left, root.val); } } return root; } } ``` > 参考: > 1、[题目](https://leetcode-cn.com/problems/delete-node-in-a-bst/) > 2、[官方解答](https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/shan-chu-er-cha-sou-suo-shu-zhong-de-jie-dian-by-l/) >本文首发于CSDN,作者:lomtom >原文链接:**[https://blog.csdn.net/qq_41929184/article/details/112662236](https://blog.csdn.net/qq_41929184/article/details/112662236)** >个人网站:**[https://lomtom.top](https://lomtom.top)**,公众号:**博思奥园**,同步更新。 > > **你的支持就是我最大的动力。** ![](https://img-blog.csdnimg.cn/20200405094243147.png)
2021-01-17
一、题目描述: 给定一个无重复元素的有序整数数组 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
一、场景引入 前提背景 在某些场景下,例如淘宝京东这样海量的数据,高访问量的场景,无疑对数据库造成了相当大的负载,同时对于系统的稳定性和扩展性提出很高的要求。 而单个服务器所能够提供的服务以及负载都是有限的。 所以,为了系统的问题,以及较快的响应速度或处理能力,在数据库方面就有了集中解决方案,**分库分表,读写分离**,这些都能在一定程度上有效地减小单台数据库的压力。 而本文就是从读写分离角度来一探究竟。 实现原理 主要理解以下三个点就差不多了: **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

CONTACT ME

You can contact me in the following ways

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