一道谷歌编程题引发的思考

写在前面

  今天做了谷歌的一道在线测试题，在理解题意的基础上，总算把程序编写完整，在提交后发现很诡异的现象：小的数值运行正确，大的数值运行错误。但是我确定，数值范围没有溢出! 没有溢出! 最终排查很久，终于发现错误。不得不说，这种错误头一次遇到，真的很诡异。

题意

  将梯形看作是仅有一对边平行的凸四边形。如果两条不平行的边相等， 则称为等腰梯形。
  有一些长度不等的木棍，你需要挑出四根来构成一个等腰梯形。求共有多少种不同的组合。即便两根木棍长度相同，他们也被视为不同的木棍。木棍不能被弯曲或折断。

输入：
  第一行是测试用例的数目T，接下来是T个测试用例；
  每个测试用例由两行组成：第一行是N，代表木棍数目；第二行是N个数字，代表每根木棍长度L

1 <= T <= 100
1 <= L <= 10^9
small dataset: 1<=N<=50
large dataset: 1<=N<=5000

输出：
  对每个测试用例，输出一行#x:y，x代表测试用例编号(从1开始),y是组合数目

思路解读

  首先，从给定木棍里面选出四根木棍，代表四条边。因为题意说明相同长度的木棍视为不同的木棍，所以这种挑选方式是一个组合数。
  然后，判断四条边能否组成一个等腰梯形。等腰梯形四条边需满足的条件是：

1. 两个腰m1, m2相等；
2. 下底bot和上底top不相等；
3. 下底bot减去上底top的差，小于两个腰的长度之和；

全部代码

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileOutputStream;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Test {
    private static ArrayList<Integer> tmpArr = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        String src = "B-small-attempt1.in";
        String des = "B-small-attempt1.out";

        Scanner sc = new Scanner(new File(src));

        // 文件输出流
        FileOutputStream fos = new FileOutputStream(des);
        OutputStreamWriter osw = new OutputStreamWriter(fos);
        BufferedWriter bw = new BufferedWriter(osw);

        // 接收输入
        int T = sc.nextInt();   // T组测试样例
        for (int t=1; t<=T; t++) {
            int N = sc.nextInt();   // 数组长度

            int[] arr = new int[N]; // 接收并初始化数组
            for (int n=0; n<N; n++) {
                arr[n] = sc.nextInt();
            }

            // 传入数组到组合数
            int[] count = {0};
            if (arr.length >= 4) {
                combine(0, 4, arr, count);              
            }
            bw.write("Case #"+t+": "+count[0]);
            bw.write(System.lineSeparator());
        }

        sc.close();

        bw.close();
        osw.close();
        fos.close();
    }


    public static void combine(int index, int k, int[] arr, int[] count) {
        if (k == 1) {
            for (int i = index; i < arr.length; i++) {
                tmpArr.add(arr[i]);
                if (check(tmpArr)) {
                    count[0]++;
                }
                tmpArr.remove((Object) arr[i]);
            }
        } else if (k > 1) {
            for (int i = index; i <= arr.length - k; i++) {
                tmpArr.add(arr[i]);
                combine(i + 1, k - 1, arr, count);
                tmpArr.remove((Object) arr[i]);
            }
        } else {
            return;
        }
    }

    private static boolean check(ArrayList<Integer> arr) {
        Collections.sort(arr);  // 排序
        int top = 0;        // 上底
        int bot = 0;        // 下底
        int m1 = 0;         // 腰
        int m2 = 0;         // 腰

        if (arr.get(0).equals(arr.get(1))) {
            m1 = arr.get(0);
            m2 = arr.get(1);
            top = Math.min(arr.get(2), arr.get(3));
            bot = Math.max(arr.get(2), arr.get(3));
        } else if (arr.get(1).equals(arr.get(2))) {
            m1 = arr.get(1);
            m2 = arr.get(2);
            top = Math.min(arr.get(0), arr.get(3));
            bot = Math.max(arr.get(0), arr.get(3));
        } else if (arr.get(2).equals(arr.get(3))) {
            m1 = arr.get(2);
            m2 = arr.get(3);
            top = Math.min(arr.get(0), arr.get(1));
            bot = Math.max(arr.get(0), arr.get(1));
        } else {
            return false;
        }

        // 判断有一对边相同情况下，能否真正构成梯形
        if (top == bot) {   // 矩形
            return false;
        } else if (((bot-top) >> 1) < m1) {
            return true;
        }

        return false;
    }
}

分块解读

1）boolean check(ArrayList arr)方法
  输入参数arr为链表，存储挑选出来的四条边。首先，对链表arr进行排序，使相等的边在排序后位置相邻，可能出现的情况有：[a, a, b, c]、[a, b, b, c]、[a, b, c, c]；然后，针对上述四种情况，分别提取出上底top、下底bot、腰m1/m1；接下来，判断top、bot、m1、m2能否组成等腰梯形。

