蓝桥杯 java
算法练习题
递归
一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法
递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
递归一般用法
案例
求n的阶乘
1
2
3
4
5
6
7
8
9
10
| public static int f1(int n){
if(n == 1){
return 1;
}
return n * f1(n - 1);
}
|
显示i到j的数
1
2
3
4
5
6
7
| public static void f2(int i,int j){
if(i > j){
return;
}
System.out.print(i + "\t");
f2(i + 1,j);
}
|
数组求和
1
2
3
4
5
6
7
8
9
10
11
12
13
| public static int f3(int[] arr,int i){
if(i == arr.length - 1){
return arr[i];
}
if(i > arr.length - 1){
return 0;
}
return arr[i] + f3(arr,i+1);
}
|
字符串反转
1
2
3
4
5
6
7
8
| public static String f4(String s,int end){
if(end == 0){
return s.charAt(end) + "";
}
return s.charAt(end) + f4(s,end - 1);
}
|
斐波那契数列
1、1、2、3、5、8、13、21、34、……
前两个相加等于第三个
1
2
3
4
5
6
7
8
| public static int f5(int n){
if(n == 1 || n == 2){
return 1;
}
return f5(n - 1) + f5(n - 2);
}
|
最大公约数
两个或多个整数共有约数中最大的一个
1
2
3
4
5
6
| public static int f6(int m,int n){
if(n == 0){
return m;
}
return f6(n,m % n);
}
|
小白上楼梯（递归设计）
楼梯有n阶台阶 小白一次可以上一阶 2阶 3阶 计算小白有多少种走完楼梯的方式
思路： 一个台阶1种方法 二个台阶2种方法 3个台阶4中该方法 4个台阶7种方法 依此类推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public static int f7(int n){
if(n == 0) {
return 1;
}
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
return f7(n - 1) + f7(n - 2) + f7(n - 3);
}
|
旋转数组的最小数字（改造二分法）
把一个数组最开始的若干个元素搬到数组的末尾 我们称之为数组的旋转 输入一个递增排序的数组的一个旋转 输出旋转数组的最小元素 例 数组{3,4,5,1,2} 为 {1,2,3,4,5}的一个旋转 该数组的最小值为1
思路：取中间值 检测左侧有序还是右侧有序 因为要旋转的部分一定在无序的那一部分当中 一直找，直到找到为止
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
| static int min(int[] arr){
int begin = 0;
int end = arr.length - 1;
if(arr[begin] < arr[end]){
return arr[begin];
}
while (begin + 1 < end){
int middle = (begin + end ) / 2;
if(arr[middle] >= arr[begin]){
begin = middle;
}else{
end = middle;
}
}
return arr[end];
}
public static void main(String[] args) {
int [] arr = {5,1,2,3,4};
int res = min(arr);
System.out.println(res);
int [] arr2 = {3,4,5,1,2};
int res2 = min(arr);
System.out.println(res2);
}
|
若中间的值和左边的值和右边的值相等比如1，0，1，1，1那么应该放弃这个算法，采用扫描法
在有空字符串的有序字符串数组中查找
有个排序后的字符串数组 其中散布着一些空字符串 找出给定字符串（肯定不是空字符串）的索引
思路： 找出中间量 依次进行比较 因为有序 所以只需多次使用二分法查找即可
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
|
static int index(String[] string,String s){
int begin = 0;
int end = string.length - 1;
while(begin < end){
int middle = begin + ((end - begin) >> 1);
if(string[middle].equals("")){
middle++;
}
if(middle > end){
return -1;
}
if(string[middle].compareTo(s) > 0){
end = middle - 1;
}else if (string[middle].compareTo(s) < 0){
begin = middle + 1;
}else{
return middle;
}
}
return -1;
}
public static void main(String[] args) {
String[] arr = {"a", "", "ac", "", "ad", "b", "", "ba"};
int res = index(arr, "abc");
System.out.println(res);
}
|
String.compareTo(参数) 返回值
如果指定的数与参数相等返回0。
如果指定的数小于参数返回 -1。
如果指定的数大于参数返回 1。
最长连续递增子序列（部分有序）
（1,9,2,5,6,3,4,6,8,0）中最长的递增子序列为（3,4,6,8）
思路： 记录一个起始下标，在记录一个从起始下标开始的下标 依次移动 直到移动的下标的下一个元素比它小 则终止当前的移动 记录下从起始下标到这个移动下标的长度 然后从移动的下标的下一下标开始作为起始下标 在重复此操作 最多即可得出最长序列
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
| public static void main(String[] args) {
int[] arr = new int[]{1,9,2,5,6,3,4,6,8,0};
System.out.println(max(arr));
}
public static int max(int[] arr){
int begin = 0;
int index = 0;
int max = 0;
while (begin < arr.length - 1){
if(arr[index] <= arr[index + 1]){
index++;
}else{
index++;
if(max < (index - begin)){
max = index - begin;
}
begin = index;
}
}
return max;
}
|
设计一个高效的求a的n次幂的算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public static int pow(int a,int n){
int result = 1;
for (int i = 0; i < n; i++){
result *= 2;
}
return result;
}
|
时间复杂度为 O(n)
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
|
public static int pow2(int a,int n){
int result = a;
int exec = 1;
if(n == 0){
return 1;
}
while ((exec<<1) < n){
result *= result;
exec <<= 1;
}
return result * pow2(a,n - exec);
}
|
时间复杂度为O（lg n）
你知道的越多 你不知道的越多 嘿 我是小博 带你一起看我目之所及的世界……