- 博客(84)
- 收藏
- 关注
RSS订阅
原创 二叉树遍历：没那么简单
使用递归遍历二叉树，已经不能熟的不能再熟了，同时还有不少问题可以用到递归的方法去求解。本文的重点不是递归遍历二叉树。迭代的形式：1.前序遍历递归的方法是jvm为我们的方法调用隐式的准备了一个FILO的栈，迭代的形式就是手动维护一个栈。class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList
2020-11-20 22:29:17
171
原创 KMP算法，固定模板，以及两三道例题
class Solution {public: void getNext(int* next, const string& s) { int j = 0; next[0] = 0; for(int i = 1; i < s.size(); i++) { while (j > 0 && s[i] != s[j]) { j = next[j - 1]; .
2020-11-12 23:50:22
171
原创 Java集合类的整理
Java集合的重要性不言而喻，必须要熟练掌握常用的集合及其方法，还有一些源码，例如面试经常会问到的HashMap，ConcurrentHashMap源码。其实看源码也不是仅仅为了应付面试，能够知道集合的底层原理，对于编程和理解非常有帮助，还有对于性能的选择。...
2020-11-09 23:11:00
63
原创 String类方法使用整理
String是一个经常使用的类，其中的类方法数量也不少，且比较重要，开个帖子记录下一些方法的使用。1. public String[] split(String regex)个人理解就是用regex字符串去分割String对象，并将每一段放入String[]数组中，例如最简单的test1 @Test public void splitTest1() { String test = "a b c d"; String[] split = test
2020-11-09 23:05:24
113
原创 通过异或位运算(^)的方式交换两个元素
在一般交换两个元素时，一般采用一个辅助变量tmp来实现，如下：tmp = s[high];s[high] = s[low];s[low] = tmp;实际上还可以通过异或位运算(^)，并且不需要辅助变量的方式，如下：s[high] ^= s[low];s[low] ^= s[high];s[high] ^= s[low]; ...
2020-11-09 18:50:49
343
原创 Inter.MAX_VALUE和MIN_VALUE,2^31-1,-2^31
做题的时候经常碰到关于数值的取值范围，比如Integer.MAX_VAULUE = 2 ^31 - 1 =2,147,483,647Integer.MIN_VALUE = -2 ^ 31 =-2,147,483,648这时候可以根据具体的数值大小来编程。
2020-10-29 10:02:31
256
原创 剑指 Offer 11. 旋转数组的最小数字
类似于已经排序的数组，一般都是用二分法来求解，定义两个首尾指针，当两个指针重合时，则返回，主要是找到arr[mid]与arr[i]和arr[j]大小判断后，指针的移动情况。题目中的数组是由一个升序数组反转来的，因此可将数组分为两部分，左半部分为较大部分数组，右半部分为较小升序数组，我们要找的就是右部分数组的第一个元素。首先定义首位指针i,j，在i < j的时候进行指针移动，当arr[i] < arr[j]时，通过题目给的示例数组，可以发现此时目标元素在i和mid指针中间，因此让j =..
2020-10-02 09:38:51
76
原创 剑指 Offer 10- II. 青蛙跳台阶问题
这道题是斐波那契数列的变种，也可以说是动态规划，都是从下往上挨个计算，直到我们需要的那个数值。第n个台阶的所有跳法，等于第n-1个台阶的跳法+第n-2个台阶的跳法。原因如下：代码：class Solution { public int numWays(int n) { if (n < 0) return -1; int f0 = 1, f1 = 1, ans = 0; if (n < 2) return 1; ...
2020-09-30 15:43:54
121
原创 剑指 Offer 14- II. 剪绳子 II
这道题与I类似，但是数据量更大，且需要求模，用我之前的代码我时没有AC。借此也在这里给出一种数学推导，知道要怎么划分之后，面向答案编程。
2020-09-30 12:26:15
81
原创 剑指 Offer 14- I. 剪绳子
这道题乍一看感觉彷佛没思路，例如要切多少段绳子，每段绳子的长度是多少才能让绳子段数乘积最大，似乎组合性太多了，根本找不出来。但是可以换一个角度（动态规划），定义一个函数y=f(n)，表示绳子长度为n时，满足题目要求的最大值。比如f(12)，就表示绳子长度为12时，题目要求的最大值就是这个。动态规划一般都会用到数组来记录每一个f(n)的值，并且计算过程是从下向上的，我们一般可以从题目或手动计算一些初始信息，比如f(0)，f(1), f(2)等等，然后根据f(n)和f(n-1)，f(n-2)来计算出f(..
2020-09-30 10:38:08
74
原创 剑指 Offer 10- I. 斐波那契数列
很明显可以根据斐波那契额数列的定义f(n) = f(n-1) + f(n-2)，可以给定初始条件，利用递归来做。但是像这种情况，递归的话先不说内存的问题，每一次计算时，因为是从上向下计算的，所以会有大量的重复数据，并且这个重复数据的出现对f(n)并没用帮助。这种情况一般采用从下向上开始计算，并且不是递归的形式，而是采用辅助变流...
2020-09-30 10:09:30
119
原创 剑指 Offer 09. 用两个栈实现队列
队列的特点是先进先出，而栈的特点是先进后出，但是这道题我们可以利用两个栈来实现队列的特点。定义了两个栈，queue作为主要的栈，aux为辅助队列。初始时刻优先将数值放入到queue中，当queue中有一个数值时，就将余下的数值放入到aux中。队列首个数值出队时，这是queue中是空，然后需要将aux中的数值弹出并压入到queue中，这时的顺序已经翻转过来了，再下次出队时，直接pop即可。当queue为空时，执行前述步骤。代码如下：class CQueue { Stack<In..
2020-09-25 22:19:54
80
原创 剑指 Offer 07. 重建二叉树
首先要懂得前序遍历和中序遍历，可以写出两个数组，自己手动来重建一下二叉树，来看看重建二叉树是怎么一个流程。以图中给出的二叉树为例，根据前序遍历的特点，可知前序遍历的首尾数字是根节点，比如这个时候根节点数值为3，可以在中序遍历中第2个位置找到数值3，在3左边的9为3的左子树，右边的15，20，7为右子树。同时可以把前序数组划分为两个数组，即左子树的前序遍历数组9，右子树的前序遍历数组20，15，7，采用递归的方式进行求解。我自己的写法中，是以中序遍历为依据返回节点的。当中序遍历数组的左边指...
2020-09-25 21:43:02
66
原创 剑指 Offer 06. 从尾到头打印链表
链表定义：/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */1.递归：如果题做的多了，一下就能想出用递归的方式去做，递归还是自己多做题多领会吧，实在想不过来去算一遍数学中的均差。代码如下：class Solution { ...
2020-09-24 20:09:05
79
原创 剑指 Offer 05. 替换空格
像有的题目，不要陷入一个圈套，无法换个角度来求解问题。比如这道题，要求去替换空格，初次做的话可能会想着怎么在原字符串上找到空格，然后把空格替换。其实可以换个角度，我们重新来构建一个字符串。简单题，可以用一个StringBuilder实现动态从0构建题目要求的字符串。遍历原来那个字符串，如果遇到空格则添加%20，否则直接添加当前遍历到的char。代码如下：class Solution { public String replaceSpace(String s) { ...
2020-09-24 19:48:36
66
原创 剑指 Offer 04. 二维数组中的查找
这道题也是需要抓住给的条件，两个递增。我们可以利用右上角或者左下角两个点作为起点，因为这两个点向两个方向有不同的的大小变化，可以更快的剔除不符合条件的行或者列。代码如下：class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { //一定不要忘记代码的鲁棒性 if (matrix == null || matrix.length == 0 || ...
2020-09-24 19:36:50
76
原创 剑指 Offer 03. 数组中重复的数字
题目如图片所示。像这种比较简单的题目，除了采用一些比较“暴力”的解法，求解的关键一般在于问题给出的特殊条件，本题中数组nums的长度为n,其中所有的数字都在0~n-1范围内就是解题关键点1.比较笨拙的办法：直接将数组排序，例如按升序排列，此时重复的数字一定是挨着的，因此可以用一个循环来判断是否有重复。代码如下：class Solution { public int findRepeatNumber(int[] nums) { Arrays.sort(nums);..
2020-09-24 19:26:30
79
原创 剑指 Offer 13. 机器人的运动范围
这道题也需要采用回溯法来解决，同时又可分为深度优先dfs和广度优先bfs实现。深度优先代码如下：class Solution { int row, column; boolean[][] isVisited; public int movingCount(int m, int n, int k) { row = m; column = n; isVisited = new boolean[m][n]; ...
2020-09-16 09:03:17
103
1
原创 剑指 Offer 12. 矩阵中的路径
题目如图片所示。这种题需要用到回溯法（等会开个算法专栏，系统学习一下），主要是要设定好减枝条件和返回条件。这道题采用了深度优先方法，代码如下：class Solution { public boolean exist(char[][] board, String word) { if (board == null || word.length() < 1 || word == null) return false; char[] target = ..
2020-09-16 08:51:58
73
原创 剑指 Offer 32 - III. 从上到下打印二叉树 III （左右顺序交替，一层一层打印）
此题目又增加了一个要求，每一层地打印顺序变换着来。对此我的想法是，加入一个判断地flag，通过if（flag）来实现顺序地改变，同时每一层的临时数据结构由前面两道题的ArrayList变为LinkedList，实现两端都能添加数据。改变主要体现在，每一层的list，添加节点的位置，前面两道都是直接使用list.add()将数值添加到最后，改变时可以用list.adFirst()方法，就能实现顺序的翻转；或者可以使用工具类Colletcions.reverse()方法，添加完毕后直接翻转整个链表。我...
2020-09-11 12:23:03
110
原创 剑指 Offer 32 - II. 从上到下打印二叉树 II （要求一层一层地输出）
这道题目增加了一个要求，即一层一层的打印节点，因此重点在于如何分层。可以记录下队列未加入新节点时的数组长度，即本层的节点个数，然后用循环的方式将这一层的节点输出。我的代码如下：class Solution { public List<List<Integer>> levelOrder(TreeNode root) { if (root == null) return new ArrayList<>(); Linke..
2020-09-11 11:53:45
73
原创 剑指 Offer 32 - I. 从上到下打印二叉树
很明显这里不能用解决树问题最常用的前序，中序，后续算法。结合队列先进先出的特点，可以利用队列来完成此题。我的代码：class Solution { public int[] levelOrder(TreeNode root) { if (root == null) return new int[0]; LinkedList<TreeNode> list = new LinkedList<>(); ArrayList..
2020-09-11 11:39:59
50
原创 HotSpot虚拟机对象探秘
#### 1.对象的创建 **1.**一般情况下创建一个对象，java中使用new关键字。当java虚拟机遇到一条字节码new指令时，首先检查这个指令的参数是否能在常量池中定位到一个类的符号引用，并且检查这个符号引用代表的类是否已被加载、解析和初始化过。如果没有，那么就先执行相应的类加载过程。 **2.**类加载检查通过后，虚拟机将为新生对象分配内存。根据java堆是否规整，或者所采用的垃圾收集器是否具备空间压缩整理能力，有两种内存分配方式：1.指针碰撞、2.空闲列表。 ...
2020-09-07 19:24:22
77
原创 JAVA内存区域——运行时数据区域
运行时数据区域：1.程序计数器：是一块较小的内存空间，可以看作是当前线程所执行的字节码的行号指示器。在JAVA虚拟机的概念模型里，字节码解释器工作时就是通过改变这个计数器的值来选取下一条需要执行的字节码指令，它是程序控制流的指示器，分支、循环、跳转、异常处理、线程恢复等基础功能都需要依赖这个计数器来完成。2.JAVA虚拟机栈：虚拟机栈描述的是java方法执行的线程内存模型：每个方法被执行的时候，java虚拟机都会同步创建一个栈帧用于存储局部变量表、操作数栈、动态连接、方法出口等信息。每一个方法...
2020-09-07 16:27:14
73
原创 win10使用scp向linux服务器传输文件可能会出现问题
之前一直用scp从win10系统向阿里云上面服务器上传文件，回到学校之后发现会报错，据阿里云错误报告显示有可能是常用地点发生了错误，通过网上查阅资料发现需要删除公钥信息。linux可以使用rm -rf 命令来删除，win10的话在C:\Users\当前用户目录\.ssh\knows_hosts路径下删除knows_hosts即可...
2020-09-05 19:57:52
573
原创 win10系统下用navicat修改的数据，通过命令流的方式让linux中的mysql执行一样的操作
数据库在win10中可以用navicat打开，修改数据（特别是一些特殊形式的数据，例如日期等）特别方便，但是在linux中就完全只能用sql命令了，不是很方便，为此我们可以使用如下方法，让linux中的mysql执行相同的操作1.打开mysql安装目录下面的bin文件，使用cmd，输入以下命令：如图所示，首先要输入mysqldump，然后-u, -p指定数据库的用户名和密码，--databases xxx 指定数据库 > xxx 指定.sql文件生成的路径和文件名称。2.将生成的sql
2020-09-05 19:40:29
132
原创 【docker】设置linux主机开机时，docker里面的镜像自动启动
在本地项目中，用到了linux虚拟机docker中的redis，因为不想让linux虚拟机自动开启，又觉得开机后启动linux，又要进去手动运行redis镜像，有些麻烦。有种方式可以解决这个麻烦：docker update --restart=always "镜像id或容器别名"这样linux开机之后，docker就会自动运行你设置的镜像，也不用我登入linux手动开启了关闭自动开启：docker update --restart=no "镜像id或镜像别名"...
2020-08-22 13:43:40
1337
原创 剑指 Offer 67. 把字符串转换成整数
题目及例子如上。本题核心的问题，就是根据字符串str来生成int型数值。比较简便的是从字符串的左边向右边生成：for (int i = 0; i < str.length(); i++) { ans = ans * 10 + str.charAt(i) - '0'; //将对应的'x'转换为实际的x数值 }这个核心问题解决之后，关键就是要得到符合我们要求的str，即str全为数字1.用flag去应对str首字母为+或者-的情况2.可以用St...
2020-08-19 00:16:12
169
原创 DeBug: Reids反序列化DateTime格式失败问题解决
在解决好redis存储DateTime类型的数据时，发现从redis提取数据即反序列化出现了错误。提示：无法转换为org.omg.CORBA.Object”错误。我的代码配置没有错误，原因是导包时为我自动导了一个org.omg.CORBA.Object的包删除掉这个导包即可正常运行...
2020-08-17 20:23:26
239
原创 Hyper-V管理下的centos7修改固定IP并连接网路
之前用vmware作为虚拟机时修改IP并连接外网我还是会的，用了Hyper_V（强推Hyper_V虚拟机）之后不会设置了。每次使用时都需要重新shh新ip地址，很麻烦。发现这篇文章完美解决问题。https://www.cnblogs.com/kasnti/p/11727755.html#1317616020以防失效，贴上另一个地址https://blog.csdn.net/tiging/article/details/104541130?utm_medium=distribute.pc_rele
2020-08-17 00:15:48
310
原创 剑指 Offer 66. 构建乘积数组
题目如上。思路如下：我们假设应该返回的答案为数组ans。显而易见B的数组长度应等于入参a数组的长度。按照题意，对应于ans数组中的每一个元素ans[i],其大小应为：<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><mi>a</mi><mi>n</mi><mi>s</mi><mo stretchy="false">...
2020-08-16 21:18:02
64
原创 服务器重启后mysql打开错误
https://blog.csdn.net/qq_32816723/article/details/108038541接着上一篇，我重启阿里云安装redis之后，打开网页发现提交的请求都是挂起状态，我才想到数据库服务器重启了，它的mysql服务并没有启动，因此网页查询不到数据。果然如此，但是我使用mysql -uroot -p123123并不能连接到mysql，给出了这样的错误：Can'tconnecttolocalMySQLserverthroughsocket'/...
2020-08-16 17:08:26
167
原创 centos安装redis6.06注意事项
我用的是阿里云免费的低配服务器，理论上它已经自带了gcc，但是安装redis6.06并且make时会出现错误，导致无法使用。解法方法如下：Redis6 跟之前有些不同，先要升级gcc的版本，输入以下命令：yum -y install centos-release-sclyum -y install devtoolset-9-gcc devtoolset-9-gcc-c++ devtoolset-9-binutilsecho "source /opt/rh/devtoolset-9/ena
2020-08-16 16:58:19
240
原创 秒杀项目优化措施
前面的待总结措施1：ngx服务器最初是与后端服务器短连接的，应使其为长连接，即keppalive这是短链接下，1000个线程循环30次的压测报告：这是长连接设置下的压测报告：emmm从图中可以看出短连接下的平均耗时竟然比长连接下更短，可能是因为长连接下样本多了3000+的原因？但是显而易见长连接下的吞吐量大幅度优于短连接（也可能是因为样本的原因？）或者是因为我的长连接没有设置正确？？anyway，反正这是一个优化手段。...
2020-08-15 20:07:20
298
原创 dubbo的基础环境搭建中日志依赖冲突问题
今晚刚结束学习（其实只是看完了视频）的springboot之中有用到过dubbo，将其中耽误我很久的bug写出来记录一下。linux安装dubbo镜像并配置端口映射之后，进入IDEA操作引入dependency依赖 <dependencies> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-
2020-07-28 21:35:03
446
原创 剑指 Offer 61. 扑克牌中的顺子
题目如图片所示。这道题目，其实一看到数组就能判断是不是能成为顺子，关键是要把人的思维转换成计算机的语言。此题主要用到了三个逻辑来判断。利用Arrays.sort()将数组排序，便于循环判断。 判断数组中是否有对子出现，若有对子（两个数一样），则肯定不能成为顺子。代码表现为，判断数组中前后两个数大小是相等。 计算出数组中0的个数，因为0可以当作任意数组使用。 计算出数组中不是连续数字的个数，并且得出数字间隔的总数。例如，3，4 这两个数是连续数字，则间隔是0，如果是3，6那么间隔就是6-3-1=..
2020-07-24 22:21:35
135
原创 Docker基础搭建
springboot里面学习到了docke，顺便温习一下linux。另外，微软牛逼，hyper-v，强无敌。先放一张命令表，以供参考1、搜索镜像[root@localhost~]#dockersearchtomcat2、拉取镜像[root@localhost~]#dockerpulltomcat3、根据镜像启动容器dockerrun‐‐namemytomcat‐dtomcat:latest4、dockerps查看运行中的容器5、停止运行中的容器do...
2020-07-19 22:52:14
72
原创 拦截器（Handler）与过滤器（Filter）的区别
拦截器是AOP思想的具体运用过滤器：servlet规范中，任何java web工程都可以使用在url-pattern中配置了/*后，可以对所有要访问的资源进行拦截拦截器：拦截器是springMVC框架自己的，只有使用了springMVC框架的工程才能使用拦截器只会拦截访问的控制器方法，如果访问的是jsp/html/css/image/js是不会拦截的自定义拦截器：实现HandlerInterceptor接口...
2020-07-06 11:03:27
2362
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人