Introduction

  • 通常答案和前後有關聯，所以必須先前後掃描才可以得出答案。

Problems

238. Product of Array Except Self

給你一個vector<int> nums，輸出所有vector的乘積除了自己。

  1. 因為每個答案和除了自己之外，前後的乘積，所以使用two-pass。
  2. 先計算出自己以外的forward和backward，最後把兩個vector乘起來就是答案。

















vector<int> productExceptSelf(vector<int>& nums) {
    int sz = nums.size();
    vector<int> fw(sz, 1), bw(sz, 1);
    for(int i = 1; i < sz; ++i) {
        fw[i] = nums[i - 1] * fw[i - 1];
    }
        
    for(int i = sz - 2; i >= 0; --i) {
        bw[i] = nums[i + 1] * bw[i + 1];
    }
    
    vector<int> rtn(sz);
    for(int i = 0; i < sz; ++i)
        rtn[i] = fw[i] * bw[i];
        
    return rtn;
}

1493. Longest Subarray of 1's After Deleting One

給你一個vector<int>只有binary 0和1，一定要刪除一個element，試找出最長的連續1的subarray。

  1. 因為一定要刪除一個element，所以等於第i個的前面和後面連續的1的長度總和，所以使用two pass。
  2. 先計算forward和backward，再找出刪除一個element之後的最長subarray。


















int longestSubarray(vector<int>& nums) {
    int sz = nums.size();
    vector<int> bwd(sz), fwd(sz);
    bwd[0] = nums[0];
    for(int i = 1; i < sz; ++i) {
        if(nums[i]) bwd[i] = bwd[i - 1] + 1;
    }
    fwd[sz - 1] = nums[sz - 1];
    for(int i = sz - 2; i >= 0; --i) {
        if(nums[i]) fwd[i] = fwd[i + 1] + 1;
    }
    int ans{};
    for(int i = 0; i < sz; ++i) {
        ans = max(ans, (i - 1 >= 0 ? bwd[i - 1] : 0) + 
                       (i + 1 < sz ? fwd[i + 1] : 0));
        }
    return ans;
}
Select a repo