二叉树的最小深度 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明:叶子节点是指没有子节点的节点。

示例:

给定二叉树[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回它的最小深度 2.

解题思路：
和二叉树的最大深度类似，但在递归的结束条件上有所不同，我们先回忆以下二叉树的最大深度问题：

1
2
3
4
5
6
7
public int maxHeight(TreeNode node){
    if(node == null)
    return 0;
    int left = maxHeight(node.left);
    int right = maxHeight(node.right);
    return Math.max(left,right)+1;
}

接下来言归正传，我们在找最小深度时，我们要明确什么是最小深度，就是根节点到最近叶子节点路径上节点的数量，那么我们在递归时可能遇到下面三种情况：
1.当root的左右子树都为null，那么这个节点就是叶子节点，返回1；
2.当root的左或右子树为null时，那么这个节点不是叶子节点，那么我们只能找到这个root不为空的子树的深度；
3.当root的左右子树都不为null时，我们返回左右子树中较小的深度+1；

1
2
3
4
5
6
7
8
9
10
11
public int minHeight(TreeNode node){
    if(node == null)
        return 0;
    if(root.left==null&&root.right==null)
        return 1;
    int left = minHeight(root.left);
    int right = minHeight(root.right);
    if(root.left==null||root.right==null)
        return Math.max(left,right)+1;
    return Math.min(left,right)+1;
}

展开全文 >>

回文字串的数量 

1
2
3
4
5
6
7
8
9
10
11
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

解题思路:
主要思路，我们使用中心扩散的思想，从反转中心向两边扩散，记录所有的回文子串的数量
其中有一些细节我们要注意：回文字串的长度分为奇偶，如果为奇数，中间的数就是回文中心，如果是偶数，我们令两个数均为对称中心，我们使用一个函数来统一实现 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int countSubstrings(String s) {
        int ans = 0;
        for(int i  = 0;i<s.length();i++){
            ans+=isReverse(s,i,i);
            ans+=isReverse(s,i,i+1);
        }
        return ans;
    }
public int isReverse(String s,int i,int j){
    int count = 0;
    while(i>=0&&j<=s.length()-1&&String.charAt(i)==String.charAt(j)){
        count++;
        i--;
        j++;
    }
    return count;
}

拓展：上述方法，主函数中遍历一遍s，调用函数中再次遍历s，复杂度o（n^2），所以我们可以使用解决最长回文字串的经典方法，马拉车算法，将时间复杂度降为o(n)，下面我们来分析以下马拉车算法:

展开全文 >>

转换AVL树 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

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

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

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

      0
     / \
   -3   9
   /   /
 -10  5

解题思路：
1.题中我们得知，这是一个升序链表，所以我们不需要根据节点的value再来判断添加到左还是右节点
2.由于二叉搜索树要求左右子树高度差<=1，所以我们取链表的中点作为根节点，如果链表个数为偶数，那么左边比右边少一个，如果链表个数为奇数，那么左右个数恰好相等
3.那么整棵树的root找到了，左子树的root其实就是左子树的中点，右子树同理，我们利用分治的思想，可以一直递归下去，直到左==右，则return null，我们返回已经排好的子节点
4.关于找链表中点我们可以用快慢指针的方法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public TreeNode sortedListToBST(ListNode head) {
        return dfsFillNode(head, null);
    }
	public TreeNode dfsFillNode(ListNode left,ListNode right) {
		if(left == right)
			return null;
		ListNode mid = findMiddleNode(left,right);
		TreeNode root = new TreeNode(mid.val);
		root.left = dfsFillNode(left, mid);
		root.right = dfsFillNode(mid.next, right);
		return root;
	}
	public ListNode findMiddleNode(ListNode node,ListNode right) {
		ListNode fast = node;
		ListNode slow = node;
		while(fast!=right&&fast.next!=right) {
			fast = fast.next.next;
			slow = slow.next;
		}
		return slow;
	}

展开全文 >>

DDL语言

DDL语句用于对数据库，表的管理
库的管理：
一、创建库
create database if not exists 库名
二、修改库
alter database 库名
三、删除库
drop database if exists 库名
表的管理：
一、创建表
create table if not exists 表名（
字段名 字段类型【约束】，
字段名 字段类型【约束】，
字段名 字段类型【约束】，….
）
二、修改表
1.添加列
alter table 表名 add column 列名 类型
2.修改列的类型或约束
alter table 表名 modify column 列名 新类型【新约束】
3.修改列名
alter table 表名 change column 旧列名 新列名 类型
4.删除列
alter table 表名 drop column 列名
5.修改表名
alter table 表名 rename 新表名
三、删除表
drop table if exists 表名
四、复制表
1.赋值表的结构
crate table 表名 like 旧表
2.赋值表的结构+数据
create table 表名
select 查询列表 from 旧表 where 筛选条件
数据类型
一、数值型
1.整型
tinyint 1子节
smallint 2子节
mediumint 3子节
int/integer 4子节
bigint 8子节
特点：
1.都可以设置无符号和有符号，默认有符号，通过unsigined设置无符号
2.如果超出了范围，会报out or range异常，会停留在临界值
2.浮点型
定点数：decimal（M，D）
浮点数：
float（M，D） 4子节
double（M，D）8子节
特点：
1.M代表整数部分+小数部分的个数，D代表小数位数
2.如果超出了范围，会报out or range异常，会停留在临界值
3.M和D都可以省略，但对于定点数，M默认为10，D默认为0
4.如果精度要求高，则有限考虑使用定点数
3.字符型
char：固定长度的字符，写法为char（M），最大长度不能超过M，其中M可以省略，默认为1
varchar：可变长度的字符，写法为varchar（M），最大长度不能超过M，M不能省略
4.日期型
year年
date日期
time时间
datetime日期+时间 8个子节
常见的约束
一种限制，用于限制表中的数据，为了保证表中的数据的准确性和可靠性
一、常见的约束
NOT NULL：非空，该字段的值必填
UNIQUE：唯一，该字段的值不可重复
DEFAULT：默认，该字段的值不用手动插入有默认值
PRIMARY KEY：主键，该字段的值不可重复并且非空 unique+notnull
FOREIGN KEY：外键，该字段的值引用了另外的表的字段
主键和唯一
1.区别：
①.一个表至多有一个主键，但可以有多个唯一
②.主键不允许为空，唯一可以为空
2.相同点：
都具有唯一性
都支持组合键，但不推荐
外键
1.用于限制两个表的关系，从表的字段引用了主表的某字段值
2.外键列和主表的被引用列要求类型一致
3.主表的被引用列要求是一个key
4.插入数据，先插入主表，删除数据，先删除从表
二、创建表时添加约束
create table 表名（
字段名 字段类型 not null，
字段名 字段类型 primary key，
字段名 字段类型 unique，
constraint 约束名 foreign key（字段名） references 主表（被引用列）

）
三、修改表时添加或删除约束
1.非空
添加非空
alter table 表名 modify column 字段名 字段类型 not null
删除非空
alter table 表名 modify column 字段名 字段类型
2.默认
添加默认
alter table 表名 modify column 字段名 字段类型 default 值
删除默认
alter table 表名 modify column 字段名 字段类型
3.主键
添加主键
alter table 表名 add primary key（字段名）
删除主键
alter table 表名 drop primary key
4.唯一
添加唯一
alter table 表名 add unique（字段名）
删除唯一
alter table 表名 drop index 索引名
四、自增长列
特点：
1.不用手动插入值，可以自动提供序列值，默认从1开始，步长为1
添加AUTO_INCREMENT
如果要更改起始值：手动插入值
如果要更改步长：set AUTO_INCREMENT = 值
2.一个表至多有一个自增长列
3.子增长列只支持数值型
4.子增长列必须为一个key

展开全文 >>

相同的树 

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
给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回false 
```  
题目即判断一颗二叉树是否为平衡二叉树，有两种思路，从顶到底和从底到顶  
**方式一：**  
从顶到底，便于想到，从顶到底判断以每个节点为根节点的子树是否是平衡二叉树，但某些节点的深度会被重复计算导致时间复杂度很高

class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null)
return true;
return (Math.abs(height(root.left)-height(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right));
//判断当前子树是否为平衡树，然后先序遍历判断当前子树的左子树，然后判断当前子树的右子树
}
public int height(TreeNode root) {
if(root==null)
return 0;
return Math.max(root.left==null?0:height(root.left), root.right==null?0:height(root.right))+1;
}
}

1
2
**方式二：**  
从底到顶递归，这样每个节点的深度只会被调用一次，这种方法类似于后序遍历，先判断当前节点的左右子树是否是平衡树，在判断当前节点，如果一个子树是平衡树则返回它的高度，否则返回-1，如果一个树的任意子树不是平衡树，则树不是平衡树
public boolean isBalanced(TreeNode root) {
    return height(root) >= 0;
}

public int height(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    } else {
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

展开全文 >>

DQL语言

DQL:全称DataQueryLanguage，数据查询语言，查询语句，凡是select语句都是DQL
基础查询: 

1
2
3
show databases;//展示所有库
use 库名;//切换库
show tables;//展示库中所有表单

1.去重关键字:字段前+distinct
2.起别名:AS + 别名，通常AS也可以省略
3.“+”的作用:
·两个数都为数值型，则进行加法运算
·只要一方为字符型，试图将字符型转换成数值型，若转换成功，则继续进行加法运算，若转换失败，则将字符型数值变为0
·只要一方为null，那么结果就是null
4.DESC:关键字+表名 显示表的结构
5.IFNULL函数用于判断是否为null，ifnull(字段,0)若字段为null，则转换为0
6.concat函数用于拼接字符串
条件查询:
一、语法:select 查询列表 from 表名 where 筛选条件
二、分类:
1.按条件运算符筛选:>,<,=,<>不等号,>=,<=
2.按逻辑运算符筛选:&&,||,!,and,or,not
3.模糊查询:
like:一般搭配通配符使用，可以判断字符型或数值型
通配符：%表示任意多个字符，可以是0个，_表示任意单个字符
between and(包括临界值),in,is null,is not null
排序查询:
一、语法：select 查询列表 from 表 where 筛选条件 order by 排序列表【asc|desc】
二、特点：
1.asc升序，如果不写默认升序，desc降序
2.排序列表支持单个字符按，多个字段，函数，表达式，别名，当有多个排序方式时，先按前者，若按前者有相同则按后一个排序
3.order by的位置一般放在查询语句的最后(除limit语句之外)
常见函数: 

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
1.字符函数
concat:连接
substr:截取字串，索引从1开始
upper:变大写
lower:变小写
replace:替代
length:获取长度
trim:去除前后空格
lpad:左填充
rpad:右填充
instr:获取字串第一次出现的索引
2.数学函数
ceil:向上取整
round:四舍五入
mod:取模
floor:向下取整
truncate:截断
rand:获取随机数，[0-1)之间
3.日期函数
now:返回当前日期+时间
year:返回年
month:返回月
day:返回日
date_format:将字符串转换为日期
curdate:当前日期
str_to_data:将日期转换为字符串
curtime:当前时间
hour:返回时
minute:返回分
second:返回秒
datediff:返回两个日期相差的天数

分组查询:
一、语法:
select 分组函数，分组后的字段
【where筛选条件】
group by 分组的字段
【having 分组后的是筛选】
【order by 排序列表】
二、特点

连接查询:(这里讲的是SQL99语法)
一、内连接
1.语法:
select 查询列表
from 表1 别名
【inner】join 表2 别名 on 连接条件
where 筛选条件
group by 分组列表
having 分组后的筛选
order by 排序列表
limit 语句
2.特点
·表的顺序可以调换
·内连接结果=多表的交集
·n表连接至少需要n-1个连接条件
二、外连接
1.语法：
select 查询列表
from 表1 别名
left|right|full join 表2 别名 on 连接条件
where 筛选条件
group by 分组列表
having 分组后的筛选
order by 排序列表
limit 语句
2.特点:
·查询的结果=主表中所有的行，如果从表和它匹配的将显示匹配行，如果从表没有匹配的则显示null
·left join 左边的是主表，right join右边的是主表
·一般用于查询除了交集部分的剩余的不匹配的行
子查询:
一、含义：嵌套在其他语句内部的select语句称为子查询或内查询，外面的语句可以是insert，update，delete，select等，一般select作为外面语句较多
二、分类
1.按出现的位置
·select后面:仅仅支持标量子查询
·from后面：表子查询
·where或having后面：标量子查询，列子查询，行子查询
·exists：标量子查询，列子查询，行子查询，表子查询
2.按结果集的行列
·标量子查询（单行子查询）：结果集为一行一列
·列子查询（多行子查询）：结果集为多行一列
·行子查询：结果集为多行多列
·表子查询：结果集为多行多列
分页查询：
一、应用场景：当要查询的条目数太多，一页显示不全
二、语法：
select 查询列表
from 表
limit 【offset，】size；
·注意：offset代表的是起始的条目索引，默认从0开始，size代表显示的条目数
·公式：假如要显示的页数为page，每一页的条目数为size
select 查询列表
from 表
limit （page-1）size，size
*查询总结：**
select 查询列表
from 表1 别名
连接类型 join 表2
on 连接条件
where 筛选
group by 分组列表
having 筛选
order by 排序列表
limit 起始条目索引，条目数

展开全文 >>

DML语言

DML操作是指对数据库中表记录的操作，主要包括表记录的插入（insert）、更新（update）、删除（delete）和查询（select），是开发人员日常使用最频繁的操作
==插入语句：==
一、方式一
·语法:
insert into 表名（列名…） values（值…）
·特点:
1.要求值的类型和字段的类型要一致或兼容
2.字段的个数和顺序不一定与原始表的字段个数和顺序一致但必须保证值和字段一一对应
3.假如表中有可以为null的字段，注意可以通过以下两种方式插入null值
①.字段和值都省略
②.字段写上，值使用null
4.字段和值的个数必须一致
5.字段名可以省略，默认为所有列
二、方式二
·语法：
insert into 表名 set 字段=值，字段=值…
两种方式的区别
方式一可以一次插入多行，语法如下:
insert into 表名【（字段名）】 values（值，…）,(值，…),…
==修改语句：==
一、修改单表的记录
语法： update 表名 set 字段=值，字段-值【where 筛选条件】
二、修改多表的记录
语法：update 表名1 别名
left|right|inner join 表2 别名
on 连接条件
set 字段=值，字段=值…
【where筛选条件】
==删除语句：==
方式一：使用delete
一、删除单表的记录
delete from 表名 where筛选条件 limit 条目数
二、级联删除
delete 别名1，别名2
from 表1 别名
inner|left|right join 表2 别名
on 连接条件
where筛选条件
·其中如果只想删除表1中的记录，delete后只用加别名1
方式二：使用truncate
truncate table 表名

展开全文 >>

大数运算(乘法&加法) 

1
2
3
4
5
6
7
给定两个字符串形式的非负整数num1 和num2，计算它们的和。
提示：

num1 和num2的长度都小于 5100
num1 和num2 都只包含数字0-9
num1 和num2 都不包含任何前导零
你不能使用任何內建 BigInteger 库，也不能直接将输入的字符串转换为整数形式

思路:模仿竖式相加的过程，巧妙运用carry解决进位的问题，主要注意最后一次进位，当carry不是0的时候，在append一个1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String addStrings(String num1, String num2) {
       int i = num1.length()-1;
		int j = num2.length()-1;
		int carry = 0;
		StringBuilder res = new StringBuilder();
		while(j>=0||i>=0) {
			int n1 = i>=0?num1.charAt(i)-'0':0;
			int n2 = j>=0?num2.charAt(j)-'0':0;
			int temp = n1+n2+carry;
			carry = temp/10;
			res.append(temp%10);
			i--;
			j--;
		}
		if(carry==0) {
			
			return res.reverse().toString();
		}
		return res.append(1).reverse().toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
给定两个以字符串形式表示的非负整数num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。

示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明：
num1和num2的长度小于110。
num1 和num2 只包含数字0-9。
num1 和num2均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理

思路:主要细节见注释:

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
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    public  String multiply(String num1, String num2) {
        if(num1=="0"||num2=="0") {
			return "0";
		}
		int i = num1.length()-1;
		int j = num2.length()-1;
		String s = "0";
		String ans = null;
		int numOfZero = 0;//用于num1和num2的每一位相乘时错位相加
		while(j>=0) {
			StringBuilder res = new StringBuilder();
			int carry = 0;
			while(i>=0) {//num1和num2的每一位相乘
				int n1 = num1.charAt(i)-'0';
				int n2 = num2.charAt(j)-'0';
				int temp = n1*n2+carry;
				carry = temp/10;
				res.append(temp%10);
				i--;
			}
			//记得加上最后一个carry
			if(carry==0) {
				res = res.reverse();
			}else {
				res = res.append(carry+"").reverse();
			}
			//用于错位相加
			for(int k = 0;k<numOfZero;k++) {
				res = res.append("0");
			}
			ans = add(s, res.toString());
			s = ans;
			i = num1.length()-1;
			j--;
			numOfZero++;
		}
		return ans;
			
    }
	public  String add(String num1,String num2) {
		int i = num1.length()-1;
		int j = num2.length()-1;
		int carry = 0;
		StringBuilder res = new StringBuilder();
		while(j>=0||i>=0) {
			int n1 = i>=0?num1.charAt(i)-'0':0;
			int n2 = j>=0?num2.charAt(j)-'0':0;
			int temp = n1+n2+carry;
			carry = temp/10;
			res.append(temp%10);
			i--;
			j--;
		}
		if(carry==0) {
			
			return res.reverse().toString();
		}
		return res.append(1).reverse().toString();
	}
}

展开全文 >>

相同的树 

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
给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例1:

输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true
示例2:

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false
示例3:

输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false
1
2
3
4
5
6
7
8
9
10
public boolean isSameTree(TreeNode p, TreeNode q) {
        //两者都到底了，没有返回肯定相同
        if(p == null&&q == null) return true;
        //两者深度不同，必不相同
		if(p == null||q==null) return false;
		//值不相同，直接返回
		if(p.val != q.val) return false;
		递归判断左子树和右子树
		return isSameTree(p.left, q.left)&&isSameTree(p.right, q.right);
    }

展开全文 >>

判断是否含有环状子链表

本文将提供两种解法：哈希表和双指针(快慢指针)
1.哈希表解法:我们将已经遍历过的节点加入到Set集合中，然后判断如果遍历的当前节点在集合中已存在，那么就是有环状结构，如果没有，将一直遍历到链表尾部，需要用额外的空间来辅助: 

1
2
3
4
5
6
7
8
9
10
11
12
public boolean hasCycle(ListNode head) {
    Set<ListNode> nodesSeen = new HashSet<>();
    while (head != null) {
        if (nodesSeen.contains(head)) {
            return true;
        } else {
            nodesSeen.add(head);
        }
        head = head.next;
    }
    return false;
}

2.利用双指针，利用fast和slow两个指针，可以想象成两个运动员在环形赛道上奔跑，fast在slow前方，那么总有一个时刻，fast会再次与slow相遇，我们就是采取这种想法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null) {
			return false;
		}
		ListNode slow = head;
		ListNode fast = head.next;
		while(slow!=fast) {
		    //如果fast能到达尾部，则不存在环，由于我们一次走两步，所以为了防止空指针，要判断两个位置
			if(fast==null||fast.next==null) {
				return false;
			}
			slow = slow.next;
			fast = fast.next.next;
		}
		return true;
	}

}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

蛙广志<br><br>总要变强<br>