2021年JAVA 面试题之--数据结构篇【附详细答案】

电玩女神 2022-11-07 04:12 283阅读 0赞

### 先罗列本篇文章包含的 Java 常见面试的主题： ###

**目录**

一、数组

二、字符串

三、栈和队列

*  链表
 *  二叉树
 *  哈希表
 *  图算法
 *  堆
 *  动态规划
 *  排序算法

### 项目推荐： ###

**[2000多G的计算机各行业电子资源分享（持续更新）][2000_G]**

**[2020年微信小程序全栈项目之喵喵交友【附课件和源码】][2020]**

**[Spring Boot开发小而美的个人博客【附课件和源码】][Spring Boot]**

**[Java微服务实战296集大型视频-谷粒商城【附代码和课件】][Java_296_-]**

**[Java开发微服务畅购商城实战【全357集大项目】-附代码和课件][Java_357_-]**

**[最全最详细数据结构与算法视频-【附课件和源码】][-]**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]

————————————————

<table> 
 <tbody> 
 <tr> 
 <td> 2021年JAVA 精心整理的常见面试题-附详细答案 </td> 
 <td><a href="https://mikejun.blog.csdn.net/article/details/114488339" rel="nofollow">https://mikejun.blog.csdn.net/article/details/114488339</a></td> 
 </tr> 
 <tr> 
 <td> 2021年- 精心整理的 SpringMVC 常见面试题-【附详细答案】 </td> 
 <td><a href="https://mikejun.blog.csdn.net/article/details/114992529" rel="nofollow">https://mikejun.blog.csdn.net/article/details/114992529</a></td> 
 </tr> 
 <tr> 
 <td> 2021年JAVA 面试题之--数据结构篇【附详细答案】 </td> 
 <td><a href="https://mikejun.blog.csdn.net/article/details/114647742" rel="nofollow">https://mikejun.blog.csdn.net/article/details/114647742</a></td> 
 </tr> 
 <tr> 
 <td> 三天刷完《剑指OFFER编程题》--Java版本实现（第一天） </td> 
 <td><a href="https://mikejun.blog.csdn.net/article/details/106996017" rel="nofollow">https://mikejun.blog.csdn.net/article/details/106996017</a></td> 
 </tr> 
 <tr> 
 <td> 三天刷完《剑指OFFER编程题》--Java版本实现（第二天） </td> 
 <td><a href="https://mikejun.blog.csdn.net/article/details/108098502" rel="nofollow">https://mikejun.blog.csdn.net/article/details/108098502</a></td> 
 </tr> 
 <tr> 
 <td> 三天刷完《剑指OFFER编程题》--Java版本实现（第三天） </td> 
 <td><a href="https://mikejun.blog.csdn.net/article/details/108253489" rel="nofollow">https://mikejun.blog.csdn.net/article/details/108253489</a></td> 
 </tr> 
 </tbody> 
</table>

## 一、数组 ##

### 1. **在java中，声明一个数组过程中，是如何分配内存的？** ###

1. 当声明数组类型变量时，为其分配了（32位）引用空间，由于未赋值，因此并不指向任何对象；

2. 当创建了一个数组对象（也就是new出来的）并将其地址赋值给了变量，其中创建出来的那几个数组元素相当于引用类型变量，因此各自占用（32位的）引用空间并按其默 认初始化规则被赋值为null

3. 程序继续运行，当创建新的对象并（将其地址）赋值给各数组元素，此时堆内存就会有值了

### 2. 找数组当中重复的元素 ###

**第一种方法：两层for循环 0(n^2)**

public class TestArray {
 	public static void main(String[] args) {
 		
 		int[] arr = new int[] {1, 2, 5, 5, 6, 6, 7, 2, 9, 2};
 		
 		findDupicateInArray(arr);
 		
 	}
 	
 	//第一种，两层for循环，指定一个循环一周 0(n^2)
 	public static void findDupicateInArray(int[] arr) {
 		int count = 0;
 		for (int i = 0; i < arr.length; i++) {
 			for (int j = i+1; j < arr.length; j++) {
 				if (arr[i] == arr [j]) {
 					System.out.println("arr["+j+"]="+ arr[i] + "和" + "arr["+i+"]="+arr[i]+"冲突" + ", ");
 				}
 			}
 			
 		}
 	}
 }

**第二种方法:扫描的时候用哈希表来存储数组的每一个元素，当碰到数组元素与哈希表中一致时，可以确认数字重复。这样的方法时间复杂度是O(N)，但是需要临时空间O(N)。**

public static boolean duplicate(int numbers[],int length,int [] duplication) {
 Map<Integer,Integer> map=new HashMap<>();
 if(length==0) return false;
 for(int i:numbers){
 if(map.containsKey(i)){
 System.out.println("产生冲突的就是"+i);
 } 
 else map.put(i,0);
 }
 duplication[0]=-1;
 return false;
 }

### 3. 翻转一个数组 ###

