網易8-11筆試算法題解析

8-11 網易筆試算法

記一次網易筆試算法題解題思路，由于原題目描述太形象化了，這裡題目描述就開門見山了。所知題目就5個(應該還有但是我找不到啊o(╯□╰)o)其中加法乘法和遊戲很容易這裡就不給出了。

瞌睡題

題目描述

給定一個數組數組的每一個位置代表一個分值，同時給定同樣長度的數組每個位置都是0或1代表分值數組對應位置是否能擷取(1可以，0不行),給定整形k代表可以叫醒k分鐘，即從任意位置開始連續k個位置的分值都可以加上，而不管對應位置是否為1或0，在隻能叫醒一次時求可以獲得的分值的最大值

輸入

• n,k代表數組長度，和叫醒一次能醒的時間
• n個數代表各個時間的分值
• n個數，都是0或1代表該時間是否清醒，1清醒，0不清醒

輸出

可以獲得的最大分值

解題思路

利用滑動視窗的方式計算最大值，視窗大小為k，一開始在視窗中為數組前k個數，視窗開始向後移動，此時如果左邊出視窗的分值對應清醒位置為0則要剪去這個分數。

代碼

//主函數負責輸入輸出
public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int len = in.nextInt();
            int wake = in.nextInt();
            int[] score = new int[len], wakeTime = new int[len];
            for(int i = ;i < len;i++){
                score[i] = in.nextInt();
            }
            for(int i = ;i < len;i++){
                wakeTime[i] = in.nextInt();
            }
            System.out.println(solve(wake,score,wakeTime));
        }
        in.nextInt();
    }

    private static int solve(int wake, int[] score, int[] wakeTime) {
        int max = ;
        int i = ;
        //初始前k個分值在視窗中
        for(;i < wake && i < score.length;i++){
            max += score[i];
        }
        int tmp = max;
        //其實這裡循環到score.length - k即可，即最後一個分值進入視窗
        for(;i < score.length;i++){
            //如果左邊出視窗元素對應位置為0要減去這個分值
            if(wakeTime[i - wake] == ){
                tmp -= score[i - wake];
            }
            //目前進入位置本身為1，說明不管在不在視窗都要加上
            //這裡max是目前最大值，而tmp是視窗目前情況最大值
            if(wakeTime[i] == ){
                max += score[i];
            }

            tmp += score[i];
            max = Math.max(tmp ,max);
        }
        return max;
    }
}
           

收貨題目

題目描述

地上有n堆蘋果，每堆ai個，求第q個蘋果屬于第幾堆

輸入

• 第一行n代表有n堆
• n個數ai代表第i堆有幾個蘋果
• m代表詢問m次
• m個qi代表每次詢問是第qi個蘋果

輸出

m行，每行代表qi詢問的答案

解題思路

首先計算出到目前堆為止一共有幾個蘋果，如輸入為[1,3,5,7],則到目前堆的蘋果數為1,4,9,16,那麼第qi個蘋果如果小于等于a0則屬于第一堆，大于a0小于等于a1在第二堆，依次類推。很明顯可以用二分查找來搜尋答案。如果用java可以用Arrays.binarySearch()方法，函數在找到時會傳回找到元素的位置，不存在時會傳回一個負數，它的絕對值代表第一個大于它的數在第幾個位置，例如對于上面例子數組a，binarySearch(a,3)傳回-2，代表第一個大于它的是在第二個位置，即下标1。

