二分查找
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
| /**
* 二分查找
*
* 数据源是有序的
* 1. 取数据源中间位置元素与目标值对比
* 2. 如果相等则返回结果，如果小于目标值则在数据源前半部分搜索，否则在后半部分搜索
* 3. 重复执行 步骤 1、2，直至找到结果或者再没有可搜索的区间
*/
public static int binSearch(int[] array, int start, int end, int value) {
if (null == array) {
throw new RuntimeException("array is null");
}
if (start < 0 || end >= array.length) {
throw new RuntimeException("index out of bounds");
}
if (start >= end) {
return -1;
}
int mid = (start + end) >> 1;
if (array[mid] > value) {
return binSearch(array, start, mid, value);
} else if (array[mid] < value) {
return binSearch(array, mid, end, value);
} else {
return mid;
}
}
|
空格替换为指定字符串
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
| /**
* 空格替换为指定字符串
* 1. 遍历字符串，获取空格个数
* 2. 根据空格数，计算新字符串长度，并初始化新长度字符数组
* 3. 从后往前将原字符串设置到新长度字符串数组，遇到空格设置指定字符串
* 4. 将字符数组转换为目标字符串
*/
public static String replaceBlackChar(String source, String replace) {
if (source == null) {
return null;
}
if (replace == null) {
return null;
}
int blank = 0;
for (int i = 0; i < source.length(); i++) {
if (source.charAt(i) == ' ') {
blank++;
}
}
char[] target = new char[source.length() + (replace.length() - 1) * blank];
int pos = target.length - 1;
for (int i = source.length() - 1; i >= 0; i--) {
if (source.charAt(i) == ' ') {
for (int j = replace.length() - 1; j >= 0; j--) {
target[pos--] = replace.charAt(j);
}
} else {
target[pos--] = source.charAt(i);
}
}
return new String(target);
}
|
字符串全排列
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
| /**
* 字符串全排列
* 1. 将源字符串转化为字符数组
* 2. 循环递归替换 depth 和 depth 以后的元素
* 3. 当 depth 等于 字符串长度时，打印字符数组
*/
public static void permutationStr(String source) {
permutationStr(source.toCharArray(), 0, source.length());
}
private static void permutationStr(char[] source, int depth, int length) {
if (depth == length) {
System.out.println(source);
return;
}
char tmp;
for (int i = depth; i < length; i++) {
tmp = source[i];
source[i] = source[depth];
source[depth] = tmp;
permutationStr(source, depth + 1, length);
tmp = source[i];
source[i] = source[depth];
source[depth] = tmp;
}
}
|
字符串第一个只出现一次的字符
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
| /**
* 第一个只出现一次的字符
* 1. 字符的范围时 0 ～ 255，定义长度为 256 的int数组，下标只是字符内容
* 2. 遍历一趟字符串，分别设置字符出现次数
* 3. 再次遍历字符串，查询字符出现次数，第一个出现次数为1的字符即为所找
*/
private static void firstNotRepeat(String source) {
if (source == null) {
return;
}
firstNotRepeat(source.toCharArray(), source.length());
}
private static void firstNotRepeat(char[] chars, int length) {
int[] table = new int[256];
Arrays.fill(table, 0);
for (int i = 0; i < length; i++) {
table[chars[i]]++;
}
for (int i = 0; i < length; i++) {
if (table[chars[i]] == 1) {
System.out.println(chars[i]);
return;
}
}
}
|
