子數(shù)組按位或操作

題目：我們有一個非負整數(shù)數(shù)組 A。對于每個（連續(xù)的）子數(shù)組 B = [A[i], A[i+1], ..., A[j]] （ i <= j），我們對 B 中的每個元素進行按位或操作，獲得結(jié)果 A[i] | A[i+1] | ... | A[j]。返回可能結(jié)果的數(shù)量。 （多次出現(xiàn)的結(jié)果在最終答案中僅計算一次。）

示例 1：
輸入：[0]
輸出：1
解釋：
只有一個可能的結(jié)果 0 。
示例 2：
輸入：[1,1,2]
輸出：3
解釋：
可能的子數(shù)組為 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
產(chǎn)生的結(jié)果為 1，1，2，1，3，3 。
有三個唯一值，所以答案是 3 。
示例 3：
輸入：[1,2,4]
輸出：6
解釋：
可能的結(jié)果是 1，2，3，4，6，以及 7 。
提示：
1 <= A.length <= 50000
0 <= A[i] <= 10^9

思路：這個題的標簽是位運算和動態(tài)規(guī)劃。因為是連續(xù)的子數(shù)組，所以這里肯定是要記錄用到當前元素前一個的所有結(jié)果。針對這些結(jié)果集才可以選擇或當前元素。當然了每個元素都可以作為一個子數(shù)組的開始來進行計算，總而言之感覺dp的性質(zhì)不強。而且這個重復結(jié)果是不作為計算的。所以初步計劃set存結(jié)果集。然后用一個集合記錄前一個元素的所有可能。再與當前元素挨個遍歷。思路比較清晰，我去代碼實現(xiàn)
第一版代碼：

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> set = new HashSet<Integer>();
        Set<Integer> last = new HashSet<Integer>();
        for(int i : arr) {
            Set<Integer> temp = new HashSet<Integer>();
            temp.add(i);
            for(int c : last) {
                temp.add(c|i);
            }
            last = temp;
            set.addAll(temp);
        }
        return set.size();
    }
}

其實這個也算是暴力過了吧。雖然性能不太好，接下來我去看看性能第一的代碼：

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        int n = arr.length;
        if(n < 2){
            return n;
        }
        Set<Integer> set = new HashSet<>(65536);
        for (int i = 0; i < n; i++) {
            set.add(arr[i]);
            for (int j = i-1; j >= 0; --j) {
                if((arr[j] & arr[i]) == arr[i]) {
                    break;
                }
                arr[j] |= arr[i];
                set.add(arr[j]);
            }
        }
        return set.size();
    }
}

思路是類似的思路。我感覺重點應該就是這個當前元素和之前某個相等直接break。因為遇到同樣元素的話說明前面的結(jié)果都是一樣的。沒必要重復計算。剩下別的沒啥了。下一題了。

RLE迭代器

題目：編寫一個遍歷游程編碼序列的迭代器。迭代器由 RLEIterator(int[] A) 初始化，其中 A 是某個序列的游程編碼。更具體地，對于所有偶數(shù) i，A[i] 告訴我們在序列中重復非負整數(shù)值 A[i + 1] 的次數(shù)。迭代器支持一個函數(shù)：next(int n)，它耗盡接下來的 n 個元素（n >= 1）并返回以這種方式耗去的最后一個元素。如果沒有剩余的元素可供耗盡，則 next 返回 -1 。例如，我們以 A = [3,8,0,9,2,5] 開始，這是序列 [8,8,8,5,5] 的游程編碼。這是因為該序列可以讀作 “三個八，零個九，兩個五”。

