最近在学习数据结构与算法相关的知识，所以打算通过写笔记的方式加强自己对数据结构与算法的理解，也是为了方便以后复习。这里整理记录了一份数据结构与算法的思维导图，也是为了以后学习更有方向性。
介绍
数据结构&算法的定义
数据结构就是指一组数据的存储结构。 算法就是操作数据的一组方法。 数据结构和算法，是指某些著名的队列、栈、堆、二分查找、动态规划等。
数据结构和算法的关系
数据结构和算法是相辅相成的。
数据结构是为算法服务的，算法要作用在特定的数据结构之上。因此，我们无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。比如，因为数组具有随机访问的特点，常用的二分查找算法需要用数组来存储数据。但如果我们选择链表这种数据结构，二分查找算法就无法工作了，因为链表并不支持随机访问。
数据结构是静态的，它只是组织数据的一种方式。如果不在它的基础上操作、构建算法，孤立存在的数据结构就是没用的。
数据结构与算法整体知识
20 个最常用的、最基础数据结构与算法：
10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树；
10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
思维导图
线性表
线性表（Linear List），就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向，包括数组，链表、队列、栈等。
数组
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的变量。
数组例题1：找到数组中重复的数字
数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
public class FindRepeatNumber {
//测试方法
public static void main(String[] args) {
int[] nums = {2, 3, 1, 0, 2, 5, 3};
// System.out.println(findRepeatNumber1(nums));
// System.out.println("---------------------");
// System.out.println(findRepeatNumber2(nums));
// System.out.println("---------------------");
// System.out.println(findRepeatNumber3(nums));
// System.out.println("---------------------");
System.out.println(findRepeatNumber4(nums));
}
//1.集合的解法 Set
public static int findRepeatNumber1(int[] nums) {
Set set = new HashSet<>();
//遍历数组
for (int num : nums) {
if (set.contains(num)) {
System.out.println("发现重复元素" + num);
return num;
}
System.out.println("添加元素" + num);
set.add(num);
}
return -1;
}
//2.先排序，再查找
public static int findRepeatNumber2(int[] nums) {
//数组工具类arrays排序和打印数组
Arrays.sort(nums);
System.out.println(Arrays.toString(nums));
//itar联想for循环 判断相邻元素是否相同
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
System.out.println("发现重复元素" + nums[i]);
return nums[i];
}
}
return -1;
}
//3.使用临时数组记录出现的数字
public static int findRepeatNumber3(int[] nums) {
//临时数组，所有元素默认为0
int[] temp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
//判断再次赋值是否为1，为1则已经有元素，后来元素重复
if (temp[num] == 1) {
System.out.println("发现重复元素" + num);
return num;
}
//找到临时数组索引位置，赋值为1
temp[num] = 1;
}
return -1;
}
//使用自身数组判断重复元素 让数字出现在索引位置上，如果交换完遍历数已经出现，则为重复元素
public static int findRepeatNumber4(int[] nums) {
//交换前打印
System.out.println(Arrays.toString(nums));
//遍历
for (int i = 0; i < nums.length; i++) {
//如果索引正好等于元素本身，是期望的结果 跳过
if(nums[i]==i) continue;
//i=0,nums[0]=2,nums[2]=1;
int num =nums[i];//记录数组当前位置的值
int temp =nums[num];//记录值为索引位置的值
//交换的位置已经有期望值，则重复了
if (nums[num]==nums[i]) {
System.out.println("当前索引为"+i+"的位置上已经与索引为"+num+"的位置上元素重复");
return num;
}
//交换顺序
nums[num]=num;//值为索引位置的值置为与索引相同
nums[i]=temp;//将原索引位置的值放入当前位置
//交换仍需遍历当前位置的值，之后i++抵消
i--;
//交换后打印
System.out.println(Arrays.toString(nums));
}
return -1;
}
}
执行结果：
法1：
添加元素2
添加元素3
添加元素1
添加元素0
发现重复元素2
2
法2：
[0, 1, 2, 2, 3, 3, 5]
发现重复元素2
2
法3：
发现重复元素2
2
法4：
[2, 3, 1, 0, 2, 5, 3]
[1, 3, 2, 0, 2, 5, 3]
[3, 1, 2, 0, 2, 5, 3]
[0, 1, 2, 3, 2, 5, 3]
当前索引为4的位置上已经与索引为2的位置上元素重复
2
数组例题2：找到数组中消失的数字
找到所有数组中消失的数字
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]
public class FindDisappearedNumber {
public static void main(String[] args) {
int[] nums = {4,3,2,7,8,2,3,1};
System.out.println(findDisappearedNumbers(nums));
System.out.println(findDisappearedNumbers1(nums));
}
//Set集合，不重复且无序
//List, 可能重复且有序
//map, <元素，出现的次数> 映射关系
public static List findDisappearedNumbers(int[] nums) {
List result =new ArrayList<>();
//使用Set 存储已出现的数字,去重
Set set =new HashSet<>();
for (int num:nums){
set.add(num);
}
//1-n开始遍历，使用List记录set未出现的元素
for (int i = 1; i < nums.length; i++) {
if(!set.contains(i)){
result.add(i);
}
}
return result;
}
//进阶：不使用额外空间
//利用索引记录已出现的数字
//元素出现时，将其对应索引位置的元素置为负数，当剩余场上还有正数时，说明其对应索引位置的值未出现
public static List findDisappearedNumbers1(int[] nums) {
List result =new ArrayList<>();
for (int i = 0; i < nums.length; i++) {//nums = [4,3,2,7,8,2,3,1]
int num = Math.abs(nums[i]);
int index=num-1;
//将对应索引位置的值置为负数，前提是这个数为正数
if(nums[index]>0){
nums[index]=-nums[index];
System.out.println("索引"+index+ Arrays.toString(nums));
}
}
//再次遍历，找到消失的元素
for (int i = 0; i < nums.length; i++) {
if (nums[i]>0){
result.add(i+1);
System.out.println(nums[i]+"元素仍为正数，找到其下标"+(i+1));
}
}
return result;
}
}
执行结果：
[5, 6]
---------------------------
索引3[4, 3, 2, -7, 8, 2, 3, 1]
索引2[4, 3, -2, -7, 8, 2, 3, 1]
索引1[4, -3, -2, -7, 8, 2, 3, 1]
索引6[4, -3, -2, -7, 8, 2, -3, 1]
索引7[4, -3, -2, -7, 8, 2, -3, -1]
索引0[-4, -3, -2, -7, 8, 2, -3, -1]
8元素仍为正数，找到其下标5
2元素仍为正数，找到其下标6
[5, 6]
数组例题3：多数元素
多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
public class MajorityNumber {
public static void main(String[] args) {
// int[] nums ={3,2,3};
int[] nums ={ 2,2,1,1,1,2,2};
//System.out.println(majorityElement1(nums));
System.out.println("-------------------");
// System.out.println(majorityElement2(nums));
System.out.println("-------------------");
System.out.println(majorityElement3(nums));
}
//法1：map<元素，出现的次数> 如果次数超过n/2，则为多数元素
public static int majorityElement1(int[] nums) {
Map map = new HashMap<>();
int halflen =nums.length/2;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int count =1;
//如果map已经出现该元素，将count值取出并自增
if (map.containsKey(num)){
count=map.get(num);
count++;
}
//判断是否是多数元素
if (count>halflen) return num;
System.out.println(num+"元素存储次数为"+count);
map.put(num,count);
}
return -1;
}
//法2：数组排序，取中间的元素，为多数元素
public static int majorityElement2(int[] nums) {
Arrays.sort(nums);
System.out.println(Arrays.toString(nums));
int halflen =nums.length/2;
return nums[halflen];
}
//法3：投票算法
//元素当候选人，新元素和候选人相同，次数加1，不同，次数减一（抵消）
//若次数为0,则候选人更新为新元素，最终为正数的为多数元素
public static int majorityElement3(int[] nums) {
//初始化候选人
int candidate = -1;
//定义次数
int count =0;
for (int i = 0; i < nums.length; i++) {
//如果出现次数为0，重置候选人
if (count==0){
candidate=nums[i];
}
//根据新元素加减候选人
if (candidate==nums[i]){
count++;
}else {
count--;
}
System.out.println("元素"+nums[i]+",次数"+count+",候选人"+candidate);
}
return candidate;
}
}
执行结果：
法1：
2元素存储次数为1
2元素存储次数为2
1元素存储次数为1
1元素存储次数为2
1元素存储次数为3
2元素存储次数为3
2
法2：
[1, 1, 1, 2, 2, 2, 2]
2:
法3：
元素2,次数1,候选人2
元素2,次数2,候选人2
元素1,次数1,候选人2
元素1,次数0,候选人2
元素1,次数1,候选人1
元素2,次数0,候选人1
元素2,次数1,候选人2
2
稀疏数组
数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3 限制：
2 <= n <= 100000
找到所有数组中消失的数字
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例 1：
输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6]
public class FindDisappearedNumber {
public static void main(String[] args) {
int[] nums = {4,3,2,7,8,2,3,1};
System.out.println(findDisappearedNumbers(nums));
System.out.println(findDisappearedNumbers1(nums));
}
//Set集合，不重复且无序
//List, 可能重复且有序
//map, <元素，出现的次数> 映射关系
public static List findDisappearedNumbers(int[] nums) {
List result =new ArrayList<>();
//使用Set 存储已出现的数字,去重
Set set =new HashSet<>();
for (int num:nums){
set.add(num);
}
//1-n开始遍历，使用List记录set未出现的元素
for (int i = 1; i < nums.length; i++) {
if(!set.contains(i)){
result.add(i);
}
}
return result;
}
//进阶：不使用额外空间
//利用索引记录已出现的数字
//元素出现时，将其对应索引位置的元素置为负数，当剩余场上还有正数时，说明其对应索引位置的值未出现
public static List findDisappearedNumbers1(int[] nums) {
List result =new ArrayList<>();
for (int i = 0; i < nums.length; i++) {//nums = [4,3,2,7,8,2,3,1]
int num = Math.abs(nums[i]);
int index=num-1;
//将对应索引位置的值置为负数，前提是这个数为正数
if(nums[index]>0){
nums[index]=-nums[index];
System.out.println("索引"+index+ Arrays.toString(nums));
}
}
//再次遍历，找到消失的元素
for (int i = 0; i < nums.length; i++) {
if (nums[i]>0){
result.add(i+1);
System.out.println(nums[i]+"元素仍为正数，找到其下标"+(i+1));
}
}
return result;
}
}
执行结果： [5, 6] --------------------------- 索引3[4, 3, 2, -7, 8, 2, 3, 1] 索引2[4, 3, -2, -7, 8, 2, 3, 1] 索引1[4, -3, -2, -7, 8, 2, 3, 1] 索引6[4, -3, -2, -7, 8, 2, -3, 1] 索引7[4, -3, -2, -7, 8, 2, -3, -1] 索引0[-4, -3, -2, -7, 8, 2, -3, -1] 8元素仍为正数，找到其下标5 2元素仍为正数，找到其下标6 [5, 6]
数组例题3：多数元素
多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
public class MajorityNumber {
public static void main(String[] args) {
// int[] nums ={3,2,3};
int[] nums ={ 2,2,1,1,1,2,2};
//System.out.println(majorityElement1(nums));
System.out.println("-------------------");
// System.out.println(majorityElement2(nums));
System.out.println("-------------------");
System.out.println(majorityElement3(nums));
}
//法1：map<元素，出现的次数> 如果次数超过n/2，则为多数元素
public static int majorityElement1(int[] nums) {
Map map = new HashMap<>();
int halflen =nums.length/2;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
int count =1;
//如果map已经出现该元素，将count值取出并自增
if (map.containsKey(num)){
count=map.get(num);
count++;
}
//判断是否是多数元素
if (count>halflen) return num;
System.out.println(num+"元素存储次数为"+count);
map.put(num,count);
}
return -1;
}
//法2：数组排序，取中间的元素，为多数元素
public static int majorityElement2(int[] nums) {
Arrays.sort(nums);
System.out.println(Arrays.toString(nums));
int halflen =nums.length/2;
return nums[halflen];
}
//法3：投票算法
//元素当候选人，新元素和候选人相同，次数加1，不同，次数减一（抵消）
//若次数为0,则候选人更新为新元素，最终为正数的为多数元素
public static int majorityElement3(int[] nums) {
//初始化候选人
int candidate = -1;
//定义次数
int count =0;
for (int i = 0; i < nums.length; i++) {
//如果出现次数为0，重置候选人
if (count==0){
candidate=nums[i];
}
//根据新元素加减候选人
if (candidate==nums[i]){
count++;
}else {
count--;
}
System.out.println("元素"+nums[i]+",次数"+count+",候选人"+candidate);
}
return candidate;
}
}
执行结果：
法1：
2元素存储次数为1
2元素存储次数为2
1元素存储次数为1
1元素存储次数为2
1元素存储次数为3
2元素存储次数为3
2
法2：
[1, 1, 1, 2, 2, 2, 2]
2:
法3：
元素2,次数1,候选人2
元素2,次数2,候选人2
元素1,次数1,候选人2
元素1,次数0,候选人2
元素1,次数1,候选人1
元素2,次数0,候选人1
元素2,次数1,候选人2
2
稀疏数组
多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
一个数组中大部分元素为0，或者为同一个值时，可以使用稀疏数组来保存该数组，进行数组内容的压缩，避免记录大量无意义的值。
稀疏数组的处理方法是：
1）记录数组一共有几行几列，有多少不同的值；
2）把具有不同值的元素的行列及值记录在一个小数组中，从而缩小程序的规模。
//稀疏数组
public class SparseArray {
public static void main(String[] args) {
int[][] arr =new int[10][10];
arr[1][2]=1;
arr[3][1]=2;
arr[2][2]=2;
System.out.println("输出原始数组：");
for (int[] ints : arr) {
for (int anInt : ints) {
System.out.print(anInt+"t");
}
System.out.println();
}
System.out.println("输出稀疏数组");
int[][] result =toSparse(arr);
for (int i = 0; i < result.length; i++) {
System.out.println(result[i][0]+"t"+result[i][1]+"t"+result[i][2]);
}
System.out.println("-------------------------");
int[][] arr1=sparseTOArray(result);
System.out.println("输出再转回来的数组：");
for (int[] ints : arr) {
for (int anInt : ints) {
System.out.print(anInt+"t");
}
System.out.println();
}
}
//把普通数组 转化为稀疏数组
public static int[][] toSparse(int[][] arr){
//(n+1)*3列的数组 初始化
//需要先求非零元素的个数
int count =0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[0].length; j++) {
if (arr[i][j]!=0){
count++;
}
}
}
//定义稀疏数组，行数取决于元素个数,d第一行记录原数组总行数和总列数和元素个数
int[][] result = new int[count+1][3];
result[0][0]=arr.length;
result[0][1]=arr[0].length;
result[0][2]=count;
//遍历数组 找到所有非0元素，存到结果中
int index =0;//定义稀疏行下标
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
if(arr[i][j]!=0){
index++;
result[index][0]=i;
result[index][1]=j;
result[index][2]=arr[i][j];
}
}
}
return result;
}
//将稀疏数组转化为普通数组,默认稀疏数组为3列
public static int[][] sparseTOArray(int[][] result){
int i=result[0][0];
int j=result[0][1];
int[][] arr = new int[i][j];
for (int index = 1; index < result.length; index++) {
arr[result[index][0]][result[index][1]]=result[index][2];
}
return arr;
}
}
执行结果： 输出原始数组： 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 输出稀疏数组 10 10 3 1 2 1 2 2 2 3 1 2 ------------------------- 输出再转回来的数组： 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
双指针应用
数组的遍历过程索引就是一个指针的一个引用
双指针有不同的遍历方式
对撞指针：两指针相反方向遍历
快慢指针：两指针相同方向，遍历速度不同，或起点不同
应用1：
删除有序数组中的重复项
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
public class DeleteDuplicate {
public static void main(String[] args) {
int[] nums = {0,0,1,1,1,2,2,3,3,4};
int n=removeDuplicates(nums);
int[] ints = Arrays.copyOfRange(nums, 0, n);
System.out.println("删除重复元素后数组为：");
System.out.println(Arrays.toString(ints));
}
//双指针解法，第一个指针负责遍历并与第一个指针比较
//第二个指针记录重复位置并覆盖
public static int removeDuplicates(int[] nums) {
if (nums.length==0) return 0;
//用于比较元素的位置
int index =0;
for (int i = 1; i < nums.length; i++) {
//如果遇到不同 与index+1进行覆盖
if(nums[i]!=nums[index]){
index++;
nums[index]=nums[i];
System.out.println("覆盖第"+index+"位置的元素为"+nums[i]);
}
}
return index+1;
}
}
执行结果： 覆盖第1位置的元素为1 覆盖第2位置的元素为2 覆盖第3位置的元素为3 覆盖第4位置的元素为4 删除重复元素后数组为： [0, 1, 2, 3, 4]
应用2：
移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
public class DeleteElement {
public static void main(String[] args) {
int[] nums ={0,1,2,2,3,0,4,2};
// int n =removeElement(nums,2);
// System.out.println(Arrays.toString(nums));
// int[] ints = Arrays.copyOfRange(nums, 0, n);
// System.out.println(Arrays.toString(ints));
int m =removeElement1(nums,2);
int[] ints1 = Arrays.copyOfRange(nums, 0, m);
System.out.println(Arrays.toString(ints1));
}
//法1：双指针覆盖法
public static int removeElement(int[] nums, int val) {
if (nums.length==0) return 0;
//用于比较元素的位置
int index =0;
for (int i = 0; i < nums.length; i++) {
//如果值不为val 与index进行覆盖
if(nums[i]!=val){
//覆盖当前位置
nums[index]=nums[i];//0,1,2,2,3,0,4,2
System.out.println("覆盖第"+index+"位置的元素为"+nums[i]);
index++;
}
}
return index;
}
//法2：指针末位数替换法（对撞指针）
//判断遍历当前值是否为要删除值，是就和倒数位元素替换，倒数位元素自减
public static int removeElement1(int[] nums, int val) {
//初始化两指针
int index =0;
int len =nums.length;//记录有效元素个数
while(true){
if (index>=len) return len;
if (nums[index]==val){
nums[index]=nums[len-1];
nums[len-1]=val;
System.out.println("替换位置"+index+"和"+(len-1)+"的元素");
System.out.println(Arrays.toString(nums));
len--;
//抵消再判断，防止替换后的值仍为val;
index--;
}
index++;
}
}
}
执行结果： 覆盖第0位置的元素为0 覆盖第1位置的元素为1 覆盖第2位置的元素为3 覆盖第3位置的元素为0 覆盖第4位置的元素为4 [0, 1, 3, 0, 4, 0, 4, 2] [0, 1, 3, 0, 4] 法2： 替换位置2和7的元素 [0, 1, 2, 2, 3, 0, 4, 2] 替换位置2和6的元素 [0, 1, 4, 2, 3, 0, 2, 2] 替换位置3和5的元素 [0, 1, 4, 0, 3, 2, 2, 2] [0, 1, 4, 0, 3]
链表
链表包含单链表，双向链表，循环链表等等。相对于线性表，添加，删除操作非常方便，因为不用移动大量的节点，只需要修改对应的前后节点指针即可。下面用一个具体实例来说明下这种结构。现在有一需求，是将具有不同编号，姓名，昵称的人添加到系统中。首先需要创建节点，既然是链表，节点除了基本信息也要加入下一节点指针，方便计算机在内存中查找。
链表分为有头节点的链表和没有头节点的链表。
插入的时候，分为头插法和尾插法。
节点关系称之为前置节点和后继节点。
节点的构成，包含数据本身，以及对后继节点的引用。
与数组区别：
优点：链表实现了真正的动态，不需要处理固定容量带来的系列问题
增删快
缺点：失去随机访问能力，查询慢
数组转链表：
public class ListNode1 {
public static void main(String[] args) {
String[] arr ={"王者荣耀","和平精英","开心消消乐","欢乐斗地主"};
ListNode1 node = ListNode1.arrayToListNode(arr);
System.out.println();
}
String data;
ListNode1 next;
public ListNode1(String data){
this.data=data;
}
public static ListNode1 arrayToListNode(String[] arr){
if(arr.length==0) return null;
//生成链表的根节点
ListNode1 root = new ListNode1(arr[0]);
//生成临时节点
ListNode1 pre =root;
for (int i=1;i
链表例题1：链表中倒数第k个节点
链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
public class ListNode {
int val;
ListNode next;
public ListNode(int val){
this.val=val;
}
public static ListNode arrayToListNode(int[] arr){
if(arr.length==0) return null;
//生成链表的根节点
ListNode root = new ListNode(arr[0]);
//生成临时节点
ListNode pre =root;
for (int i=1;i
public class KthNodeFromEnd {
public static void main(String[] args) {
int[] arr ={1,2,3,4,5,6};
ListNode head =ListNode.arrayToListNode(arr);
ListNode node =getKthFromEnd(head,3);
System.out.println(node.val);
ListNode node1 =getKthFromEnd1(head,3);
System.out.println(node1.val);
}
//法一
public static ListNode getKthFromEnd(ListNode head, int k) {
//先统计总共多少节点
int n =0;
ListNode temp=head;
while(temp.next!=null){
n++;
temp=temp.next;//下移一个节点
}
//再次遍历，找到第n-k+1个节点，即为倒数第k个节点
temp=head;
for (int i = 0; i < n-k+1; i++) {
temp=temp.next;
}
return temp;
}
public static ListNode getKthFromEnd1(ListNode head, int k) {
ListNode slow =head;
ListNode fast=head;
for (int i = 0; i
执行结果：
4->5
----------------
slow移动到2,fast移动到4
slow移动到3,fast移动到5
slow移动到4,fast移动到6
4->5
链表例题2：反转链表
反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
public class ReverseList {
public static void main(String[] args) {
int[] arr ={1,2,3,4,5};
ListNode head =ListNode.arrayToListNode(arr);
ListNode reasult = reverseList(head);
print(reasult);
}
public static ListNode reverseList(ListNode head) {
//记录前置节点和当前节点
ListNode pre =null;
ListNode cur=head;
//不断移动cur节点，向后遍历，同时更改其next
//当cur为null时，停止遍历
while (cur!=null){
//创建临时节点记录下个节点
ListNode temp =cur.next;
//更改指向
cur.next=pre;
if(cur!=null&&pre!=null){
System.out.println("让"+cur.val+"的next指向"+pre.val);
}
//pre和cur向后移动
pre=cur;
cur=temp;
}
return pre;
}
//打印链表
public static void print(ListNode head){
while (head!=null){
System.out.print(head.val);
if (head.next!=null){
System.out.print("->");
}
head=head.next;
}
}
}
执行结果：
让2的next指向1
让3的next指向2
让4的next指向3
让5的next指向4
5->4->3->2->1
双链表
数据+下一个节点的引用+对上一个节点的引用（即数据加前置指针和后置指针）
链表例题3：环形链表
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
链表例题4：环形链表II
环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
public class CycleList {
public static void main(String[] args) {
int[] arr ={3,2,0,-4};
ListNode node =ListNode.arrayToListNode(arr);
ListNode.toCycle(node,1);
System.out.println(hasCyale(node));
// System.out.println(detectCycle(node).val);
}
//判断链表是否有环
public static boolean hasCyale(ListNode head){
//链表不能为空
if(head==null||head.next==null) return false;
ListNode slow =head;
ListNode fast =head;
while (true) {
if (fast==null||fast.next==null){
return false;
}
slow=slow.next;
fast=fast.next.next;
if (slow!=null){
System.out.println("slow走到"+slow.val);
}
if (fast!=null){
System.out.println("fast走到"+fast.val);
}
//当快节点追上慢节点时，说明有环
if (slow==fast) return true;
}
}
//
public static ListNode detectCycle(ListNode head) {
//链表不能为空
if(head==null||head.next==null) return null;
ListNode slow =head;
ListNode fast =head;
while (true) {
if (fast==null||fast.next==null){
return null;
}
slow=slow.next;
fast=fast.next.next;
if (slow!=null){
System.out.println("slow走到"+slow.val);
}
if (fast!=null){
System.out.println("fast走到"+fast.val);
}
//当快节点追上慢节点时，说明有环
if (slow==fast) break;
}
//第一次相遇后，让快指针重新指向头节点，慢指针不变
//fast和slow按照相同的速度移动，再次相遇的节点为环形节点的入口
fast=head;
//如果环节点为完全闭环那么头节点就为入口节点
while (slow!=fast){
slow=slow.next;
fast=fast.next;
if (slow!=null){
System.out.println("slow走到"+slow.val);
}
if (fast!=null){
System.out.println("fast走到"+fast.val);
}
}
return slow;
}
}
执行结果：
slow走到2
fast走到0
slow走到0
fast走到2
slow走到-4
fast走到-4
true
slow走到2
fast走到0
slow走到0
fast走到2
slow走到-4
fast走到-4
slow走到2
fast走到2
2
约瑟夫环问题：
约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。
分析：
（1）由于对于每个人只有死和活两种状态，因此可以用布尔型数组标记每个人的状态，可用true表示死，false表示活。
（2）开始时每个人都是活的，所以数组初值全部赋为false。
（3）模拟杀人过程，直到所有人都被杀死为止。
public class Josephus {
public static void main(String[] args) {
//System.out.println("41,3 ->"+josephus(41,3));
System.out.println("41,3 ->"+josephus1(41,3));
}
public static int josephus(int n,int m){
//初始化环形列表
int[] arr = new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i]=i+1;
}
ListNode node =ListNode.arrayToListNode(arr);
ListNode.toCycle(node,0);
//将每一个人视作链表中的一个节点，当报数到m的时候，删除节点，直到剩下最后一个节点
//当找到报数m-1的节点 node node.next=node.next.next
//当剩最后一个节点时，node.next=node
int cnt =1;
while (true){
if(cnt==m-1){
System.out.println("删除节点"+node.next.val);
node.next=node.next.next;
cnt=0;
}
cnt++;
node=node.next;
if (node.next==node) return node.val;
}
}
public static int josephus1(int n,int m){
//数组记录，初始值为0，挂掉的人为-1
int[] person =new int[n];
//人的索引
int index=-1;
//报数记录 1 2 ... m
int cnt =0;
//剩余人数
int remain =n;
while (remain>0){
index++;
//到达数组尾部，重头遍历
if (index>=n) index=0;
//如果此人已经为-1，跳过
if(person[index]==-1){
continue;
}
//报数到m，将index对应位置人，置为-1
if(cnt==m){
person[index]=-1;
cnt=0;
remain--;
}
cnt++;
}
return index;
}
}
执行结果：
41,3 ->31
队列
像栈一样，队列（queue）也是一种线性表，它的特性是先进先出，插入在一端，删除在另一端。就像排队一样，刚来的人入队（push）要排在队尾(rear)，每次出队(pop)的都是队首(front)的人。如图1，描述了一个队列模型。
队列（Queue）与栈一样，是一种线性存储结构，它具有如下特点：
队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构。
在队尾添加元素，在队头删除元素。
public class ArrayQueue {
//最大容量
int maxCapacity;
//声明头尾指针
int head;
int tail;
//存储元素
int[] arr;
//初始化
public ArrayQueue(int maxCapacity){
arr =new int[maxCapacity];
this.maxCapacity=maxCapacity;
head=0;
tail=0;
}
public boolean isFull(){
//尾指针到头时
return tail==maxCapacity;
}
public boolean isEmpty(){
return head==tail;
}
public void add(int n){
//先判断队列容量大小
if(!isFull()){
arr[tail]=n;
tail++;
}
}
public int get(){
//先判断队列是否为空
if (isEmpty()){
return -1;
}
int result =arr[head];
head++;
return result;
}
}
public class LinkedListTest {
public static void main(String[] args) {
Queue queue = new LinkedList<>();
//都能添加元素
queue.add(1);
queue.offer(2);
//两者区别：当队列满时，add会抛异常，offer会返回false 更健壮更友好
//取出元素，分为两种
//1 只获取对头元素 不取出
queue.peek();
queue.element();
//两者区别 当队列为空时 element会抛出异常 peek会返回空值
//2 获取队头元素，同时取出
queue.poll();
queue.remove();
//两者区别 当队列为空时 remove会抛出异常 poll会返回空值
}
}
双端队列
区别于普通队列
两端都可以入队和出队
LinkedList和ArrayDeque
第一个元素（头部） 最后一个元素（头部） 抛出异常 特殊值 抛出异常 特殊值 插入 addFirst(e) offerFirst(e) addLast(e) offerLast(e) 删除 removeFirst() pollFirst() removeLast() pollLast() 获取 getFirst() peekFirst() getLast() peekLast()
【特别的队列】
1) 优先级队列
元素携带了相关的优先级，优先级更高的元素排在头部
PriorityQueue，提供了Comparable接口，元素可以实现其方法，改变在队列中的顺序
2）阻塞队列
当队列满的时候，等待有空余位置再存数据；当队列空的时候，等待有新的数据再读取
BlockingQueue，put()和take()方法提供了存取的阻塞逻辑
分为两种情况，一种是无限期的等，一种是指定阻塞时间
3）延迟队列
在指定时间内获取队列元素，头部元素是最近过期时间的。
DelayQueue 给顶一个接口设置延迟时间 元素会按照时间排序
队列例题1：队列最大值
队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：
输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]
分析：
队头 队尾
[1,2,3,4,53,2,1]
在队列发生更改时 记录出最大值
增删操作时 ，都可能影响最大值的变化
如果是新增操作，比较新元素和当前最大值之间，更大的值为新最大值
如果是删除操作，删除元素如果不是最大值，那么最大值不变，如果是最大值，最大值
要更改为剩余元素最大值
使用二维的队列记录最大值的变化
原队列 max队列
[1] [1]
[1,2] [2]
[1,2,3] [3]
[2,3] [3]
[2,3,2] [3,2]
[2,3,2,1] [3,2,1]
[3,2,1] [3,2,1]
[2,1] [2,1]
[2,1,4] [4]
队首删 队尾加
public class MaxQueue {
public static void main(String[] args) {
MaxQueue obj =new MaxQueue();
obj.push_back(2);
obj.push_back(5);
obj.push_back(3);
obj.push_back(1);
obj.push_back(4);
System.out.println("原始队列"+obj.queue.toString());
System.out.println("队列最大值为"+obj.max_value());
System.out.println("删除"+obj.pop_front());
System.out.println("队列最大值为"+obj.max_value());
System.out.println("删除"+obj.pop_front());
System.out.println("队列最大值为"+obj.max_value());
System.out.println("删除"+obj.pop_front());
System.out.println("队列最大值为"+obj.max_value());
obj.push_back(6);
System.out.println("增加"+6);
System.out.println("队列最大值为"+obj.max_value());
}
//原始队列
public LinkedList queue;
//最大值的候选值
public LinkedList max;
public MaxQueue() {
queue = new LinkedList<>();
max = new LinkedList<>();
}
public int max_value() {
if(max.isEmpty())return -1;
return max.peekFirst();//队首元素
}
//新增元素时 ele时 ele>max 取队列中队尾元素比较，如果满足，进行覆盖并循环比较
// 直到把所有比它小的值都覆盖为止
// elemax
while (!max.isEmpty()&&max.peekLast()
执行结果：
原始队列[2, 5, 3, 1, 4]
队列最大值为5
删除2
队列最大值为5
删除5
队列最大值为4
删除3
队列最大值为4
增加6
队列最大值为6
队列例题2：滑动窗口最大值
滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
分析：数组长度为n 窗口的大小为k 可形成的窗口个数 n-k+1
通过队列来记录最大值
窗口未形成阶段
遍历数组，同时更新队列
窗口已形成阶段
每次窗口移动，都是在头部移除元素，尾部增加元素
在窗口的变化过程中 记录其最大值变化（让最大值一直出现在第一位）
让队列中已存在的元素 和新添加的元素比较 如果存在的更小 那么覆盖
如果存在的更大· 新添加的元素是候选 缀到队列之后
窗口 max队列
[1 3 -1] [1]->[3]->[3,-1]
[3 -1 -3] [3.-1.-3]
[-1 -3 5] [-1,-3]->[5]
[-3 5 3] [5,3]
[5 3 6] [6]
[3 6 7] [7]
窗口最大值 3 3 5 5 6 7
public class SlideWindow {
public static void main(String[] args) {
int[] nums ={1,3,-1,-3,5,3,6,7};
int k =3;
int[] ints =maxSlidingWindow(nums,k);
System.out.println(Arrays.toString(ints));
}
public static int[] maxSlidingWindow(int[] nums, int k) {
//新建一个数组存放每个窗口的最大值
int[] result =new int[nums.length-k+1];
//新建队列存放最大值
Deque deque =new ArrayDeque<>();
// 防止数组为空报空指针异常
if(nums.length==0) return new int[nums.length];
//窗口未形成阶段
for (int i = 0; i < k; i++) {
//每次都取队尾元素和新元素 比较 如果队尾更小，删除
while (!deque.isEmpty()&&deque.peekLast()
执行结果：
初始窗口最大值为3
[3, -1]
-----第1次滑动-----
最大值为3
[3, -1, -3]
-----第2次滑动-----
最大值为5
[5]
-----第3次滑动-----
最大值为5
[5, 3]
-----第4次滑动-----
最大值为6
[6]
-----第5次滑动-----
最大值为7
[7]
[3, 3, 5, 5, 6, 7]
循环队列
为了解决，队列存取数据后，空间无法 重复利用的问题，通过构造环形，重复使用
例题：设计循环队列
设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
public class MyCircularQueue {
public static void main(String[] args) {
MyCircularQueue a = new MyCircularQueue(2);
System.out.println("增加元素"+a.enQueue(8));
System.out.println(Arrays.toString(a.queue));
System.out.println("增加元素"+a.enQueue(8));
System.out.println(Arrays.toString(a.queue));
System.out.println("获取队首元素为"+a.Front());
System.out.println("增加元素"+a.enQueue(4));
System.out.println(Arrays.toString(a.queue));
System.out.println("删除元素"+a.deQueue());
System.out.println(Arrays.toString(a.queue));
System.out.println("增加元素"+a.enQueue(1));
System.out.println(Arrays.toString(a.queue));
System.out.println("增加元素"+a.enQueue(1));
System.out.println("队列是否为满"+a.isFull());
System.out.println(Arrays.toString(a.queue));
System.out.println("获取队尾元素为"+ a.Rear());
System.out.println("队列是否为空"+a.isEmpty());
System.out.println("获取队首元素为"+a.Front());
System.out.println("删除元素"+a.deQueue());
System.out.println(Arrays.toString(a.queue));
}
int[]queue;//存储元素数组
int capacity;//最大容量
int head;//头指针
int tail;//尾指针
int count;//实际队列长度
// * MyCircularQueue(k): 构造器，设置队列长度为 k 。
public MyCircularQueue(int k) {
capacity =k;
queue=new int[k];
head=0;
tail=0;
count=0;
}
// * enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
public boolean enQueue(int value) {
if (isFull()) return false;
queue[tail]=value; //尾指针处插入，尾指针进一位
tail =(tail+1)%capacity;
count++;
return true;
}
// * deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
public boolean deQueue() {
if (isEmpty()) return false;
queue[head]=0;
head=(head+1)%capacity;
count--;
return true;
}
// * Front: 从队首获取元素。如果队列为空，返回 -1 。
public int Front() {
if (isEmpty()) return -1;
return queue[head];
}
// * Rear: 获取队尾元素。如果队列为空，返回 -1 。
public int Rear() {
if (isEmpty()) return -1;
return queue[(tail-1+capacity)%capacity];
//or return queue[tail == 0 ? capacity - 1 : tail - 1];
}
// * isEmpty(): 检查循环队列是否为空。
public boolean isEmpty() {
return count ==0;
}
// * isFull(): 检查循环队列是否已满。
public boolean isFull() {
return count==capacity;
}
}
执行结果：
增加元素true
[8, 0]
增加元素true
[8, 8]
获取队首元素为8
增加元素false
[8, 8]
删除元素true
[0, 8]
增加元素true
[1, 8]
增加元素false
队列是否为满true
[1, 8]
获取队尾元素为1
队列是否为空false
获取队首元素为8
删除元素true
[1, 0]
栈 Stack
在同一端进行插入和删除 遵循的是先进后出/后进先出LIFO(Last in first out)的原则
存入数据——进栈、压栈
取出数据——出栈、弹栈
栈是有记忆的，比如回退功能用的就是栈
栈的实现方式：
数组（顺序栈）
队列实现栈（链栈）
栈例题1：有效的括号
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
public class ValidParenthese {
public static void main(String[] args) {
System.out.println(isValid("()[]{}"));
System.out.println(isValid("(]"));
System.out.println(isValid("([)]"));
System.out.println(isValid("{[]}"));
System.out.println(isValid("{["));
System.out.println(isValid("]}"));
System.out.println("----------------------");
System.out.println(isValid1("()[]{}"));
System.out.println(isValid1("(]"));
System.out.println(isValid1("([)]"));
System.out.println(isValid1("{[]}"));
System.out.println(isValid1("{["));
System.out.println(isValid1("]}"));
}
//法1：栈存左括号，出现右括号相同就抵消
//如果是右括号 寻找栈顶元素 能否进行匹配 匹配不上 无效
//如果是左括号 直接压入栈中
// 当遍历完成的时候 如果不是空栈 说明左括号未被匹配到 无效 反之，有效
public static boolean isValid(String s) {
Map map =new HashMap<>();
map.put('(',')');
map.put('[',']');
map.put('{','}');
char[] arr =s.toCharArray();
Stack stack = new Stack<>();
for (char c : arr) {
if (map.containsKey(c)){
//左括号
stack.push(c);
}else {
//右括号
if (stack.empty()){
System.out.println("右括号出现，但左括号未出现");
return false;
}
char top =stack.peek();
if (!map.get(top).equals(c)){
System.out.println("右括号出现，但不是与之对应的左括号");
return false;
}
//弹出左括号，已被抵消
stack.pop();
}
}
if (!stack.empty()){
System.out.println("左括号出现，但右括号仍未出现");
return false;
}
return true;
}
//法2：当出现左括号时，直接存入右括号，当出现右括号时，直接取出栈顶元素
public static boolean isValid1(String s) {
Stack stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c=='('){
stack.push(')');
}else if (c=='['){
stack.push(']');
}else if (c=='{'){
stack.push('}');
}
else {
if (stack.empty()||c!=stack.pop()){//取出栈顶元素比较
System.out.println("右括号出现，但左括号未出现");
return false;
}
}
}
return stack.empty();//最终为空则有效括号
}
}
执行结果：
true
右括号出现，但不是与之对应的左括号
false
右括号出现，但不是与之对应的左括号
false
true
左括号出现，但右括号仍未出现
false
右括号出现，但左括号未出现
false
----------------------
true
右括号出现，但左括号未出现
false
右括号出现，但左括号未出现
false
true
false
右括号出现，但左括号未出现
false
栈的数组实现方式
//数组实现栈
public class MyStack {
public static void main(String[] args) {
MyStack myStack = new MyStack(3);
myStack.push(1);
myStack.push(2);
myStack.push(3);
System.out.println(myStack.peek());
System.out.println(myStack.pop());
System.out.println(myStack.pop());
System.out.println(myStack.pop());
System.out.println(myStack.isEmpty());
System.out.println(myStack.isFull());
}
//存储数据
int[] array;
//最大容量
int maxSize;
//栈指针
int top;
public MyStack(int size){
maxSize=size;
array=new int[maxSize];
top=-1;
}
public void push(int value){
if (top
执行结果：
3
3
2
1
true
false
栈例题2：队列实现栈
用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
public class MyStackByQueue {
public static void main(String[] args) {
MyStackByQueue obj = new MyStackByQueue();
obj.push(1);
obj.push(2);
int param_2 = obj.top();
int param_3 = obj.pop();
boolean param_4 = obj.empty();
System.out.println(param_2+" "+param_3+" "+param_4);
}
Queue dataQueue =new LinkedList<>();//存储数据的队列
Queue tempQueue =new LinkedList<>();//临时队列
int top;//栈顶元素
public void push(int x) {
dataQueue.add(x);
top=x;
}
public int pop() {
while (dataQueue.size()>1){
top=dataQueue.poll();
tempQueue.add(top);
}
int num =dataQueue.poll();
//将dataQueue元素移回去
Queue temp = dataQueue;
dataQueue = tempQueue;
tempQueue=temp;
return num;
}
public int top() {
return top;
}
public boolean empty() {
return dataQueue.size()==0;
}
}
执行结果：
2 2 false
public class MyStackByQueue2 {
public static void main(String[] args) {
MyStackByQueue2 obj = new MyStackByQueue2();
obj.push(1);
obj.push(2);
int param_2 = obj.top();
int param_3 = obj.pop();
boolean param_4 = obj.empty();
System.out.println(param_2+" "+param_3+" "+param_4);
}
Queue dataQueue =new LinkedList<>();//存储数据的队列
public void push(int x) {
dataQueue.add(x);
//把对头的元素拿出来，放到队尾，颠倒 size-1次
int size =dataQueue.size();
while (size>1){
int tail = dataQueue.poll();
dataQueue.offer(tail);
size--;
}
}
public int pop() {
return dataQueue.poll();
}
public int top() {
return dataQueue.peek();
}
public boolean empty() {
return dataQueue.size()==0;
}
}
执行结果：
2 2 false
栈例题3：栈实现队列
用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
public class MyQueueByStack{
public static void main(String[] args) {
MyQueueByStack myQueue = new MyQueueByStack();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
System.out.println(myQueue.stack1);
System.out.println( myQueue.peek()); // return 1
System.out.println(myQueue.pop()); // return 1, queue is [2]
System.out.println(myQueue.empty()); // return false
}
Stack stack1 = new Stack<>();//入栈
Stack stack2 = new Stack<>();//出栈
public void push(int x) {
stack1.push(x);
}
public int pop() {
//如果stack2为空，就将stack1出栈，stack2入栈
if (stack2.empty()) {
while(stack1.size()>0){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
//如果stack2为空，就将stack1出栈，stack2入栈
if (stack2.empty()) {
while(stack1.size()>0){
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean empty() {
//stack1和stack2两个都空才为空
return stack2.empty()&&stack1.empty();
}
}
执行结果：
[1, 2]
1
1
false
栈例题4：栈的最小值
栈的最小值
请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
public class MinStack {
Stack stack = new Stack<>();
Stack min = new Stack<>();//栈顶存储栈的最小值
public void push(int x) {
stack.push(x);
if (!min.empty()&&min.peek()
public class MinStack1 {
Stack stack = new Stack<>();
int min =Integer.MAX_VALUE;//初始化min
public void push(int x) {
//如果新元素使最小值发生变化，则会存储两个值（原来的最小值，当前的最小值）
if(min>=x){
if (!stack.empty()){
stack.push(min);
}
//最小值重新赋值
min=x;
}
stack.push(x);
}
public void pop() {
if (stack.empty()) return;
if (stack.size()==1){
min=Integer.MAX_VALUE;
}else if (min==stack.peek()){
stack.pop();
min=stack.peek();
}
//如果移除的不是最小值，直接pop，
// 如果移除的是最小值， 前面移除一次，再移除之前保存的最小值
stack.pop();
min=stack.peek();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
栈例题5：下一个更大元素
下一个更大元素 I
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
示例 1：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2：
输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
public class NextGreaterNum {
public static void main(String[] args) {
int[] nums1 ={2,3,5,1,0,7,4};
int[] nums2 ={2,3,5,1,0,7,4};
int[] result = nextGreaterElement(nums1,nums2);
System.out.println(Arrays.toString(result));
}
public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
//暂时忽略nums1 直接求取nums2中 每一个元素的下一个最大值
Stack stack =new Stack<>();
Map map = new HashMap<>();//键存储元素，值存储其下一个最大值
int[] result = new int[nums1.length];
for (int i = 0; i < nums2.length; i++) {
//比较 栈顶元素和新元素
while(!stack.empty()&&nums2[i]>stack.peek()){
map.put(stack.pop(),nums2[i]);
}
//如果新元素更小，直接入栈 等待后面出现的更大元素
//如果找到更大元素 存入map后 新元素仍要入栈
stack.push(nums2[i]);
}
//如果栈中还有元素 代表没出现过更大元素
while(!stack.empty()){
map.put(stack.pop(),-1);
}
for (int i = 0; i
[3, 5, -1, -1, 7, -1, -1]
算数表达式：
3+4-5=2
3+4*5=23
前缀、中缀、后缀表达式（指的是运算符的位置）
前缀又叫波兰表达式 后缀又叫逆波兰表达式
3+4-5
中缀：3+4-5
前缀：+--543
后缀：34+5-
栈例题：逆波兰表达式
逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
public class ReversePolishNotation {
public static void main(String[] args) {
// String[] str1 = {"2","1","+","3","*"};
// String[] str2 = {"4","13","5","/","+"};
// String[] str3 = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
// System.out.println(evalRPN(str1));
// System.out.println(evalRPN(str2));
// System.out.println(evalRPN(str3));
transfer("1+((2+3)*4)-5");
}
public static int evalRPN(String[] tokens) {
Stack stack = new Stack<>();
int nums1,nums2;
for (int i = 0; i < tokens.length; i++) {
switch (tokens[i]){
case "+":
nums1=Integer.parseInt(stack.pop());
nums2=Integer.parseInt(stack.pop());
stack.push(nums2+nums1+"");
break;
case "-":
nums1=Integer.parseInt(stack.pop());
nums2=Integer.parseInt(stack.pop());
stack.push(nums2-nums1+"");
break;
case "*":
nums1=Integer.parseInt(stack.pop());
nums2=Integer.parseInt(stack.pop());
stack.push(nums2*nums1+"");break;
case "/":
nums1=Integer.parseInt(stack.pop());
nums2=Integer.parseInt(stack.pop());
stack.push(nums2/nums1+"");break;
default:
//如果是数字，直接入栈
stack.push(tokens[i]);
}
}
return Integer.parseInt(stack.pop());
}
//中缀转后缀
public static void transfer(String str){
Stack stack1 = new Stack<>();//运算符栈
Stack stack2 = new Stack<>();//中间结果栈
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
switch (chars[i]){
//判断 是运算符 还是操作数 以及 具体的加减乘除或括号
case '+':
case '-':
case '*':
case '/':
//有两种情况 直接存入s1
//如果s1为空 或者栈顶元素是括号
//如果 当前运算符 优先级比栈顶元素高，直接存入
while (true) {
if (stack1.empty() || stack1.peek().equals('(')
|| compare(chars[i], stack1.peek()) > 0) {
stack1.push(chars[i]);
break;
}
stack2.push(stack1.pop());
}
break;
case '(':
stack1.push(chars[i]);
break;
case ')':
while (!stack1.peek().equals('(')){
//中间运算符 取出并存入s2
stack2.push(stack1.pop());
}
//此时左括号被抵消，所以取出
stack1.pop();
break;
default:
//是数字
stack2.push(chars[i]);
}
}
while (!stack1.empty()){
stack2.push(stack1.pop());
}
//将栈中元素 倒序输出到数组中
String[] arr = new String[stack2.size()];
int size = stack2.size()-1;
while (!stack2.isEmpty()){
arr[size]=stack2.pop()+"";
size--;
}
System.out.println(Arrays.toString(arr));
}
//定义优先级 乘除大于加减 1代表c1优先级高 -1代表c2优先级高 0代表相同
public static int compare(char c1,char c2){
if (c1=='+'|| c1=='-'){
if(c2=='*'||c2=='/'){
return -1;
}
return 0;
}
if (c1=='*'|| c1=='/'){
if(c2=='+'||c2=='-'){
return 1;
}
return 0;
}
return 0;
}
}
9
6
22
拓展：中缀转后缀表达式（代码为上）
分析：
中缀-->后缀
1+（（2+3）*4）-5
元素 s2（中间结果栈） s1（运算符栈） 说明
1 1
+ +
( + (
( + ( (
2 1 2
+ + ( ( +
3 1 2 3
) 1 2 3 + + (
出现右括号 在s1中找到对应的左括号
将中间元素存入s2
* + ( *
4 1 2 3 + 4
) 1 2 3 + 4 * +
- 1 2 3 + 4 * + -
当新运算符和栈顶运算符同一优先级
取出s1元素，存入s2
5 1 2 3 + 4 * + 5
null 1 2 3 + 4 * + 5 -
[1, 2, 3, +, 4, *, +, 5, -]
散列表（哈希表）
什么是哈希表？
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
记录的存储位置=f(关键字)
这里的对应关系f称为散列函数，又称为哈希（Hash函数），采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。
哈希表hashtable(key，value) 就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。（或者：把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。）
而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。
Hash的应用
1、Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。
2、查找：哈希表，又称为散列，是一种更加快捷的查找技术。我们之前的查找，都是这样一种思路：集合中拿出来一个元素，看看是否与我们要找的相等，如果不等，缩小范围，继续查找。而哈希表是完全另外一种思路：当我知道key值以后，我就可以直接计算出这个元素在集合中的位置，根本不需要一次又一次的查找！
举一个例子，假如我的数组A中，第i个元素里面装的key就是i，那么数字3肯定是在第3个位置，数字10肯定是在第10个位置。哈希表就是利用利用这种基本的思想，建立一个从key到位置的函数，然后进行直接计算查找。
3、Hash表在海量数据处理中有着广泛应用。
散列表的查找步骤
当存储记录时，通过散列函数计算出记录的散列地址
当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录
哈希算法：
将任意长度的输入，通过算法 ，转换为固定长度的输出
散列法：
1）直接寻址法，取关键字或关键字的线性函数 作为散列地址
2）除留取模法，对关键字或关键字的部分取模 作为散列地址
取模的除数，一般为素数/质数
3）取随机数法，使用随机函数，取关键字的随机值 作为散列地址
4）数字分析法，根据数字的特性，经过分析，取部分进行计算（如手机号后四位等）
5）平方取中法
先求平方，取中间几位 作为散列地址
6）折叠法
取关键字的几部分
散列冲突（哈希冲突）
原因——抽屉原理
map中不同映射指向同一个地址 哈希碰撞
解决办法：再找一个空闲位置
具体如下
1）线性探测
key01 ——1号柜
如果满了 顺延的下一个位置 ——2号柜子
2）二次探测
如果满了 按照一定规律顺延
如以二次方顺延 value value^2 value+2^2
3)双重哈希
使用两种哈希函数 第一个位置被占用时 计算第二个
4）链表法
让一个位置 存储多个value
哈希应用
哈希例题1：两数之和
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
public class TwoSum {
public static void main(String[] args) {
int[] ints ={2,7,11,15};
System.out.println(Arrays.toString(twoSum(ints,26)));
System.out.println(Arrays.toString(twoSum1(ints,26)));
System.out.println(Arrays.toString(twoSum2(ints,26)));
}
//法一，暴力破解；遍历每个元素，查找后续元素与其相加的和 是否等于target
//依次遍历出每两个元素的和
public static int[] twoSum(int[] nums, int target) {
//遍历每个元素 查找后续元素与其相加的和 是否等于target
for (int i = 0; i < nums.length; i++) {
for (int j = i+1; j < nums.length; j++) {
if(nums[i]+nums[j]==target){
return new int[]{i,j};
}
}
}
return new int[]{-1,-1};
}
//法二：倒推法
//使用额外容器存储 快速找到是否存在某个值
//<元素值，索引位置> hashmap
public static int[] twoSum1(int[] nums, int target) {
//使用map存储 <元素值，索引位置>
Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i],i );
}
//再次遍历，
//用map查找另一个值，另一个值相加的
for (int i = 0; i < nums.length; i++) {
int num = target-nums[i];
//数组中同一元素不能使用两遍
if (map.containsKey(num)&&map.get(num)!=i){
return new int[]{i,map.get(num)};
}
}
return new int[]{-1,-1};
}
//法三：一次遍历，哈希，合并法一法二
//边遍历边修改
public static int[] twoSum2(int[] nums, int target) {
Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int num = target-nums[i];
if (map.containsKey(num)&&map.get(num)!=i){
return new int[]{map.get(num),i};
}
map.put(nums[i],i);
}
return new int[]{-1,-1};
}
}
[2, 3]
[3, 2]
[3, 2]
哈希例题2：两数之和
找不同
给定两个字符串 s 和 t ，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例 1：
输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。
示例 2：
输入：s = "", t = "y"
输出："y"
public class FindDifferent {
public static void main(String[] args) {
System.out.println(findTheDifference("abcd","abcde"));
System.out.println(findTheDifference("abcd","abcda"));
System.out.println("---------------");
System.out.println(findTheDifference1("abcd","abcde"));
System.out.println(findTheDifference1("abcd","abcda"));
System.out.println("---------------");
System.out.println(findTheDifference2("abcd","abcde"));
System.out.println(findTheDifference2("abcd","abcda"));
System.out.println("---------------");
System.out.println(findTheDifference3("abcd","abcde"));
System.out.println(findTheDifference3("abcd","abcda"));
}
//法一：
//使用map分别记录 s和t中<字母，出现次数>
//t中也出现了，就抵消，
//t出现多了。或者t有s没有，即为新增字母
public static char findTheDifference(String s, String t) {
Map map = new HashMap<>();
for (Character character : s.toCharArray()) {
if (map.containsKey(character)){
Integer integer = map.get(character)+1;
map.put(character,integer);
continue;
}
map.put(character,1);
}
//查找t中出现多了一次，即再次循环为map中value0时
//或者t中出现map中不存在，都为新增元素
for (Character character : t.toCharArray()) {
if (!map.containsKey(character)){
return character;
}
if (map.containsKey(character)&&map.get(character)>0){
//出现就抵消一次
Integer integer = map.get(character)-1;
map.put(character,integer);
continue;
}else {
return character;
}
}
return '-';
}
//法二：字符串替换法 replace()
//遍历s，将s中t替换
public static char findTheDifference1(String s, String t) {
for (Object o : s.toCharArray()) {
//替换第一个出现的位置
t=t.replaceFirst(o.toString(),"");
}
return t.toCharArray()[0];
}
//法三：根据ASCII码特性，s和t字母ascii码之和的差值为多出来的字母ascii码值
public static char findTheDifference2(String s, String t) {
int sSum =0,tSum=0;
for (byte aByte : s.getBytes()) {
sSum+=aByte;
}
for (byte aByte : t.getBytes()) {
tSum+=aByte;
}
return (char) (tSum-sSum);
}
//法四：异或运算 利用同异或等于0，异或0等于本身特性
public static char findTheDifference3(String s, String t) {
int result =0;
for (char c : s.toCharArray()) {
result^=c;
}
for (char c : t.toCharArray()) {
result^=c;
}
return (char) result;
}
}
e
a
---------------
e
a
---------------
e
a
---------------
e
a
递归
斐波那契数列（Fibonacci sequence）
又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
public class Fibonacci {
public static void main(String[] args) {
System.out.println(fib(6));
}
//返回第n个月有多少只兔子
public static int fib(int N){
if (N==1) return 1;
if (N==2) return 1;
System.out.println("求第"+N+"个月的兔子数量");
System.out.println("转化为求第"+(N-1)+"个月和第"+(N-2)+"个月的兔子数量");
return fib(N-1)+fib(N-2);
}
}
求第6个月的兔子数量
转化为求第5个月和第4个月的兔子数量
求第5个月的兔子数量
转化为求第4个月和第3个月的兔子数量
求第4个月的兔子数量
转化为求第3个月和第2个月的兔子数量
求第3个月的兔子数量
转化为求第2个月和第1个月的兔子数量
求第3个月的兔子数量
转化为求第2个月和第1个月的兔子数量
求第4个月的兔子数量
转化为求第3个月和第2个月的兔子数量
求第3个月的兔子数量
转化为求第2个月和第1个月的兔子数量
8
大部分递归可以转化为迭代处理
main函数：System.out.println(fib(6));
public static int fib1(int N){
//6 —— 0 1 2 3 4 5
//fib(0)=0 有时需要处理
if (N<=1) return 1;
int[] arr =new int[N];
arr[0]=1;
arr[1]=1;
for (int i = 2; i < arr.length; i++) {
arr[i]=arr[i-1]+arr[i-2];
}
return arr[N-1];
}
结果：8
汉诺塔问题（不能通过迭代处理）
public class Hanoi {
public static void main(String[] args) {
//三个圆盘 A->C A->B C->B(把前两个圆盘 从A移动到B)
// A->C (移动最大的圆盘)
// B->A B->C A->C (再把前两个圆盘 从B移动到C)
hanoi(3,'A','B','C');
System.out.println((int) time(3)+"次");
}
//四个参数 有n个圆盘 需要从A柱子移动到C 经由B
// 起始 中间 终点
public static void hanoi(int n,char A,char B,char C){
//出口
if(n==1){
System.out.println(A+"->"+C);
return;
}
// 先把前N-1个圆盘 从A移动到B （经由C）
// 再把最大的圆盘 从A移动到C
// 最后把前N-1个圆盘 从B移动到C（经由A）
hanoi(n-1,A,C,B);
System.out.println(A+"->"+C);
hanoi(n-1,B,A,C);
}
public static double time(int n){
return Math.pow(2,3)-1;
}
}
A->C
A->B
C->B
A->C
B->A
B->C
A->C
7
阶乘
public class Factorial {
//递归计算n的阶乘
public static void main(String[] args) {
System.out.println(factorial(6));
System.out.println(factorial1(6));
System.out.println(factorial2(6));
}
//递归计算n的阶乘
public static int factorial(int n){
if (n==1) return 1;
return n*factorial(n-1);
}
//数组法
public static int factorial1(int n){
if (n<=1) return 1;
int[] arr =new int[n+1];
arr[0]=1;
arr[1]=1;
for (int i = 2; i < arr.length; i++) {
arr[i]=arr[i-1]*i;
}
return arr[n];
}
//循环法,n必须大于0
public static int factorial2(int n){
int result=1;
while(n>1){
result*=n*(n-1);
n-=2;
}
return result;
}
}
720
720
720
倒叙输出正整数
public class OutputIntegerByReverse {
public static void main(String[] args) {
System.out.println(optInt(413586));
System.out.println(optInt1(413586));
optInt2(413586);
}
//法一，递归法：利用个位数是前一位的特性
//(1) 1
//(12) 2+1
//(123) 3+(12)
public static int optInt(int n){
if(n<10)return n;
System.out.print(n%10);
return optInt(n/10);
}
//法二：循环法
//定义一个String量，拼接字符
public static int optInt1(int n){
String s="";
while (n>0){
s+=n%10;
n/=10;
}
return Integer.parseInt(s) ;
}
//法三：数组法
public static void optInt2(int n){
int[] arr =new int[Integer.toString(n).length()];
int i=0;
while(n>0){
arr[i]=n%10;
n/=10;
System.out.print(arr[i]);
i++;
}
}
}
685314
685314
685314
树
树定义和基本术语
定义
树(Tree)是n(n≥0)个节点的有限集T，并且当n＞0时满足下列条件：
（1）有且仅有一个特定的称为根(Root)的节点；
（2）当n＞1时，其余节点可以划分为m(m＞0)个互不相交的有限集T1、T2 、…、Tm，每个集Ti(1≤i≤m)均为树，且称为树T的子树(SubTree)。
特别地，不含任何节点(即n＝0)的树，称为空树。
基本术语
节点：存储数据元素和指向子树的链接，由数据元素和构造数据元素之间关系的引用组成。
孩子节点：树中一个节点的子树的根结点称为这个节点的孩子节点，如图1中的A的孩子节点有B、C、D
双亲节点：树中某个节点有孩子节点(即该节点的度不为0)，该节点称为它孩子节点的双亲节点，也叫前驱节点。双亲节点和孩子节点是相互的，如图1中，A的孩子节点是B、C、D，B、C、D的双亲节点是A。
兄弟节点：具有相同双亲节点(即同一个前驱)的节点称为兄弟节点，如图1中B、B、D为兄弟节点。
节点的度：节点所有子树的个数称为该节点的度，如图1，A的度为3，B的度为2.
树的度：树中所有节点的度的最大值称为树的度，如图1的度为3.
叶子节点：度为0的节点称为叶子节点，也叫终端节点。如图1的K、L、F、G、M、I、J
分支节点：度不为0的节点称为分支节点，也叫非终端节点。如图1的A、B、C、D、E、H
节点的层次：从根节点到树中某节点所经路径的分支数称为该节点的层次。根节点的层次一般为1(也可以自己定义为0)，这样，其它节点的层次是其双亲节点的层次加1.
树的深度：树中所有节点的层次的最大值称为该树的深度(也就是最下面那个节点的层次)。
有序树和无序树：树中任意一个节点的各子树按从左到右是有序的，称为有序树，否则称为无序树。
树的抽象数据类型描述
数据元素：具有相同特性的数据元素的集合。
结构关系：树中数据元素间的结构关系由树的定义确定。
树的实现
树是一种递归结构，表示方式一般有孩子表示法和孩子兄弟表示法两种。树实现方式有很多种、有可以由广义表的递归实现，也可以有二叉树实现，其中最常见的是将树用孩子兄弟表示法转化成二叉树来实现。
二叉树
二叉树是一种特殊的树，每个节点最多只能有两个子节点。（如图1.1）
二叉搜索树要求：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树
二叉树的深度
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
public class Depth {
public static void main(String[] args) {
// 3
// /
// 9 20
// /
// 15 7
TreeNode treeNode = new TreeNode(3);
TreeNode leftNote = new TreeNode(9);
TreeNode rightNote = new TreeNode(20);
TreeNode subLeft = new TreeNode(15);
TreeNode subRight = new TreeNode(7);
treeNode.left=leftNote;
treeNode.right=rightNote;
rightNote.left=subLeft;
rightNote.right=subRight;
System.out.println(maxDepth(treeNode));
}
public static int maxDepth(TreeNode root) {
//树的深度 左子树的深度和右子树的深度中 更夫的值 +1
if (root==null)return 0;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth,rightDepth)+1;
}
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
3
新建完全二叉树
public class CreateTree {
public static void main(String[] args) {
TreeNode node = createTree();
System.out.println();
}
private static int[] array ={1,2,3,4,5};
private static List nodeList =new LinkedList<>();
//完全二叉树
public static TreeNode createTree(){
//构造节点
for (int i = 0; i < array.length; i++) {
TreeNode node = new TreeNode(array[i]);
nodeList.add(node);
}
//构造节点之间的关系
for (int i = 0;i
相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false
public class IsSameTree {
//两棵树，如果有左右子树，树A的左子树==树B的左子树，同时树A的右子树==树B的右子树
//如果两棵树都是空，是相同的
//如果一棵为空，一棵不为空，是不同的
//如果数值不同，也是不同的
public boolean isSameTree(TreeNode p, TreeNode q) {
//递归出口
if (p==q&&p==null){
return true;
}
if (p.val!=q.val){
return false;
}
if (p==null||q==null){
return false;
}
//递归规律
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}
}
先序：根左右 中序：左根右 后序：左右根
满二叉树
完全二叉树
递归实现遍历完全二叉树
//递归实现遍历
public class TreeSearch {
public static void main(String[] args) {
TreeNode node=CreateTree.createTree();
System.out.println("先序：");
preOrder(node);
System.out.println("n中序：");
midOrder(node);
System.out.println("n后序：");
lasOrder(node);
}
//先序遍历
public static void preOrder(TreeNode node){
//递归出口
if(node==null) return;
System.out.print(node.val+" ");//根
preOrder(node.left);//左
preOrder(node.right);//右
}
//中序遍历
public static void midOrder(TreeNode node){
//递归出口
if(node==null) return;
midOrder(node.left);//左
System.out.print(node.val+" ");//根
midOrder(node.right);//右
}
//后序遍历
public static void lasOrder(TreeNode node){
//递归出口
if(node==null) return;
lasOrder(node.left);//左
lasOrder(node.right);//右
System.out.print(node.val+" ");//根
}
}
先序：
1 2 4 8 9 5 3 6 7
中序：
8 4 9 2 5 1 6 3 7
后序：
8 9 4 5 2 6 7 3 1
广度优先遍历
public class TreeSearchByQueue {
public static void main(String[] args) {
TreeNode node=CreateTree.createTree();
bfs(node);
}
//广度优先遍历的实现
//通过队列实现 从根节点开始存储到队列中
//对队列元素的处理是 将队头节点的孩子存入队列中，取出队头节点
//直到队列为空 所有节点处理完成 同时节点的顺序是按照层级的
public static void bfs(TreeNode node){
if (node==null)return;
Queue queue =new LinkedList<>();
queue.offer(node);
while (queue.size()>0){
//取出队首元素
TreeNode node1 =queue.poll();
System.out.print(node1.val+" ");
//如果其有左孩子或者右孩子，将其存入队列中
if (node1.left!=null) {
queue.offer(node1.left);
}
if (node1.right!=null) {
queue.offer(node1.right);
}
}
}
1 2 3 4 5 6 7 8 9
非递归实现遍历完全二叉树
public class TreeSearch2 {
public static void main(String[] args) {
TreeNode node=CreateTree.createTree();
System.out.println("先序：");
preOrderByLoop(node);
System.out.println("n中序：");
midOrderByLoop(node);
System.out.println("n后序：");
lasOrderByLoop(node);
}
//栈实现先序遍历
public static void preOrderByLoop(TreeNode node){
if(node==null) return;
Stack stack = new Stack<>();
//使用指针记录遍历到哪个节点
TreeNode p = node;
while (p!=null||!stack.isEmpty()) {
//入栈 把当前能读到的所有左孩子都存入栈中
//入栈的方式就是先序遍历的结果
while (p!=null){
//先序是入栈打印
System.out.print(p.val+" ");
stack.push(p);
p=p.left;
}
//入栈顺序：1 2 4 8 9 5 3 6 7
//出栈顺序：8 4 9 2 5 1 6 3 7
//1 2 4 8
//1 2 9
//1 5
//3 6
//7
//出栈，如果 栈不为空，弹出栈顶元素，找到右孩子
if (!stack.isEmpty()){
p = stack.pop();
p = p.right;//指针下移
}
}
}
//栈实现中序遍历
public static void midOrderByLoop(TreeNode node){
if(node==null) return;
Stack stack = new Stack<>();
//使用指针记录遍历到哪个节点
TreeNode p = node;
while (p!=null||!stack.isEmpty()) {
//入栈 把当前能读到的所有左孩子都存入栈中
//入栈的方式就是先序遍历的结果
while (p!=null){
stack.push(p);
p=p.left;
}
//1 2 4 8
//1 2 9
//1 5
//3 6
//7
//出栈，如果 栈不为空，弹出栈顶元素，找到右孩子
if (!stack.isEmpty()){
p = stack.pop();
//中序是出栈打印
System.out.print(p.val+" ");
p = p.right;//指针下移
}
}
}
//栈实现后序遍历
public static void lasOrderByLoop(TreeNode node){
if(node==null) return;
Stack stack = new Stack<>();
//使用指针记录遍历到哪个节点
TreeNode p = node;
//记录上一次访问的节点
TreeNode pre = node;
while (p!=null||!stack.isEmpty()) {
//入栈 把当前能读到的所有左孩子都存入栈中
//入栈的方式就是先序遍历的结果
while (p!=null){
//先序是入栈打印
stack.push(p);
p=p.left;
}
//遍历经过的路径 左 - 根 - 右
// 后序遍历时 根节点不从栈中弹出 要在右子树遍历后 再弹出
// 如何判断右子树被遍历完成
// 通过上一次遍历的是当前节点的右子树 代表此根节点也可以被遍历出来
//1 2 4 8
//1 2 4 9
//1 2
//1 2 5
//1 3 6
//1 3 7
//入栈顺序：1 2 4 8 9 5 3 6 7
//出栈顺序：8 9 4 5 2 6 7 3 1
//节点出栈情况：
//1)当前节点是叶子节点
//2）上次出栈的节点是当前节点的右孩子
if (!stack.isEmpty()){
p = stack.pop();
if(p.right==null||pre==p.right){
System.out.print(p.val+" ");
pre=p;
p=null;
}else {
//不满足出栈条件，因为节点有右孩子，且没被访问到
stack.push(p);
p = p.right;//指针下移
}
}
}
}
}
先序：
1 2 4 8 9 5 3 6 7
中序：
8 4 9 2 5 1 6 3 7
后序：
8 9 4 5 2 6 7 3 1
例题1：对称二叉树
对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
public class Symmetric {
public static void main(String[] args) {
Integer[] arr = {1,2,2,null,3,null,3};
TreeNode node = CreateTree.createTreeByArray(arr,0);
System.out.println(isSymmetric(node));
System.out.println(isSymmetric1(node));
}
//递归
public static boolean isSymmetric(TreeNode root) {
//排除空树的情况
if(root==null)return true;
//拆分成左右子树 递归判断
return isMirror(root.left,root.right);
}
// 将树拆解为 左子树A 右子树B
// A的左子树和B的右子树要对称
// A的右子树和B的左子树有对称
public static boolean isMirror(TreeNode node1,TreeNode node2){
//递归的出口
if (node1==null&& node2==null) return true;
if (node1==null||node2==null) return false;
if (node1.val!=node2.val) return false;
return isMirror(node1.left,node2.right)
&& isMirror(node1.right,node2.left);
}
//====================================================
//非递归 队列法
public static boolean isSymmetric1(TreeNode root) {
if(root==null) return true;
Queue queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()){
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
if (node1==null&& node2==null) continue;
//判断是否不对称
if (node1==null||node2==null) return false;
if (node1.val!=node2.val) return false;
//
queue.offer(node1.left);
queue.offer(node2.right);
queue.offer(node1.right);
queue.offer(node2.left);
}
return true;
}
}
false
false
例题2：翻转二叉树
翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
public class InvertTree {
public static void main(String[] args) {
Integer[] arr ={4,2,7,1,3,6,9};
TreeNode node=CreateTree.createTreeByArray(arr,0);
// TreeNode result1 = invertTree1(node);
TreeNode result2 = invertTree1(node);
// TreeNode result3 = invertTree1(node);
// TreeNode result4 = invertTree1(node);
System.out.println();
}
//法一(前序遍历)：先将左右子树交换 然后再分别 翻转左右子树
public static TreeNode invertTree1(TreeNode root) {
//递归出口
if (root==null)return null;
TreeNode tmp = root.left;
root.left=root.right;
root.right=tmp;
invertTree1(root.left);
invertTree1(root.right);
return root;
}
//法二(中序遍历)：先翻转左子树，然后左右子树交换，再翻转左子树（原来右子树）
public static TreeNode invertTree2(TreeNode root) {
//递归出口
if (root==null)return null;
invertTree2(root.left);
TreeNode tmp = root.left;
root.left=root.right;
root.right=tmp;
invertTree2(root.left);
return root;
}
//法三(后序遍历)：先翻转左子树，再翻转右子树，然后左右子树交换
public static TreeNode invertTree3(TreeNode root) {
//递归出口
if (root==null)return null;
invertTree3(root.left);
invertTree3(root.right);
TreeNode tmp = root.left;
root.left=root.right;
root.right=tmp;
return root;
}
//广度优先遍历
public static TreeNode invertTree4(TreeNode root) {
if (root==null)return null;
Queue queue =new LinkedList<>();
queue.offer(root);
while (queue.size()>0){
//取出队首元素
TreeNode node1 =queue.poll();
//交换此节点的左右子树
TreeNode tmp = node1.left;
node1.left=node1.right;
node1.right=tmp;
//如果其有左孩子或者右孩子，将其存入队列中
if (node1.left!=null) {
queue.offer(node1.left);
}
if (node1.right!=null) {
queue.offer(node1.right);
}
}
return root;
}
}
public class BuildTreeByOrder {
public static void main(String[] args) {
int[] preOrder = {1,2,3,4,5};
int[] inOrder = {3,4,2,1,5};
TreeNode root =buildTree(preOrder,inOrder);
}
public static TreeNode buildTree(int[] preOrder,int[] inOrder){
//递归出口
if(preOrder.length==0)return null;
//在前序结果中 找到根节点
int rootValue = preOrder[0];
TreeNode root = new TreeNode(rootValue);
//查找根节点在中序结果中的位置
int leftSize = find(inOrder,rootValue);
//切分出左子树的前序和中序结果
//使用 Arrays，copyOfRange方法 三个参数 原始数组 起始位置 终止位置
//[起始位置，终止位置]
//
//2 3 4 [1,leftSize+1)
//3 4 2 [0,leftSize)
int[] leftPreOrder = Arrays.copyOfRange(preOrder,1,leftSize+1);
int[] leftInOrder = Arrays.copyOfRange(inOrder,0,leftSize);
root.left = buildTree(leftPreOrder,leftInOrder);
//切分出右子树的前序和中序结果
// 5 [leftSize+1,end)
// 5 [leftSize+1,end)
int[] rightPreOrder= Arrays.copyOfRange(preOrder,leftSize+1,preOrder.length);
int[] rightInOrder= Arrays.copyOfRange(inOrder,leftSize+1,inOrder.length);
root.right=buildTree(rightPreOrder,rightInOrder);
return root;
}
//查找索引位置
private static int find(int[] array,int value) {
for (int i = 0; i < array.length; i++) {
if (array[i]==value){
return i;
}
}
return -1;
}
}
图
基础知识
图是由顶点集合和顶点之间边的集合组成 ，通常表示为G-V-E G(V,E)
G 表示图 V表示图中顶点的集合 E表示图中边的集合
特殊的图：1，自环：即一条连接一个顶点和其自身的边；
2.平行边：连接同一对顶点的两条边；
图的分类
根据图中边的方向可分为：无向图和有向图
无向图：顶点之间没有指向
有向图：顶点之间有方向
带权无向图：顶点之间的边加上了权重的度量
带权有向图：顶点之间的边加上了权重的度量 （注意：两顶点之间不同方向之间的权重可以不同）
无向图
图的相关术语
相邻顶点：
当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点。
度：
某个顶点的度就是依附于该顶点的边的个数
子图：
是一幅图所有边的子集（包括这些边依附的顶点）组成的图；
路径：
是由边顺序连接的一系列的顶点组成
环：
是一条至少含有一条边且终点和起点相同的路径
连通图：
如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称之为连通图
连通子图：
一个非连通图由若干连通部分组成，每一个连通的部分都可以称为该图的连通子图
图的存储结构
常用的图的表示结构：邻接矩阵和邻接表
邻接矩阵
下面四种图
其临接矩阵为：
邻接表
图的实现
图的API设计
类名 Graph 构造方法 Graph(int V):创建一个包含v个顶点但不包含边的图 成员方法 1.public int V():获取图中顶点的数量
2.publi int E():获取图中边的数量
3.public void addEdge(int V,int W):向图中添加一条边v-w
4.public Queueadj(int v):获取和顶点v相邻的所有顶点
成员变量 1.private final int V：记录顶点数量
2.private int E：记录边的数量
3.private Queue []adj：邻接表
import java.util.LinkedList;
import java.util.Queue;
public class Graph {
//顶点数目
private final int V;
//边的数目
private int E;
//邻接表
private Queue[] adj;
public Graph(int V){
//初始化顶点数量
this.V=V;
//初始化边的数量
this.E=0;
//初始化邻接表
this.adj=new Queue[V];
for (int i = 0; i < adj.length; i++) {
adj[i] = new LinkedList<>();
}
}
//获取顶点数目
public int V(){
return V;
}
//获取边的数目
public int E(){
return E;
}
//向图中添加一条边 v-w
public void addEdge(int v,int w){
//在无向图，边是没有方向，所以改变既可以是(v到w的边，又可以从w到v的边，
// 因此需要让w出现在v的；邻接表中，并且还要让v出现在w的邻接表中)
adj[v].offer(w);
adj[w].offer(v);
//边的数量+1
E++;
}
//获取和顶点v相邻的所有顶点
public Queue adj(int v){
return adj[v];
}
}
图的搜索
深度优先搜索
因为边是没有方向的，为了不对顶点重复搜索，应有标记来表示当前有没有搜索过，可以使用一个布尔类型的数组 boolean[V] marked,索引代表顶点，值代表当前顶点是否已经搜索，如果已经搜索，标记为true，如果没有搜索，标记为false；
类名 DepthFirstSearch 构造方法 DepthFirstSearch(Graph G,int s):构造深度优先搜索对象，使用深度优先搜索找到G图s顶点的所有相通顶点 成员方法 1.private void dfs(Graph G,int v):使用深度优先搜索找出G图中v顶点的所有相通的顶点
2.public boolean marked(int w):判断w顶点与s顶点是否相通
3.public int count(): 获取与顶点s相通的所有顶点的总数
成员变量 1.private boolean[] marked: 索引代表顶点，值代表当前顶点是否已经被搜索
2.private int count：记录有多个顶点与s顶点相通
