Skip to content

Latest commit

 

History

History
354 lines (276 loc) · 8.91 KB

1.1错题-基础编程模型.md

File metadata and controls

354 lines (276 loc) · 8.91 KB
Raw

1.1错题-基础编程模型

二分查找的循环法和递归法

public static int BinarySearch(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 int rankSearch(int key, int[] a) {
        return rank(key, a, 0, a.length - 1);
    }

    public static int rankSearch(int key, int[] a, int lo, int hi) {
        if(lo > hi) return -1;
        int mid = lo + (hi - lo) / 2;
        if(key < a[mid]) return rank(key, a, lo, mid -1);
        else if(key > a[mid]) return rank(key, a, mid + 1, hi);
        else return mid;
    }

rank(key,int[] a) 返回数组中小于key的元素的数量

count(key,int[] a) 返回数组中等于key的元素的数量

/**
     * @param key
     * @param a   返回小于key的元素的数量
     */
    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 {
                while (a[mid] == a[mid - 1] && mid > 0) {
                    mid--;
                }
                return mid;
            }
        }
        return -1;
    }

    public static int count(int key,int[]a ) {
        int cnt = 0;
        int i = rank(key, a);
        while (a[i] == a[i + 1] && i < a.length) {
            cnt++;
            i++;
        }

        return cnt;
    }

  • 2.0e-6 * 100000000.1

    • 2.0e-6 是一个科学计数法，表示 0.000002
    • 0.000002 * 100000000.1 = 200.0000002
int sum = 0;
        for (int i = 1; i < 1000; i++) {
            for (int j = 0; j < i; j++) {
                sum++;
            }
        }
        System.out.println(sum);


注意i,j值的范围
        System.out.println('b');
        System.out.println('b' + 'c');
        System.out.println((char) ('a' + 4));

b
197
e

将一个正整数用二进制表示并转换为一个String

  • 除2取余循环商，逆序排列法:用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为0时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

  • 算法分析

    • 字符串相加时可以通过加号顺序实现逆序排列
    • n = n/2实现取商
    • n % 2 实现取余
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        String s = "";

        for (int n = N; n > 0; n /= 2) {
            s = (n % 2) + s;
        }
考虑输出的值
int[] a = new int[10];

        for(int i = 0;i<10;i++) {
            a[i] = 9 - i;
        }
        for (int i = 0; i < 10; i++) {
            a[i] = a[a[i]];
        }

        for (int i = 0; i < 10; i++) {
            System.out.println(a[i]);
        }

编写一个静态方法lg(),接受整形参数N,返回不大于log2 N的最大整数, 不要使用Math库

public static int lo(int N) {
        int x = -1;
        int product = 1;
        while (product <= N) {
            product *= 2;
            x++;
        }
        return x;
    }

优化递归调用的斐波那契方法

待优化的方法:
public static long F(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        return F(n - 1) + F(n - 2);
    }


不使用递归会提高效率
public static long F(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        long f = 0;
        long g = 1;
        for(int i = 0;i<n;i++) {
            f = f + g;
            g = g + f;
        }
        return f;
    }

删除一个 排序后 数组中的重复元素

public static int[] deleteRepeat(int[] a) {
        int[] b = new int[a.length];
        int s = 0;

        b[0] = a[0];
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] == a[i + 1]) {
                s++;
            } else {
                b[i - s + 1] = a[i + 1];
            }
        }

        //优化数组,删除后面空的地址
        int[] result = new int[b.length - s];
        for (int i = 0; i < b.length - s; i++) {
            result[i] = b[i];
        }

        return result;
    }

返回两个数的最大公因子

  • 递归算法
public static int gcd(int m, int n) {
       if (m == 0 || n == 0) return 1;
       if (m % n == 0) return n;
       else return gcd(n, m % n);
   }

接受一个int N和double p,在一个圆上画出间距相等的N个点,然后将每对点按照概率p连接

public static void drawRandConn(int N, double p) {
    //这里应该添加一个对p的检查

    //设置画布大小
    StdDraw.setCanvasSize(1024, 1024);
    //设置相对坐标
    StdDraw.setScale(-1.0, 1.0);
    StdDraw.setPenRadius(.015);

    double[][] d = new double[N][2];
    //通过改变α角 来控制点的位置
    for (int i = 0; i < N; i++) {
        //x = r.cos α ,  y = r.sin α
        d[i][0] = Math.cos(2 * Math.PI * i / N);
        d[i][1] = Math.sin(2 * Math.PI * i / N);
        StdDraw.point(d[i][0], d[i][1]);
    }

    StdDraw.setPenRadius();

    //N个点,遍历N-1次,最后一个点在前面遍历时已经被用了
    for (int i = 0; i < N - 1; i++) {
        //j = i+1  从当前点(i)的下一个点开始遍历
        for (int j = i + 1; j < N; j++) {
            //根据概率返回一个随机boolean
            if (Math.random() < p) {
                StdDraw.line(d[i][0], d[i][1], d[j][0], d[j][1]);
            }
        }
    }


}

模拟投掷两枚骰子,计算两枚骰子之和出现的概率,计算理想情况下的概率,并把模拟的概率和理想的比较

  • 分别写两个方法,一个是理想情况,一个是模拟投掷
  • StdRandom.uniform(1, 7)
public static double[] getExact() {
        int SIDES = 6;
        //下标表示两次骰子之和,值表示概率
        double[] dist = new double[2 * SIDES + 1];


        //对两次骰子之和遍历,每遍历到一个和这个和的计数器加1
        for (int i = 1; i <= SIDES; i++) {
            for (int j = 1; j <= SIDES; j++) {
                dist[i + j] += 1.0;
            }
        }
        //之所以不用遍历是因为dist[0] 和 dist[1]的值都是0,除法运算无意义
        for (int i = 2; i <= 2 * SIDES; i++) {
            //一共36种情况
            dist[i] /= 36.0;
        }

        return dist;
    }

    public static double[] getExperience(int throwNum) {
        int SIDES = 6;
        double[] dist = new double[2 * SIDES + 1];


        //对投掷次数进行遍历,模拟每一次投掷
        for (int i = 0; i < throwNum; i++) {
            int x = StdRandom.uniform(1, 7) + StdRandom.uniform(1, 7);
            dist[x] += 1.0;
        }

        for (int i = 0; i < SIDES * 2; i++) {
            dist[i] /= throwNum;
        }

        return dist;

    }

从String1中剪切掉String2,补上一个换行符

public static String cut(String t, String p) {
        boolean succ = false;
        int j;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i <= t.length() - p.length(); i++) {
            j = 0;
            succ = false;
            while (j < p.length()) {
                if (t.charAt(i + j) != p.charAt(j)) {
                    succ = false;
                    break;
                } else {
                    j++;
                    succ = true;
                }
            }

            if (!succ) {
                sb.append(t.charAt(i));
            } else {
                sb.append('\n');
                i += p.length()-1;
            }
        }

        return sb.toString();
    }