什么是并查集

​ 并查集是一种树形的数据结构，，用于处理一些不想交集合的合并即查询问题，我们可以通过并查集以接近O(1)的时间完成两个不相交集合的合并，并且以O(1)的时间判断一个元素属于哪个集合

剑指 Offer——面试题 4-1

题目

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

样例

1
2
3
4
5
6
7
8
9
10
11
12

输入数组：

[
  [1,2,8,9]，
  [2,4,9,12]，
  [4,7,10,13]，
  [6,8,11,15]
]

如果输入查找数值为7，则返回true，

如果输入查找数值为5，则返回false。

滑动窗口

给定一个大小为n≤106的数组。

有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。

您只能在窗口中看到k个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为[1 3 -1 -3 5 3 6 7]，k为3。

您的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数n和k，分别代表数组长度和滑动窗口的长度。

第二行有n个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：

1
2

8 3
1 3 -1 -3 5 3 6 7

输出样例：

1
2

-1 -3 -3 -3 3 3
3 3 5 5 6 7

动态规划

​ 今天来谈一谈我对动态规划的理解，我也是初学者，这里只是通过爬楼梯这道简单的问题，介绍一下动态规划的核心思想和基于这道题的 DP 分析

前缀和及差分

​ 前缀和与差分是互为逆运算的两种计算方式，前缀和指的是一个数组是另一个数组中前n项元素之和，而差分指的是一个数组的前n项的和是另一个数组

​ 实际上就是，如果数组a是数组b的前缀和，那b就是a的差分

Spring 框架中的 @Autowired 注解

​ 在使用注解进行 Spring 项目的开发时，我们经常会用到Autowired注解，它可以对类成员变量、方法及构造函数进行标注，完成IOC容器自动装配的工作

剑指 Offer——面试题 3-2

题目

不修改数组找出重复的数字

在一个长度位n + 1的数组里的所有数字都在1 ~ n的范围内，所以数组中至少有一个数字是重复的，请找出数组中任意一个重复的数字，但不能修改输入的数组

输入样例

1

[2, 3, 5, 4, 3, 2, 6, 7]

输出样例

1

2 或 3

AcWing 1453 移掉 k 位数字

题目

给定一个以字符串表示的非负整数num，移除这个数中的k位数字，使得剩下的数字最小

注意：

• 空字符串被视为0
• 如果结果中包含前导零，则需要将前导零删除，最后删除的前导零不用包含在移除的k个数字中

输入格式

第一行输入一个字符串，用来表示非负整数num

第二行输入一个整数，表示k

输出格式

输出一个字符串，表示移除k位数字后所能得到的最小数字

数据范围

0≤k≤字符串长度≤100000
num中不包含任何前导0

输入样例1：

1
2

1432219
3

输出样例1：

1

1219

样例1解释

移除掉三个数字4,3,2可形成一个新的最小的数字1219

输入样例2：

1
2

10200
1

输出样例2：

1

200

样例2解释：

移掉首位的1剩下的数字为200，注意输出不能有任何前导零

输入样例3：

1
2

10
2

输出样例3：

1

0

样例3解释

从原数字移除所有的数字，剩余为空就是0

AcWing 35 反转链表

题目

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点

思考题：

• 请同时实现迭代版本和递归版本

样例

1
2
3

输入:1->2->3->4->5->NULL

输出:5->4->3->2->1->NULL

AcWing 34 链表中环的入口节点

题目

给定一个链表，若其中包含环，则输出环的入口节点

若其中不包含环，则输出null

样例

1
2
3
4
5
6

给定如上所示的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.