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

广度优先和深度优先搜索

前言

看着这两个搜索的前提的是读者具备图这一数据结构的基本知识,这些可以直接百度一波就了解了。图也像树一样,遍历具有很多的学问在里面,下面我将借用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;
}