腾讯模拟题题解

第一题是给出四个点的坐标，判断其是否能组成一个正方形

输入：

3
0 0 2 2
0 2 0 2
0 1 5 6
1 6 0 5
0 0 7 7
0 3 0 3
输出：

Yes

Yes

No

思路：俩俩求一次距离，然后将结果放进一个map中，如果map的siz不是2，返回false；如果是2，那么肯定有一个的键值是2，一个键值是4。因为如果要组成一个正方形，必定有四条边相等，并且其中两条对角线也相等。

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final int t = Integer.valueOf(sc.nextLine());
        List ret  = new ArrayList();
        int index = 0;
        while (index++ < t){
            String rowx = sc.nextLine();
            String rowy = sc.nextLine();
            String[] row_x = rowx.split(" ");
            String[] row_y = rowy.split(" ");
            int[] x = new int[4];
            int[] y = new int[4];
            for(int i = 0; i < row_x.length; i++){
                x[i] = Integer.valueOf(row_x[i]);
                y[i] = Integer.valueOf(row_y[i]);
            }
            if(solve(x, y)){
                ret.add("Yes");
            }else {
                ret.add("No");
            }
        }
        for(int i = 0; i < ret.size(); i++){
            System.out.println(ret.get(i));
        }
    }
   public static boolean solve(int[] x, int[] y){
        double[] dd = new double[6];
        int index = 0;
        for(int i = 0; i < 3; i++){
            for(int j = i + 1; j < 4; j++){
                dd[index++] = dis(x, y, i, j);
            }
        }
        Map<Double, Integer> map = new HashMap<>();
        for(int i = 0; i < dd.length; i++){
            map.put(dd[i], map.getOrDefault(dd[i], 0) + 1);
        }
        if(map.size() != 2) return false;

        int iter = 0;
        int first = 0;
        int second = 0;
        for(Map.Entry<Double, Integer> entry : map.entrySet()){
            if(iter == 0) first = entry.getValue();
            else if(iter == 1) second = entry.getValue();
            iter++;
        }

        if((first == 2 && second == 4) || (first == 4 && second == 2))
            return true;
        return false;
    }
       
    public static double dis(int[] x, int[] y, int a, int b){
        return Math.sqrt((double)(x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
    }

第二题是一个土豪拥有的硬币面额及数量如下(注意每个面额只有两个)
1, 1, 2, 2, 4, 4, 8, 8, ...(无穷尽也)
求给定一个正整数n, 能获得的总额为n的硬币组合数
参考了projecteuler 169
它思路是统计每两个一之间连续0的个数，并且有下面的递推式：

其中zeros代表从高位i开始往低位统计所得连续0的个数，
举个例子：
10 -> 1010 -> 统计连续0的结果是{1,1}
13 -> 1101 -> 统计连续0的结果是{0,1}
14 -> 1110 -> 统计连续0的结果是{0,0,1} 有两个0是因为高三位每两个一之间都没有0
得出统计连续0的结果后，根据上面的递推式，很容易就可以算出所有组合数。

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        final long n = Long.valueOf(in.nextLine());
        final char[] nn = Long.toBinaryString(n).toCharArray();
        int sum = 1;
        int ret = 1;
        List<Integer> zeros = countZeros(nn);
        for(int i = 0; i < zeros.size(); i++){
            ret += zeros.get(i) * sum;
            sum += ret;
        }
        System.out.println(ret);
    }
    public static List<Integer> countZeros(char[] x){
        int consecutive = 0;
        List<Integer> ret = new ArrayList<>();
        int n = x.length - 1;
        if(x[n] == '1')
            n = n - 1;
        while (n >= 0){
            if(x[n] == '0'){
                consecutive++;
            }else {
                ret.add(0, consecutive);
                consecutive = 0;
            }
            n--;
        }
        return ret;
    }

有错误的话，欢迎指正，一起进步！