算法

1. 数组

1. 剑指Offer：数组旋转

1. 题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

原题传送门：link.

2. 关键词：

二分查找

3. 思路

• 利用二分查找的思路，将数组中间的元素和最右端元素对比大小。

int mid = low + (high - low) / 2;

• 分情况讨论

1. 小部分旋转到后面的情况，array=【23451】时，mid=4，high=1。mid>high，最小的数字一定在后半部分，low=mid+1；

//此时mid不可能是最小的数字

2. 大部分旋转到后面的情况，array=【51234】时，mid=2，high=4。mid<high，最小的数字一定在前半部分，high=mid；

//此时mid有可能是最小的数

3. 特殊的情况，array=【11101】或array=【10111】时，mid=high=1。最小的数字一可能在前半部分也可能在后半部分，high=high-1。

//保留了与high相等mid，排除high不影响。

4. 代码实现（Java）

import java.util.ArrayList;
public class Solution {public int minNumberInRotateArray(int [] array) {int low = 0 ; int high = array.length - 1;   while(low < high){//mid为动态取值int mid = low + (high - low) / 2;        if(array[mid] > array[high]){low = mid + 1;}else if(array[mid] == array[high]){high = high - 1;}else{high = mid;}   }return array[low];}
}

5. 知识积累

掌握二分查找

2. 剑指Offer：调整数组顺序使奇数位于偶数前面

1. 题目描述

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

NOTE：保证base和exponent不同时为0

原题传送门：link.

2. 关键词

冒泡排序

3. 思路

• 我们可以借鉴冒泡排序的特点，让偶数不断向右边移动，而冒泡的过程本身也可以保证相对顺序的不变,最后所有的偶数都移动到了右边，最坏情况下外层循环需要进行array.size()次。

来自牛客网：link.

4. 代码实现（Java）

public class Solution {public void reOrderArray(int [] array) {//每次至少会有一个偶数换到最后for(int len=array.length;len>0;len--){Boolean change=false;for(int i=0;i<array.length-1;i++){if (array[i]%2==0&&array[i+1]%2==1){//若为偶数且下一个数为奇数int temp=array[i];array[i]=array[i+1];array[i+1]=temp；change = true;//结束条件是不发生交换}}if(!change){return;}} }
}

时间复杂度为（O^2）

5. 知识积累

暂无

3. 剑指Offer： 顺时针打印矩阵

1. 题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

原题传送门：link.

2. 关键词

ArrayList

3. 链接：
   简单来说，就是不断地收缩矩阵的边界
   定义四个变量代表范围，up、down、left、right