private static boolean check(ArrayList<Integer> arr) {
    Collections.sort(arr);  // 排序
    int top = 0;        // 上底
    int bot = 0;        // 下底
    int m1 = 0;         // 腰
    int m2 = 0;         // 腰

    if (arr.get(0).equals(arr.get(1))) {
        m1 = arr.get(0);
        m2 = arr.get(1);
        top = Math.min(arr.get(2), arr.get(3));
        bot = Math.max(arr.get(2), arr.get(3));
    } else if (arr.get(1).equals(arr.get(2))) {
        m1 = arr.get(1);
        m2 = arr.get(2);
        top = Math.min(arr.get(0), arr.get(3));
        bot = Math.max(arr.get(0), arr.get(3));
    } else if (arr.get(2).equals(arr.get(3))) {
        m1 = arr.get(2);
        m2 = arr.get(3);
        top = Math.min(arr.get(0), arr.get(1));
        bot = Math.max(arr.get(0), arr.get(1));
    } else {
        return false;
    }

    // 判断有一对边相同情况下，能否真正构成梯形
    if (top == bot) {   // 矩形
        return false;
    } else if (((bot-top) >> 1) < m1) {
        return true;
    }

    return false;
}

2）void combine(int index, int k, int[] arr, int[] count) 方法
  该方法用于生成组合数，并在生成完毕后将挑选出来的数字传入check()方法，根据check()的返回值决定是否计数

public static void combine(int index, int k, int[] arr, int[] count) {
    if (k == 1) {
        for (int i = index; i < arr.length; i++) {
            tmpArr.add(arr[i]);
            if (check(tmpArr)) {
                count[0]++;
            }
            tmpArr.remove((Object) arr[i]);
        }
    } else if (k > 1) {
        for (int i = index; i <= arr.length - k; i++) {
            tmpArr.add(arr[i]);
            combine(i + 1, k - 1, arr, count);
            tmpArr.remove((Object) arr[i]);
        }
    } else {
        return;
    }
}

输入文件样例

输出文件格式

经验教训

  最初，check()方法中的if语句判断两个数字相等时，使用的是双等号”==”，导致较小数值比较的结果正确，较大数值比较结果错误，以至于小的测试样例可以通过，大的测试样例不能通过。究其原因，是Integer对象的比较方式随数值范围的不同而不同。不得不说，这个错误很隐蔽，稍不留神就忽略了。

  java语言中Integer类型对于[-128, 127]之间的数是在缓冲区存取的，数值比较的时候可以用双等号”==”直接比较数值，也可以用equals()方法比较对象，还可以用intValue()方法提取出int型数值，在进行值比较。如果数值范围超出了[-128, 127]，则对象是存储在堆中的，双等号”==”比较的则是地址空间。

    public static void main(String[] args) {
        /**
         * Integer数值范围在[-128, 127]之间，存储在缓冲区中
         * */
        Integer a1 = -129, b1 = -129;
        System.out.println(a1==b1);     // false

        Integer a2 = -128, b2 = -128;
        System.out.println(a2==b2);     // true

        Integer a3 = 127, b3 = 127;
        System.out.println(a3==b3);     // true

        Integer a4 = 128, b4 = 128;
        System.out.println(a4==b4);     // false

        /**
         * 凡是new出来的对象，无论数值范围，直接存储在栈
         * */
        Integer a5 = new Integer(0), b5 = new Integer(0);
        System.out.println(a5 == b5);   // false

        /**
         * 缓冲区中的对象可以用三种方法比较数值
         * */
        Integer a6 = 0, b6 = 0;
        System.out.println(a6 == b6);                           // true
        System.out.println(a6.intValue() == b6.intValue());     // true
        System.out.println(a6.equals(b6));                      // true

        /**
         * 堆中的对象不能用双等号直接比较数值
         * */
        Integer a7 = new Integer(0), b7 = new Integer(0);
        System.out.println(a7 == b7);                           // false
        System.out.println(a7.intValue() == b7.intValue());     // true
        System.out.println(a7.equals(b7));                      // true

        System.out.println("/***************************************************************/");
        /**
         * Short类型、Long类型,存储原理与Integer类型一致:[-128, 127]存储在缓冲区
         * */
        Short c1 = -129, d1 = -129;
        System.out.println(c1==d1);     // false

        Short c2 = -128, d2 = -128;
        System.out.println(c2==d2);     // true

        Short c3 = 127, d3 = 127;
        System.out.println(c3==d3);     // true

        Short c4 = 128, d4 = 128;
        System.out.println(c4==d4);     // false

        Long e1 = -129L, f1 = -129L;
        System.out.println(e1 == f1);   // false

        Long e2 = -128L, f2 = -128L;
        System.out.println(e2 == f2);   // true

        Long e3 = 127L, f3 = 127L;
        System.out.println(e3 == f3);   // true

        Long e4 = 128L, f4 = 128L;
        System.out.println(e4 == f4);   // false

        System.out.println("/***************************************************************/");
        /**
         * Float/Double类型无论数值范围，直接存储在堆
         * */
        Double g1 = 0.00001, h1 = 0.00001;
        System.out.println(g1 == h1);                               // false
        System.out.println(g1.doubleValue() == h1.doubleValue());   // true

        Float m1 = 0.0F, n1 = 0.0F;
        System.out.println(m1 == n1);                               // false
        System.out.println(f1.floatValue() == f2.floatValue());     // true
    }