leetcode入门之数组系列


前言

之前看到刷leetcode的技巧相关文章的时候,看到一个大神建议说,在一开始可以先按数组、字符串、链表、树的tag来刷,同时切记一开始先刷easy的。这样可以很大程度上将基础巩固,因为在后面的中等题以上都是会用到这些基础知识,如果有了牢固基础,相信在学习其他复杂的知识点就可以很快解决。下面是记录一些解题的技巧和好的题目。

题目

#leetcode-learn环节

下面的例题是在英文版本的leetcode中的explore环节的学习。

1、找出连续1的数组长度

image-20200603100321399

2、位数为偶数位的个数

image-20200603102137902

image-20200603102106796

3、数组的平方

image-20200603103439065

做法一

image-20200603103553978

做法二

image-20200603104524713

4、复制零并且移动数组

image-20200603221149084

image-20200603224454937

5、合并数组

image-20200604095218172

image-20200604095321571

6、删除数组中的重复数字

image-20200604164428972

image-20200604163548016

7、在升序的数组删除重复的数字。6的变式

image-20200610212514429

O(1)空间复杂度的数组复制

image-20200610213506246

#66-加一操作

image-20200523141838014

答案示例,这里的思路和清晰,这个题看似简单,但是里面的数组进位操作处理有点意思。

image-20200523142054241

#88 合并两个有序数组

image-20200524105015152

这里需要注意的是,这道题是直接在数组一上操作,不是开辟个新数组,这道题可以从后往前做,这样可以节省空间,更加高效,代码也很简洁。代码在下面

image-20200524105113799

#287-寻找重复数

题目如下,方框中是所需要注意的点

image-20200526085409344

采用快慢指针的方法,这是一个环的入口问题

#974 子数组被K整除的个数

image-20200527234100861

使用前缀和的方法-简单的讲是记录数组的前n项

有 N 个的正整数放到数组 A 里,现在要求一个新的数组 B,新数组的第 i 个数 B[i]是原数组 A 第 0 到第 i 个数的和。

#1464 数组中最大的两个数

image-20200611085650281

暴力法

image-20200611085928108

城市轨道交通与其它交通方式衔接的研究2017052397-颜华艺

DFS和BFS


约束

[toc]

约束

是SQL规范以约束的方式对表数据进行额外的条件限制,创建时候规定(CREATE TABLE),创建之后规定也可以(使用ALTER TABLE语句)

分类

具体有以下几种

1
2
3
4
5
6
NOT NULL 非空约束,规定某个字段不能为空
UNIQUE 唯一约束,规定某个字段在整个表中是唯一的
PRIMARY KEY 主键(非空且唯一)
FOREIGN KEY 外键
CHECK 检查约束(mysql不支持,但可以使用,没有效果便是)
DEFAULT 默认值

还可以分为单列和多列约束;列级和表级约束;

使用方法

NOT NULL

1
2
3
4
5
6
7
8
9
10
1.CRATE TABLE table1(
id INT(10) NOT NULL
);
# 创建之后的
2.ALTER TABLE emp
MODIFY sex VARCHAR(30) NOT NULL;
# 还可以取消
1.ALTER TABLE emp
MODIFY sex VARCHAR(30) NULL;
#(使用DEFAULT 'abc'增加默认值)

UNIQUE :唯一约束,允许出现多个空值:NULL。

