0%

最近在刷leetcode算法的入门题,刷到二叉树,一开始浑浑噩噩,后来掌握了套路,自己搞定一个,而且很优雅,比留言中的大部分都优雅,嗯,写个日志自嗨一把。
所有刷题都提交到我的github上了,具体位置:windanchaos的github

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
题目要求:
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:

0
/ \
-3 9
/ /
-10 5

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
阅读全文 »

最近在看一本讲数据库架构的英文书,书中很多次提及到一个叫缓存的词语,在我们商城的业务系统中也经常听到缓存这个词语。于是百度找到这篇文章。内心觉得总结很到位。转自:缓存技术原理

一、前言

应用中使用缓存技术,往往可以大大减少计算量,有效提升响应速度,让有限的资源服务更多的用户。但是,似乎还没有一种缓存方案可以满足所有的业务场景,我们需要根据自身的特殊场景和背景,选择最适合的缓存方案,尽量以最小的成本最快的效率达到最优的目的。本文将从多个方面对缓存进行分析,以便作为选择缓存方案的考量。
二、文章要点

三、缓存的理解 3.1 狭义的理解

缓存指的是 CPU 缓存,当 CPU 要读取一个数据时,首先从 CPU 缓存中查找,找到就立即读取并送给 CPU 处理;没有找到,就从速率相对较慢的内存中读取并送给 CPU 处理,同时把这个数据所在的数据块调入缓存中,可以使得以后对整块数据的读取都从缓存中进行,不必再调用内存。

阅读全文 »

问题描述:
我们的tomcat启动了apr启动https端口,我设置了systemd的tomcat.service的文件,使用systemctl start tomcat,始终无法识别apr的环境变量。研究了一会后解决。
先贴tomcat.service最终设置,只需加一行配置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[Unit]
Description=java tomcat project
After=syslog.target network.target

[Service]
Type=forking
User=user
Group=user
EnvironmentFile=/opt/apache-tomcat/bin/config
ExecStart=/opt/apache-tomcat/bin/startup.sh
ExecReload=
ExecStop=/arthas/servers/apache-tomcat-8.5.4-80/bin/shutdown.sh
PrivateTmp=true

[Install]
WantedBy=multi-user.target
阅读全文 »

git在维护版本库的时候统一使用的是LF,这样就可以保证文件跨平台的时候保持一致。
在Linux下默认的换行符也是LF,那也就不存在什么问题。
在Windows下默认的换行符是CRLF,那么我们需要保证在文件提交到版本库的时候文件的换行符是LF,通常来说有两种方法:

1
2
3
4
5
6
# 在工作区使用CRLF,使用git commit提交的时候git帮你把所有的CRLF转换为LF。
git config --global core.autocrlf true
# 在工作区使用LF
git config --global core.autocrlf input
# 避免文件中有混用换行符
git config --global core.safecrlf true
阅读全文 »

最近在践行代码,先把尚学堂的习题做完,遇到有点代表的就发个日志。
以下算法时间复杂度为N,还可以。这个好像是用了某种算法,具体叫动态规划法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
103. 【上机】编程求:∑1+∑2+……+∑100
这里输入最大数100作为参数
*/
public void sigma(int num){
//利用数组记录∑n的值,数组的index=n,特征:∑n=∑(n-1)+n
//数组下标等于数字,数组index为0的丢弃
int[] array_tmp=new int[num+1];
int sum=0;
for(int i=1;i<num+1;i++){
//数组index为0时,默认值0,可直接迭代
array_tmp[i]=array_tmp[i-1]+i;
sum=sum+array_tmp[i];
}
System.out.println("∑1+∑2+……+∑"+num+"的和为:"+sum);
}
阅读全文 »

修复问题描述

