Graptolite
Back
Other 2020-06-25 Views ...

算法第四版 练习题记录

Language 中文 English
algorithms

课后题并没有全部做,只是挑出几个无法确定或不能想到结果的进行记录 因为之前没有使用过IDEA导致浪费很多时间进行IDE的配置用户调试

算法第四版

算法第一章

题目概要:检索用户输入”[()]{}{[()()]}“进行相应符号的配对,如果符号无法匹配输出false

思路,参考之前书中提到过的算术表达式求值(P79) 通过创建下压栈lops进行记录左侧符号,包含[ { (,如果在读取语句中遇到右侧符号] } ),lops.pop()弹出栈上最上面的值,如果不是左右匹配则输出错误,直至全部循环结束

== 由于jar包里面的类加上IDE使用不熟悉,所以没有进行语句的全部录入并拆解 ==

code

public class MainProject {
    public static void main(String[] args) {
             StdOut.println(IsEquals());
    }
    private static boolean IsEquals(){
        Stack<String> lops = new Stack<String>();
        Stack<String> rops = new Stack<String>();
        //一个存储左侧符号一个存储右侧符号 '{ [ ( ' R'} ] )'
        //string s = "[()]{}{[()()]}";
        int h=0;
        int n=0;
        while (h<14) {

            //读取字符串,将其压入栈
            String s = StdIn.readString();
           if(s.equals("[")) {
              lops.push(s);
           }
           else if(s.equals("{")){lops.push(s);}
           else if(s.equals("(")){lops.push(s);}
           else if(s.equals("]")){
               if(!lops.pop().equals("["))
               {n++;}
           }
           else if(s.equals("}"))
           {
           if(!lops.pop().equals("{")){n++;}

           }
           else if(s.equals(")")){
               if(!lops.pop().equals("(")){
                   n++;
               }

           }
           h++;
        }
        if(n!=0){
             return false;
         }
         else {return  true;}
    }
}