**第一种方法：新开辟一个空间**

public class TestArray {
 	public static void main(String[] args) {
 		
 		int[] arr = new int[] {1,2,3,4,5};
 		//定义一个新数组，把老数组中的元素反向添加到新数组中
 		newArrReverse(arr);
 
 		//在本数组上进行翻转
 		ArrReverse(arr);
 		
 		
 	}
 	//定义一个新数组，把老数组中的元素反向添加到新数组中
 	public static void newArrReverse(int[] arr) {
 		int[] brr = new int[arr.length];
 		int length = arr.length - 1; //定义一个从后向前的指针
 		for (int i = 0; i < arr.length; i++) {
 			brr[i] = arr[length];
 			length --;
 		}
 		System.out.println(Arrays.toString(brr));
 	}	
 }

**第二种方法：交换法。i一直递增，length一直递减，交换**

//在本数组上进行翻转
 	public static void ArrReverse(int[] arr) {
 		int temp = 0;
 		int length = arr.length - 1; 
 		for (int i = 0; i < arr.length; i++) {
 			if (length == i) {
 				break;
 			}
 			 temp = arr[i];
 			 arr[i] = arr[length];
 			 arr[length] = temp;
 			 length --;
 		}
 		System.out.println(Arrays.toString(arr));
 	}

### 4. 二维数组中的查找 ###

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

\[  
\[1, 4, 7, 11, 15\],  
\[2, 5, 8, 12, 19\],  
\[3, 6, 9, 16, 22\],  
\[10, 13, 14, 17, 24\],  
\[18, 21, 23, 26, 30\]  
\]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

从左下角开始搜索，如果该数大于目标数，则 行数 减去 1，向上搜索小的数值；

如果小于目标数，则 列数 + 1 ，向左边搜索，搜索更大的数值

public class Solution {
 public boolean Find(int target, int [][] array) {
 int row = array.length-1;
 int col = 0; // 从左下角开始搜索,array.length 表示行的大小，array[0].length表示列的大小
 
 while (row >= 0 && col <= array[0].length-1){
 if (array[row][col] == target){
 return true;
 }else if(array[row][col] > target){
 row--;
 }else{
 col++;
 }
 
 }
 return false;
 
 }
 }

### 5. 旋转数组的最小数字 ###

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。  
例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。  
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

二分查找的变形，注意到旋转数组的首元素肯定不小于旋转数组的尾元素，设置中间点。

1. 如果中间点大于首元素，说明最小数字在后面一半，如果中间点小于尾元素，说明最小数字在前一半。依次循环。

2. 当一次循环中首元素小于尾元素，说明最小值就是首元素。

3. 但是当首元素等于尾元素等于中间值，只能在这个区域顺序查找。如： 【1,2,2,3,4】 --> 【2,3,4,1,2】

import java.util.ArrayList;
 public class Solution {
 public int minNumberInRotateArray(int [] array) {
 int len = array.length;
 if (len == 0){
 return 0;
 }
 
 // 如果第一个数字 都比最后一个数字小，则代表没有旋转
 int left = 0;
 int right = len - 1;
 if (array[left] < array[right]){
 return array[left];
 }
 
 int mid;
 int minVal = array[left];
 while ((right - left) > 1){
 mid = (right + left) / 2;
 if (array[left] <= array[mid]){
 left = mid;
 }else if (array[right] >= array[mid]){
 right = mid;
 }else if ((array[left] == array[mid]) && array[mid] == array[right]){
 // 只能遍历找到最小的值
 for (int i = 0; i < len; i++){
 if (minVal > array[i]){
 minVal = array[i];
 right = i;
 }
 
 }
 }
 }
 
 return array[right];
 
 
 }
 }

### 6. 矩形覆盖 ###

我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？

比如n=3时，2\*3的矩形块有3种覆盖方法：

![format_png][]

还是找规律的一道题，归根结底还是 斐波那契数列

public class Solution {
 public int RectCover(int target) {
 if (target <= 0) return 0;
 if (target == 1) return 1;
 if (target == 2) return 2;
 
 return (RectCover(target - 1) + RectCover(target - 2));
 
 }
 }

### 7.调整数组顺序使奇数位于偶数前面 ###

**题目描述**

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

public class Solution {
 public void reOrderArray(int [] array) {
 int index = 0; // 用于保存奇数位置
 int size = array.length;
 
 for (int i =0; i< size; i++){
 if (array[i] % 2 == 1){ // 如果是奇数的话
 int j = i;
 while (j > index){ // 循环交换奇数和偶数位置，偶数位置相对不变
 int temp = array[j];
 array[j] = array[j-1];
 array[j-1] = temp;
 j--;
 }
 index++; // 更新奇数位置
 
 }
 }
 
 }
 }

### 8.数组中出现次数超过一半的数字 ###

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

\#使用哈希表 思路: 使用hash，key是数字，value是出现的次数