1
2
3
4
5
ALTER TABLE USER ADD UNIQUE(NAME,PASSWORD);
# 删除约束
ALTER TABLE USER DROP INDEX uk_name_pwd;
# 表级约束
ALTER TABLE USER ADD CONSTRAINT uk_name_pwd UNIQUE(NAME,PASSWORD

PRIMARY KEY 约束 :相当于唯一约束和非空约束

1
2
3
4
5
6
7
8
9
10
11
/*MySQL的主键名总是PRIMARY,当创建主键约束时,系统默认会在所在的列和列组合上建立对应的唯一索引*/

# 组合模式
CREATE TABLE emp6(
id INT NOT NULL,
NAME VARCHAR(20),
pwd VARCHAR(15),
CONSTRAINT emp7_pk PRIMARY KEY(NAME,pwd)
);
# 删除 DROP 修改 MODIFY 添加 ADD
ALTER TABLE emp5 DROP PRIMARY KEY;

FOREIGN KEY 约束:外键约束是保证一个或两个表之间的参照完整性,外键是构建于一个表的两个字段或是两个表的两个字段之间的参照关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
外键约束的参照列,在主表中引用的只能是主键或唯一键约束的列
-FOREIGN KEY: 在表级指定子表中的列
–REFERENCES: 标示在父表中的列
*/
# 主表
CREATE TABLE classes(
id INT,
NAME VARCHAR(20),
number INT,
PRIMARY KEY(NAME,number)
);
# 从表
CREATE TABLE student(
id INT AUTO_INCREMENT PRIMARY KEY,
classes_name VARCHAR(20),
classes_number INT,
FOREIGN KEY(classes_name,classes_number)
REFERENCES classes(NAME,number)
);

#删除 添加和之前那些约束差不多

MySQL中使用limit实现分页

格式

1
2
3
4
select 查询列表
from
where 条件】
limit 【起始条目索引,】查询的条目数;
1
2
3
4
limit子句必须放在整个查询语句的最后!
前10条记录:SELECT * FROM table LIMIT 0,10;
第11至20条记录:SELECT * FROM table LIMIT 10,10;
第21至30条记录:SELECT * FROM table LIMIT 20,10;

mysql中的索引‘

索引是一种特殊的文件(InnoDB数据表上的索引是表空间的一个组成部分),它们包含着对数据表里所有记录的引用指针。

索引是一种数据结构。数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。就相当于目录。

缺点的一个是索引也是文件,占物理空间

创建索引

  • 在create table就创建
1
2
3
4
5
6
7
8
9
10
1.CREATE TABLE user_index2 (
id INT auto_increment PRIMARY KEY,
first_name VARCHAR (16),
last_name VARCHAR (16),
id_card VARCHAR (18),
information text,
KEY name (first_name, last_name),
FULLTEXT KEY (information),
UNIQUE KEY (id_card)
);
  • 创建table之后创建—使用ALTER TABLE
1
LTER TABLE table_name ADD INDEX index_name (column_list);
  • 使用CREATE INDEX命令创建
1
CREATE INDEX index_name ON table_name(column_list);

删除索引

  1. 格式:alter table 表名 drop KEY 索引名
1
alter table user_index drop KEY name;
  • 注意的是,如果主键自增长,则不可直接删除,要先解除自增长;不过很少删除主键

B树和B+树

  • 在B树中,你可以将键和值存放在内部节点和叶子节点;但在B+树中,内部节点都是键,没有值,叶子节点同时存放键和值。
  • B+树的叶子节点有一条链相连,而B树的叶子节点各自独立。

比较

1
2
3
4
5
1、B树只适合随机检索,而B+树同时支持随机检索和顺序检索;
2、B+树空间利用率更高,可减少I/O次数,磁盘读写代价更低。一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗。B+树的内部结点并没有指向关键字具体信息的指针,只是作为索引使用,其内部结点比B树小,盘块能容纳的结点中关键字数量更多,一次性读入内存中可以查找的关键字也就越多,相对的,IO读写次数也就降低了。而IO读写次数是影响索引检索效率的最大因素;
3、B+树的查询效率更加稳定。B树搜索有可能会在非叶子结点结束,越靠近根节点的记录查找时间越短,只要找到关键字即可确定记录的存在,其性能等价于在关键字全集内做一次二分查找。而在B+树中,顺序检索比较明显,随机检索时,任何关键字的查找都必须走一条从根节点到叶节点的路,所有关键字的查找路径长度相同,导致每一个关键字的查询效率相当。
4、B-树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。B+树的叶子节点使用指针顺序连接在一起,只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作。
增删文件(节点)时,效率更高。因为B+树的叶子节点包含所有关键字,并以有序的链表结构存储,这样可很好提高增删效率。

DFS和BFS

广度优先和深度优先搜索

前言

看着这两个搜索的前提的是读者具备图这一数据结构的基本知识,这些可以直接百度一波就了解了。图也像树一样,遍历具有很多的学问在里面,下面我将借用leetcode的题目讲解一下,虽然是图的遍历,但是借助树好像讲的更见浅白一点,不好的地方多指教。

广度优先搜索(BFS)

-对于树而言,就是一种层层遍历的感觉,在实现的过程中,常常借助的是辅助队列来实现,也就是借助先进先出的特性来实现的。下图来看。用BFS的话,就是3-9-20-15-7的结果。

整体实现来说,就是遍历root再来遍历左右子树,不过与DFS区别的是,这里是借助先进先出的特点,也就是要将前面的先排列出来,不用走到叶子结点才输出。一句话简单来说,BFS就是队列,入队列,出队列;

下面是借助leetcode的题目来巩固这个知识点,上面的图也是这个题的。题目要求层层从左往右遍历结点。

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
  class Solution {
public int[] levelOrder(TreeNode root) {
//特殊情况
if(root == null){
return new int[0];
}
//用队列来实现广度优先搜索
ArrayList<Integer> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
// 出列,这里的顺序就是先进先出,层层逐个遍历
TreeNode node = queue.poll();
list.add(node.val);
// 逐个入列,辅助队列也是BFS的关键点
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}

}
// 这样转换会慢一点
// int[] res = list.stream().mapToInt(Integer::valueOf).toArray();
int[] res = new int[list.size()];
for(int i = 0; i < list.size();i++){
res[i] = list.get(i);
}
//题目要求返回的是int[]
return res;



}
}


}

