前言

今天開始我將陸續(xù)為大家更新面試經(jīng)典150題中較難理解的題目。今天我為大家分享的是，除自身以外數(shù)組的乘積、跳躍游戲| 和 跳躍游戲||。

除自身以外數(shù)組的乘積

除自身以外數(shù)組的乘積

要求

給你一個整數(shù)數(shù)組 nums，返回 數(shù)組 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積 。

題目數(shù)據(jù) 保證 數(shù)組 nums之中任意元素的全部前綴元素和后綴的乘積都在 32 位 整數(shù)范圍內(nèi)。

請不要使用除法，且在 O(n) 時間復雜度內(nèi)完成此題

示例 1:

輸入: nums = [1,2,3,4]
輸出: [24,12,8,6]
示例 2:

輸入: nums = [-1,1,0,-3,3]
輸出: [0,0,9,0,0]

class Solution {
    public int[] productExceptSelf(int[] nums) {

    }
}

思路

按照一般的思路，我們可能會想：先將數(shù)組中所有的元素相乘得到一個sum，然后再遍歷一遍數(shù)組，answer[i] = sum / nums[i]，如果nums[i] = 0，answer[i] = sum。但是這個題目要求我們不使用除法，那么我們該怎么辦呢？因為是除自身以外的數(shù)組的乘積，自身以外的數(shù)組被分為左右兩部分，我們只需要將 左邊部分數(shù)組元素的乘積 x 右邊部分數(shù)組元素的乘積 就得到除自身以外的數(shù)組的乘積。所以我們可以使用兩個數(shù)組L和R來分別存儲數(shù)組第 i 個元素左邊部分數(shù)組元素的乘積和右邊部分數(shù)組元素的乘積，最后再遍歷一遍數(shù)組，answer[i] = L[i] * R[i]。

代碼

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        int[] L = new int[n];
        int[] R = new int[n];
        L[0] = 1;
        for(int i = 1; i < n; i++) {
        //L[i]等于前i-2個數(shù)的乘積乘上第i-1個數(shù)
            L[i] = L[i-1] * nums[i-1];
        } 
        R[n-1] = 1;
        for(int i = n - 2; i >= 0; i--) {
        //R[i]等于后 length-i-2 個數(shù)的乘積乘上第 length-i-1個數(shù)
            R[i] = R[i+1] * nums[i+1];
        }

        for(int i = 0; i < n; i++) {
            answer[i] = L[i] * R[i];
        }

        return answer;
    }
}

跳躍游戲|

跳躍游戲|

要求

給定一個非負整數(shù)數(shù)組 nums ，你最初位于數(shù)組的 第一個下標 。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最后一個下標。

示例 1：

輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然后再從下標 1 跳 3 步到達最后一個下標。
示例 2：

輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達下標為 3 的位置。但該下標的最大跳躍長度是 0 ， 所以永遠不可能到達最后一個下標。

class Solution {
    public int jump(int[] nums) {

    }
}

題解

其實這個題目可以換一種理解方式：在某位置的跳躍范圍內(nèi)時候有某一位置可以跳躍到最后一個下標處。我們可以使用 rightmost 來記錄在某位置的跳躍范圍內(nèi)的最大跳躍位置， 最大跳躍位置 = i + nums[i] 如果 rightmost >= length-1，那么說明可以到達最后一個下標處。

代碼

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for(int i = 0; i < n; i++) {
            if(i <= rightmost) {
                rightmost = Math.max(rightmost,i + nums[i]);
                if(rightmost >= n-1) {
                    return true;
                }
            }
        }
        return false;
    }
}

跳躍游戲||

跳躍游戲||

要求

給定一個長度為 n 的 0 索引整數(shù)數(shù)組 nums。初始位置為 nums[0]。

每個元素 nums[i] 表示從索引 i 向前跳轉(zhuǎn)的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉(zhuǎn)到任意 nums[i + j] 處:

0 <= j <= nums[i]
i + j < n
返回到達 nums[n - 1] 的最小跳躍次數(shù)。生成的測試用例可以到達 nums[n - 1]。

示例 1:

輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數(shù)是 2。
從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達數(shù)組的最后一個位置。
示例 2:

輸入: nums = [2,3,0,1,4]
輸出: 2

class Solution {
    public int jump(int[] nums) {

    }
}

題解

因為題目中說生成的測試用例可以到達nums[i-1]，求最小的跳躍次數(shù)。所以我們每次跳躍的位置就是在跳躍區(qū)間中能跳躍最遠的位置。并且在遍歷數(shù)組時，我們不訪問最后一個元素，這是因為在訪問最后一個元素之前，我們的邊界一定大于等于最后一個位置，否則就無法跳到最后一個位置了。如果訪問最后一個元素，在邊界正好為最后一個位置的情況下，我們會增加一次「不必要的跳躍次數(shù)」，因此我們不必訪問最后一個元素。

代碼

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        //end用來記錄跳躍區(qū)間
        int end = 0;
        int step = 0;
        for(int i = 0; i < n - 1; i++) {
            rightmost = Math.max(rightmost,i + nums[i]);
            if(i == end) {
                end = rightmost;
                step++;
            }
        }

        return step;
    }
}

文章來源地址http://www.zghlxwxcb.cn/news/detail-495418.html

到了這里，關(guān)于面試經(jīng)典150題（1）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！