import java.util.Map;
 import java.util.HashMap;
 
 public class Solution {
 public int MoreThanHalfNum_Solution(int [] array) {
 if (array.length == 0) return 0;
 HashMap<Integer, Integer> map = new HashMap();
 for (int i = 0; i < array.length; i++){
 int num = array[i];
 if (map.containsKey(num)){ // 如果原map中key值存在，则 + 1
 map.put(num, map.get(num)+1);
 }else{
 map.put(num, 1);
 }
 }
 for (Map.Entry<Integer, Integer> entry: map.entrySet()){ // 遍历所有的索引和值
 if (entry.getValue() > array.length/2){
 return entry.getKey();
 }
 }
 return 0;
 }
 }

### 9 把数组排成最小数 ###

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

例如输入数组\{3，32，321\}，则打印出这三个数字能排成的最小数字为321323。

这里自定义一个比较大小的函数，比较两个字符串s1, s2大小的时候，先将它们拼接起来，比较s1+s2,和s2+s1那个大，如果s1+s2大，那说明s2应该放前面，所以按这个规则，s2就应该排在s1前面。（类似于排序算法）

比如： s1 = 32， s2 = 321， 先将两者字符串转换成数字，比较 s1 + s2 = 32321， 和 s2 + s1 = 32132的数字的大小，

如果前者比较大的话，将s1 和 s2交换。

代码这里使用了一个小技巧：

> int pre = Integer.valueOf(numbers\[i\] +"" + numbers\[j\]); // 将数字转换为字符串，拼接，再转换成数字

import java.util.ArrayList;
 
 public class Solution {
 public String PrintMinNumber(int [] numbers) {
 
 String res = "";
 for (int i = 0; i < numbers.length; i++){
 for (int j = i+1; j < numbers.length; j++){
 int pre = Integer.valueOf(numbers[i] +"" + numbers[j]); // 将数字转换为字符串，拼接，再转换成数字
 int tail = Integer.valueOf(numbers[j] +"" + numbers[i]);
 if (pre > tail){
 int temp;
 temp = numbers[i];
 numbers[i] = numbers[j];
 numbers[j] = temp;
 }
 }
 }
 for (int i = 0; i < numbers.length; i++){
 res += numbers[i];
 }
 return res;
 
 }
 }

### 10.丑数 ###

丑数的定义：把只包含质因子2、3和5的数称作丑数（Ugly Number）。

例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

首先从丑数的定义我们知道，一个丑数的因子只有2,3,5，那么丑数p = 2 ^ x \* 3 ^ y \* 5 ^ z，换句话说一个丑数一定由另一个丑数乘以2或者乘以3或者乘以5得到，那么我们从1开始乘以2,3,5，就得到2,3,5三个丑数，在从这三个丑数出发乘以2,3,5就得到4，6,10,6，9,15,10,15,25九个丑数，我们发现这种方法得到重复的丑数，而且我们题目要求第N个丑数。

（1）丑数数组： 1

乘以2的队列：2

乘以3的队列：3

乘以5的队列：5

选择三个队列头最小的数2加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；

（2）丑数数组：1,2

乘以2的队列：4

乘以3的队列：3，6

乘以5的队列：5，10

此时可能出现，乘以5 的数值大于 乘以3 的数值，所以要取 乘以3和乘以5的最小值

选择三个队列头最小的数3加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；

（3）丑数数组：1,2,3

乘以2的队列：4,6

乘以3的队列：6,9

乘以5的队列：5,10,15

选择三个队列头里最小的数4加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；

import java.util.ArrayList;
 
 public class Solution {
 public int GetUglyNumber_Solution(int index) {
 
 if (index <= 0) return 0;
 ArrayList<Integer> res = new ArrayList();
 res.add(1);
 int i2=0, i3=0, i5=0;
 
 while (res.size() < index){
 int i2_value = res.get(i2) * 2;
 int i3_value = res.get(i3) * 3;
 int i5_value = res.get(i5) * 5;
 // 找到最小的值
 int minValue = Math.min(i2_value, Math.min(i3_value, i5_value));
 res.add(minValue);
 if (i2_value == minValue) i2++; // 将index往后移动
 if (i3_value == minValue) i3++;
 if (i5_value == minValue) i5++;
 }
 
 return res.get(res.size()-1);
 }
 }

### 11. .数组中只出现一次的数字 ###

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

使用哈希表,这是比较容易想到的方法

//num1,num2分别为长度为1的数组。传出参数
 //将num1[0],num2[0]设置为返回结果
 import java.util.HashMap;
 public class Solution {
 public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
 int size = array.length;
 HashMap<Integer, Integer> map = new HashMap();
 for (int i = 0; i < size; i++){
 if (!map.containsKey(array[i])){
 map.put(array[i], 1);
 }else{
 map.put(array[i], map.get(array[i]) + 1);
 }
 }
 // 获取value值为 1 的key值
 boolean sign = false;
 for (int i = 0; i < size; i++){
 
 if (map.get(array[i]) == 1){
 if (sign == false){
 num1[0] = array[i];
 sign = true;
 }else{
 num2[0] = array[i];
 }
 
 }
 }
 
 }
 }