算法(第四版) 2.2 自上而下的归并排序算法

  1. 利用周末将上班日看的算法进行练习,复原算法,果然周一看的已经忘得差不多了,通过再次复原算法的每一步,理清思路再与后面书中的步骤进行对照:smile:

  2. code

     public static void main(String[] args) {
        String[] a=new String[]{"A","E","Q","S","U","Y","E","I","N","O","S","T"};
        Merga.sort(a);
        Merga.show(a);

    }
    public static class Merga{
        private static Comparable[] aux;

        public static void merge(Comparable[] a ,int lo,int mid,int hi){
            int i=lo;
            int j=mid+1;
            for(int k=lo;k<=hi;k++){
                aux[k] = a[k];
            }
            //此处进行全部数组的遍历,最小值为:lo 最大值:hi
            for(int k=lo;k<=hi;k++){
                if(i>mid) a[k]=aux[j++]; //1. 当lo>mid时 取右半边元素 此时a[k]=a[j] j自加
                else if(j>hi) a[k]=aux[i++];//2. 当mid+1>hi时 取左半边元素 此时a[k]=a[i] i自加
                else if(less(aux[j],aux[i])) a[k]=aux[j++];//3. 将a[j]<a[i]时,a[k]=a[j] j自加
                else a[k]=aux[i++];//4. 反之,a[k]=a[i] i自加
            }
            /*
             循环的意思为:
             当左半区域第一位与右半区域第一位进行比较如果右侧大于左侧,则互换位置
             此时i不停自加,当i的值大于mid中间值的时候代表左侧区域值全部取完,此时取右侧元素
             j同理
             */
//            StdOut.print("Merga -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
        }

        public static void sort(Comparable[] a){
            aux=new Comparable[a.length];
            sort(a,0,a.length-1);
        }
        public static void sort(Comparable[] a ,int lo,int hi){
            if(hi<=lo) return;
            int mid = lo+(hi-lo)/2;
            StdOut.print("TT -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
            sort(a,lo,mid);//此处递归值,将从0,5,11依次递减至0,0,1停止,此时运行第二个递归将从0,0,1开始,第二个递归接收值使用hi<lo直到0,2,5
            StdOut.print("First Sort -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
            sort(a,mid+1,hi);//此处递归值,有人前期可能会理解为统一层面,不明白hi为何会一直变化,他发挥作用其实是在a,lo,mid的值
            StdOut.print("Second Sort -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
            merge(a,lo,mid,hi);
            /*
            由于此结构相当于三层递归,所以会产生一定的理解误差,第二个sort函数sort(a,mid+1,hi)其实一直在第一个函数之下,可以理解成
            sort(a,lo,mid){sort(a,mid+1,hi)},通过将满足的数组不断遍历 从而比较大小进行互换
             */
        }
        private static  boolean less(Comparable v,Comparable w){
            return v.compareTo(w)<0;
        }
        private static void show(Comparable[] a ){
            for(int i=0;i<a.length;i++){
                StdOut.print(a[i]+" ");
            }
            StdOut.println();
        }
        private static boolean isSorted(Comparable[] a){
            for(int i=1;i<a.length;i++)
                if(less(a[i],a[i-1])) return false;
            return true;
        }
    }

  3. Merga方法

# Java

 public static void merge(Comparable[] a ,int lo,int mid,int hi){
            int i=lo;
            int j=mid+1;
            for(int k=lo;k<=hi;k++){
                aux[k] = a[k];
            }
            //此处进行全部数组的遍历,最小值为:lo 最大值:hi
            for(int k=lo;k<=hi;k++){
                if(i>mid) a[k]=aux[j++]; //1. 当lo>mid时 取右半边元素 此时a[k]=a[j] j自加
                else if(j>hi) a[k]=aux[i++];//2. 当mid+1>hi时 取左半边元素 此时a[k]=a[i] i自加
                else if(less(aux[j],aux[i])) a[k]=aux[j++];//3. 将a[j]<a[i]时,a[k]=a[j] j自加
                else a[k]=aux[i++];//4. 反之,a[k]=a[i] i自加
            }
            /*
             循环的意思为:
             当左半区域第一位与右半区域第一位进行比较如果右侧大于左侧,则互换位置
             此时i不停自加,当i的值大于mid中间值的时候代表左侧区域值全部取完,此时取右侧元素
             j同理
             */
        }

  1. sort自我遍历

    # Java
 public static void sort(Comparable[] a ,int lo,int hi){
            if(hi<=lo) return;
            int mid = lo+(hi-lo)/2;
            StdOut.print("TT -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
            sort(a,lo,mid);//此处递归值,将从0,5,11依次递减至0,0,1停止,此时运行第二个递归将从0,0,1开始,第二个递归接收值使用hi<lo直到0,2,5
            StdOut.print("First Sort -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
            sort(a,mid+1,hi);//此处递归值,有人前期可能会理解为统一层面,不明白hi为何会一直变化,他发挥作用其实是在a,lo,mid的值
            StdOut.print("Second Sort -- lo:"+lo+" mid: "+mid+" hi: "+hi+"\r\n");
            merge(a,lo,mid,hi);
            /*
            由于此结构相当于三层递归,所以会产生一定的理解误差,第二个sort函数sort(a,mid+1,hi)其实一直在第一个函数之下,可以理解成
            sort(a,lo,mid){sort(a,mid+1,hi)},通过将满足的数组不断遍历 从而比较大小进行互换
             */
        }

    此处的值为

TT -- lo:0 mid: 5 hi: 11
 TT -- lo:0 mid: 2 hi: 5
TT -- lo:0 mid: 1 hi: 2
TT -- lo:0 mid: 0 hi: 1
First Sort -- lo:0 mid: 0 hi: 1
Second Sort -- lo:0 mid: 0 hi: 1
Merga -- lo:0 mid: 0 hi: 1
First Sort -- lo:0 mid: 1 hi: 2
Second Sort -- lo:0 mid: 1 hi: 2
Merga -- lo:0 mid: 1 hi: 2
First Sort -- lo:0 mid: 2 hi: 5
TT -- lo:3 mid: 4 hi: 5
TT -- lo:3 mid: 3 hi: 4
First Sort -- lo:3 mid: 3 hi: 4
Second Sort -- lo:3 mid: 3 hi: 4
Merga -- lo:3 mid: 3 hi: 4
First Sort -- lo:3 mid: 4 hi: 5
Second Sort -- lo:3 mid: 4 hi: 5
Merga -- lo:3 mid: 4 hi: 5
Second Sort -- lo:0 mid: 2 hi: 5
Merga -- lo:0 mid: 2 hi: 5
First Sort -- lo:0 mid: 5 hi: 11
TT -- lo:6 mid: 8 hi: 11
TT -- lo:6 mid: 7 hi: 8
TT -- lo:6 mid: 6 hi: 7
First Sort -- lo:6 mid: 6 hi: 7
Second Sort -- lo:6 mid: 6 hi: 7
Merga -- lo:6 mid: 6 hi: 7
First Sort -- lo:6 mid: 7 hi: 8
Second Sort -- lo:6 mid: 7 hi: 8
Merga -- lo:6 mid: 7 hi: 8
First Sort -- lo:6 mid: 8 hi: 11
TT -- lo:9 mid: 10 hi: 11
TT -- lo:9 mid: 9 hi: 10
First Sort -- lo:9 mid: 9 hi: 10
Second Sort -- lo:9 mid: 9 hi: 10
Merga -- lo:9 mid: 9 hi: 10
First Sort -- lo:9 mid: 10 hi: 11
Second Sort -- lo:9 mid: 10 hi: 11
Merga -- lo:9 mid: 10 hi: 11
Second Sort -- lo:6 mid: 8 hi: 11
Merga -- lo:6 mid: 8 hi: 11
Second Sort -- lo:0 mid: 5 hi: 11
Merga -- lo:0 mid: 5 hi: 11

通过值可以清晰的看出递归的层次结构,最终将简化为针对小数组进行互换,最后与书中实例讲解比对一下,自己理解没有出现很大的误差,算是重新复习一下

算法(第四版) 2.3 快速排序

  • 快速排序时选出一个基准参数,就开那个数组进行怕排序,左侧指针小于基准,右侧大于基准,三向快速排序中还会增加等于基准指针的值

  • 与2.2归并排序的思路一致,通过对数组的不断递归,逐步将左侧和右侧进行排序得出结果

  • code:

    public static class Quick{

        private static Comparable[] aux;

        public static void sort(Comparable[] a){
            aux=new Comparable[a.length];
            sort(a,0,a.length-1);
        }
        public static void sort(Comparable[] a ,int lo,int hi){
            if(hi<=lo) return ;
            int lt=lo,i=lo+1,gt=hi;
            Comparable v = a[lo];//随机值,设置数组起点
            while(i<=gt){
                int cmp = a[i].compareTo(v);
                if(cmp<0) exch(a,lt++,i++);//如果a[i]<a[lo] 交换a[lt]-->a[lo]与a[i]-->a[lo+1],相应参数运算后自加
                else if(cmp>0) exch(a,i,gt--);//反之,交换a[i]与a[gt],当道第三个指针中,gt自减~指针左移,转换位置之后i不变再次循环将继续判断a[i]
                else i++;
                StdOut.print("while statement lt: "+lt+" i:"+i+" gt:"+gt+"\r\n");
            }
            sort(a,lo,lt-1);//运行完第一次之后,将划分为三段<a[lo];=a[lo];>a[lo],此时针对,a[lo]部分进行排序,逐步递归,将左侧区域位置变为有序数组
            StdOut.print("second lo:"+lo+" lt:"+lt+"\r\n");
            sort(a,gt+1,hi);
            StdOut.print("third gt:"+gt+" hi:"+hi+"\r\n");
        }
       private static void exch(Comparable[] a ,int lo,int hi){
            Comparable tmp ;
            tmp=a[lo];
            a[lo]=a[hi];
            a[hi]=tmp;
       }
        private static void show(Comparable[] a ){
            for(int i=0;i<a.length;i++){
                StdOut.print(a[i]+" ");
            }
            StdOut.println();
        }
    }

    输出:

    while statement lt: 0 i:1 gt:10
while statement lt: 0 i:1 gt:9
while statement lt: 0 i:1 gt:8
while statement lt: 0 i:1 gt:7
while statement lt: 0 i:1 gt:6
while statement lt: 0 i:1 gt:5
while statement lt: 0 i:1 gt:4
while statement lt: 0 i:1 gt:3
while statement lt: 0 i:1 gt:2
while statement lt: 0 i:1 gt:1
while statement lt: 0 i:1 gt:0
second lo:0 lt-1:-1
while statement lt: 1 i:2 gt:10
while statement lt: 2 i:3 gt:10
while statement lt: 2 i:3 gt:9
while statement lt: 2 i:3 gt:8
while statement lt: 2 i:3 gt:7
while statement lt: 3 i:4 gt:7
while statement lt: 3 i:4 gt:6
while statement lt: 4 i:5 gt:6
while statement lt: 5 i:6 gt:6
while statement lt: 6 i:7 gt:6
while statement lt: 1 i:2 gt:4
while statement lt: 1 i:2 gt:3
while statement lt: 1 i:3 gt:3
while statement lt: 1 i:3 gt:2
second lo:1 lt-1:0
while statement lt: 4 i:5 gt:5
while statement lt: 4 i:5 gt:4
second lo:3 lt-1:3
third gt+1:5 hi:5
third gt+1:3 hi:5
second lo:1 lt-1:5
while statement lt: 8 i:9 gt:11
while statement lt: 9 i:10 gt:11
while statement lt: 10 i:11 gt:11
while statement lt: 11 i:12 gt:11
while statement lt: 7 i:8 gt:9
while statement lt: 7 i:9 gt:9
while statement lt: 7 i:9 gt:8
second lo:7 lt-1:6
while statement lt: 10 i:11 gt:10
second lo:9 lt-1:9
third gt+1:11 hi:10
third gt+1:9 hi:10
second lo:7 lt-1:10
third gt+1:12 hi:11
third gt+1:7 hi:11
third gt+1:1 hi:11
Recommended View Other
2025-07-22 VS Code SSH-Remote 远程连接之后只能控制台访问无法看到使用openFloder 2024-11-20 Autodesk AutoCAD .Net 创建PatternSet和工具栏 2023-08-07 ObjectArx2016 报错 对象不支持 additem属性或方法