   1. 向右走存入整行的值，当存入后，该行再也不会被遍历，代表上边界的 up 加一，同时判断是否和代表下边界的 down 交错
   2. 向下走存入整列的值，当存入后，该列再也不会被遍历，代表右边界的 right 减一，同时判断是否和代表左边界的 left 交错
   3. 向左走存入整行的值，当存入后，该行再也不会被遍历，代表下边界的 down 减一，同时判断是否和代表上边界的 up 交错
   4. 向上走存入整列的值，当存入后，该列再也不会被遍历，代表左边界的 left 加一，同时判断是否和代表右边界的 right 交错

   

• 暂无

4. 代码实现（Java）

import java.util.ArrayList;
public class Solution {public ArrayList<Integer> printMatrix(int [][] matrix) {if(matrix==null)return null;ArrayList<Integer> list=new ArrayList<Integer> ();int left=0,top=0,right=matrix.length-1,bottom=matrix[0].length-1;while(left<=right&&top<=bottom){//从左向右for(int i=left;i<=right;i++){list.add(matrix[top][i]);}//从上到下（从下一行开始向下走）for(int j=top+1;j<=bottom;j++){list.add(matrix[j][right]);}//从右到左，有可能出现特殊的情况只有一行，为了避免重复访问if(top!=bottom){for(int k=right-1;k>=left;k--){list.add(matrix[bottom][k]);}}//从下到上，有可能出现特殊的情况只有一列，为了避免重复访问if(left!=right){for(int l=bottom-1;l>top;l--){list.add(matrix[l][left]);}} //下一个正方形矩阵top++;left++;right--;bottom--;}return list; }
}

5. 知识积累

• 数组：连续存储，索引速度快 缺点不好插入数据

• ArrayList：继承了IList类，插入删除方便快捷

4. 剑指Offer: 数组中出现次数超过一半的数字

1. 题目描述

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

原题传送门：link.

2. 关键词

分形叶思想

3. 思路

• 如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。

• 在遍历数组时维护两个变量：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。

1. 假设数组中有一个数字x出现的次数超过数组长度的一半。【1,2,3,4,5,6,6,6,6,6,6】中，x=6符合条件。
2. 从数组中随机选择两个数。若相同，保留；若不同，抵消。那么6一定会保留下来。
3. 所以上述方法可以达到此目的。

• 遍历结束后，所保存的数字即为所求，他可能满足条件。然后再判断它是否符合条件即可。

判断是否符合条件是必要的。比如数组【1,2,3]，最后会留下3，但是不符合条件！

4. 代码（Java）

public class Solution
{public int MoreThanHalfNum_Solution(int [] array){int count=0;int temp=0;for(int i=0;i<array.length;i++){if(temp==array[i])count++;else if(count>0)count--;else{temp=array[i];count=1;}}  count=0;for(int i=0;i<array.length;i++){if(temp==array[i])count ++;}return count>array.length/2?temp:0;}
}

5. 知识积累

• 另一种方法：将数组排个序，输出中间的元素，因为如果有出现次数超过一半的数值话，排完序后中间的那个元素肯定是它。然后再遍历这个数组求其数量是否符合题意即可。
• 但样做的话排序的时间复杂度一般来说是O(NlogN)，本文算法时间复杂度为O(N)。

5. 剑指Offer：丑数

1. 题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。原题传送门：link.

2. 关键词

丑数

3. 思路

首先从丑数的定义我们知道，一个丑数的因子只有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
选择三个队列头最小的数3加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
（3）丑数数组：1,2,3
乘以2的队列：4,6
乘以3的队列：6,9
乘以5的队列：5,10,15
选择三个队列头里最小的数4加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
（4）丑数数组：1,2,3,4
乘以2的队列：6，8
乘以3的队列：6,9,12
乘以5的队列：5,10,15,20
选择三个队列头里最小的数5加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
（5）丑数数组：1,2,3,4,5
乘以2的队列：6,8,10，
乘以3的队列：6,9,12,15
乘以5的队列：10,15,20,25
选择三个队列头里最小的数6加入丑数数组，但我们发现，有两个队列头都为6，所以我们弹出两个队列头，同时将12,18,30放入三个队列；
……………………
疑问：
1.为什么分三个队列？
丑数数组里的数一定是有序的，因为我们是从丑数数组里的数乘以2,3,5选出的最小数，一定比以前未乘以2,3,5大，同时对于三个队列内部，按先后顺序乘以2,3,5分别放入，所以同一个队列内部也是有序的；
2.为什么比较三个队列头部最小的数放入丑数数组？
因为三个队列是有序的，所以取出三个头中最小的，等同于找到了三个队列所有数中最小的。
实现思路：
我们没有必要维护三个队列，只需要记录三个指针显示到达哪一步；“|”表示指针,arr表示丑数数组；
（1）1
|2
|3
|5
目前指针指向0,0,0，队列头arr[0] * 2 = 2, arr[0] * 3 = 3, arr[0] * 5 = 5
（2）1 2
2 |4
|3 6
|5 10
目前指针指向1,0,0，队列头arr[1] * 2 = 4, arr[0] * 3 = 3, arr[0] * 5 = 5
（3）1 2 3
2| 4 6
3 |6 9
|5 10 15
目前指针指向1,1,0，队列头arr[1] * 2 = 4, arr[1] * 3 = 6, arr[0] * 5 = 5
………………

4. 代码（Java）

public class Solution {public int GetUglyNumber_Solution(int index) {if(index<=0)return 0;int[] result = new int[index];int count = 0;int i2 = 0;int i3 = 0;int i5 = 0;result[0] = 1;int tmp = 0;while (count < index-1) {tmp = min(result[i2] * 2, min(result[i3] * 3, result[i5] * 5));if(tmp==result[i2] * 2) i2++;//三条if防止值是一样的，不要改成else的if(tmp==result[i3] * 3) i3++;if(tmp==result[i5]*5) i5++;result[++count]=tmp;}return result[index - 1];}private int min(int a, int b) {return (a > b) ? b : a;}
}

5. 复杂度

• 暂无

6. 知识积累

• 暂无

6. 剑指Offer: 数组中的逆序对

1. 题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%100000000

题目保证输入的数组中没有的相同的数字数据范围：

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2*10^5

2. 关键词：归并排序

3. 思路：归并排序的改进，把数据分成前后两个数组(递归分到每个数组仅有一个数据项)，合并数组，合并时，出现前面的数组值array[i]大于后面数组值array[j]时；则前面数组array[i]~array[mid]都是大于array[j]的，count += mid+1 - i。

4. 代码（Java）

public class Solution {public int InversePairs(int [] array) {if(array==null||array.length==0){return 0;}int[] copy = new int[array.length];for(int i=0;i<array.length;i++){copy[i] = array[i];}int count = InversePairsCore(array,copy,0,array.length-1);//数值过大求余return count;}private int InversePairsCore(int[] array,int[] copy,int low,int high){if(low==high){return 0;}int mid = (low+high)>>1;int leftCount = InversePairsCore(array,copy,low,mid)%1000000007;int rightCount = InversePairsCore(array,copy,mid+1,high)%1000000007;int count = 0;int i=mid;int j=high;int locCopy = high;while(i>=low&&j>mid){if(array[i]>array[j]){count += j-mid;copy[locCopy--] = array[i--];if(count>=1000000007)//数值过大求余{count%=1000000007;}}else{copy[locCopy--] = array[j--];}}for(;i>=low;i--){copy[locCopy--]=array[i];}for(;j>mid;j--){copy[locCopy--]=array[j];}for(int s=low;s<=high;s++){array[s] = copy[s];}return (leftCount+rightCount+count)%1000000007;}
}

5. 复杂度

6. 知识积累

• 暂无

7. 剑指Offer: 扑克牌顺子

1. 题目描述

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。

原题传送门：link.

2. 关键词

翻转字符串

3. 思路

• 将数组排序
  例：排序前：【1，2，0，3，0 】排序后：【0，0，1，2，3】
• 遍历数组，在此期间期间
  1. 遇到数字“0”，统计0的个数记为numOfZero，并使用continue跳出此次循环（为的是不做其他任何处理）。
  2. 遇到数字非“0”，
     1） 如果有相同元素（排序后一定连续的），直接返回false（此时一定不是癞子）。
     2）记录相邻数字间的总间隔numOfInterval：【1，2】之间间隔记为“0”，【1，3】之间间隔数记为1。
  3. 如果numOfZero >= numOfInterval，则可以组成癞子，否则不能。（癞子可以填充一个空隙，故有"= “，并填充左右和数字中间，故有”> "）

4. 代码（Java）

import java.util.Arrays;
public class Solution {public boolean isContinuous(int[] numbers) {int numOfZero = 0;int numOfInterval = 0;int length = numbers.length;if(length == 0){return false;}//必须先排序Arrays.sort(numbers);//遍历数组for (int i = 0; i < length - 1; i++) {// 计算癞子数量if (numbers[i] == 0) {numOfZero++;continue;}// 对子，直接返回if (numbers[i] == numbers[i + 1]) {return false;}//记录数字间的非正常间隔numOfInterval += numbers[i + 1] - numbers[i] - 1;}if (numOfZero >= numOfInterval) {return true;}return false;}
}

5. 复杂度

• 暂无

6. 知识积累

• 暂无

8. 剑指Offer: 数组中重复的数字

1. 题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

原题传送门：link.

2. 关键词

哈希表

3. 思路

• 因为是在一个长度为n的数组里的所有数字都在0到n-1的范围内，所以可以新建一个数组，使每个数字对应相应的数组下标，若出现一次在新数组对应索引下标里标记，再出现若检测到返回true。
• 第一个重复的数字，可以使用布尔类型的数组进行记录，可以节省空间。

4. 代码（Java）

public class Solution {    
public boolean duplicate(int numbers[], int length, int[] duplication) {// boolean类型的变量,默认是falseboolean[] k = new boolean[length];for (int i = 0; i < k.length; i++) {//如果内部有之前遇到过的if (k[numbers[i]] == true) {duplication[0] = numbers[i];return true;}//如果没有，则标记为truek[numbers[i]] = true;}return false;}
}

5.复杂度

• 暂无

6. 知识积累

• 暂无

9. 剑指Offer: 构建乘积数组

1. 题目描述

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）

原题传送门：link.

2. 关键词

数组

3. 思路

解析链接：https://www.nowcoder.com/profile/645151/codeBookDetail?submissionId=1516453

B[i]的值可以看作下图的矩阵中每行的乘积。

下三角用连乘可以很容求得，上三角，从下向上也是连乘。

因此我们的思路就很清晰了，先算下三角中的连乘，即我们先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。

4. 代码（Java）

public class Solution {public int[] multiply(int[] A) {int length = A.length;int[] B = new int[length];if(length != 0 ){B[0] = 1;//计算下三角连乘for(int i = 1; i < length; i++){B[i] = B[i-1] * A[i-1];}int temp = 1;//计算上三角for(int j = length-2; j >= 0; j--){temp *= A[j+1];B[j] *= temp;}}return B;}
}

5. 复杂度

• 暂无

6. 知识积累

• 暂无

10. 剑指Offer: 数据流中的中位数

题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

解题思路
先用java集合PriorityQueue来设置一个小顶堆和大顶堆
主要的思想是：因为要求的是中位数，那么这两个堆，大顶堆用来存较小的数，从大到小排列；
小顶堆存较大的数，从小到大的顺序排序，显然中位数就是大顶堆的根节点与小顶堆的根节点和的平均数。
⭐保证：小顶堆中的元素都大于等于大顶堆中的元素，所以每次塞值，并不是直接塞进去，而是从另一个堆中poll出一个最大（最小）的塞值
⭐当数目为偶数的时候，将这个值插入大顶堆中，再将大顶堆中根节点（即最大值）插入到小顶堆中；
⭐当数目为奇数的时候，将这个值插入小顶堆中，再讲小顶堆中根节点（即最小值）插入到大顶堆中；
⭐取中位数的时候，如果当前个数为偶数，显然是取小顶堆和大顶堆根结点的平均值；如果当前个数为奇数，显然是取小顶堆的根节点
理解了上面所述的主体思想，下面举个例子辅助验证一下。

例如，传入的数据为：[5,2,3,4,1,6,7,0,8],那么按照要求，输出是"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "

那么整个程序的执行流程应该是（用min表示小顶堆，max表示大顶堆）：

5先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[5],max=[无]，avg=[5.00]
2先进入小顶堆，然后将小顶堆中最小值放入大顶堆中，此时min=[5],max=[2],avg=[(5+2)/2]=[3.50]
3先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[3,5],max=[2],avg=[3.00]
4先进入小顶堆，然后将小顶堆中最小值放入大顶堆中，此时min=[4,5],max=[3,2],avg=[(4+3)/2]=[3.50]
1先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[3,4,5],max=[2,1]，avg=[3/00]
6先进入小顶堆，然后将小顶堆中最小值放入大顶堆中，此时min=[4,5,6],max=[3,2,1],avg=[(4+3)/2]=[3.50]
7先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[4,5,6,7],max=[3,2,1],avg=[4]=[4.00]
0先进入小顶堆，然后将小顶堆中最大值放入小顶堆中，此时min=[4,5,6,7],max=[3,2,1,0],avg=[(4+3)/2]=[3.50]
8先进入大顶堆，然后将大顶堆中最小值放入大顶堆中，此时min=[4,5,6,7,8],max=[3,2,1,0],avg=[4.00]

import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {//小顶堆private PriorityQueue<Integer> minHeap = new PriorityQueue<>();//大顶堆private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});//记录偶数个还是奇数个int count = 0;//每次插入小顶堆的是当前大顶堆中最大的数//每次插入大顶堆的是当前小顶堆中最小的数//这样保证小顶堆中的数永远大于等于大顶堆中的数//中位数就可以方便地从两者的根结点中获取了public void Insert(Integer num) {//个数为偶数的话，则先插入到大顶堆，然后将大顶堆中最大的数插入小顶堆中if(count % 2 == 0){//offer：插入一个元素，不能被立即执行的情况下会返回一个特殊的值maxHeap.offer(num);int max = maxHeap.poll();minHeap.offer(max);}else{//个数为奇数的话，则先插入到小顶堆，然后将小顶堆中最小的数插入大顶堆中minHeap.offer(num);int min = minHeap.poll();maxHeap.offer(min);}count++;}public Double GetMedian() {//当前为偶数个，则取小顶堆和大顶堆的堆顶元素求平均if(count % 2 == 0){return new Double(minHeap.peek() + maxHeap.peek())/2;}else{//当前为奇数个，则直接从小顶堆中取元素即可return new Double(minHeap.peek());}}
}

11. 剑指Offer: 矩阵中的路径

Dfs模板：

dfs(){// 第一步，检查下标是否满足条件// 第二步：检查是否被访问过，或者是否满足当前匹配条件// 第三步：检查是否满足返回结果条件// 第四步：都没有返回，说明应该进行下一步递归// 标记dfs(下一次)// 回溯
}  
main() {for (对所有可能情况) {dfs()}
}

基本思路:
\0. 根据给定数组，初始化一个标志位数组，初始化为false，表示未走过，true表示已经走过，不能走第二次

1. 根据行数和列数，遍历数组，先找到一个与str字符串的第一个元素相匹配的矩阵元素，进入hasPathCore
2. 根据col和row先确定一维数组的位置，因为给定的matrix是一个一维数组
3. 确定递归终止条件：越界，当前找到的矩阵值不等于数组对应位置的值，已经走过的，这三类情况，都直接false，说明这条路不通
4. 若pathLength，就是待判定的字符串str的索引已经判断到了最后一位，此时说明是匹配成功的
5. 下面就是本题的精髓，递归不断地寻找周围四个格子是否符合条件，只要有一个格子符合条件，就继续再找这个符合条件的格子的四周是否存在符合条件的格子，直到pathLength到达末尾或者不满足递归条件就停止。
6. 走到这一步，说明本次是不成功的，我们要还原一下标志位数组index处的标志位，进入下一轮的判断。

/**
用一个状态数组保存之前访问过的字符，然后再分别按上，下，左，右递归
*/
public class Solution {public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {//用一个状态数组保存之前访问过的字符int flag[] = new int[matrix.length];//遍历数组中的每个值for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (helper(matrix, rows, cols, i, j, str, 0, flag))return true;}}return false;}private boolean helper(char[] matrix, int rows, int cols, int i, int j, char[] str, int k, int[] flag) {int index = i * cols + j;//检查下标是否满足条件if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index] == 1) return false;//若pathLength已经到str末尾,说明之前的匹配成功了,直接返回True即可;if(k == str.length - 1) return true;//标记当前位置flag[index] = 1;//只要存在通路，则返回tureif (helper(matrix, rows, cols, i - 1, j, str, k + 1, flag)|| helper(matrix, rows, cols, i + 1, j, str, k + 1, flag)|| helper(matrix, rows, cols, i, j - 1, str, k + 1, flag)|| helper(matrix, rows, cols, i, j + 1, str, k + 1, flag)) {return true;}//如果此路不通，则将当前位置置0flag[index] = 0;return false;}
}

2. 链表

1. 剑指Offer：从尾到头打印链表

1. 题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

原题传送门：link.

2. 关键词

链表的头插法

3. 思路

• 首先使用头插法逆置链表
• 然后将链表导入到数组里

4. 代码实现（Java）

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Collections;
public class Solution {public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {ListNode newhead= new ListNode(-1);while(listNode!=null){ListNode next=listNode.next;listNode.next=newhead.next;newhead.next=listNode;listNode=next;}next=newhead.next;//newhead的下一个结点才是要导出的第一个结点ArrayList<Integer> list = new ArrayList<Integer>(-1);while(next!=null){list.add[next.val];next=next.next;}   return list;}
}  

5. 知识积累

需掌握数组，链表的基本操作和内部结构。

2. 剑指Offer: 链表中倒数第k个结点

1. 题目描述

输入一个链表，输出该链表中倒数第k个结点。

原题传送门：link.

2. 关键词

链表，倒数第k个

3. 思路

• 链表长度无法直接输出，可遍历得出
• 本题使用快慢指针，使快指针与慢指针间始终相差k个节点
• 当快指针到达尾部后的null时，慢指针刚好在倒数第k个节点
• 要考虑数组长度小于k的情况，此时返回null

4. 代码实现（Java）

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindKthToTail(ListNode head,int k) {ListNode fast=head,slow=head;int i=0;while(fast!=null){i++;if(i>k){slow=slow.next;}fast=fast.next;} return i<k?null:slow;}
}

5. 知识积累

暂无

3. 剑指Offer: 反转链表

1. 题目描述

输入一个链表，反转链表后，输出新链表的表头。

原题传送门：link.

2. 关键词

反转链表

3. 思路

• 头插法
• 返回头节点应该为newhead.next
• newhead应该被定义为链表
• 递归方法传送门：link.

4. 代码实现（Java）

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode ReverseList(ListNode head) {ListNode newhead= new ListNode(-1);newhead.next=null;while(head!=null){ListNode next=head.next;head.next=newhead.next;newhead.next=head;head=next;}return newhead.next;}
}

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if(head==null||head.next==null){return head;}//ListNode next=head.next;ListNode newhead=reverseList(head.next);//必须使用head.next.next，而非newhead.next,因为只有第一次时head.next=newhead;head.next.next=head;//释放指针，否则会在链表尾部生成环：7 6 5 4 3 2 1 2 1 2  ...head.next=null;return newhead;}
}

1. 知识积累

暂无

4. 剑指Offer: 合并两个排序的链表

1. 题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

2. 关键词

反转链表

3. 思路

• 非递归
• 尾插法
• 递归传送门：link.

4. 代码实现（Java）

/*
/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {ListNode list3 = new ListNode (-1);ListNode root=list3;while(list1!=null&&list2!=null){if(list2.val>list1.val){root.next=list1;list1=list1.next;root=root.next;                }else{root.next=list2;list2=list2.next;root=root.next;}}root.next=list1!=null?list1:list2;return list3.next;}
}
/*** 递归做法*/
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1==null) return l2;if(l2==null) return l1;if(l1.val>l2.val){l2.next=mergeTwoLists(l1,l2.next);//这是嵌套入口，return l2;}else{l1.next=mergeTwoLists(l1.next,l2);return l1;}}
}

5. 知识积累

暂无

5. 剑指Offer: 复杂链表的复制

1. 题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

原题传送门：link.

2. 关键词

复杂链表的复制

3. 思路

• 在每一个结点后面插入复制的结点
• 对复制结点的random的链接进行赋值
• 拆分出复制的链表

4. 代码（Java）

/*
public class RandomListNode {int label;RandomListNode next = null;RandomListNode random = null;RandomListNode(int label) {this.label = label;}
}
*/
public class Solution {public RandomListNode Clone(RandomListNode pHead){RandomListNode p=pHead;RandomListNode t=pHead;//在每个节点后面插入一个节点并赋值while(p!=null){RandomListNode q=new RandomListNode(p.label);q.next=p.next;p.next=q;p=q.next;}//赋值randomwhile(t!=null){RandomListNode q=t.next;if(t.random!=null)q.random=t.random.next;t=q.next;}//删除RandomListNode s=new RandomListNode(0);RandomListNode s1=s;while(pHead!=null){//定位，防止删除后找不到RandomListNode  q=pHead.next;//删除pHead.next=q.next;q.next=s.next;//插入s.next=q;s=s.next;//定位移动pHead=pHead.next;       }return s1.next;}
}

5. 知识积累

暂无

6. 剑指Offer: 两个链表的第一个公共结点

1. 题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
原题传送门：link.

2. 关键词

哈希数组

3. 思路

• 首先将两个指针全部遍历到链表的尾部，并且分别记录两个链表的长度
• 然后长链表的长度len1减去短链表len2的长度得len1-len2
• 然后设置短链表指针指针从头出发，长链表指针从len1-len2处出发
• 第一个交点便是他们第一个公共节点

4. 代码（Java）

/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {if(pHead1==null||pHead2==null){return null;}ListNode head1=pHead1,head2=pHead2;int len1=0,len2=0;while(head1!=null){head1=head1.next;len1++;}while(head2!=null){head2=head2.next;len2++;}head1=pHead1;head2=pHead2;int sub_value1=len2-len1;int sub_value2=len1-len2;if(sub_value1>0){while(sub_value1>0){head2=head2.next;sub_value1--;  }}if(sub_value2>0){while(sub_value2>0){head1=head1.next;sub_value2--;  } }while(head1!=null){if(head1.val==head2.val){return head1;}head1=head1.next;head2=head2.next;}return null;}
}

5.复杂度

• 暂无

6. 知识积累

• 暂无

7. 剑指Offer: 孩子们的游戏(圆圈中最后剩下的数)

1. 题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

原题传送门：link.

2. 关键词

用线性表模拟环，取余

3. 思路

• 用线性表模拟环，为什么不用数组？因为数组增删不方便

4. 代码（Java）

import java.util.LinkedList; 
public class Solution {public int LastRemaining_Solution(int n, int m) {if(n ==0 ) {return -1;}//加入第一个线性表LinkedList<Integer> list = new LinkedList<Integer>();for (int i = 0; i < n; i ++) {list.add(i);}//模拟环的操作，bt是从0开始的，bt= 0为第一个学生int bt = 0;while (list.size() > 1) {bt = (bt + m - 1) % list.size();//由于下标是从0开始的，所以这里要减去1list.remove(bt);}//当剩下一个小朋友，返回他的编号return list.get(0);}
}

5. 复杂度

• 暂无

6. 知识积累

• 暂无

8. 剑指Offer: 链表中环的入口结点

1. 题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

原题传送门：link.

2. 关键词

link

3. 思路

用快慢指针，慢指针每次走一步，快指针每次走两步，快指针与慢指针第一次相遇的的位置慢指针走了t步，快指针走了2t步，如果不相遇则没有环。

t=x+a， 2t=x+a+kc (c为环的结点数，k=1,2,3…)

可得到 2x+2a=x+a+kc， x=kc-a， x=(k-1)c+ c-a

可以得到，当两个指针相遇时，把一个指针的指向链表开头，两指针都以每次一步的速度走，两指针再次相遇时就是环的入口结点。

**为什么用快慢指针可以判断是否有环：**https://blog.csdn.net/mucaoyx/article/details/81395782

1. 代码（Java）

/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
*/
public class Solution {public ListNode EntryNodeOfLoop(ListNode pHead){if(pHead==null||pHead.next==null||pHead.next.next==null) return null;ListNode slow = pHead.next;//设置快慢指针ListNode fast = pHead.next.next;while(slow!=fast){if(slow==null||fast.next==null) return null;slow = slow.next;fast = fast.next.next;}//先通过快慢指针判断是否有环，然后再去找到入口结点slow=pHead;while(fast!=slow){fast=fast.next;slow=slow.next;}return fast;}
}

5.复杂度

• 暂无

6. 知识积累

• 暂无

9. 剑指Offer: 删除链表中重复的结点

1. 题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

原题传送门：link.

2. 关键词

三指针法

3. 思路

4. 首先添加一个头节点，以方便碰到第一个，第二个节点就相同的情况

5. 设置 pre ，last 指针， pre指针指向当前确定不重复的那个节点，所以使用一个空节点，而last指针相当于工作指针，一直往后面搜索。

6. 代码（Java）

/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
*/
public class Solution {public static ListNode delete(ListNode listNode) {ListNode  newhead=new ListNode(0);newhead.next=listNode;ListNode pre=newhead;ListNode last=listNode.next;//遍历while (last!=null){//如果相等if(last.val==listNode.val){//一直循环到不相等那个值while(last.val==listNode.val){last=last.next;}//链接归位pre.next=last;listNode=last;last=last.next;pre=pre.next;}else{//全部后退listNode=listNode.next;last=last.next;pre=pre.next;}}return newhead.next;}}

5.复杂度

• 暂无

6. 知识积累

• 暂无

10. LeetCode：归并两个有序的链表 (递归)

题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

原题链接：link.

代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1==null) return l2;if(l2==null) return l1;if(l1.val>l2.val){l2.next=mergeTwoLists(l1,l2.next);，return l2;}else{l1.next=mergeTwoLists(l1.next,l2);return l1;}}
}

思路

1.先设置嵌套出口

当极端情况下：l1为空，返回l2；l2为空，返回l1。