使用异或

使用的原则是：

位运算中异或的性质：两个相同数字异或=0，一个数和0异或还是它本身。

当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。

只不过这里使用两次异或，内在还是要将不同的两个数字分开，再异或。

任何一个数字异或他自己都等于0，0异或任何一个数都等于那个数。数组中出了两个数字之外，其他数字都出现两次，那么我们从头到尾依次异或数组中的每个数，那么出现两次的数字都在整个过程中被抵消掉，那两个不同的数字异或的值不为0，也就是说这两个数的异或值中至少某一位为1。

我们找到结果数字中最右边为1的那一位i，然后一次遍历数组中的数字，如果数字的第i位为1，则数字分到第一组，数字的第i位不为1，则数字分到第二组。这样任何两个相同的数字就分到了一组，而两个不同的数字在第i位必然一个为1一个不为1而分到不同的组，然后再对两个组依次进行异或操作，最后每一组得到的结果对应的就是两个只出现一次的数字。

//num1,num2分别为长度为1的数组。传出参数
 //将num1[0],num2[0]设置为返回结果
 public class Solution {
 public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
 int size = array.length;
 if (size == 0) return ;
 int num = 0;
 for (int i = 0; i < size; i++){
 num ^= array[i];
 }
 int index = getFirstBitOne(num);
 for (int i = 0; i< size; i++){
 if(isBitOne(array[i], index)){
 num1[0] ^= array[i];
 }else{
 num2[0] ^= array[i];
 }
 }
 }
 
 private int getFirstBitOne(int num){
 int index = 0;
 while ((num & 1) == 0 && index < 32){
 num >>= 1;
 index += 1;
 }
 return index;
 }
 
 private boolean isBitOne(int num, int index){
 // 判断num在第index位是否为 1
 return (((num >> index)& 1) == 1);
 }
 
 }

### 12.数组中重复的数字 ###

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

例如，如果输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出是第一个重复的数字2。

使用类似哈希表的方法：

public class Solution {
 // Parameters:
 // numbers: an array of integers
 // length: the length of array numbers
 // duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
 // Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
 // 这里要特别注意~返回任意重复的一个，赋值duplication[0]
 // Return value: true if the input is valid, and there are some duplications in the array number
 // otherwise false
 public boolean duplicate(int numbers[],int length,int [] duplication) {
 //由于： 一个长度为n的数组里的所有数字都在0到n-1的范围内
 boolean[] sign = new boolean[length];
 
 for (int i = 0; i < length; i++){
 if (sign[numbers[i]] == true){
 duplication[0] = numbers[i];
 return true;
 }
 sign[numbers[i]] = true;
 }
 return false;
 }
 }

## 二、字符串 ##

### 1.将字符串转换成整数 ###

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

输入描述:

输入一个字符串,包括数字字母符号,可以为空  
输出描述:

如果是合法的数值表达则返回该数字，否则返回0  
示例1

输入

> \+2147483647  
> 1a33

输出

> 2147483647  
> 0

public class Solution {
 public int StrToInt(String str) {
 int size = str.length();
 if (str.equals("+") && size==1) return 0;
 if (str.equals("-") && size == 1) return 0;
 if (size == 0) return 0;
 
 int sum = 0;
 for (int i = 0; i < size; i++){
 if (str.charAt(i) == '-'){
 continue;
 }else if (str.charAt(i) == '+'){
 continue;
 }else if (str.charAt(i) >= '0' && str.charAt(i) <= '9'){
 sum = sum * 10 + str.charAt(i) - '0';
 }else{
 return 0;
 }
 }
 return str.charAt(0) == '-' ? -sum : sum; // 判断第一个符号是否是 + -
 }
 }

### 2.表示数值的字符串 ###

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。

但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

需要注意的是，指数E后面必须跟一个整数，不能没有数，也不能为小数。

public class Solution {
 public boolean isNumeric(char[] str) {
 int size = str.length;
 if (size == 0) return false;
 
 boolean hasE = false, hasDot = false, hasSign = false;
 for (int i = 0; i < size; i++){
 // 如果当前字符是 e， E
 if (str[i] == 'e' || str[i] == 'E'){
 // 1.首部出现，2.尾部出现，3.重复出现,均不是
 if (i == 0) return false;
 if (i == size-1) return false;
 if (hasE) return false;
 hasE = true;
 // 如果当前字符是 +， -
 }else if (str[i] == '+' || str[i] == '-'){
 // 1.如果当前不是第一位，且前一位不是E， e
 // 2.如果已经出现过+-， 且前一位不是 E， e,均为false
 if(i != 0 && str[i-1] != 'E' && str[i-1] != 'e') return false;
 if (hasSign && str[i-1] != 'E' && str[i-1] != 'e') return false;
 hasSign = true;
 }else if (str[i] == '.'){
 // 1.存在多个 . 2. 在 E 后面
 if (hasDot) return false;
 if (hasE) return false;
 hasDot = true;
 }else if (str[i] < '0' || str[i] > '9'){
 return false;
 }
 }
 return true;
 }
 }

