Seeker的奇妙求職曆險（阿裡巴巴筆試）

恐龍下蛋

給出一個降序數組，每一輪數組中的元素

a[i]

都會增加

i

，傳回幾輪之後數組中會出現相同的元素。

輸入描述：第一行為一個數字，表示數組的長度，第二行為數組中的元素。

輸出描述：幾輪之後會出現相同的元素，如果不用變化則輸出0。-

輸入：

3

8 4 2

輸出：

2

分析，這道題看着比較複雜，想到了還是比較簡單的。我一開始直接暴力模拟，隻通過了50%，估計後面的逾時了。

對于數組中的元素a[i]和a[i+1]來說，每次後面一個元素比前面那個元素多增加1，是以經過a[i]-a[i+1]輪之後，兩個元素持平，由此可以得出代碼：

public static void main(String[] arg){
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] nums = new int[n];
    for(int i=0;i<nums.length;i++){
        nums[i] = scanner.nextInt();
    }
    //因為元素是降序排列的，是以可以斷言最大內插補點為nums[0]
    int min = nums[0];
    for(int i=0;i<n-1;i++){
        min = Math.min(nums[i]-nums[i+1],min);
    }
    System.out.println(min);
}
           

驿站

n 個客棧依次排列，給出 n - 1 條路的權重。從任意一處出發，每走過一條路，該路的權重減 1，但得到1 點利益。不能走權重為 0 的路。求最大利益。

輸入：

5

2 1 4 3

輸出

9

說明

考慮滿足條件的路徑為2-1-2-3-4-5-4-3-4-5

清華大佬的題解：https://www.nowcoder.com/discuss/462000?type=post&order=time&pos=&page=1&channel=1012&source_id=search_post

public static void a02(int n,int[] nums){
    //從第k個客棧出發，在客棧左邊獲得的利益。
    int[] f_l = new int[n];
    //從第k個客棧出發，在客棧右邊獲得的利益。
    int[] f_r = new int[n];
    //從第k個客棧出發，并且在k個客棧結束，在客棧左邊獲得的利益。
    int[] g_l = new int[n];
    //從第k個客棧出發，并在第k個客棧結束，在R_k中獲得的最大利益
    int[] g_r = new int[n];
    f_l[0] = 0;
    g_l[0] = 0;
    for(int i=1;i<n;i++){
        if(nums[i-1]%2 == 1){
            f_l[i] = f_l[i-1]+nums[i-1];
            //因為最後要回到出發點，是以隻能周遊偶數次
            g_l[i] = g_l[i-1]+nums[i-1]-1;
        }else{
            g_l[i] = g_l[i-1]+nums[i-1];
            f_l[i] = Math.max(f_l[i-1]+nums[i-1]-1, g_l[i]);
        }
    }
    for(int i=n-2;i>=0;i--){
        if(nums[i]%2 == 1){
            f_r[i] = f_r[i+1]+nums[i];
            //因為最後要回到出發點，是以隻能周遊偶數次
            g_r[i] = g_r[i+1]+nums[i]-1;
        }else{
            g_r[i] = g_r[i+1]+nums[i];
            f_r[i] = Math.max(f_r[i+1]+nums[i]-1, g_r[i]);
        }
    }
    int max = Integer.MIN_VALUE;
    for(int i=0;i<n;i++){
        max = Math.max(Math.max(f_l[i]+g_r[i],f_r[i]+g_l[i]),max);
    }
    System.out.println(max);
}
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] nums = new int[n-1];
    for(int i=0;i<n-1;i++)
        nums[i] = scanner.nextInt();
    a02(n,nums);
}