阿里云上的安全监测提示:
近日,Apache软件基金会(ASF)向Apache Struts项目管理员发布了关于CVE-2016-1000031漏洞的安全公告,其中披露一个Commons FileUpload库的历史高危漏洞CVE-2016-1000031,而2.3.x系列版本的Apache Struts2仍在使用低版本的Commons FileUpload库,该库作为Struts2的一部分,被用作文件上传的默认机制,远程攻击者利用该漏洞可直接获得服务器权限。2.5.12以上版本的Struts2暂不受影响。
注意:java类web应用的修复一般都需要重启应用
方案一:
升级至2.5.18及以上版本的Struts2,官方下载链接:https://struts.apache.org/download.cgi
方案二:
升级Struts2依赖的Commons FileUpload库版本至最新1.3.3,官方下载地址:https://commons.apache.org/proper/commons-fileupload/download_fileupload.cgi

阅读全文 »

由低向上的学习计算机是一条比较漫长的道路。但是,得来的知识却是体系化的。而且越到上边,学习的理解的效率是越高的(暂且自我欺骗,毕竟还没达到那高度)
下面就最近研究和学习做一个复盘。以问题出发为脉络。
1、计算机是怎么做运算的?
关键字:二进制、逻辑门
2、在问题1的基础上又问:为什么是二进制?
3、CPU是如何工作?

1、计算机是怎么做运算的?

回答这个问题,要先弄懂人类在使用10进制做计算时的方法,不赘述。
10进制方法迁移到二进制。基本的加法、乘法(可转成进位的加法),减法转成加法实现,除法转成乘法实现(这个我还没深究)。
进制之间可以平滑的换算。

数和进制的抽象

(这是我独立思考得出的,未见有人说过,或者有但我不了解)。
位和进制大小、进位。是三个基本元素。
位是进位中的位,是进制数的承载单元。位只能承载(0到进制-1)的数。比如:10进制中,一个位可以放0-9的数字,到10的时候就需要进位。二进制,最大放1,到2就要进位。
进制大小:就是所谓的2、10、16。
进位:位中承载的数等于进制大小时,发生的高位+1行为。

阅读全文 »

正则引擎

正则引擎主要可以分为两大类:一种是DFA,一种是NFA。这两种引擎都有了很久的历史(至今二十多年),当中也由这两种引擎产生了很多变体!于是POSIX的出台规避了不必要变体的继续产生。这样一来,主流的正则引擎又分为3类:一、DFA,二、传统型NFA,三、POSIX NFA。
DFA 引擎在线性时状态下执行,因为它们不要求回溯(并因此它们永远不测试相同的字符两次)。DFA 引擎还可以确保匹配最长的可能的字符串。但是,因为 DFA 引擎只包含有限的状态,所以它不能匹配具有反向引用的模式;并且因为它不构造显示扩展,所以它不可以捕获子表达式。
传统的 NFA 引擎运行所谓的“贪婪的”匹配回溯算法,以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。因为传统的 NFA 构造正则表达式的特定扩展以获得成功的匹配,所以它可以捕获子表达式匹配和匹配的反向引用。但是,因为传统的 NFA 回溯,所以它可以访问完全相同的状态多次(如果通过不同的路径到达该状态)。因此,在最坏情况下,它的执行速度可能非常慢。因为传统的 NFA 接受它找到的第一个匹配,所以它还可能会导致其他(可能更长)匹配未被发现。
POSIX NFA 引擎与传统的 NFA 引擎类似,不同的一点在于:在它们可以确保已找到了可能的最长的匹配之前,它们将继续回溯。因此,POSIX NFA 引擎的速度慢于传统的 NFA 引擎;并且在使用 POSIX NFA 时,您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索,而非较长的匹配搜索。
使用DFA引擎的程序主要有:awk,egrep,flex,lex,MySQL,Procmail等;
使用传统型NFA引擎的程序主要有:GNU Emacs,Java,ergp,less,more,.NET语言,PCRE library,Perl,PHP,Python,Ruby,sed,vi;
使用POSIX NFA引擎的程序主要有:mawk,Mortice Kern Systems’ utilities,GNU Emacs(使用时可以明确指定);
也有使用DFA/NFA混合的引擎:GNU awk,GNU grep/egrep,Tcl。
举例简单说明NFA与DFA工作的区别:
比如有字符串this is yansen’s blog,正则表达式为 /ya(msen|nsen|nsem)/ (不要在乎表达式怎么样,这里只是为了说明引擎间的工作区别)。 NFA工作方式如下,先在字符串中查找 y 然后匹配其后是否为 a ,如果是 a 则继续,查找其后是否为 m 如果不是则匹配其后是否为 n (此时淘汰msen选择支)。然后继续看其后是否依次为 s,e,接着测试是否为 n ,是 n 则匹配成功,不是则测试是否为 m 。为什么是 m ?因为 NFA 工作方式是以正则表达式为标准,反复测试字符串,这样同样一个字符串有可能被反复测试了很多次!
而DFA则不是如此,DFA会从 this 中 t 开始依次查找 y,定位到 y ,已知其后为a,则查看表达式是否有 a ,此处正好有a 。然后字符串a 后为n ,DFA依次测试表达式,此时 msen 不符合要求淘汰。nsen 和 nsem 符合要求,然后DFA依次检查字符串,检测到sen 中的 n 时只有nsen 分支符合,则匹配成功!
由此可以看出来,两种引擎的工作方式完全不同,一个(NFA)以表达式为主导,一个(DFA)以文本为主导!一般而论,DFA引擎则搜索更快一些!但是NFA以表达式为主导,反而更容易操纵,因此一般程序员更偏爱NFA引擎! 两种引擎各有所长,而真正的引用则取决与你的需要以及所使用的语言!