### 3.字符流中第一个不重复的元素 ###

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

输出描述:

如果当前字符流没有存在出现一次的字符，返回\#字符。

public class Solution {
 //Insert one char from stringstream
 String str = "";
 char[] hash = new char[256];
 public void Insert(char ch)
 {
 str += ch; // 拼接字符串
 hash[ch] += 1; // 对字符 计数
 }
 //return the first appearence once char in current stringstream
 public char FirstAppearingOnce()
 {
 for (int i = 0; i < str.length(); i++){
 char ch = str.charAt(i);
 if (hash[ch] == 1){
 return ch;
 }
 }
 return '#';
 }
 }

### 4.字符串的排列 ###

输入一个字符串,按字典序打印出该字符串中字符的所有排列。

例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。  
递归法，问题转换为先固定第一个字符，求剩余字符的排列；求剩余字符排列时跟原问题一样。

递归算法实现：

![format_png 1][]

(1) 遍历出所有可能出现在第一个位置的字符（即：依次将第一个字符同后面所有字符交换）；

(2) 固定第一个字符，求后面字符的排列（即：在第1步的遍历过程中，插入递归进行实现）。

以"abc"为例

1.第一次进到这里是ch=\['a','b','c'\],list=\[\],i=0，我称为 状态A ，即初始状态

那么j=0，swap(ch,0,0)，就是\['a','b','c'\]，进入递归，自己调自己，只是i为1，交换(0,0)位置之后的状态我称为 状态B

i不等于2，来到这里，j=1，执行第一个swap(ch,1,1)，这个状态我称为 状态C1 ,再进入递归函数，此时标记为T1，i为2，那么这时就进入上一个if，将"abc"放进list中

\-------》此时结果集为\["abc"\]

2.执行完list.add之后，遇到return，回退到T1处，接下来执行第二个swap(ch,1,1)，状态C1又恢复为状态B

恢复完之后，继续执行for循环，此时j=2,那么swap(ch,1,2),得到"acb"，这个状态我称为C2,然后执行递归函数，此时标记为T2,发现i+1=2,所以也被添加进结果集，此时return回退到T2处往下执行

\-------》此时结果集为\["abc","acb"\]

然后执行第二个swap(ch,1,2)，状态C2回归状态B,然后状态B的for循环退出回到状态A

// a|b|c(状态A)

// |

// |swap(0,0)

// |

// a|b|c(状态B)

// / \\

// swap(1,1)/ \\swap(1,2) (状态C1和状态C2)

// / \\

// a|b|c a|c|b

3.回到状态A之后，继续for循环，j=1,即swap(ch,0,1)，即"bac",这个状态可以再次叫做状态A,下面的步骤同上

\-------》此时结果集为\["abc","acb","bac","bca"\]

// a|b|c(状态A)

// |

// |swap(0,1)

// |

// b|a|c(状态B)

// / \\

// swap(1,1)/ \\swap(1,2) (状态C1和状态C2)

// / \\

// b|a|c b|c|a

4.再继续for循环，j=2,即swap(ch,0,2)，即"cab",这个状态可以再次叫做状态A，下面的步骤同上

\-------》此时结果集为\["abc","acb","bac","bca","cab","cba"\]

// a|b|c(状态A)

// |

// |swap(0,2)

// |

// c|b|a(状态B)

// / \\

// swap(1,1)/ \\swap(1,2) (状态C1和状态C2)

// / \\

// c|b|a c|a|b

5.最后退出for循环，结束。

import java.util.ArrayList;
 import java.util.List;
 import java.util.Collections;
 public class Solution {
 public ArrayList<String> Permutation(String str) {
 List<String> list = new ArrayList();
 if (str.length() == 0) return (ArrayList)list;
 
 permutationHelper(str.toCharArray(), 0, list); // 递归实现
 Collections.sort(list);
 return (ArrayList)list;
 }
 
 private void permutationHelper(char[] cs, int i, List<String> list){
 if (i == cs.length-1){ // 如果索引是最后一位的话
 String s = String.valueOf(cs);
 if (!list.contains(s)){ // 防止有重复的字符串，如输入为 aab时
 list.add(s);
 return;
 }
 }else{
 for (int j = i; j < cs.length; j++){
 swap(cs, i, j);
 permutationHelper(cs, i+1, list);
 swap(cs, i, j); // 回溯法，恢复之前字符串顺序，达到第一位依次跟其他位交换的目的
 }
 }
 }
 
 private void swap(char[] cs, int i, int j){ // 交换两个字符
 char temp; 
 temp = cs[i];
 cs[i] = cs[j];
 cs[j] = temp;
 }
 }

