【数据结构】24种常见算法题（二）

publicIStringdelete(intbegin , intend) {
// 1 参数校验if(begin<0||end>curlen||begin>end) {
thrownewStringIndexOutOfBoundsException("条件不合法");
    }
// 2 核心：将后面内容移动到签名// 2.1 移动for(inti=0 ; i<curlen-end ; i++) {
strvalue[i+begin] =strvalue[i+end];      
    }
// 2.2 重新统计长度  (end-begin 需要删除串的长度)curlen=curlen- (end-begin)    
returnthis;
}

publicclassTestFactorial {
publicstaticvoidmain(String[] args) {
System.out.println(factorial(4));
    }
privatestaticintfactorial(intn) {
if(n==1 ) {                         【代码1】return1;
        }
returnn*factorial(n-1);             【代码2】    }
}

publicvoidinsertSort() {
RecordNodetemp;
inti, j;
for (i=1; i<this.curlen; i++) {
temp=r[i];
for (j=i-1; j>=0&&temp.key.compareTo(r[j].key) <0; j--) {
r[j+1] =r[j];
        }
r[j+1] =temp;
display();
    }
}

publicvoidinsertSortWithGuard() {
inti, j;
for (i=1; i<this.curlen; i++) {
r[0] =r[i];
for (j=i-1; r[0].key.compareTo(r[j].key) <0; j--) {
r[j+1] =r[j];
        }
r[j+1] =r[0];
System.out.print("第"+i+"趟: ");
display(9);
    }
}

publicvoidbubbleSort() {
RecordNodetemp;
booleanflag=true;
for (inti=1; i<this.curlen&&flag; i++) {
flag=false;
for (intj=0; j<this.curlen-i; j++) {
if (r[j].key.compareTo(r[j+1].key) >0) {
temp=r[j];
r[j] =r[j+1];
r[j+1] =temp;
flag=true;
            }
        }
System.out.print("第"+i+"趟: ");
display();
    }
}

publicvoidselectSort() {
RecordNodetemp;
for (inti=0; i<this.curlen-1; i++) {
intmin=i;
for (intj=i+1; j<this.curlen; j++) {
if (r[j].key.compareTo(r[min].key) <0) {
min=j;
            }
        }
if (min!=i) {
temp=r[i];
r[i] =r[min];
r[min] =temp;
        }
    }
}

publicvoidmergepass(RecordNode[] r, RecordNode[] order, ints, intn) {……}//一趟归并算法publicvoidmergeSort() {
ints=1;
intn=this.curlen;
RecordNode[] temp=newRecordNode[n];
while (s<n) {
mergepass(r, temp, s, n);
s*=2;
mergepass(temp, r, s, n);
s*=2;
}
}

publicintseqSearchWithGuard(Comparablekey) {
inti=length() -1;
r[0].key=key;
while(r[i].key.compareTo(key) !=0) {
i--;
}
returni>0?i : -1;
}

publicintseqSearch(Comparablekey) {
inti=0 , n=length();
while(i<n&&r[i].key.compareTo(key) !=0) {
i++;
}
returni<n?i : -1}

publicintbinarySearch(Comparablekey) {
if(length() >0) {
intlow=0, high=length() -1;
while (low<=high) {
intmid= (low+high) /2;
if(r[mid].key.compareTo(key) ==0) {
returnmid;
            } elseif (r[mid].key.compareTo(key) >0) { // 中间值比给定值大high=mid-1;
            } else {
low=mid+1;
            }
        }
    }
return-1;
}

privateObjectsearchBST(BiTreeNodep, Comparablekey) {
if (p!=null) {
if (key.compareTo(((RecordNode) p.data).key) ==0) {
returnp.data;
        }
if (key.compareTo(((RecordNode) p.data).key) <0) {
returnsearchBST(p.lchild, key);
        } else {
returnsearchBST(p.rchild, key);
        }
    }
returnnull;
}