 if(l1==null) return l2;if(l2==null) return l1;

2.再设置嵌套入口

若l1.val>l2.val，那么l2是所需要的结点，故,
l2.next=mergeTwoLists(l1,l2.next)。

if(l1.val>l2.val){l2.next=mergeTwoLists(l1,l2.next);//return l2;}else{l1.next=mergeTwoLists(l1.next,l2);//return l1;}

3.大问题化小问题

若l1.val>l2.val，那么l2是所需要的结点。故, return l2。
若l2.val>l1.val，那么l1是所需要的结点，故, return l1。

if(l1.val>l2.val){l2.next=mergeTwoLists(l1,l2.next);return l2;}else{l1.next=mergeTwoLists(l1.next,l2);return l1;}

11. LeetCode：两两交换链表中的节点

给定 1->2->3->4, 你应该返回 2->1->4->3.

package 数据结构与算法.链表;import java.util.List;//# 链表的两两翻转 # 给定链表:  1->2->3->4->5->6->7 # 返回结果：  2->1->4->3->6->5->7
public class 链表两两反转 {public static void main(String[] args) {ListNode headNode =new ListNode(1);ListNode node=new ListNode(2);ListNode node1=new ListNode(3);ListNode node2=new ListNode(4);ListNode node3=new ListNode(5);ListNode node4=new ListNode(6);ListNode node5=new ListNode(7);headNode.next=node;node.next=node1;node1.next=node2;node2.next=node3;node3.next=node4;node4.next=node5;ListNode next=headNode;System.out.print("正序打印结果:");while(next!=null){System.out.print(next.val+" ");next=next.next;}ListNode next1=swapPairs1(headNode);System.out.print("两两反转结果:");while(next1!=null){System.out.print(next1.val+" ");next1=next1.next;}}public static ListNode swapPairs(ListNode head) {// 1. 终止条件：当前没有节点或者只有一个节点，肯定就不需要交换了if (head == null || head.next == null) return head;// 2. 调用单元// 需要交换的两个节点是 head 和 head.nextListNode firstNode = head;ListNode secondNode = head.next;// firstNode 连接后面交换完成的子链表firstNode.next = swapPairs(secondNode.next);// secondNode 连接 firstNodesecondNode.next = firstNode;// 3. 返回值：返回交换完成的子链表// secondNode 变成了头结点return secondNode;}//三指针法，并且用一个新建一个空结点指向头结点。public static ListNode swapPairs1(ListNode head) {ListNode pre = new ListNode(0);pre.next = head;ListNode temp = pre;while(temp.next != null && temp.next.next != null) {ListNode start = temp.next;ListNode end = temp.next.next;temp.next = end;start.next = end.next;end.next = start;temp = start;}return pre.next;}
}

3. 栈和队列

1. 剑指Offer：用两个栈实现队列

1. 题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
原题传送门：link.

2. 关键词

栈，队列

3. 思路

• 暂无

4. 代码实现（Java）

import java.util.Stack;public class Solution {Stack<Integer> stack1 = new Stack<Integer>();Stack<Integer> stack2 = new Stack<Integer>();//入队时，将stack2的值压入stack1 后，压stack1栈public void push(int node) {stack1.push(node);}    //出队时，将stack1的值压入stack2 后，出stack2栈public int pop() {if(stack2.isEmpty()){while(!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.pop();}
}

5. 知识积累

暂无

2. 剑指Offer: 包含min函数的栈

1. 题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法

原题传送门：link.

2. 关键词

栈

3. 思路

• 看到这个问题, 我们最开始可能会想, 添加一个成员变量用于保存最小元素, 每次压栈时如果压栈元素比当前最小元素更小, 就更新最小元素.

  但是这样会有一个问题, 如果最小元素被弹出了呢, 如何获得下一个最小元素呢? 分析到这里可以发现, 仅仅添加一个成员变量存放最小元素是不够的, 我们需要在最小元素弹出后还能得到次小元素, 次小的弹出后, 还要能得到次次小的.

  因此, 用另一个栈来保存这些元素是再合适不过的了. 我们叫它最小元素栈.

  每次压栈操作时, 如果压栈元素比当前最小元素更小, 就把这个元素压入最小元素栈, 原本的最小元素就成了次小元素. 同理, 弹栈时, 如果弹出的元素和最小元素栈的栈顶元素相等, 就把最小元素的栈顶弹出.

4. 代码实现（Java）

import java.util.Stack;public class Solution {Stack<Integer> s1=new Stack<Integer>();Stack<Integer> s2=new Stack<Integer>();public void push(int node) {s1.push(node);//如果s2为空或者，node小于等于s2.peek()if(s2.isEmpty()||s2.peek()>=node)//入s2栈s2.add(node);else{//否则 s2从自己栈顶复制一个值入本栈s2.add(s2.peek());}}//这里也可以通过判断栈顶元素是否相同public void pop() {s1.pop();s2.pop();}public int top() {return s1.peek();}public int min() {return s2.peek();  }
}

5. 知识积累

暂无

3. 剑指Offer：栈的压入、弹出序列

1. 题目描述

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

原题传送门：link.

2. 关键词

栈

3. 思路

• 用一个栈来模拟压入弹出操作
• 假设序列1【1,2,3,4,5】是某栈的压入顺序，序列2【4,5,3,2,1】为某栈的弹出序列，具体操作：
  1. 序列1持续入栈：1,2,3,4
  2. 当序列1中的数值’4’等于序列2中的数值’4’，'4’出栈
  3. 重复步骤1.和步骤2.
  4. 当栈空时，则题目为真。

4. 代码实现（Java）

import java.util.ArrayList;
import java.util.Stack;
public class Solution {public boolean IsPopOrder(int [] pushA,int [] popA) {int n=pushA.length;Stack<Integer> stack=new Stack<Integer>();for (int pushIndex=0,popIndex=0;pushIndex<n; pushIndex++){stack.push(pushA[pushIndex]);while(!stack.isEmpty()&&popIndex<n&&stack.peek()==popA[popIndex]){stack.pop();popIndex++;}}return stack.isEmpty();}
}

5. 知识积累

暂无

4. 字符串

1. 剑指Offer：替换空格

1. 题目描述

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

原题传送门：link.

2. 关键词

字符串

3. 思路

问题1：替换字符串，是在原来的字符串上做替换，还是新开辟一个字符串做替换
问题2：在当前字符串替换，怎么替换才更有效率（不考虑java里现有的replace方法）。
从前往后替换，后面的字符要不断往后移动，要多次移动，所以效率低下
从后往前，先计算需要多少空间，然后从后往前移动，则每个字符只为移动一次，这样效率更高一点

分析：由于函数返回为void，说明此题不能另外开辟数组，需要in-place操作。我们知道字符串的遍历无非是从左到右和从右到左两种。
1）如果从左到右，会发现如果遇到空格，会将原来的字符覆盖。于是，此方法不行。
2）那么就考虑从右向左，遇到空格，就填充“20%“，否则将原字符移动应该呆的位置。

4. 代码实现（Java）

public class Solution {public String replaceSpace(StringBuffer str) {if(str==null){renturn null;}StringBuilder newStr=new StringBuilder();for(int i=0,i<str.length(),i++){if(Str.charAt(i)==''){newStr.append(%);newStr.append(2);newStr.append(0);}else{newStr.append(Str.charAt(i));}}return newStr.toString();}
}

5. 知识积累

• 考察String基本操作方法
  1、 获取字符串长度方法length()
  int length = str.length();
  2、获取字符串中的第i个字符方法charAt(i)
  char ch = str.charAt(i);

  3、向字符串中添加字符
  newStr.append(0);

  4、获取指定位置的字符方法

  getChars(indexBegin,indexEnd,array,arrayBegin)

  1. indexBegin：需要复制的字符串的开始索引

  2. indexEnd: 需要复制的字符串的结束索引，indexEnd-1

  3. array: 前面定义的char型数组的数组名

  4. arrayBegin:数组array开始存储的位置索引号

• String，StringBuffer，StringBuilder区别：
  1、String类是不可变类，即一旦一个String对象被创建以后，包含在这个对象中的字符序列是不可改变的，直至这个对象被销毁。
  2、StringBuffer对象则代表一个字符序列可变的字符串，当一个StringBuffer被创建以后，通过StringBuffer提供的append()、insert()、reverse()、setCharAt()、setLength()等方法可以改变这个字符串对象的字符序列。一旦通过StringBuffer生成了最终想要的字符串，就可以调用它的toString()方法将其转换为一个String对象。
  3、StringBuilder类也代表可变字符串对象。实际上，StringBuilder和StringBuffer基本相似，两个类的构造器和方法也基本相同。不同的是：StringBuffer是线程安全的，而StringBuilder则没有实现线程安全功能，所以性能略高。
  注：StringBuilder类也代表可变字符串对象。实际上，StringBuilder和StringBuffer基本相似，两个类的构造器和方法也基本相同。不同的是：StringBuffer是线程安全的，而StringBuilder则没有实现线程安全功能，所以性能略高。

原文传送门：link.

2. 剑指Offer: 字符串的排列

1. 题目描述

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

输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

原题传送门：link.

2. 关键词

打印字符串

3. 思路

• 所在网站//https://blog.csdn.net/qq_33575542/article/details/80825221

4. 代码（Java）

/*** 1、递归算法** 解析：http://www.cnblogs.com/cxjchen/p/3932949.html  (感谢该文作者！)** 对于无重复值的情况** 固定第一个字符，递归取得首位后面的各种字符串组合；* 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合； *递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。** 假如有重复值呢？* *由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。* 例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。* 但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。* 由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。** 换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，* 所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！*** @param str* @return*/
package 字符串;import java.nio.charset.Charset;
import java.util.*;/*** 输入一个字符串,按字典序打印出该字符串中字符的所有排列。* 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。* */
public class 字符串的排列 {public static void main(String[] args) {String str="abb";HashSet<String> charset=new HashSet<>();if(str!=null&&str.length()>0){helper(str.toCharArray(),charset,0);}Iterator<String> iterator = charset.iterator();//遍历器while(iterator.hasNext())System.out.print(iterator.next()+" ");//判断是否有，有就输出}private static void helper (char []chars,HashSet<String> charset, int i){//递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。// for循环和swap的含义：对于“ABC”，// 第一次'A' 与 'A'交换，字符串为"ABC", pos为0， 相当于固定'A'// 第二次'A' 与 'B'交换，字符串为"BAC", pos为0， 相当于固定'B'// 第三次'A' 与 'C'交换，字符串为"CBA", pos为0， 相当于固定'C'if(i==chars.length-1){charset.add(String.valueOf(chars));}else{for(int j=i;j<chars.length;j++){swap(chars,i,j);helper(chars,charset,i+1);swap(chars,j,i);}}}private static void  swap(char[] cs,int i,int j){char temp=cs[i];cs[i]=cs[j];cs[j]=temp;}
}

5. 知识积累

链接：https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7?answerType=1&f=discussion

链接：https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7?answerType=1&f=discussion
来源：牛客网//String的用法：
//java中String是只读的，没有办法进行变换，因此需要使用StringBuilder。
String.length() //获取字符串的长度
String.charAt(i) //获取第i个字符的内容
String.subString(start)   //获取[start,）的字符串
String.subString(start,end) //获取[start,end）中的字符串
char[] c = iniString.toCharArray() //将字符串转为char数组来进行改变字符内容
String.equal() //判断两个字符串是否相等//StringBuilder的用法：
除了String中支持的方法外，StringBuilder支持字符的增、删、改。
stringBuilder.append("we");  //添加we在词尾
stringBuilder.insert(0,"we");//在0的位置加入后面的内容
stringBuilder.delete(0,1);  //删除[0,1)的数据
stringBuilder.deleteCharAt(0);
stringBuilder.setCharAt(0,'p'); //在某一个独特位置设置字符
char c = stringBuilder.charAt(i);//查询某个位置上的字符
System.out.println(stringBuilder);
new String(stringBuilder);//用stringBuilder来初始化String

3. 剑指Offer：整数中1出现的次数

1. 题目描述

求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

原题传送门：link.

2. 关键词

字符串

3. 思路

• 链接：https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6?answerType=1&f=discussion

  。统计某个位置上 1出现的次数。如34，1在十位上出现的次数是10次
  （10到19），1在个位上出现的次数是4次（1，11，21，31），因此34中1出现了14次。

  对于整数n，将这个整数分为三部分：当前位数字cur，更高位数字high，更低位数字low，如：对于n=21034，当位数是十位时，cur=3，high=210，low=4。
  我们从个位到最高位 依次计算每个位置出现1的次数：
  在计算时，会出现三种情况
  1）当前位的数字等于0时，例如n=21034，在百位上的数字cur=0，百位上是1的情况有：00100-00199，01100-01199，……，20100-20199。一共有21100种情况，即high100;
  2）当前位的数字等于1时，例如n=21034，在千位上的数字cur=1，千位上是1的情况有：01000-01999，11000-11999，21000-21034。一共有21000+（34+1）种情况，即high1000+(low+1)。
  3）当前位的数字大于1时，例如n=21034，在十位上的数字cur=3，十位上是1的情况有：00010-00019，……，21010-21019。一共有(210+1)*10种情况，即(high+1)*10。

4. 代码（Java）

public class Solution {public int NumberOf1Between1AndN_Solution(int n) {int count=0;for(int i=1;i<=n;i*=10){  //i代表位数int high=n/(i*10); //更高位数字int low=(n%i);  //更低位数字int cur=(n/i)%10;  //当前位数字if(cur==0){count+=high*i;}else if(cur==1){count+=high*i+(low+1);}else{count+=(high+1)*i;}}return count;}
}

5.复杂度

• 暂无

6. 知识积累

• 暂无

4. 剑指Offer：把数组排成最小的数

1. 题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323
原题传送门：link.

2. 关键词

字符串

3. 思路

• 自定义一个比较大小的函数，比较两个字符串s1, s2大小的时候，
• 先将它们拼接起来，比较s1+s2,和s2+s1那个小,
• 由于求能排成的最小数字，所以如果s1+s2小，那说明s2应该放前面
• compareTo()是用来比较大小的，a.compareTo(b)，a>b 的情况返回1，a<b 的情况返回-1， a=b的情况返回0

4. 代码（Java）

public String PrintMinNumber(int [] numbers) {if(numbers == null || numbers.length == 0) return "";int len = numbers.length;String[] str = new String[len];StringBuilder sb = new StringBuilder();for(int i = 0; i < len; i++){
// String.valueOf(numbers[i]) numbers[i] 转换成字符串 str[i] = String.valueOf(numbers[i]);}//实现了Arrays接口的sort方法，将集合元素按照compare方法的规则进行排序Arrays.sort(str,new Comparator<String>(){@Overridepublic int compare(String s1, String s2) {String c1 = s1 + s2;String c2 = s2 + s1;return c1.compareTo(c2);}});for(int i = 0; i < len; i++){sb.append(str[i]);}return sb.toString();}

5. 复杂度

• 暂无

6. 知识积累

• 暂无

5. 剑指Offer: 第一个只出现一次的字符

1. 题目描述

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

2. 关键词

哈希数组

3. 思路

• 建立一个key为字符，val为次数（整数类型）的哈希map；
• 遍历字符串，将字符和次数插入到哈希map中；
• 规则为：定义time就是字符出现的次数，每出现一次加1；
• 再次从头到尾遍历字符串，配合hash表找出符合条件的字符。

4. 代码（Java）

import java.util.HashMap;
public class Solution
{public int FirstNotRepeatingChar(String str){//新建hashmapHashMap<Character,Integer> map=new HashMap<Character,Integer>();//遍历字符串for(int i=0;i<str.length();i++){char c=str.charAt(i);//如果存在相同的key，覆盖if(map.containsKey(c)){int time=map.get(c);time++;map.put(c,time);}//如果不存在相同的key,插入else{map.put(c,1);}}//再次从头遍历字符串，输出第一个为1的字符for(int i=0;i<str.length();i++){char c=str.charAt(i);if(map.get(c)==1)return i;}return -1;}
}

package 字符串;
/*** 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置,* 如果没有则返回 -1（需要区分大小写）.** 遍历一次字符串，使用一个数组来保存他们的状态** */
public class 第一个只出现一次的字符 {public static void main(String[] args) {String str ="ssadcasdassdad";System.out.println(helper(str));}private  static char helper(String str){int [] count =new int ['z'-'A'];for(int i=0;i<str.length();i++){count[str.charAt(i)-'A']++;}for(int i=0;i<str.length();i++){if(count[str.charAt(i)-'A']==1){return str.charAt(i);}}return 0;}
}

5. 复杂度

• 时间复杂度为O(n)
• 空间复杂度为O(n)

6. 知识积累

• 暂无

6. 剑指Offer: 翻转单词顺序列

1. 题目描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

原题传送门：link.

2. 关键词

翻转字符串

3. 思路

• 先翻转整个句子，然后，依次翻转每个单词。
• 依据空格来确定单词的起始和终止位置

4. 代码（Java）

public class Solution {public String ReverseSentence(String str) {//将字符串转化为字符串数组char[] chars = str.toCharArray();//翻转整个字符串，需要自己写reverse(chars,0,chars.length - 1);int blank = -1;//依据空格来确定单词的起始和终止位置，依次翻转每个单词。for(int i = 0;i < chars.length;i++){if(chars[i] == ' '){ int nextBlank = i;reverse(chars,blank + 1,nextBlank - 1);blank = nextBlank;}}//最后一个单词单独进行反转reverse(chars,blank + 1,chars.length - 1);return new String(chars);}//翻转字符串算法：使用两个指针指向表头和表尾，交换到指针相交时结束。public void reverse(char[] chars,int low,int high){while(low < high){char temp = chars[low];chars[low] = chars[high];chars[high] = temp;low++;high--;}}
}

5. 复杂度

• 暂无

6. 知识积累

• 暂无

7. 剑指Offer: 把字符串转换成整数

1. 题目描述

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

原题传送门：link.

2. 关键词

字符串

3. 思路

暂无

4. 代码（Java）

public class Solution
{public int StrToInt(String str){if (str.equals("") || str.length() == 0)return 0;char[] a = str.toCharArray();int fuhao = 0;if (a[0] == '-')fuhao = 1;int sum = 0;for (int i = fuhao; i < a.length; i++){if (a[i] == '+')continue;if (a[i] < 48 || a[i] > 57)return 0;sum = sum * 10 + a[i] - 48;}return fuhao == 0 ? sum : sum * -1;}}

5. 复杂度

• 暂无

6. 知识积累

• 暂无

8. 剑指Offer: 正则表达式匹配

1. 题目描述

请实现一个函数用来匹配包括’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配

原题传送门：link.

2. 关键词

字符串

3. 思路

• 暂无

4. 代码（Java）

public class Solution {
public boolean match(char[] str, char[] pattern){return matchTwo(str,0,str.length,pattern,0,pattern.length);}
private boolean matchTwo(char[] str, int i, int length1, char[] pattern,int j, int length2) {if(i==length1&&j==length2) {return true;}if(i==length1&&j!=length2) {while(j!=length2){if(pattern[j]!='*'&&(j+1>=length2||pattern[j+1]!='*')){return false;}j++;}return true;}if(i!=length1&&j==length2) {return false;}if(j+1==length2){if(str[i]==pattern[j]||pattern[j]=='.')return matchTwo(str, i+1, length1, pattern, j+1, length2);else {return false;}}if((str[i]==pattern[j]||pattern[j]=='.')&&pattern[j+1]!='*')return matchTwo(str, i+1, length1, pattern, j+1, length2);if((str[i]==pattern[j]||pattern[j]=='.')&&pattern[j+1]=='*')return matchTwo(str, i, length1, pattern, j+2, length2)||matchTwo(str, i+1, length1, pattern, j, length2);if(pattern[j+1]=='*')return matchTwo(str, i, length1, pattern, j+2, length2);return false;}
}

5. 复杂度

• 暂无

6. 知识积累

• 暂无

9. 剑指Offer: 表示数值的字符串

1. 题目描述

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。

原题传送门：link.

2. 关键词

字符串

3. 思路

• 暂无

4. 代码（Java）

//正则表达式解法
public class Solution {public boolean isNumeric(char[] str) {String string = String.valueOf(str);return string.matches("[\\+\\-]?\\d*(\\.\\d+)?([eE][\\+\\-]?\\d+)?");}
}
/*
以下对正则进行解释:
[\\+\\-]?            -> 正或负符号出现与否
\\d*                 -> 整数部分是否出现，如-.34 或 +3.34均符合
(\\.\\d+)?           -> 如果出现小数点，那么小数点后面必须有数字；否则一起不出现
([eE][\\+\\-]?\\d+)? -> 如果存在指数部分，那么e或E肯定出现，+或-可以不出现，紧接着必须跟着整数；或者整个部分都不出现
*///参见剑指offer
public class Solution {private int index = 0;public boolean isNumeric(char[] str) {if (str.length < 1)return false;boolean flag = scanInteger(str);if (index < str.length && str[index] == '.') {index++;flag = scanUnsignedInteger(str) || flag;}if (index < str.length && (str[index] == 'E' || str[index] == 'e')) {index++;flag = flag && scanInteger(str);}return flag && index == str.length;}private boolean scanInteger(char[] str) {if (index < str.length && (str[index] == '+' || str[index] == '-') )index++;return scanUnsignedInteger(str);}private boolean scanUnsignedInteger(char[] str) {int start = index;while (index < str.length && str[index] >= '0' && str[index] <= '9')index++;return start < index; //是否存在整数}
}

5. 复杂度

• 暂无

6. 知识积累

• 暂无

10. 剑指Offer: 字符流中第一个不重复的字符（重要）

1. 题目描述

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

原题传送门：link.

2. 关键词

字符串

3. 思路

• 要遍历整个字符流才能知道一个字符是否只出现了一次。

1. 用一个256大小的数组统计每个字符出现的次数
2. 再次遍历字符串，找出第一个出现一次的字符。
3. 代码（Java）

package 剑指offer;import java.util.Scanner;public class 找第一个不重复字符 {public static void main(String[] args) {//“google"中找“l”Scanner sc=new Scanner(System.in);String s=sc.next();int arr[]=new int[256];for(int i=0;i<s.length();i++){arr[s.charAt(i)-'a']++;}for(int i=0;i<s.length();i++){if(arr[s.charAt(i)-'a']==1) {System.out.println(s.charAt(i));break;}}}
}

5. 复杂度

• 暂无

6. 知识积累

• 暂无

11. 数据结构与算法：KMP算法

前言

【例】：主串ｓ：AAAABABABBBBB
　　　模式串ｔ ：ABABABB
　　　
本文主要针对KMP算法的代码方式进行解析，首先我们要知道KMP算法的作用，是用来进行字符串匹配的，即在s串中找出与t串完全匹配的字符串，并且返回起始位置。

1. 首先介绍字符串匹配的暴力匹配算法；
2. 然后介绍有next数组的KMP匹配算法；
3. 最后介绍next数组的求解算法；

这是因为以上三种算法在形式上有一定的相似之处，且思想是是由简单到困难的。

1. 暴力匹配算法

2. 使用两个指针，一个指针i指向主串，一个指针j指向模式串。

3. 从主串和模式串的第一位（下标为0）开始，同时移动指针i，j，并且对比字符串是否匹配，如果匹配，则同时移动，直到某一个指针越界(i<s.length() && j<t.length())。

4. 如果不匹配，则i和j同时回退到原来的位置并前移一个位置后开始匹配。原来位置用k记录。

5. 最后判断，j是否等于t.length()。若等于则存在返回i-j(或者k)，否则匹配失败。

    public static int index(String s, String t) {int i=0,j=0,k=0;while(i<s.length() && j<t.length()){if(s.charAt(i)==t.charAt(j)){i++;j++;}else{i=++k;j=0;}}if (j==t.length()){return i-j;}else{return 0;}}

2. KMP匹配算法

3. 同样，使用两个指针，一个指针i指向主串，一个指针j指向模式串。

4. 如果匹配成功则与暴力匹配算法相似：. 从主串和模式串的第一位（下标为0）开始，同时移动指针i，j，并且对比字符串是否匹配，如果匹配，则同时移动，直到某一个指针越界(i<s.length() && j<t.length())。

5. 若匹配失败，需要根据next数组重置j的下标，再进行匹配。若失败，则循环此步骤。

KMP算法与next数组：
KMP算法主串上的指针i不需要移动，若匹配失败则只需要移动模式串上的指针j与主串上i的字符进行比较就可以。next数组中存储的该位置字符串是匹配失败后，j需要移动到的位置。且next数组保证了j位置前的子串与模式串匹配！

4. 特殊情况，若移动到模式串的第一位仍然和主串不匹配。则i和j同时回退到原来的位置并前移一个位置后开始匹配。此时next数组中next[j]=0; 故，此时，i++；j++; 即可（因为）。
5. 最后判断，j是否等于t.length()。若等于则存在返回i-j，否则匹配失败。

我们可以先写出暴力的解法，然后再改为KMP算法！

    public static int kmpMatch(String s, String t){int[] next = getNextArray(t);int i = 0, j = 0;while (i<s.length() && j<t.length()){if(j == 0 || s.charAt(i)==t.charAt(j)){   //此处与暴力解法不同i++;j++;}elsej = next[j];  //此处与暴力解法不同}if(j == t.length())return i-j;elsereturn 0;}

3. next数组求解算法

4. next数组求解算法只针对模式串，其代码相似度与KMP算法很像，因为其内部也使用了KMP算法的思想！

5. 若t.charAt(i)==t.charAt(j)，则next[i+1]=j+1;

6. 若t.charAt(i)！=t.charAt(j)，则使用KMP算法，直到匹配，则使用步骤2;

7. 特殊情况，若移动到模式串的第一位仍然和主串不匹配，此时j==0。则 next[i+1]=1; 所以写在一起就可以；

8. 最后返回的是next数组。

    public static int[] getNextArray(String  t) {int[] next = new int[t.length()+1];int i=1,j=0; //这里的j存储的是next数组内的值，即t中的下标next[1]=0;while(i<t.length()){if(j==0||t.charAt(i)==t.charAt(j)){next[i+1]=j+1;  //此处与KMP算法不同i++;j++;}else{j=next[j];}}return next; //此处与KMP算法不同} 
   

12. 数据结构与算法：Rabin-Karp算法

1. 题目描述

查找目标字符串K中是否有与字符串L匹配的子串（指纹字符串查找算法)。

2. 关键词

哈希

3. 思路

4. 当子串L的长度为m，目标字符串K的长度为n

5. 计算子串L的hash值

6. 使用滑动窗口，计算目标字符串K中每个长度为m的子串的hash值（共需要计算n-m+1次）

7. 依次比较hash值并且对997取余（在不溢出的情况下选择一个尽可能大的值）。

在计算机中，当要表示的数据超出计算机所使用的数据的表示范围时，则产生数据的溢出

5. 如果hash值不同，字符串必然不匹配，如果hash值相同，还需要使用朴素算法再次判断。
6. 时间及空间复杂度

时间复杂度：O(M+N)

空间复杂度：O(1)

5. 代码（Java）

public class RabinKarp {private String pat;    private long patHash;   private int m;       private long q;       private int R;         private long RM;      //字符串hash值计算方法private long hash(String key, int m) {    long h = 0; for (int j = 0; j < m; j++) h = (R * h + key.charAt(j)) % q;return h;
}public RabinKarp(String pat) {this.pat = pat;R = 256;m = pat.length();q = longRandomPrime();RM = 1;for (int i = 1; i <= m-1; i++)RM = (R * RM) % q;patHash = hash(pat, m);} private long hash(String key, int m) { long h = 0; for (int j = 0; j < m; j++) h = (R * h + key.charAt(j)) % q;return h;}private boolean check(String txt, int i) {for (int j = 0; j < m; j++) if (pat.charAt(j) != txt.charAt(i + j)) return false; return true;}public int search(String txt) {int n = txt.length(); if (n < m) return n;long txtHash = hash(txt, m); if ((patHash == txtHash) && check(txt, 0))return 0;for (int i = m; i < n; i++) {txtHash = (txtHash + q - RM*txt.charAt(i-m) % q) % q; txtHash = (txtHash*R + txt.charAt(i)) % q; int offset = i - m + 1;if ((patHash == txtHash) && check(txt, offset))return offset;}return n;}   private static long longRandomPrime() {BigInteger prime = BigInteger.probablePrime(31, new Random());return prime.longValue();}
}

13. LeetCode：最长公共子序列

1. 题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。
示例 1:

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace”，它的长度为 3。

示例 2:

输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc”，它的长度为 3。

示例 3:

输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0。

提示:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• 输入的字符串只含有小写英文字符。

来源：力扣（LeetCode）
原题传送门：link.

2. 关键词

二维数组，动态规划

3. 思路

   

   1. 首先创建一个二维数组，其长度行宽为s1.length() + 1，列宽为s2.length() + 1；

   2. 使用两个for循环遍历数组

   3. 分两种情况向内添加值，如果末端字符串相同，则此处值为对角线上的数字加1；如果末端字符串不同，则此处值等于上方与左方数字的最大值：
      

解析传送门：link.

4. 代码（Java）

class Solution {public int longestCommonSubsequence(String text1, String text2) {char[] s1 = text1.toCharArray();char[] s2 = text2.toCharArray();int[][] dp = new int[s1.length + 1][s2.length + 1];for(int i = 1 ; i < s1.length + 1 ; i ++){for(int j = 1 ; j < s2.length + 1 ; j ++){//如果末端相同if(s1[i - 1] == s2[j - 1]){dp[i][j] = dp[i-1][j-1] + 1;}else{//如果末端不同dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}return dp[s1.length][s2.length];}
}

6. 知识积累

• 暂无

14. LeetCode：字符串的排列及题目改进

1. 题目描述

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).

示例2:

输入: s1= “ab” s2 = “eidboaoo”
输出: False

注意：

输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间

来源：力扣（LeetCode）
原题传送门：link.

2. 考察知识点

hash表，滑动窗口

3. 思路

• 由于长度固定，所以可以使用滑动窗口，由于时排列不同，如何判断呢？
• 如果说S1是S的排列之一，就等价于它们每个字母出现的频率是相同的。所以可以建一个数组，数组索引对应字符，数组内的值记录字符出现的频率。
• 当s2的滑动窗口内的字符串与s1的字符串字符出现频率相同时，说明匹配（可以用一个循环来对比）。
• 如果不相同，那么滑动下去（字符的增加删除对应了数组内的频率增减）。

链接：link.
来源：力扣（LeetCode）

4. 代码（Java）

public class Solution {public boolean checkInclusion(String s1, String s2) {//if (s1.length() > s2.length())return false;
//滑动字符串对应的数组初始化int[] s1map = new int[26];int[] s2map = new int[26];for (int i = 0; i < s1.length(); i++) {s1map[s1.charAt(i) - 'a']++;s2map[s2.charAt(i) - 'a']++;}
//滑动s2字符串上的窗口尝试找到同频率字符串for (int i = 0,j= s1.length(); j < s2.length(); i++,j++) {if (matches(s1map, s2map))return true;s2map[s2.charAt(j) - 'a']++;s2map[s2.charAt(i) - 'a']--;}return matches(s1map, s2map);}
//对比字符频率是否相同public boolean matches(int[] s1map, int[] s2map) {for (int i = 0; i < 26; i++) {if (s1map[i] != s2map[i])return false;}return true;}
}

package 字符串;import 美团笔试.Main;/*** 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含s1的排列。* 换句话说，第一个字符串的排列之一是第二个字符串的子串。* */
public class 字符串的排列及题目改进 {public static void main(String[] args) {String str1="cba";String str2="abcdefg";System.out.println(checkInclusion(str1,str2));}public static  boolean checkInclusion (String s1,String s2){if(s1.length()>s2.length()){return false;}char[] chars1 =new char[26];char[] chars2=new char[26];for(int i=0;i<s1.length();i++){chars1[s1.charAt(i)-'a']++;chars2[s2.charAt(i)-'a']++;}for (int i=0;i<s2.length()-s1.length();i++){if(swap(chars1,chars2)){return true;}else{chars2[s2.charAt(i)-'a']--;chars2[s2.charAt(i+s1.length())-'a']++;}}return  false;}public static  boolean swap(char[] chars1,char[] chars2){for(int i=0;i<26;i++){if(chars1[i]!=chars2[i]){return false;}}return true;}
}

1. 时间及空间复杂度

6. 改进思路

• 上一种方法可以优化，如果不是比较每个更新的 s2map的哈希表的所有元素，而是对应于 s2 考虑的每个窗口，我们会跟踪先前哈希表中已经匹配的元素数量当我们向右移动窗口时，只更新匹配元素的数量。

• 为此，我们维护一个 count 变量，该变量存储字符频率对应的个数。当两个字符串字母频率完全不同时count =0；当两个字符串字母频率完全相同时count =26；s1内字符频率是相同的。当我们在s2内滑动窗口时，如果增加最后一个字符ch_r（ 对应数组的改变为：s2map[r]++）会导致两种情况：

1. 原来两字符串字符ch_r频率不相同，但是增加后频率相同(s2map[r] == s1map[r])，此时count++；
2. 原来两字符串字符ch_end频率相同，但是因为增加后频率不相同 (s2map[r] == s1map[r] + 1)，此时count–；

注意这里一定是因为增加引起的频率由相同到不相同的转变，才count–

如果扣除第一个字符ch_i（ 对应数组的改变为：s2map[i]–）会导致以下情况：

1. 原来两字符串字符ch_i频率不相同，但是扣除后频率相同(s2map[i] == s1map[i])，此时count++；
2. 原来两字符串字符ch_end频率相同，但是因为扣除后频率不相同 (s2map[i] == s1map[i] - 1)，此时count–；

注意这里一定是因为扣除引起的频率由相同到不相同的转变，才count–

• 如果在移动窗口后，count的计算结果为26，则表示所有字符的频率完全匹配。所以，我们立即返回一个True。

public class Solution {public boolean checkInclusion(String s1, String s2) {if (s1.length() > s2.length())return false;int[] s1map = new int[26];int[] s2map = new int[26];for (int i = 0; i < s1.length(); i++) {s1map[s1.charAt(i) - 'a']++;s2map[s2.charAt(i) - 'a']++;}int count = 0;for (int i = 0; i < 26; i++)if (s1map[i] == s2map[i])count++;for (int i = 0; i < s2.length() - s1.length(); i++) {int r = s2.charAt(i + s1.length()) - 'a', l = s2.charAt(i) - 'a';if (count == 26)return true;s2map[r]++;if (s2map[r] == s1map[r])count++;else if (s2map[r] == s1map[r] + 1)count--;s2map[l]--;if (s2map[l] == s1map[l])count++;else if (s2map[l] == s1map[l] - 1)count--;}return count == 26;}
}

7. 题目升级：s1不重复，如何快速查找？

• 思路1：查找s2中与s1长度相同且字符不重复的子串，然后将所以可能逐一对比，知道找到相同频率的字串。
• 思路2：滑动窗口的过程中判断字符串的子串是否重复，如果重复不对比直接向下滑动。

//1.滑动窗口不动，从前往后检测滑动窗口内第一个字符，使用mount=0计数，当mount=26时，退出，对滑动窗口内的字符串与s1进行比对。
//2.同时在数组内检索每个字符的频率，当频率为1时，mount++，窗口不动。
//3.当遇到频率大于1，滑动窗口的起点至此。mount=0
//对比字符频率是否相同
public class Solution {public boolean checkInclusion(String s1, String s2) {//if (s1.length() > s2.length())return false;
//滑动字符串对应的数组初始化int[] s1map = new int[26];int[] s2map = new int[26];for (int i = 0; i < s1.length(); i++) {s1map[s1.charAt(i) - 'a']++; s2map[s2.charAt(i) - 'a']++;}int x=0;int count=0;int i = 0,j= s1.length();
//滑动s2字符串上的窗口尝试找到同频率字符串while(count!=26&&j<s2.length()){count=0;x++;if(s1map[s1.charAt(i)- 'a']==s2map[s1.charAt(i)- 'a']){count++; }else{int y= x-i;while(y>0){y--; s2map[s2.charAt(j) - 'a']++;s2map[s2.charAt(i) - 'a']--; j++;i++;}}  }if(count==26) {return true; }else{return false; }      }
}         

15. LeetCode：无重复字符的最长子串

1. 题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

来源：力扣（LeetCode）
原题传送门：link.

2. 考察知识点

字符串操作，滑动窗口

3. 思路

这道题主要用到思路是：滑动窗口

什么是滑动窗口？
其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？
我们只要把队列的左边的元素移出就行了，直到满足题目要求！
一直维持这样的队列，找出队列出现最长的长度时候，求出解！

如何优化？
上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。也就是说，如果 s[j] 在 [i, j)范围内有与 j重复的字符，我们不需要逐渐增加 i。 我们可以直接跳过 [i，j ′] 范围内的所有元素，并将 i 变为 j’ + 1。
当我们知道该字符集比较小的时侯，我们可以用一个整数数组作为直接访问表来替换 Map
常用的表如下所示：
int [26] 用于字母 ‘a’ - ‘z’ 或 ‘A’ - ‘Z’
int [128] 用于ASCII码
int [256] 用于扩展ASCII码

作者：powcai
链接：link.
来源：力扣（LeetCode）

4. 代码（Java）

import java.util.HashMap;
import java.util.Map;/*** Created by xu on 2020/4/13.*/
public class 最长不重复子串 {public static void main (String[] args){int temp=lengthOfLongestSubstring("sdadabcdefgasdasda");System.out.print(temp);}public static int lengthOfLongestSubstring(String s) {int n = s.length(), ans = 0;//使用一个hash表Map<Character, Integer> map = new HashMap<>(); // current index of character// try to extend the range [i, j]for (int j = 0, i = 0; j < n; j++) {//如果有重复字符，找出重复字符的位置（必须在[i, j)内）//******[i*******j'****]j**********//***************j'[i***j]**********if (map.containsKey(s.charAt(j))) {i = Math.max(map.get(s.charAt(j))+1, i);}//实时记录最长长度ans = Math.max(ans, j - i + 1);//j入数组map.put(s.charAt(j), j);}return ans;}
}