### 5.第一次只出现一次的字符 ###

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）

使用哈希解题，遍历字符串，哈希key值为遍历的单个字符，value为出现次数；最后重新遍历，找到一开始value为1的key值

import java.util.HashMap;
 
 public class Solution {
 public int FirstNotRepeatingChar(String str) {
 int size = str.length();
 if (size == 0) return -1;
 
 HashMap<Character, Integer> map = new HashMap();
 for (int i = 0; i < size; i++){
 char value = str.charAt(i);
 if (!map.containsKey(value)){ // 如果key 值不存在，则新建key值，value为1
 map.put(value, 1);
 }else{
 map.put(value, map.get(value)+1); // value 值加一
 }
 }
 
 for (int i=0; i < size; i++){
 if (map.get(str.charAt(i)) == 1){
 return i;
 }
 }
 
 return -1;
 }
 }

另外一种比较巧妙的方法：  
主要还是hash，利用每个字母的ASCII码作hash来作为数组的index。首先用一个58长度的数组来存储每个字母出现的次数，为什么是58呢，主要是由于A-Z对应的ASCII码为65-90，a-z对应的ASCII码值为97-122，而每个字母的index=int(word)-65，比如g=103-65=38，而数组中具体记录的内容是该字母出现的次数，最终遍历一遍字符串，找出第一个数组内容为1的字母就可以了，时间复杂度为O(n)

public class Solution {
 public int FirstNotRepeatingChar(String str) {
 int size = str.length();
 if (size == 0) return -1;
 int[] array = new int[58];
 
 for (int i = 0; i< size; i++){
 array[(int)str.charAt(i)-65]++; 
 }
 
 for (int i= 0; i < size; i++){
 if (array[(int)str.charAt(i)-65] == 1){
 return i;
 }
 }
 
 
 return -1;
 }
 }

### 6. 左旋转字符串 ###

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。

例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

解题思路：

原理：YX = (X^T Y ^T) ^T，初始看这种想法还是蛮有技巧的

假设输入str为abcXYZdef，n=3

反转前3个字符，得到cbaXYZdef

反转第n个字符后面所有的字符cbafedZYX

反转整个字符串XYZdefabc

public class Solution {
 public String LeftRotateString(String str,int n) {
 int size = str.length();
 if (size == 0 || n < 0) return "";
 n = n % size;
 
 char[] strChar = str.toCharArray();
 reverse(strChar, 0, n-1); // 前n 个字符反转
 reverse(strChar, n, size-1); // n个字符后反转
 reverse(strChar, 0, size-1); // 将反转了的字符串再反转
 return new String(strChar);
 
 }
 // 二分法将数组反转
 private void reverse(char[] strChar, int start, int end){
 while (start < end){
 char temp = strChar[start];
 strChar[start] = strChar[end];
 strChar[end] = temp;
 start += 1;
 end -= 1;
 }
 }
 }

### 7.翻转单词序列 ###

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。

例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

1.将 字符串转换成字符串数组

2. 新建一个空间

3. 从字符串数组尾部开始遍历

4.将其字符存放到新的空间，并每次增加空格

public class Solution {
        public String ReverseSentence(String str) {
            if (str.trim().equals("")) return str;
            String[] s = str.split(" ");
            StringBuffer sb = new StringBuffer();
            
            for (int i = s.length-1; i >= 0; i--){
                sb.append(s[i]);
                if (i > 0){
                    sb.append(" ");
                }
            }
            return sb.toString();
        }
    }

### 8.扑克牌的顺子 ###

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^\_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

先置换特殊字符AJQK为数字，排序，然后求出大小王即0的个数，然后求出除去0之外的，数组间的数字间隔(求间隔的时候记得减去1，比如4和5的间隔为5-4-1，表示4和5是连续的数字)，同时求间隔的时候需要鉴别是否出现对。最后比较0的个数和间隔的大小即可。

\# 如果出现相同的数，则必定不是顺子

1、排序

2、计算所有相邻数字间隔总数

3、计算0的个数

4、如果2、3相等，就是顺子

5、如果出现对子，则不是顺子

import java.util.Arrays;
 public class Solution {
 public boolean isContinuous(int [] numbers) {
 int size = numbers.length;
 if (size < 5) return false;
 
 int oneNums = 0;
 int intervalNums = 0;
 Arrays.sort(numbers); // 对数组排序
 for (int i = 0; i < size-1; i++){
 
 if (numbers[i] == 0){
 oneNums += 1;
 continue;
 }
 if (numbers[i] == numbers[i+1]) return false; // 此行代码要放在==0判断后面，防止有2个0
 intervalNums += numbers[i+1] - numbers[i] - 1;
 }
 if (oneNums >= intervalNums) return true;
 return false;
 
 }
 }

## 三、栈和队列 ##

### 1. 请实现一个栈 ###

public class Stack {
    
