突然萌生了一个想法 就是收集一些经典、优雅的算法
没事多翻翻看看 能够沉淀下来一些就好了
1、最大子序列的和
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public static int maxSubsequenceSum(int[] a ,int N){
int thisSum,MaxSum;
thisSum = MaxSum = 0 ;
for (int i = 0; i < N; i++) {
thisSum += a[i];
if(thisSum > MaxSum){
MaxSum = thisSum;
}else if(thisSum < 0){
thisSum = 0 ;
}
}
return MaxSum;
}
|
在数列不是全部为负数的前提下
算法很巧妙的用两个变量来储存 当前子列和 以及 最大子列和
并且及时地交换二者的值或者是 在当前子列和 小于0时 重置为 0
实现 一遍遍历就能得到最大子列和的目的 即 复杂度为O(n)
2、二分查找
1
2
3
4
5
6
7
8
9
10
11
12
|
public static int binarySearch(int key,int[] a){
int lo = 0 ;
int hi = a.length -1 ;
while( lo <= hi){
int mid = (lo + hi) / 2 ;
if ( key < a[mid]) hi = mid - 1 ;
else if( a[mid] < key) lo = mid + 1 ;
else return mid ;
}
return -1 ;
}
|
是一个很经典的算法 前提是数列有序 复杂度为 O(lg n)
3、进制转换
1
2
3
4
5
6
7
8
|
char digits[] = {'0','1','2','3','4','5','6','7','8','9','A',
'B','C','D','E','F'}; //全局变量
void convert(int x,int y){
if( x != 0) {
convert(x /y , y);
printf("%c",digits[x % y]);
}
}
|
一个精巧的进制转换代码，将十进制整数 x 转换为 y 进制 然后输出。
进制转换无非就是 除 然后 取余 ，但是有一个输出和处理过程是颠倒的问题。
精妙之处在于利用递归解决了输出需要逆置的问题，也可以用栈结构来解决。
待续…