上面这道可以变形成输出结果不一样,也就是剑指offer中的后面两道-面试题31 - II. 从上到下打印二叉树和面试32题。

31题是要求输出的结果是不同数组的集合,每层的结点作为一个数组,解决代码如下

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
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return res;
}
//用队列来实现广度优先搜索
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
ArrayList<Integer> list = new ArrayList<>();
//用队列的长度来做,这里在for循环中,长度一直在变,所以要先将其取出来
//关键点:主要思想在于用每次的队列长度来 判定这一层的结点有多少
//正如一开始只有一个根结点,所以长度等于一,只需执行一次添加list
int size = queue.size();
for(int i = 0; i < size; i++){
// 出列,这里的顺序就是先进先出,层层逐个遍历
TreeNode node = queue.poll();
//这道题要求每层出一个数组
list.add(node.val);
// 逐个入列,辅助队列也是BFS的关键点
if(node.left != null){ queue.add(node.left);}
if(node.right != null){queue.add(node.right);}
}
//每层加完就添加到结果里面
res.add(list);

}

//题目要求返回的是List<List<>>
return res;



}

}

32题有和上面不一样的地方在于,第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。就是奇数偶数层不一样的遍历方式。可以通过借助一个布尔常量来实现。

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
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return res;
}
//用队列来实现广度优先搜索
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
boolean flag = true;
while(!queue.isEmpty()){
//这道题有实现头插法,为了高效,使用链表数组
List<Integer> list = new LinkedList<>();
//用队列的长度来做,这里在for循环中,长度一直在变,所以要先将其取出来
int size = queue.size();
for(int i = 0; i < size; i++){
// 出列,这里的顺序就是先进先出,层层逐个遍历
TreeNode node = queue.poll();
//关键点:这道题要求每层出一个数组,而且奇数行和偶数不一样
//奇数行是从左往右,偶数行是从右往左走
//借助一个布尔类型来完成
if(flag){
list.add(node.val);
}else{
//前面开始插
list.add(0,node.val);
}
// 逐个入列,辅助队列也是BFS的关键点
if(node.left != null){ queue.add(node.left);}
if(node.right != null){queue.add(node.right);}
}
//每次遍历完一行便开始更换布尔类型
flag = !flag;
//每层加完就添加到结果里面
res.add(list);

}

//题目要求返回的是List<List<>>a
return res;

}
}

深度优先搜索DFS

讲到DFS,很容易想到递归,没错它就是借助了递归的思想。在图中的描述是:深度优先搜索在搜索过程中访问某个顶点后,需要递归地访问此顶点的所有未访问过的相邻顶点

上面的图即是该题,题目要求输入一个目标sum,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

1
2
3
4
5
比如给出22,则返回下面
{
[5,4,11,2],
[5,8,4,5]
}
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
/**
leetcode 二叉树中和为某一值的路径(剑指offer34题)
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
LinkedList<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
// 有遍历 有递归
recur(root,sum);
//返回的是链表的链表结果
return res;
}

public void recur(TreeNode root,int sum){
// 递归的终止条件
if (root == null){
return;
}
path.add(root.val);
sum -= root.val;
//找到了最后叶子结点,且可以满足sum的和要求,便将该结果添加进去res
if (sum == 0&& root.left ==null&&root.right == null){
//这里需要添加新的对象
res.add(new LinkedList<>(path));
}
// 左子树递归
recur(root.left,sum);
// 右子树递归
recur(root.right,sum);
// 删掉上一个结点,这一步是比较难理解的,这一步有点回溯的感觉,就是你找到最后不符合要求的结点,你要返回到上一步,重新走下去。这一步是左右子树都递归完成后就会执行的
path.removeLast();

}
}

leetcode104-求深度

这个题是要求求树的深度,可以很好得对比BFS和DFS的做法,实例如下。

直接上代码,格式和模板都和上面的差不多。

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
   public int maxDepth(TreeNode root) {
// bfs
//时间复杂度也为O(n)
if(root == null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int num = 0;
while(!queue.isEmpty()){
num++;
//借助队列来完成
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
}
}
return num;

}


//Dfs 只有这两行。
// 时间复杂度为O(n),
if(root == null){
return 0;
}else{
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}