        public Node head;
        public Node current;
    
    
        //方法：入栈操作
        public void push(int data) {
            if (head == null) {
                head = new Node(data);
                current = head;
            } else {
                Node node = new Node(data);
                node.pre = current;//current结点将作为当前结点的前驱结点
                current = node;  //让current结点永远指向新添加的那个结点
            }
        }
    
        public Node pop() {
            if (current == null) {
                return null;
            }
    
            Node node = current; // current结点是我们要出栈的结点
            current = current.pre;  //每出栈一个结点后，current后退一位
            return node;
    
        }
    
    
        class Node {
            int data;
            Node pre;  //我们需要知道当前结点的前一个结点
    
            public Node(int data) {
                this.data = data;
            }
        }
    
    
        public static void main(String[] args) {
    
            Stack stack = new Stack();
            stack.push(1);
            stack.push(2);
            stack.push(3);
    
            System.out.println(stack.pop().data);
            System.out.println(stack.pop().data);
            System.out.println(stack.pop().data);
        }
    
    }

### 2. 请实现一个队列 ###

队列的创建有两种形式：基于数组结构实现（顺序队列）、基于链表结构实现（链式队列）。

我们接下来通过链表的形式来创建队列，这样的话，队列在扩充时会比较方便。队列在出队时，从头结点head开始。

public class Queue {
 public Node head;
 public Node curent;
 
 //方法：链表中添加结点
 public void add(int data) {
 if (head == null) {
 head = new Node(data);
 curent = head;
 } else {
 curent.next = new Node(data);
 curent = curent.next;
 }
 }
 
 //方法：出队操作
 public int pop() throws Exception {
 if (head == null) {
 throw new Exception("队列为空");
 }
 
 Node node = head; //node结点就是我们要出队的结点
 head = head.next; //出队之后，head指针向下移
 
 return node.data;
 
 }
 
 
 class Node {
 int data;
 Node next;
 
 public Node(int data) {
 this.data = data;
 }
 }
 
 
 public static void main(String[] args) throws Exception {
 Queue queue = new Queue();
 //入队操作
 for (int i = 0; i < 5; i++) {
 queue.add(i);
 }
 
 //出队操作
 System.out.println(queue.pop());
 System.out.println(queue.pop());
 System.out.println(queue.pop());
 
 }
 }

### 3. 2 个队列实现一个栈 ###

入栈时把数据入到有数据的那个队列中  
出栈时把有数据的队列中的数据除过最后一个，其他都入队到另外一个队列，最后一个就是要出栈的元素

/**
 * 实现两个队列实现一个栈
 */
 public class StackQueue1 {
 private LinkedList<Integer> list1;
 private LinkedList<Integer> list2;
 public StackQueue1() {
 list1 = new LinkedList<>();
 list2 = new LinkedList<>();
 }
 
 /**
 * 入栈
 */
 public void push(int data) {
 if(!list1.isEmpty()) {
 list1.offer(data);
 } else {
 //默认栈为空的时候都入栈到list2
 list2.offer(data);
 }
 }
 
 /**
 * 出栈
 */
 public Integer pop() {
 if(isEmpty()) {
 return null;
 }
 //srcList表示有数据的队列，destList表示没有数据的队列
 LinkedList<Integer> srcList = list1;
 LinkedList<Integer> destList = list2;
 if(list1.isEmpty()) {
 srcList = list2;
 destList = list1;
 }
 Integer poll = null;
 while(!srcList.isEmpty()) {
 poll = srcList.poll();
 //如果是最后一次出队，那么不再把最后一个元素入队到另一个队列中
 if(srcList.isEmpty()) {
 break;
 }
 destList.offer(poll);
 }
 return poll;
 }
 
 /**
 * 判断栈空
 * @return
 */
 private boolean isEmpty() {
 return list1.isEmpty() && list2.isEmpty();
 }
 }

### 4. 两个栈实现一个队列 ###

/**
 * 两个栈实现一个队列
 */
 public class StackQueue2 {
 private LinkedList<Integer> srcList;
 private LinkedList<Integer> destList;
 
 public StackQueue2() {
 srcList = new LinkedList<>();
 destList = new LinkedList<>();
 }
 
 /**
 * 入队
 */
 public void offer(int data) {
 srcList.push(data);
 }
 
 /**
 * 出队
 */
 public Integer poll() {
 if(isEmpty()) {
 return null;
 }
 if(destList.isEmpty()) {
 //把srcList中的数据都搬过来
 while(!srcList.isEmpty()) {
 Integer pop = srcList.pop();
 destList.push(pop);
 }
 }
 return destList.pop();
 }
 
 /**
 * 判断队列是否为空
 * @return
 */
 private boolean isEmpty() {
 return srcList.isEmpty() && destList.isEmpty();
 }
 }

### 5. 包含min函数的栈 ###

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

思路：利用一个辅助栈来存放最小值

栈 3，4，2，5，1

辅助栈 3，3，2，2，1

每入栈一次，就与辅助栈顶比较大小，如果小就入栈，如果大就入栈当前的辅助栈顶

