秋招面/笔试题目集合——13-创新互联

leetcode2141：同时运行 N 台电脑的最长时间
思路：二分答案 + 前缀和

public class 第一题13 {public static long maxRunTime(int n,int[] batteries){Arrays.sort(batteries);
            int m = batteries.length;
            long[] pre = new long[m + 1];
            for (int i = 1;i<= m;i++){pre[i] = pre[i - 1] + batteries[i - 1];
            }
            long l = 0;
            long r = pre[m];
            long ans = 0;
            while (l<= r){long mid = (l + r) / 2;
                if (ok(batteries,pre,n,mid)){ans = mid;
                    l = mid + 1;
                }else {r = mid - 1;
                }
            }
            return ans;
        }

        private static boolean ok(int[] batteries, long[] pre, int n, long limit) {int l = 0;
            int r = batteries.length - 1;
            int index = 0;
            while (l<= r){int mid = (l + r) / 2;
                if (batteries[mid] >= limit){index = mid;
                    r = mid - 1;
                }else {l = mid + 1;
                }
            }
            long sum = pre[index];
            int rest = n - (batteries.length - index);
            return sum >= rest * limit;
        }
}

思路：位图

public class 第二题13 {public static int[] record(int n, int m, int q, int[][] A, int[][] B) {int size = (n + 31) / 32;
        int[][] bitmap = new int[m][size];
        for (int i = 0;i< n;i++){for (int j = 0;j< A[i].length;j++){bitmap[A[i][j]][i] |= 1<< (i % 32);
            }
        }
        int[] ans = new int[B.length];
        for (int i = 0;i< B.length;i++){int sum = 0;
            for (int j = 0;j< size;j++){int count = 0;
                for (int k = 0;k< B[i].length;k++){count |= bitmap[B[i][k]][j];
                }
                sum += countOnes(count);
            }
            ans[i] = sum;
        }
        return ans;
    }
    public static int[] record2(int n, int m, int q, int[][] A, int[][] B) {// n 一共有多少人
        // 任何一个实验，需要几个整数，能表示所有人谁出现谁没出现？
        int parts = (n + 31) / 32;
        // m 0 ~ m -1
        // [i] [.........]
        int[][] bitMap = new int[m][parts];
        for (int i = 0; i< n; i++) {// i 人的编号 : a b c
            for (int exp : A[i]) {bitMap[exp][i / 32] |= 1<< (i % 32);
            }
        }
        int[] ans = new int[q];
        for (int i = 0; i< q; i++) {// i号查询 ： a、c、e，一共有多少去重的人
            // a[0] | c[0] | e[0] ->几个1
            // a[1] | c[1] | e[1] ->几个1
            int all = 0;
            for (int j = 0; j< parts; j++) {int status = 0;
                for (int exp : B[i]) {status |= bitMap[exp][j];
                }
                all += countOnes(status);
            }
            ans[i] = all;
        }
        return ans;
    }

    private static int countOnes(int n) {n = (n & 0x55555555) + ((n >>>1) & 0x55555555);
        n = (n & 0x33333333) + ((n >>>2) & 0x33333333);
        n = (n & 0x0f0f0f0f) + ((n >>>4) & 0x0f0f0f0f);
        n = (n & 0x00ff00ff) + ((n >>>8) & 0x00ff00ff);
        n = (n & 0x0000ffff) + ((n >>>16) & 0x0000ffff);
        return n;
    }
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