算法－第四版－练习1.2.9解答

雨点打透心脏的1/2处 2022-04-23 10:26 60阅读 0赞

# 题目分析 #

**1.修改 BinarySearch（请见 1.1.10.1 节中的二分查找代码），  
2.使用 Counter 统计在有查找中被检查的键的总数并在查找全部结束后打印该值。  
3.提示：在 main() 中创建一个 Counter 对象并将它作为参数传递给 rank()。**

看了两三遍不知道题目说啥,看了别人的答案以后才知道  
**第二句话**的意思是:用二分查找法来找数组里面的一个数字,需要找几次才能找到.或者找几次才找不到

# 准备材料 #

算法第四版材料自带的素材,tiny作为白名单  
把tinyW里面的每一个数字拿出来,去白名单里面找,是否存在于白名单  
![在这里插入图片描述][20190208104809960.png]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]

# 原始代码 #

import edu.princeton.cs.algs4.In;
    import edu.princeton.cs.algs4.StdIn;
    import edu.princeton.cs.algs4.StdOut;
     
    import java.util.Arrays;
     
     
    public class BinarySearch {
        public static int rank(int key, int[] a) {
            int lo = 0;
            int hi = a.length - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (key < a[mid]) hi = mid - 1;
                else if (key > a[mid]) lo = mid + 1;
                else return mid;
            }
            return -1;
        }
     
        public static void main(String[] args) {
            int[] whitelist = In.readInts(args[0]);
            Arrays.sort(whitelist);
            while (!StdIn.isEmpty()) {
                int key = StdIn.readInt();
                if (rank(key, whitelist) < 0) {
                    StdOut.println(key);
                }
            }
        }
    }

# 本题代码 #

package homework1_2;
    
    import edu.princeton.cs.algs4.Counter;
    import edu.princeton.cs.algs4.In;
    import edu.princeton.cs.algs4.StdIn;
    import edu.princeton.cs.algs4.StdOut;
    
    import java.util.Arrays;
    
    /**
     * @description: ${description}
     * @create: 2019-02-08
     **/
    public class W_1_2_9 {
        public static int rank(int key, int[] a,Counter counter) {//增加传入参数
            int lo = 0;
            int hi = a.length - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                counter.increment();//每次查找的话,就要先找到一个中间点,那么就给次数+1
                if (key < a[mid]) hi = mid - 1;
                else if (key > a[mid]) lo = mid + 1;
                else return mid;
            }
            return -1;
        }
    
        public static void main(String[] args) {
            int[] whitelist = In.readInts(args[0]);
            Arrays.sort(whitelist);
            while (!StdIn.isEmpty()) {
                int key = StdIn.readInt();
                Counter c=new Counter("times");//上面那行代码的意思是读取文件中的一个具体的数字,然后去白名单里面去找 是否有这个数字
                if (rank(key, whitelist,c) < 0) {
                    StdOut.print(key);
                    System.out.print(" is not in whitelist:");
                    System.out.print("...how many times to find num not in whiteList:");
                    System.out.print(c);
                    System.out.println();
                }else {
                    StdOut.print(key);
                    System.out.print(" is in whitelist:");
                    System.out.print("...how many times to find num in whiteList:");
                    System.out.print(c);
                    System.out.println();
                }
            }
        }
    }

# 终端输入内容 #

F:\javalearn\ideacode\suanfa\src>javac homework1_2/W_1_2_9.java -Xlint
    		homework1_2\W_1_2_9.java:29: 警告: [deprecation] In中的readInts(String)已过时
            int[] whitelist = In.readInts(args[0]);1 个警告
    F:\javalearn\ideacode\suanfa\src>java homework1_2/W_1_2_9 tinyW.txt < tinyT.txt

# 控制台显示结果 #

23 is in whitelist:…how many times to find num in whiteList:3 times  
50 is not in whitelist:…how many times to find num not in whiteList:4 times  
10 is in whitelist:…how many times to find num in whiteList:4 times  
99 is not in whitelist:…how many times to find num not in whiteList:4 times  
18 is in whitelist:…how many times to find num in whiteList:4 times  
23 is in whitelist:…how many times to find num in whiteList:3 times  
98 is in whitelist:…how many times to find num in whiteList:4 times  
84 is in whitelist:…how many times to find num in whiteList:3 times  
11 is in whitelist:…how many times to find num in whiteList:3 times  
10 is in whitelist:…how many times to find num in whiteList:4 times  
48 is in whitelist:…how many times to find num in whiteList:4 times  
77 is in whitelist:…how many times to find num in whiteList:4 times  
13 is not in whitelist:…how many times to find num not in whiteList:4 times  
54 is in whitelist:…how many times to find num in whiteList:3 times  
98 is in whitelist:…how many times to find num in whiteList:4 times  
77 is in whitelist:…how many times to find num in whiteList:4 times  
77 is in whitelist:…how many times to find num in whiteList:4 times  
68 is in whitelist:…how many times to find num in whiteList:2 times

# 解题心得 #

1.看不懂题目,可能是理解问题或者是英文翻译的问题  
2.看懂了题目然后就要通过数学思维把问题抽象化,编程化  
3.如何把结果正确的展示出来  
4.关键 计数器放在哪里取决于什么时候清零.什么时候加一

[20190208104809960.png]: https://img-blog.csdnimg.cn/20190208104809960.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]: /images/20220321/d735f50b156745b4a41951f013487bdf.png