LeetCode Week 1 - Array

#11-Container With Most Water.cpp

// 從兩頭開始算容積，接著把矮的一邊往內縮持續比對
// 時間複雜度: O(n) / 空間複雜度 O(1)
class Solution {
public:
    int maxArea(vector<int>& height) {
        int result = 0;
        int length = height.size();
        int left = 0;
        int right = length - 1;
        int containerWidth = 0;
        int containerHeight = 0;
        int containerSize = 0;
        
        while(left < right){
            containerWidth = right - left;
            containerHeight = height[left];
            if(height[right] < containerHeight){
                containerHeight = height[right];
            }
            
            containerSize = containerWidth * containerHeight;
            if(containerSize > result){
                result = containerSize;
            }
            
            if(height[left] < height[right]){
                left ++;
            }else{
                right --;
            }
        }
        
        return result;
    }
};

#15-3Sum.cpp

// 先將陣列排序，接著將 3sum 簡化成 2sum 問題
// 途中要記得跳過重複的 element 避免答案重複
// 時間複雜度: O(n^2), 空間複雜度: O(1)
// *註記: 因為對 c++ 不熟，一開始 nextNonRepeatedValue 傳入 vector 沒有傳址 (&)，導致超時錯誤
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        
        if(nums.size() < 3){
            return result;
        }
        
        std::sort (nums.begin(), nums.end());
        for(int i=0; i < nums.size() - 2; i++){            
            int left = i+1;
            int right = nums.size() - 1;
            
            if(nums[i] > 0){
                break;
            }
            
            if(i>0 && nums[i] == nums[i-1]){
                continue;
            }
            
            while(left < right){
                // cout << left << ":" << right << endl;
                int twoSum = nums[left] + nums[right];
                
                if(nums[i] + twoSum == 0){
                    int _answer[] = { nums[i], nums[left], nums[right] }; 
                    int n = sizeof(_answer) / sizeof(_answer[0]); 
                    vector<int> answer(_answer, _answer + n);
                    
                    result.push_back(answer);
                    left = this -> nextNonRepeatedValue(nums, left, right-1, false);
                    right = this -> nextNonRepeatedValue(nums, right, left+1, true);
                } else if(nums[i] + twoSum > 0){
                    if(nums[i] > 0 && nums[left] > 0){
                        break;
                    }
                    
                    right = this -> nextNonRepeatedValue(nums, right, left+1, true);
                } else {
                    if(nums[i] < 0 && nums[right] < 0){
                        break;
                    }
                    
                    left = this -> nextNonRepeatedValue(nums, left, right-1, false);
                }     
            }
        }
        
        return result;
    }
    
    private: int nextNonRepeatedValue(vector<int>& vec, int start, int end, bool dir){
        if(dir==true){
            while(vec[start] == vec[start-1] && start > end){
                start--;
            }
            start--;
        }else{
            while(vec[start] == vec[start+1] && start < end){
                start++;
            }
            start++;
        }
        return start;
    }
};

#16-3Sum Closest.cpp

// 類似於 3sum，先將 array 排序後，同樣先解化為 2sum，只是改成比對最接近的組合
// 過程中判斷 +/- 遇到取絕對值正負號轉換有點卡住，但整體還算簡單
// 時間複雜度: O(n^2), 空間複雜度: O(1)
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        
        int result = INT_MAX - abs(target), sum=0, isMoreClose=false;
        for(int i=0; i < nums.size()-2; i++){            
            int l=i+1, r = nums.size()-1;
            
            while(l<r){
                int sum =  nums[i] + nums[l] + nums[r];
                
                isMoreClose = abs(sum - target) < abs(result - target);
                if(isMoreClose){
                    result = sum;
                }
                
                int _target = target - nums[i];
                int towSum = nums[l] + nums[r];
                if( towSum > _target){
                    r--;
                }else{
                    l++;
                }
            }
        }
        return result;
    }
};

#18-4Sum.cpp

// 一樣是 2sum 家族變形
// 時間複雜度: O(n^3), 空間複雜度: O(1)
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        
        if(nums.size() < 3){
            return ans;
        }
        
        sort(nums.begin(), nums.end());
        int sum = 0;
        for(int i=0; i<nums.size() - 3;){
            for(int j=i+1; j < nums.size() - 2;){
                int l=j+1, r=nums.size()-1;
                
                // cout<< i << j << l << endl;
                while(l<r){
                    sum = nums[i]+nums[j]+nums[l]+nums[r];
                    if(sum==target){
                        vector<int> arr = { nums[i],nums[j],nums[l],nums[r]};
                        ans.push_back(arr);
                        l++;
                        while(l<r && nums[l] == nums[l-1])l++;
                        r--;
                        while(l<r && nums[r] == nums[r+1])r--;
                    }else if(sum>target){
                        r--;
                    }else{
                        l++;
                    }
                }
                j++;
                while(nums[j]==nums[j-1] && j < nums.size() - 2){
                    j++;
                }
            }
            i++;
            while(nums[i]==nums[i-1] && i<nums.size() - 3){
                i++;
            }
        }
        return ans;
    }
};

#31-Next Permutation.cpp

// 花了點時間研究，把 1234 的排列組合依照題目按小到大排序，觀察到相鄰兩者的變化規則如下
// 從最後一個數字開始往前找，如果找到第一個小於該數(j)，則兩數兌換，且 array 在 j 位置之後的子陣列由小到大排序
// 如果最後一個數字找不到，則 loop 完後換倒數第二個直到結束
// ex. 132 -> 213: 2 往前找到 1 兩者對調 231，接著 pos 0 之後要排序變成 213 
// 時間複雜度: O(n^2), 空間複雜度: O(1)
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int temp = 0;
        
        int nextSmallPos = -1;
        int swap1 = 0;
        int swap2 = 0;
        for(int i=nums.size()-1; i > 0; i--){
            for(int j=i-1; j >= 0; j--){
                if(nums[i] > nums[j]){
                    if(j > nextSmallPos){
                        swap1 = i;
                        swap2 = j;
                        nextSmallPos = j;
                    }
                    break;
                }
            }
        }
        swap(nums[swap1], nums[swap2]);
        
        sort(nums.begin() + nextSmallPos + 1, nums.end());
    }
};