越来越喜欢算法了，离上次看算法书已经过去一个多月了，惊叹于它的简单的魅力，就好像优雅的诗。
在网上下载了一本pdf版的《数据结构和算法分析》，开始了探索之旅，很开心，遇到非常有趣的东西。
兴趣是最好的老师。
首先关于递归的算法，平常我经常使用，但是没有考虑过是否滥用或者错用的情况，作者提出了使用递归的四条法则：
1.基准情形。相当于数学归纳法的最简单的实现证明，能马上得到结果的，它也是结束递归的关键，不然变成无限循环，最终整个计算机崩溃。
2.不断推进。如果不能最终得到基准情形的值，结果也是无限的运行和崩溃。
3.设计法则。假设所有的递归调用都能运行，我把它理解为假设无限的情况下某条公式也能成立。
4.合成效益法则。我理解为求解同一个题目的时候最好不要在一个等式上使用多次递归，这样会引起很多重复调用，并且让程序变慢。
算法分析的描述就更有趣了，我上瘾也不为过。它通过四种不同的算法去实现同一个问题的功能：
最大子序列和问题。例如对于输入 -2 ，11，-4，13，-5，-2，答案为20(从A2到A4)。
这个问题很有代表性，四种算法的时间和空间复杂度分别如下图：
我手写了几遍代码，其中第三种解法是核心代码没有写全的。
package com.demo;
/**
* 求最大子序列的和
* 例如对于输入 -2 ，11，-4，13，-5，-2，答案为20(从A2到A4)
* @author liao
*
*/
public class SubSum {
public static void main(String[] args) {
int[] a= {-2,11,-4,13,-5,-2};
// int maxSum=sum1(a);
System.out.println("算法1:"+sum1(a));
System.out.println("算法2:"+sum2(a));
System.out.println("算法3:"+sum3(a,0,a.length-1));
System.out.println("算法4:"+sum4(a));
}
/**
* 算法一 全部都累加计算了一下，复杂度是n的三次方
* @param a
* @return
*/
public static int sum1(int[] a) {
int maxSum=0;
for(int i=0;i<a.length;i++) {
for(int j=i;j<a.length;j++) {
int thisSum=0;
for(int k=i;k<=j;k++) {
thisSum+=a[k];
}
if(thisSum>maxSum) {
maxSum=thisSum;
}
}
}
return maxSum;
}
/**
* 算法二
* 复杂度 n的二次方
* @param a
* @return
*/
public static int sum2(int[] a) {
int maxSum=0;
for(int i=0;i<a.length;i++) {
int sum=0;
for(int j=i;j<a.length;j++) {
sum+=a[j];
if(sum>maxSum) {
maxSum=sum;
}
}
}
return maxSum;
}
/**
* 算法三 分治法
* @param a
* @return
*/
public static int sum3(int[] a,int left,int right) {
if(left==right) {// Base case
if(a[left]>0) {
return a[left];
}else {
return 0;
}
}
int center=(left+right)/2;
int maxLeftSum=sum3(a,left,center);
int maxRightSum=sum3(a,center+1,right);
int maxLeftBorderSum=0,leftBorderSum=0;
for(int i=center;i>=left;i--) {
leftBorderSum+=a[i];
if(leftBorderSum>maxLeftBorderSum) {
maxLeftBorderSum=leftBorderSum;
}
}
int maxRightBorderSum=0,rightBorderSum=0;
for(int i=center+1;i<=right;i++) {
rightBorderSum+=a[i];
if(rightBorderSum>maxRightBorderSum) {
maxRightBorderSum=rightBorderSum;
}
}
System.out.println(maxLeftSum+" "+maxRightSum+" "+(maxLeftSum+maxRightSum));
return 0;
}
/**
* 算法四
* @param a -2,11,-4,13,-5,-2
* @return
*/
public static int sum4(int[] a) {
int maxSum=0,sum=0;
for(int j=0;j<a.length;j++) {
sum+=a[j];
if(sum>maxSum) {
maxSum=sum;
}else if(sum<0) {
sum=0;
}
}
return maxSum;
}
}
最有魅力的莫过于最后一种算法了吧，如此简单美妙，同时时间复杂度那么低。称之为诗也不为过。
写了折半查找算法，它对于已经排好序的数组非常优先，数据越多，越能体现它的威力，可以把几万次查询精简到几十次。每次都能过滤一半，今天写的时候就感觉像金庸的天山折梅手。
折半查找(binary search)验证X是否是居中的元素。如果是，则答案就找到了。如果X小于居中元素，那么我们可以应用同样的策略于居中元素左边已排序的子序列；同理，如果X大于居中元素，那么我们检查数据的右半部分
package com.demo;
/**
* 折半查找，适用于已经排好序的数组
* @author liao
*
*/
public class BinarySearch {
public static void main(String[] args) {
Integer[] a= {1,3,5,7,9,77};
System.out.println(demo1(a,77));
}
public static <AnyType extends Comparable<? super AnyType>> int demo1(AnyType[] a,AnyType b) {
int low=0,high=a.length-1;
while(low<=high) {
int mid=(low+high)/2;
if(a[mid].compareTo(b)<0) {//右边继续半折,最左边就变成了从mid+1开始了
low=mid+1;
}else if(a[mid].compareTo(b)>0) {//左边继续半折，最右边的范围就变成mid-1了
high=mid-1;
}else {//等于的情况，就是匹配到了
return mid;
}
}
return -1;
}
}
欧几里得的最大公因数算法，优美得只需要几行代码。
算法太美妙了，它在表达神圣和极致的美，代码还可以这么玩。
两个整数得最大公因数(gcd)是同时整除二者得最大整数。于是gcd(50,15)=5
算法连续计算余数直到余数是0为止，最后得非零余数就是最大公因数。
/**
* 假设m>=n,如果n<m,则循环的第一次迭代将它们置换位置
* @param m
* @param n
* @return
*/
public static long demo1(long m,long n) {
while(n!=0) {
long rem=m%n;
m=n;
n=rem;
System.out.println("n:"+n+",m:"+m);
}
return m;
}
表的两种实现，通过手动仿写两个真正的类去深刻理解数组和链表的底层实现原理
package com.demo;
import java.util.Iterator;
public class MyArrayList<AnyType> implements Iterable<AnyType>{
private static final int DEFAULT_CAPACITY=10;
private int theSize;
private AnyType[] theItems;
public MyArrayList() {
doClear();
}
public void clear() {
doClear();
}
public void doClear() {
theSize=0;
ensureCapacity(DEFAULT_CAPACITY);
}
public int size() {
return theSize;
}
public boolean isEmpty() {
return theSize==0;
}
public void trimToSize() {
ensureCapacity(size());
}
public AnyType get(int idx) {
if(idx<0||idx>=size()) {
throw new ArrayIndexOutOfBoundsException();
}
return theItems[idx];
}
public AnyType set(int idx,AnyType newVal) {
if(idx<0||idx>=size()) {
throw new ArrayIndexOutOfBoundsException();
}
AnyType old=theItems[idx];
theItems[idx]=newVal;
return old;
}
public boolean add(AnyType x) {
add(size(),x);
return true;
}
public void add(int idx,AnyType x) {
//自动扩容
if(theItems.length==size()) {
ensureCapacity(size()*2+1);
}
//移位
for(int i=theSize;i>idx;i--) {
theItems[i]=theItems[i-1];
}
theItems[idx]=x;
theSize++;
}
public AnyType remove(int idx) {
AnyType removeItem=theItems[idx];
//移位
for(int i=idx;i<size()-1;i++) {
//所删除的位置的往后的元素都往前移动意味
theItems[i]=theItems[i+1];
}
theSize--;
return removeItem;
}
public void ensureCapacity(int newCapacity) {
if(newCapacity<theSize) {
return;
}
AnyType[] old=theItems;
theItems=(AnyType[])new Object[newCapacity];
for(int i=0;i<size();i++) {
theItems[i]=old[i];
}
}
@Override
public Iterator<AnyType> iterator() {
// TODO Auto-generated method stub
return new ArrayListIterator();
}
private class ArrayListIterator implements java.util.Iterator<AnyType>{
private int current=0;
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return current<size();
}
@Override
public AnyType next() {
if(!hasNext()) {
throw new java.util.NoSuchElementException();
}
// TODO Auto-generated method stub
return theItems[current++];
}
public void remove() {
MyArrayList.this.remove(--current);
}
}
}
MyLinkedList类，便于理解链表的实现原理
package com.demo;
import java.util.Iterator;
/**
* 自定义LinkedList的实现
* 包含一个私有嵌套类Node，一个节点包含数据以及到前一个节点的链和
* 到下一个节点的链，还有一些恰当的构造方法
* 包括另一个私有嵌套类LinkedListIterator，该类抽象了位置的
* 概念，并实现接口Iterator.它提供了方法next\hasNext和remove
*
* @author liao
*
*/
public class MyLinkedList<AnyType> implements Iterable<AnyType> {
private int theSize;
private int modCount=0;
private Node<AnyType> beginMarker;
private Node<AnyType> endMarker;
private static class Node<AnyType>{
public AnyType data;//当前节点数据
public Node<AnyType> prev;//上一个节点数据
public Node<AnyType> next;//下一个节点数据
public Node(AnyType d,Node<AnyType> p,Node<AnyType> n) {
data=d;
prev=p;
next=n;
}
}
public MyLinkedList() {
doClear();
}
public void clear() {
}
private void doClear() {
beginMarker=new Node<AnyType>(null,null,null);
endMarker=new Node<AnyType>(null,beginMarker,null);
beginMarker.next=endMarker;
theSize=0;
modCount++;
}
public int size() {
return theSize;
}
public boolean isEmpty() {
return size()==0;
}
public boolean add(AnyType x) {
add(size(),x);return true;
}
public void add(int idx,AnyType x) {
addBefore(getNode(idx,0,size()),x);
}
public AnyType get(int idx) {
return getNode(idx).data;
}
public AnyType set(int idx,AnyType newVal) {
Node<AnyType> p=getNode(idx);
AnyType oldVal=p.data;
p.data=newVal;
return oldVal;
}
public AnyType remove(int idx) {
return remove(getNode(idx));
}
private void addBefore(Node<AnyType> p,AnyType x) {
Node<AnyType> newNode=new Node<>(x,p.prev,p);
newNode.prev.next=newNode;
p.prev=newNode;
theSize++;
modCount++;
}
private AnyType remove(Node<AnyType> p) {
p.next.prev=p.prev;
p.prev.next=p.next;
theSize--;
modCount++;
return p.data;
}
private Node<AnyType> getNode(int idx){
return getNode(idx,0,size()-1);
}
private Node<AnyType> getNode(int idx,int lower,int upper){
Node<AnyType> p;
if(idx<lower||idx>upper) {
throw new IndexOutOfBoundsException();
}
if(idx<size()/2) {
p=beginMarker.next;
for(int i=0;i<idx;i++) {
p=p.next;
}
}else {
p=endMarker;
for(int i=size();i>idx;i--) {
p=p.prev;
}
}
return p;
}
@Override
public Iterator<AnyType> iterator() {
// TODO Auto-generated method stub
return new LinkedListIterator();
}
private class LinkedListIterator implements java.util.Iterator<AnyType>{
private Node<AnyType> current=beginMarker.next;
private int expectedModCount=modCount;
private boolean okToRemove=false;
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return current!=endMarker;
}
@Override
public AnyType next() {
if(modCount!=expectedModCount) {
throw new java.util.ConcurrentModificationException();
}
if(!hasNext()) {
throw new java.util.NoSuchElementException();
}
AnyType nextItem=current.data;
current=current.next;
okToRemove=true;
return nextItem;
}
public void remove() {
if(modCount!=expectedModCount) {
throw new java.util.ConcurrentModificationException();
}
if(!okToRemove) {
throw new IllegalStateException();
}
MyLinkedList.this.remove(current.prev);
expectedModCount++;
okToRemove=false;
}
}
}
网友评论