thảo luận Leetcode mỗi ngày

public class Solution
{
    public int FindLengthOfShortestSubarray(int[] arr)
    {
        var len = arr.Length;
        var l = -1;
        var r = -1;
        for (int i = 0; i < len - 1; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                l = i;
                break;
            }
        }

        for (int i = len - 1; i > 0; i--)
        {
            if (arr[i - 1] > arr[i])
            {
                r = i;
                break;
            }
        }

        var res = len;
        if (l >= r) return 0;

        if (arr[l] > arr[r])
        {
            int i = 0, j = r;
            while (i <= l)
            {
                if (j < len && arr[i] > arr[j])
                {
                    j++;
                }
                else
                {
                    res = Math.Min(res, j - i - 1);
                    i++;
                }
            }

            i = 0;
            j = r;
            while (j < len)
            {
                if (i <= l && arr[i] <= arr[j])
                {
                    i++;
                }
                else
                {
                    res = Math.Min(res, j - i);
                    j++;
                }
            }
        }
        else
        {
            res = r - l - 1;
        }

        return res;
    }
}

public class Solution {
    public IList<long> MaximumEvenSplit(long finalSum)
    {
        if (finalSum % 2 == 1) return [];
        var res = new List<long>();
        var i = 1;
       
        while (finalSum > 0)
        {
            var num = i * 2;
            if (finalSum <= num*2)
            {
                res.Add(finalSum);
                break;
            }
            else
            {
                res.Add(num);
                finalSum -= num;
                i++;
            }
        }
       
        return res;
    }
}

/**
 * @param {number[]} arr
 * @return {number}
 */
var findLengthOfShortestSubarray = function(arr) {
    let n = arr.length;
    let left = 0;
    let right = n - 1;
    while(left < n - 1 && arr[left] <= arr[left+1]) left++;
    while(right > 0 && arr[right] >= arr[right-1]) right--;
    if(right <= left) return 0; // already sorted

    const binarySearchNextIndexInRightSide = (low, high, i) =>{
        let result = -1;
        while(low <= high){
            const mid = low + Math.floor((high - low)/2);
            if(arr[mid] >= arr[i]) {
                high = mid - 1;
                result = mid;
            }
            else low = mid + 1;
        }
        return result;
    }

    let result = Math.min(n - left - 1, right);
    for(let i = 0; i <= left; i++){
        let nextIndexInRightSide = binarySearchNextIndexInRightSide(right, n - 1, i);
        if(nextIndexInRightSide === -1) break;
        let leftPart = i + 1;
        let rightPart = n - nextIndexInRightSide;       
        result = Math.min(n - (leftPart + rightPart), result)
    }
    return result;
};

class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        List<Integer> prev = new ArrayList<>();
        prev.add(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] >= arr[i - 1]) {
                prev.add(arr[i]);
                continue;
            }
            break;
        }

        if (prev.size() == arr.length) return 0;

        int maximumRemain = prev.size();
        int suffix = 1;
        for (int i = arr.length - 1; i>= prev.size(); i--) {
            int properPre = lowerBound(prev, arr[i]);
            maximumRemain = Math.max(
                suffix + properPre,
                maximumRemain
            );

            if (arr[i] >= arr[i - 1]) {
                suffix++;
                continue;
            }
            break;
        }

        return arr.length - maximumRemain;
    }

    public int lowerBound(List<Integer> prev, int value) {
        int left = 0, right = prev.size() - 1;
        int found = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (prev.get(mid) <= value) {
                found = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return found + 1;
    }
}

class Solution {
    public List<Long> maximumEvenSplit(long finalSum) {
        List<Long> res = new ArrayList();
        if(finalSum%2==1) return res;
        long half = finalSum/2;
        long i =1;
        while(half>=i){
            res.add(i*2);
            half-=i;i++;
        }
        res.set(res.size()-1,res.get(res.size()-1)+half*2);
        return res;
    }
}

func findLengthOfShortestSubarray(arr []int) int {
    n := len(arr)
    left, right := 0, n-1

    for left+1 < n && arr[left] <= arr[left+1] {
        left++
    }

    if left == n-1 {
        return 0
    }

    for right > 0 && arr[right-1] <= arr[right] {
        right--
    }

    r := min(n-1-left, right)
    for l := 0; l <= left; l++ {
        for right < n && arr[right] < arr[l] {
            right++
        }
        r = min(r, right-l-1)
    }

    return r
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        accum = [0]*(len(arr)-1)
        cnt=0
        for i in range(1,len(arr)):
            if arr[i-1]>arr[i]:
                cnt+=1
            accum[i-1]=cnt
        # print(accum)
        if cnt==0: return 0
        if cnt==len(arr)-1 : return len(arr)-1
        def check(a, ac, start, out):
            if start > 0 and start+out < len(a) and a[start-1]>a[start+out]: return False
            if start > 1 and ac[start-2]>0: return False
            if start+out<len(a) and ac[-1]-ac[start+out-1]>0: return False
            return True

        left=1
        right=len(arr)-1
        while left<=right:
            mid=(left+right)//2
            # print(left, mid, right)
            flag=False
            for i in range(0, len(arr)-mid+1):
                if check(arr,accum,i,mid):
                    flag=True
                    break
            # print(mid, i, flag)
            if flag: right=mid-1
            else: left=mid+1
        return left

class Solution:
    def maximumEvenSplit(self, finalSum: int) -> List[int]:
        if finalSum%2==1: return []
        res=[]
        c=2
        while finalSum>=1:
            n=finalSum-c
            if n<=c:
                res.append(finalSum)
                break
            res.append(c)
            c+=2
            finalSum=n
        return res

vector<int> resultsArray(vector<int>& nums, int k) {
    deque<int> dq;
    int n = nums.size();
    vector<int> res(nums.size() - k + 1);
    for (int l=0, r=0; r < n; ++r) {
        while (!dq.empty() && nums[r] != nums[dq.back()] + 1) {
            dq.pop_back();
        }
        dq.push_back(r);



        if (r < k - 1) {
            continue;
        }

        if (dq.size() == k) {
            res[r-k+1] = nums[dq.back()];
        } else {
            res[r-k+1] = -1;
        }

        if (l == dq.front()) {
            dq.pop_front();
        }
        ++l;
    }
    return res;
}