快手面試題

題目描述

博主的思路： 先用一個集合list，存盤0的下標，然后依次判斷，這些0所在的位置能否種花，若能，則將flowerbed對應位置改為1；

具體代碼：

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if(n==0){
            return true;
        }
        if(flowerbed.length==1&&flowerbed[0]==0&&n==1){
            return true;
        }
         if(flowerbed.length==1&&flowerbed[0]==0&&n>1){
            return false;
        }
         if(flowerbed.length==1&&flowerbed[0]==1&&n>=1){
            return false;
        }
        
        List<Integer> list=new ArrayList<Integer>();
        int count=0;
        for(int i=0;i<flowerbed.length;i++){
            if(flowerbed[i]==0){
                list.add(i);
            }
        }
         if(list.get(0)==0&&flowerbed[list.get(0)+1]==0){
                flowerbed[0]=1;
                count++;
            }
        for(int i=1;i<list.size();i++){
            if(flowerbed[list.get(i)-1]==0&&list.get(i)!=flowerbed.length-1&&flowerbed[list.get(i)+1]==0){
                flowerbed[list.get(i)]=1;
                count++;
            }else if(list.get(i)==flowerbed.length-1&&flowerbed[list.get(i)-1]==0){
                flowerbed[list.get(i)]=1;
                count++;
            }
        }
        return count>=n;     }
}

前面的代碼寫的不太美觀，修正下

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
       /*
       分析題意：判斷每個位置能否種花，要看他的前置結點和后置結點是否為0，有的話此節點可以種花
       存在兩個特殊的情況，如果是第一個位置的話，則只需要判斷后置結點是否為0即可，
       如果是最后一個位置，只需要判斷前置結點是否為0即可，但是我們為了保證判斷條件的一致性，
       所以第一個花盆，讓他的前置結點直接給0.最后一個花盆，后置結點直接給0
       */
        int size=flowerbed.length;
        for (int i=0;i<size;i++){
           if (flowerbed[i]==1){
               continue;
           }
        //如果當前位置為0 則判斷其前置結點和后置結點是否為0
            int pre=i==0?0:flowerbed[i-1];
           int next=i==(size-1)?0:flowerbed[i+1];
           if (pre==0&&next==0){
               flowerbed[i]=1;
               n--;
           }
        }
    return n<=0;}
}

628. 三個數的最大乘積

題目描述：

思路：

通過歸納不難分析出，陣列有五種情況

第一種：全正 最大為后三個相乘

第二種：全負 最大為后三個相乘

第三種：一個正 最大為前兩個和最后一個相乘

第四種：兩個正 最大為后三個或者前兩個和最后一個相乘

第五種：三個正及以上 最大為后三個相乘或者前兩個和最后一個相乘

總結發現，一個陣列三個數的最大乘積，要么是陣列的后三個乘積之和，要么是前兩個和最后一個相乘，

方法一具體代碼

class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;  
 return   Math.max(nums[0]*nums[1]*nums[n-1],nums[n-1]*nums[n-2]*nums[n-3]);
    }
}

方法二

線性掃描

在方法一中，我們實際上只要求出陣列中最大的三個數以及最小的兩個數，因此我們可以不用排序，用線性掃描直接得出這五個數，

具體代碼

class Solution {
    public int maximumProduct(int[] nums) {
        // 最小的和第二小的
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        // 最大的、第二大的和第三大的
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;

        for (int x : nums) {
            if (x < min1) {
                min2 = min1;
                min1 = x;
            } else if (x < min2) {
                min2 = x;
            }

            if (x > max1) {
                max3 = max2;
                max2 = max1;
                max1 = x;
            } else if (x > max2) {
                max3 = max2;
                max2 = x;
            } else if (x > max3) {
                max3 = x;
            }
        }

        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }
}