代碼

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int[] arr = new int[n];
            for(int i = ;i < n;i++){
                arr[i] = in.nextInt();
                //計算目前位置一共有幾個蘋果
                if(i>){
                    arr[i] += arr[i-];
                }
            }
            int m = in.nextInt();
            for (int i = ;i < m;i++){
                System.out.println(solve(arr, in.nextInt()));
            }
        }
        in.close();
    }

    private static int solve(int[] arr, int pos) {
        int ans = Arrays.binarySearch(arr,pos);
        return ans >=  ? ans +  : Math.abs(ans);
    }

    //為了了解自己寫一個binarySearch的類似實作,這裡不存在直接傳回第一個大于他的元素的位置
    private static int binarSeach(int[] arr,int val){
        int left = , right = arr.length - ;
        while (left < right){
            int mid = left + (right - left >> );
            if(arr[mid] == val)
                return mid;
            if(arr[mid] < val)
                left = mid + ;
            else
                right = mid;
        }
        return left;
    }
           

字典

題目描述

輸入整形n,m代表這個字典裡有n個’a’,m個’z’，他們所有的排列組合按字典順序排序，求第k個字元串。

輸入

n,m,k分别代表n個’a’,m個’z’，求字典第k個字元串

輸出

第k個字元串，如n = 2,m = 2,k = 6輸出”zzaa”

因為n = 2, m = 2,在字典有

aazz, azaz, azza, zaaz, zaza, zzaa

解題思路

這題的第一反應就是做一個帶有重複元素的字元數組的全排列，然後按字典排序，或者直接将每次全排列的結果加入優先權隊列或者TreeSet都可以。然而全排列時間複雜度為O(n!)輸入m和n為0-100明顯會逾時，其實在n+m>22左右就開始逾時了。是以這題應該是用dp算法來解決。

我們設dp[n][m]代表n個’a’,m個’z’有dp[n][m]個排列組合的數量，很明顯dp[n][m]所有情況可以由兩種方式得到,dp[n][m-1]代表n個’a’，m-1個’z’，由它的所有情況前面加一個’z’得到，還有dp[n-1][m]的所有情況前面加’a’得到(其實這個’a’或’z’加最前最後中間都行，但是一定要所有情況加在同一位置，并且加在最前面好了解這個算法)。這樣我們可以得到公式如下

dp[n][m] = dp[n][m-1] + dp[n-1][m]

那麼如何通過dp[n][m]得到第k個的字元串呢？首先明顯的是k > dp[n][m]肯定不存在傳回-1。那麼當k <= dp[n][m]時，按字典順序肯定先走a在前的是以先看dp[n-1]m如果k小于它說明肯定是前面加a,反之如果比dp[n-1][m]大，說明它在dp[n][m-1]中，前面要加z，并且它是dp[n][m-1]中的第k-dp[n-1][m]個(a開頭的消耗了dp[n-1][m]個)，那麼直到尋找到dp的邊界，剩下的’a’和’z’按照先’a’的原則追加到末尾

代碼

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();
            System.out.println(solve(n, m, k));
        }
        in.close();
    }

private static String solve(int n, int m, int k){
        int[][] dp = new int[n+][m+];
        initDp(dp);
        if(k > dp[n][m])
            return "-1";
        int i = n, j = m;
        StringBuilder sb = new StringBuilder();
        while(i > && j > ){
            int addA = dp[i-][j], addZ = dp[i][j-];
            if(addA >= k){//屬于前dp[i-1][j]個追加'a'
                sb.append('a');
                i--;//因為是從dp[i-1][j]來的是以下一次對dp[i-1][j]繼續搜尋
                n--;//消耗了一個'a','a'剩餘數量減1
            }else {
                sb.append('z');
                j--;
                m--;
                k = k - addA;
            }
        }
        while (n > ) {
            sb.append('a');
            n--;
        }
        while (m > ) {
            sb.append('z');
            m--;
        }
        return sb.toString();
    }

    //初始化dp
    private static void initDp(int[][] dp){
        int n = dp.length, m = dp[].length;
        for(int i = ;i < m;i++){
            dp[][i] = ;
        }
        for(int j = ;j < n;j++){
            dp[j][] = ;
        }
        for(int i = ;i < n;i++){
            for(int j = ;j < m;j++){
                dp[i][j] = dp[i-][j] + dp[i][j-];
            }
        }
    }