示例：
輸入：["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]]
輸出：[null,8,8,5,-1]
解釋：
RLEIterator 由 RLEIterator([3,8,0,9,2,5]) 初始化。
這映射到序列 [8,8,8,5,5]。
然后調(diào)用 RLEIterator.next 4次。
.next(2) 耗去序列的 2 個項，返回 8?，F(xiàn)在剩下的序列是 [8, 5, 5]。
.next(1) 耗去序列的 1 個項，返回 8?，F(xiàn)在剩下的序列是 [5, 5]。
.next(1) 耗去序列的 1 個項，返回 5?，F(xiàn)在剩下的序列是 [5]。
.next(2) 耗去序列的 2 個項，返回 -1。 這是由于第一個被耗去的項是 5，
但第二個項并不存在。由于最后一個要耗去的項不存在，我們返回 -1。
提示：
0 <= A.length <= 1000
A.length 是偶數(shù)。
0 <= A[i] <= 10^9
每個測試用例最多調(diào)用 1000 次 RLEIterator.next(int n)。
每次調(diào)用 RLEIterator.next(int n) 都有 1 <= n <= 10^9 。

思路：這個題怎么說呢，感覺還是挺簡單的。首先分析數(shù)據(jù)范圍：雖然A的長度小于1000.但是因為A[I]的范圍是10的九次方。所以這個字符串是沒必要都湊出來的。然后好像可以直接處理。數(shù)數(shù)的時候奇數(shù)遍歷。取值的時候下一個取值。大概思路是有了。我去實現(xiàn)下試試。
第一版代碼：

class RLEIterator {
    int[] arr;
    int idx = 0;
    public RLEIterator(int[] encoding) {
        this.arr = encoding;
    }
    
    public int next(int n) {
        for(int i = idx;i<arr.length;i+=2) {
            if(arr[i]>=n) {
                arr[i] -= n;
                idx = i;
                return arr[i+1];
            }else {
                n -= arr[i];
            }
        }
        idx = arr.length+1;
        return -1;
    }
}

/**
 * Your RLEIterator object will be instantiated and called as such:
 * RLEIterator obj = new RLEIterator(encoding);
 * int param_1 = obj.next(n);
 */

這個題果然比較簡單，做完了也沒覺得有什么坑點。然后這個代碼的性能還行。我再去看看性能第一的代碼:

class RLEIterator {

    int index;
    int[] encoding;
    public RLEIterator(int[] encoding) {
        index = 0;
        this.encoding = encoding;
    }

    public int next(int n) {
        int res = -1;
        while (index < encoding.length && n > 0){
            if(n > encoding[index]){
                n -= encoding[index];
                index += 2;
            }else {
                encoding[index] -= n;
                n = 0;
                res = encoding[index + 1];
            }
        }
        return res;
    }
}

差不多的思路，也沒啥兩點，下一題了。

股票價格跨度

題目：編寫一個 StockSpanner 類，它收集某些股票的每日報價，并返回該股票當日價格的跨度。今天股票價格的跨度被定義為股票價格小于或等于今天價格的最大連續(xù)日數(shù)（從今天開始往回數(shù)，包括今天）。例如，如果未來7天股票的價格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度將是 [1, 1, 1, 2, 1, 4, 6]。

示例：
輸入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
輸出：[null,1,1,1,2,1,4,6]
解釋：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被調(diào)用并返回 1，
S.next(80) 被調(diào)用并返回 1，
S.next(60) 被調(diào)用并返回 1，
S.next(70) 被調(diào)用并返回 2，
S.next(60) 被調(diào)用并返回 1，
S.next(75) 被調(diào)用并返回 4，
S.next(85) 被調(diào)用并返回 6。
注意 (例如) S.next(75) 返回 4，因為截至今天的最后 4 個價格
(包括今天的價格 75) 小于或等于今天的價格。
提示：
調(diào)用 StockSpanner.next(int price) 時，將有 1 <= price <= 10^5。
每個測試用例最多可以調(diào)用 10000 次 StockSpanner.next。
在所有測試用例中，最多調(diào)用 150000 次 StockSpanner.next。
此問題的總時間限制減少了 50%。

思路：怎么說呢，這個題還特別說了時間限制。暫時沒有什么特別的思路，我打算先暴力試水下。畢竟單個案例最多調(diào)用10000次。也就是說存儲空間上將肯定是夠用的。
第一版代碼：

class StockSpanner {
    List<Integer> list;
    public StockSpanner() {
        this.list = new ArrayList<Integer>();
    }
    
    public int next(int price) {
        int n = 0;
        list.add(price);
        for(int i = list.size()-1;i>=0;i--) {
            if(list.get(i) <= price) {
                n++;
            }else {             
                return n;
            }
        }
        return n;
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

我簡直起了怪了，我都做好了超時的準備，結(jié)果居然過了。神奇的一批。然后題目的標簽是棧。其實我覺得優(yōu)化點是跳躍尋找。比如前一天是10，今天比昨天還大的話就可以直接從前一天的前10個元素開始。因為比昨天還小的也一定比今天小。但是思路還不完善，所以先暴力法試試水，結(jié)果發(fā)現(xiàn)過了，然后繼續(xù)說這個題，優(yōu)化版我覺得還是像我剛剛上面說的那樣。然后具體的實現(xiàn)可能是用空間換時間，用一個二維數(shù)組來計數(shù)。大概思路是這樣。我去實現(xiàn)試試。
第二版代碼：

class StockSpanner {
    int[][] d = new int[10000][2];
    int idx = 0;
    public StockSpanner() {
    }
    
    public int next(int price) {
        //數(shù)組的第一個元素存當前值。第二個元素存比它小的個數(shù)
        d[idx][0] = price;
        int temp = idx-1;
        while(temp>=0 && d[temp][0]<=price) {
            temp -= d[temp][1]; 
        }
        d[idx][1] = idx-temp;
        idx++;
        return d[idx-1][1];
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

跟第一版比性能大大的提升了，但是還沒達到好的地步。不過我思路也就這樣了，我去看看性能第一的代碼:

class StockSpanner {

    private LinkedList<int[]> stack;

    public StockSpanner() {
        stack = new LinkedList<>();
    }
    
    public int next(int price) {
        int weight=1;
        while(!stack.isEmpty() && stack.peekLast()[0]<=price){
            int[] last = stack.pollLast();
            weight+=last[1];
        }
        stack.add(new int[]{price,weight});
        return weight;
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

思路和我之前說的差不多，但是人家用的是棧，我用的是二維數(shù)組。別的也沒啥特別的了，下一題。

水果成藍

題目：在一排樹中，第 i 棵樹產(chǎn)生 tree[i] 型的水果。你可以從你選擇的任何樹開始，然后重復執(zhí)行以下步驟：

把這棵樹上的水果放進你的籃子里。如果你做不到，就停下來。

移動到當前樹右側(cè)的下一棵樹。如果右邊沒有樹，就停下來。

請注意，在選擇一顆樹后，你沒有任何選擇：你必須執(zhí)行步驟 1，然后執(zhí)行步驟 2，然后返回步驟 1，然后執(zhí)行步驟 2，依此類推，直至停止。你有兩個籃子，每個籃子可以攜帶任何數(shù)量的水果，但你希望每個籃子只攜帶一種類型的水果。用這個程序你能收集的水果樹的最大總量是多少？

示例 1：
輸入：[1,2,1]
輸出：3
解釋：我們可以收集 [1,2,1]。
示例 2：
輸入：[0,1,2,2]
輸出：3
解釋：我們可以收集 [1,2,2]
如果我們從第一棵樹開始，我們將只能收集到 [0, 1]。
示例 3：
輸入：[1,2,3,2,2]
輸出：4
解釋：我們可以收集 [2,3,2,2]
如果我們從第一棵樹開始，我們將只能收集到 [1, 2]。
示例 4：
輸入：[3,3,3,1,2,1,1,2,3,3,4]
輸出：5
解釋：我們可以收集 [1,2,1,1,2]
如果我們從第一棵樹或第八棵樹開始，我們將只能收集到 4 棵水果樹。
提示：
1 <= tree.length <= 40000
0 <= tree[i] < tree.length

思路：這個題怎么說呢，我覺得重點應該是找到起摘點，根據(jù)題目的兩個條件來說，摘果子應該是連續(xù)的。所以說從哪個點開始摘很重要。因為只有兩個籃子。所以我可以換個說法：數(shù)組中只包含兩個數(shù)字的子數(shù)組最長是多少這個題的答案就是多少。大概思路就這樣了，我去代碼實現(xiàn)了。
第一版本代碼：

class Solution {
    public int totalFruit(int[] tree) {
        int max = 1;
        for(int i = 0;i<tree.length;i++) {
            if(i>0 && tree[i] == tree[i-1]) continue;
            int f = -1;
            for(int j = i+1;j<tree.length;j++) {
                if(f == -1) {
                     if(tree[j] != tree[i]) f = tree[j];                
                }else {
                    if(tree[j] != tree[i] && tree[j] != f) {
                        max = Math.max(j-i, max);
                        break;
                    }
                }
                if(j == tree.length-1) {
                    max = Math.max(max, j-i+1);
                    return max;
                }
            }
        }
        return max;
    }
}

思路還是挺清晰的。就像我上面說的子數(shù)組中元素種類不超過2個。打頭的算一個。所以額外記錄一個。如果出現(xiàn)了超出這兩種的元素當前元素開頭的數(shù)組不用計算了，走不下去了。
還有兩個小優(yōu)化點：一個是重復元素不用重復計算。所以當前元素和上一個相等直接跳過。
另外如果已經(jīng)遍歷到結(jié)尾了就不用再繼續(xù)判斷了。因為只能越往后數(shù)值越小。所以這個代碼ac了，性能還湊合。我直接去看性能第一的代碼了：

class Solution {
    public int totalFruit(int[] tree) {
        int res = 0, len = tree.length;
        int one = tree[0], two, begin = 0, end = 1; //2種樹的狀態(tài)(one, two)， one初始化為tree數(shù)組的第1個元素
        while (end < len && tree[end] == one)   //尋找two的初始值，以構成初始(one, two)
            ++end;
        if (end == len) return len; //若整個數(shù)組的元素都由初始的(one, two)所構成，則直接返回數(shù)組長度
        two = tree[end++];  //構成初始的(one, two)
        for (; end < len; ++end) {
            if (one != tree[end] && two != tree[end]) { //遇到了第3種樹
                res = Math.max(res, end - begin);   //更新最終返回結(jié)果
                one = tree[end - 1];    //(one, two)更新為(第3種樹的左邊的樹, 第3種樹)
                two = tree[end];
                begin = end - 1;    //更新由當前(one, two)所構成的連續(xù)子數(shù)組的左邊界
                while (tree[begin - 1] == one)   //向左尋找由one構成的連續(xù)子數(shù)組
                    --begin;
            }
        }
        return Math.max(res, end - begin);
    }
}

首先這種做法我其實本來是想這么寫來這，但是到了寫代碼的時候發(fā)現(xiàn)略復雜，所以換了思路。用雙指針的好處就是可以少做很多無用功。比如子數(shù)組的內(nèi)部不用重復計算了。例如1,2,1,2,1,2,3.如果是我的做法每個元素其實都要遍歷一遍，但是人家的代碼直接第一個1到了最后一個2.遇到3往前導一次。確實能理解人家的性能好。但是我最開始思路不清楚，所以代碼沒寫出來就換思路了，哎。下一題吧。

子數(shù)組的最小值之和

題目：給定一個整數(shù)數(shù)組 arr，找到 min(b) 的總和，其中 b 的范圍為 arr 的每個（連續(xù)）子數(shù)組。由于答案可能很大，因此 返回答案模 10^9 + 7 。

示例 1：
輸入：arr = [3,1,2,4]
輸出：17
解釋：
子數(shù)組為 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
最小值為 3，1，2，4，1，1，2，1，1，1，和為 17。
示例 2：
輸入：arr = [11,81,94,43,3]
輸出：444
提示：
1 <= arr.length <= 3 * 10^4
1 <= arr[i] <= 3 * 10^4

思路：這個題怎么說呢，首先數(shù)據(jù)范圍是30000.不算是很大。但是這種子數(shù)組的計算方式，感覺暴力法肯定會超時。然后題目的標簽是棧。這種題目第一反應單調(diào)棧沒跑了。暴力法的時間復雜度n方不行。用棧的話應該盡量o（n）時間復雜度，emmmm...我還是去試試代碼吧
第一版暴力超時代碼：

class Solution {
    public int sumSubarrayMins(int[] arr) {
        long ans = 0;
        for(int i = 0;i<arr.length;i++) {
            int temp = arr[i];
            ans += temp;
            for(int j = i+1;j<arr.length;j++) {
                temp = Math.min(temp, arr[j]);
                ans += temp;
            }
        }
        return (int)(ans%1000000007);
    }
}

我果然不能懷有僥幸心理。。然后繼續(xù)說，之前就說了這個題應該可以用單調(diào)棧來實現(xiàn)。能把時間復雜度大大的降低。然后看上面的代碼。因為正常的思維邏輯應該是：
找到所有的子數(shù)組，找到所有子數(shù)組的最小值
但是我們可以用逆向思維:
找到所有的最小值，然后我們判斷這個最小值能湊出來的子數(shù)組的個數(shù)。
然后說一個一眼能看出來的小規(guī)律：
一個元素是一個范圍的最小值。這個元素左邊x個元素，右邊y個元素。那么這個元素能組成的子數(shù)組的個數(shù)是x乘y。至于原因其實就是左邊x種可能，右邊y種，總數(shù)應該是笛卡爾積的形式。也就是xy。
接下來這個題就稍微好做一點了，我去敲第二版本代碼：

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int cost = 0;
        long ans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1); // 元素范圍1開始，所以填充-1永遠不會彈出
        for (int i = 0; i < n; i++) {
            while (stack.size() > 1 && arr[stack.peek()] > arr[i]) {
                int top = stack.pop();
                cost -= arr[top] * (top - stack.peek());
            }
            cost += arr[i] * (i - stack.peek());
            ans = cost + ans;
            stack.push(i);  // 壓棧
        }
        return (int)(ans%1000000007);
    }
}

我感覺思路啥的說的挺清楚了，就不多說了，我去看看性能第一的代碼：

class Solution {
    public int sumSubarrayMins(int[] arr) {
        final long factor = (long)Math.pow(10, 9) + 7;
        int[] dp = new int[arr.length + 1];
        int[] imin = new int[arr.length + 1];
        dp[0] = arr[0];
        imin[0] = -1;
        long result = dp[0];
        for (int i = 1; i < arr.length; i++) {
            int j = i - 1;
            while(j >= 0 && arr[j] > arr[i]) {
                j = imin[j];
            }
            imin[i] = j;
            dp[i] = (i - j) * arr[i] + (j >= 0 ? dp[j] : 0);
            result += dp[i];
        }

        return (int)(result % factor);
    }
}

大部分思路雷同，只不過人家是用dp的方式來記錄的。然后其實本質(zhì)上也還是分左右部分，然后乘法算出所有結(jié)果。這個題就不多說了，下一題。

你能在你最喜歡的那天吃到你最喜歡的糖果嗎？

題目：給你一個下標從 0 開始的正整數(shù)數(shù)組 candiesCount ，其中 candiesCount[i] 表示你擁有的第 i 類糖果的數(shù)目。同時給你一個二維數(shù)組 queries ，其中 queries[i] = [favoriteTypei, favoriteDayi, dailyCapi] 。你按照如下規(guī)則進行一場游戲：

你從第 0 天開始吃糖果。

你在吃完 所有 第 i - 1 類糖果之前，不能 吃任何一顆第 i 類糖果。

在吃完所有糖果之前，你必須每天 至少 吃 一顆 糖果。

請你構建一個布爾型數(shù)組 answer ，滿足 answer.length == queries.length 。answer[i] 為 true 的條件是：在每天吃 不超過 dailyCapi 顆糖果的前提下，你可以在第 favoriteDayi 天吃到第 favoriteTypei 類糖果；否則 answer[i] 為 false 。注意，只要滿足上面 3 條規(guī)則中的第二條規(guī)則，你就可以在同一天吃不同類型的糖果。請你返回得到的數(shù)組 answer 。

示例 1：
輸入：candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
輸出：[true,false,true]
提示：
1- 在第 0 天吃 2 顆糖果(類型 0），第 1 天吃 2 顆糖果（類型 0），第 2 天你可以吃到類型 0 的糖果。
2- 每天你最多吃 4 顆糖果。即使第 0 天吃 4 顆糖果（類型 0），第 1 天吃 4 顆糖果（類型 0 和類型 1），你也沒辦法在第 2 天吃到類型 4 的糖果。換言之，你沒法在每天吃 4 顆糖果的限制下在第 2 天吃到第 4 類糖果。
3- 如果你每天吃 1 顆糖果，你可以在第 13 天吃到類型 2 的糖果。
示例 2：
輸入：candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
輸出：[false,true,true,false,false]
提示：
1 <= candiesCount.length <= 105
1 <= candiesCount[i] <= 105
1 <= queries.length <= 105
queries[i].length == 3
0 <= favoriteTypei < candiesCount.length
0 <= favoriteDayi <= 109
1 <= dailyCapi <= 109

思路：今天兒童節(jié)，題目都這么有童心。雖然這個題目本身除了名字可愛點外并不友好，我仔細看了下好像每次判斷都是單獨的計算，所以我有個大膽的想法：首先用累加的方法算出前面的總和。然后只要天數(shù)<前綴。并且天數(shù)乘可吃最大值小于等于前面的個數(shù)。差不多思路就這樣，我去代碼試試吧。
第一版代碼：

class Solution {
    public boolean[] canEat(int[] candiesCount, int[][] queries) {
        long[] sum = new long[candiesCount.length+1];
        for(int i = 1;i<sum.length;i++) sum[i] = sum[i-1]+candiesCount[i-1];
        boolean[] ans = new boolean[queries.length];
        for(int i = 0;i<ans.length;i++) {
            long max = queries[i][2];
            int type = queries[i][0];
            int day = queries[i][1]+1;
            if(max*day<=sum[type] || sum[type+1]<day) {
                //這個類型之前的糖果大于等于到今天能吃的最大值，所以false
                //如果一天一顆糖到今天會把這個類型的糖都吃完了也false
                ans[i] = false;
            }else {
                ans[i] = true;
            }
        }
        return ans;                
    }
}

思路沒啥問題，就是這里天數(shù)是從0開始的，想要參與計算要+1才是表示第幾天，然后第二個坑點就是溢出！
連著wa了三次，兩次都是溢出的問題，第一次是sum溢出，第二次是max乘法溢出。然后面向測試案例編程，好不容易過了。
思路比較清晰，也沒啥好說的。這個代碼性能不是很好，我覺得應該是細節(jié)處理上的問題，我去看看性能第一的代碼：

class Solution {
    public boolean[] canEat(int[] candiesCount, int[][] queries) {
        int n = candiesCount.length;
        long[] preSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + candiesCount[i];
        }

        boolean[] ans = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int type = queries[i][0];
            long day = queries[i][1];
            long cap = queries[i][2];
            long min = day + 1;
            long max = min * cap;
            if (max > preSum[type] && min <= preSum[type + 1]) {
                ans[i] = true;
            }
        }
        return ans;
    }
}

差不多一樣一樣的思路，細節(jié)處理上因為默認都是false，所以只要填充true就行了。還有人家全部變量用的long，剩下其實大體的判斷是一樣的，這個題的性能相差不大，就這么過了吧。
本篇筆記就到這里，如果稍微幫到你了記得點個喜歡點個關注。也祝大家工作順順利利，生活健健康康！另外今天兒童節(jié)，也祝大家兒童節(jié)快樂吧~！