当出栈时，辅助栈也要出栈

这种做法可以保证辅助栈顶一定都当前栈的最小值

import java.util.Stack;
 
 public class Solution {
 
 private Stack<Integer> dataStack = new Stack();
 private Stack<Integer> minStack = new Stack();
 
 public void push(int node) {
 dataStack.push(node);
 if (minStack.isEmpty() || min() > node){ // 如果为空，则之间push进去，如果最小栈的最小值都比node大，也把node值push
 minStack.push(node); 
 }else{
 minStack.push(min());
 }
 }
 
 public void pop() {
 dataStack.pop();
 minStack.pop();
 }
 
 public int top() {
 return dataStack.peek();
 }
 
 public int min() {
 return minStack.peek();
 }
 }

### 6. 栈的压入弹出序列 ###

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

1. 建立一个辅助栈，把push序列的数字依次压入辅助栈，

2. 每次压入后，比较辅助栈的栈顶元素和pop序列的首元素是否相等，相等的话就推出pop序列的首元素和辅助栈的栈顶元素，

3.若最后辅助栈为空，则push序列可以对应于pop序列。

举例：

入栈1,2,3,4,5

出栈4,5,3,2,1

首先1入辅助栈，此时栈顶1≠4，继续入栈2

此时栈顶2≠4，继续入栈3

此时栈顶3≠4，继续入栈4

此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，,辅助栈里面是1,2,3

此时栈顶3≠5，继续入栈5

此时栈顶5=5，出栈5,弹出序列向后一位，此时为3，,辅助栈里面是1,2,3

import java.util.ArrayList;
 import java.util.Stack;
 
 public class Solution {
 public boolean IsPopOrder(int [] pushA,int [] popA) {
 if (pushA.length==0 || popA.length == 0){
 return false;
 }
 // 使用一个辅助栈
 Stack<Integer> stack = new Stack();
 int index = 0;
 for (int i=0; i< pushA.length; i++){
 stack.push(pushA[i]);
 while (!stack.isEmpty() && stack.peek()==popA[index]){
 stack.pop();
 index++; // 用于数组后一位继续判断
 }
 }
 return stack.isEmpty();
 }
 }

### 7.从上往下打印二叉树 ###

相当于时树的层次遍历

从上往下打印出二叉树的每个节点，同层节点从左至右打印。（依次打印出每层的结点值）

需要一个队列和一个存储数据的数组

import java.util.ArrayList;
 import java.util.LinkedList;
 /**
 public class TreeNode {
 int val = 0;
 TreeNode left = null;
 TreeNode right = null;
 public TreeNode(int val) {
 this.val = val;
 }
 }
 */
 public class Solution {
 public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
 // 使用队列的方法
 ArrayList<Integer> res = new ArrayList();
 if (root == null){
 return res;
 }
 
 LinkedList<TreeNode> queue = new LinkedList();
 queue.offer(root);
 
 while (!queue.isEmpty()){
 TreeNode node = queue.poll();
 res.add(node.val);
 if (node.left != null){
 queue.offer(node.left);
 }
 if (node.right != null){
 queue.offer(node.right);
 }
 }
 return res;
 
 }
 }

[2000_G]: https://mp.weixin.qq.com/s/sP4JgGWkCzpgwKr9sAV2_Q
[2020]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487704&idx=1&sn=5f4b2127c4d49fd07ae072a0721424a2&chksm=e8036fc2df74e6d489c4aa9b06f917ef7cee6027f13e150fca53cf79d5d188d4ccc1af49e098&scene=21#wechat_redirect
[Spring Boot]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487798&idx=2&sn=ac0293b996521b872a9dba5fbb3e65e6&chksm=e8036e2cdf74e73aba104a9a994a5b2e31483e8dcbe0f1d9936f6d5173b887e1560f59d2819c&scene=21#wechat_redirect
[Java_296_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487674&idx=1&sn=7aff0bdf2bb727303f3d3618995aef21&chksm=e8036fa0df74e6b6d872c7e6ece179c524ed463a4a6b74c96875475c9a3d5ddb903427dd993b&scene=21#wechat_redirect
[Java_357_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247486376&idx=1&sn=d1fef270c463ea8ac663f6fbfedd70a0&chksm=e80374b2df74fda4d3bafba878a106a19e18c5fcda266008f4f37975847a21bc612ffcd5ff39&scene=21#wechat_redirect
[-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487750&idx=1&sn=747bccbb5f5ea6b58915198de40da777&chksm=e8036e1cdf74e70ae97a5e8e265b49d7236d904d291203309159d07ba1724033062c0e370843&scene=21#wechat_redirect
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221023/068d60cf362f42a6b33c44af75d9f839.png
[format_png]: /images/20221023/27e6e8804ad746f3988e61b36daf3828.png
[format_png 1]: /images/20221023/5cc376e370b84e66b6167f02ecc0ada1.png