0%

判断单链表里面有没有环系列

1.判断单链表是否有环

使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步,指针fast每次走2步。如果存在环,则指针slow、fast会相遇;如果不存在环,指针fast遇到NULL退出。

2.求有环单链表的环长

在环上相遇后,记录第一次相遇点为Pos,之后指针slow继续每次走1步,fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈,也就是多走的距离等于环长。

阅读全文 »

判断单链表里面有没有环系列问题

1.判断单链表是否有环

使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步,指针fast每次走2步。如果存在环,则指针slow、fast会相遇;如果不存在环,指针fast遇到NULL退出。

2.求有环单链表的环长

在环上相遇后,记录第一次相遇点为Pos,之后指针slow继续每次走1步,fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈,也就是多走的距离等于环长。

阅读全文 »

刷剑指Offer遇见一题

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。(长度不超过9(可能有字符重复),字符只包括大小写字母。)

这种全排列问题是经典的回溯法问题

回溯法,把问题的解空间转化成了图或者树的结构表示,然后使用深度优先搜索策略进行遍历,遍历的过程中记录和寻找所有可行解或者最优解。经典问题有:字符串全排列,八皇后,正方体八个数等。

递归方法求全排列

对于无重复值的情况

  1. 固定第一个字符,递归取得首位后面的各种字符串组合;
  2. 再把第一个字符与后面每一个字符交换,并同样递归获得首位后面的字符串组合;递归的出口,就是只剩一个字符的时候,递归的循环过程,就是从每个子串的第二个字符开始依次与第一个字符交换,然后继续处理子串。

有重复值的情况

由于全排列就是从第一个数字起,每个数分别与它后面的数字交换,我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。

例如abb,第一个数与后面两个数交换得bab,bba。
然后abb中第二个数和第三个数相同,就不用交换了。但是对bab,第二个数和第三个数不 同,则需要交换,得到bba。
由于这里的bba和开始第一个数与第三个数交换的结果相同了,因此这个方法不行。
换种思维,对abb,第一个数a与第二个数b交换得到bab,然后考虑第一个数与第三个数交换,此时由于第三个数等于第二个数,所以第一个数就不再用与第三个数交换了。再考虑bab,它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕!

阅读全文 »

排序算法之基数排序

基数排序(radix sorting)将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。 然后 从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class RadixSort {
public static void radixSort(int[] arr) {
if(arr == null && arr.length == 0)
return ;
int maxBit = getMaxBit(arr);

for(int i=1; i<=maxBit; i++) {

List<List<Integer>> buf = distribute(arr, i); //分配
collecte(arr, buf); //收集
}

}

//分配
public static List<List<Integer>> distribute(int[] arr, int iBit) {
List<List<Integer>> buf = new ArrayList<List<Integer>>();
for(int j=0; j<10; j++) {
buf.add(new LinkedList<Integer>());
}
for(int i=0; i<arr.length; i++) {
buf.get(getNBit(arr[i], iBit)).add(arr[i]);
}
return buf;
}

//收集
public static void collecte(int[] arr, List<List<Integer>> buf) {
int k = 0;
for(List<Integer> bucket : buf) {
for(int ele : bucket) {
arr[k++] = ele;
}
}

}

//获取最大位数
public static int getMaxBit(int[] arr) {
int max = Integer.MIN_VALUE;
for(int ele : arr) {
int len = (ele+"").length();
if(len > max)
max = len;
}
return max;
}

//获取x的第n位,如果没有则为0.
public static int getNBit(int x, int n) {

String sx = x + "";
if(sx.length() < n)
return 0;
else
return sx.charAt(sx.length()-n) - '0';
}
}

堆与堆排序

堆排序与快速排序,归并排序一样都是时间复杂度为O(NlogN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。

二叉堆的定义

二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性:
1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆:

由于其它几种堆(二项式堆,斐波纳契堆等)用的较少,一般将二叉堆就简称为堆。

阅读全文 »

排序算法之桶排序

桶排序算是计数排序的一种改进和推广,要比计数排序复杂许多。

桶排序的基本思想:
假设有一组长度为N的待排关键字序列K[1….n]。首先将这个序列划分成M个的子区间(桶)。然后基于某种映射函数 ,将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ,那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]….B[M]中的全部内容即是一个有序序列。bindex=f(key) 其中,bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。桶排序之所以能够高效,其关键在于这个映射函数,它必须做到:
如果关键字k1 < k2,那么f(k1)<=f(k2)。也就是说B(i)中的最小数据都要大于B(i-1)中最大数据。很显然,映射函数的确定与数据本身的特点有很大的关系。

阅读全文 »

排序算法之计数排序

待排序的数要满足一定的范围的整数,比如 [0~100],[10000~19999] 这样的数据,而且计数排序需要比较多的辅助空间,仅适用于数据比较集中的情况。

基本思想是:对每一个输入的元素arr[i],确定小于 arr[i] 的元素个数。

需要三个数组:

  • 待排序数组 int[] arr = new int[]{4,3,6,3,5,1};
  • 辅助计数数组 int[] help = new int[max - min + 1]; //该数组大小为待排序数组中的最大值减最小值+1
  • 输出数组 int[] res = new int[arr.length];
阅读全文 »

排序算法之归并排序

归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序的时间复杂度也是O(nlogn),稳定排序方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class MergeSort {
public static void mergeSort(int [] array) {
divide(array, 0, array.length-1);
}

public static void divide(int [] array, int left, int right) {
if (left == right) {
return ;
}
int middle = (left + right) / 2;
divide(array, left, middle);
divide(array, middle+1, right);
merge(array, left, middle, right);
}

public static void merge(int [] array, int left, int middle, int right) {
//[left, middle][middle+1, right]
int[] tempArray = new int[right - left + 1];

int i = left;
int j = middle + 1;
int k = 0;

//把较小的数先移到tempArray
while (i <= middle && j <= right) {
if (array[i] < array[j]) {
tempArray[k++] = array[i++];
}else {
tempArray[k++] = array[j++];
}
}
//把左边或者右边剩余数组移入新数组
while(i < middle)
tempArray[k++] = array[i++];
while(j < right)
tempArray[k++] = array[j++];

//一次遍历,新数组覆盖原数组
for (int m = 0; m < tempArray.length; m++) {
array[m + left] = tempArray[m];
}
}
}

排序算法之希尔排序

希尔排序(缩小增量插入排序)
先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class ShellSort {
public static void shellSort(int[] array) {
if (array == null || array.length == 0)
return ;
//每次将步长缩短为原来的一半
for (int increment = array.length / 2; increment > 0; increment /= 2) {
for (int i = increment; i < array.length; i++) {
int temp = array[i];
for (int j = i; (j >= increment) && (temp < array[j - increment]); j -= increment) {
array[j] = array[j-increment];
}
array[j] = temp;
}
}
}
}