阅读全文 »

目录

老生常谈,再谈谈测试职业发展

有这么个普遍现象

测试招聘者,特别是一、二线互联网公司的招聘者最苦恼的事儿就是招人。想找到一个合适的人难于上青天,每天各种撒网,简历看几百份,面大几十人,能捞到一个中意的小伙伴就谢天谢地了。但同时很多测试小伙伴发现找工作很难,特别是进大一点的厂,他们特别挑:代码要会写,要有软件架构能力,问一大坨平时根本用不到的技术问题,还挑经验,挑沟通能力,挑这挑那,有时候还特么挑学历、挑年龄。。。 供求总难以匹配起来,造成了双方都很痛苦。

Why?

能力要求不匹配是最核心的问题。软件、互联网近20年来飞速成长,其实也经历了很多阶段。行业软件兴盛阶段和外包兴盛阶段(2000-2010年)行业进入了大量的测试人员,当时最主流的测试实践是:重心放在系统验收阶段。测试人员的主要工作基本都投入在了基于业务的黑盒测试上,对代码能力、系统理解的能力要求不多。2010年后,互联网行业的真正兴起让国内软件开发模式开始缓慢调头,快速迭代的模式逐步兴起,开发周期越来越短,迭代越来越快,但系统越来越越庞大、复杂。原来的测试工作模式和工作范围越来越无法满足要求了。但大量从业人员技能范围转变是一件很难的事情,行业是有巨大惯性的。从宏观上看大量QA技能转变跟不上需求转变是造成市场供求不匹配的主要原因

阅读全文 »

navicat中的explain

单条查询语句的性能分析。

阿里云混合云数据库管理HDM方案

利用阿里云提供的混合云,无侵入的方式监控数据的各项性能和指标。

sqlprofiler

工具的机制是在本机启动一个拦截服务(127.0.0.1:4040),本机的开发环境需要将jdbc连接串修改为指向该ip和端口,拦截服务获取sql后,传递给数据库并执行,从而统计出相关数据。
官网:http://www.profilesql.com/

集成druid

Druid是Java语言中最好的数据库连接池。Druid能够提供强大的监控和扩展功能。具体用法可自行百度。
GitHub:https://github.com/alibaba/druid

监控slowSQL

看咋个实现了。