第一題

leetcode2141：同時(shí)運(yùn)行 N 臺(tái)電腦的最長(zhǎng)時(shí)間
思路：二分答案 + 前綴和

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛(ài)。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶，將通過(guò)不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名與空間、網(wǎng)絡(luò)空間、營(yíng)銷軟件、網(wǎng)站建設(shè)、點(diǎn)軍網(wǎng)站維護(hù)、網(wǎng)站推廣。

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 一共有多少人
        // 任何一個(gè)實(shí)驗(yàn)，需要幾個(gè)整數(shù)，能表示所有人誰(shuí)出現(xiàn)誰(shuí)沒(méi)出現(xià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 人的編號(hào) : 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號(hào)查詢 ： a、c、e，一共有多少去重的人
            // a[0] | c[0] | e[0] ->幾個(gè)1
            // a[1] | c[1] | e[1] ->幾個(gè)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;
    }
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文標(biāo)題：秋招面/筆試題目集合——13-創(chuàng)新互聯(lián)
分享路徑：http://weahome.cn/article/ddepcc.html