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

Bài này quá medium

Code: 
total= (totalSubArrays <= k) - (totalSubArrays <= k - 1)
Python: 
class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        def slidingWindows(nums, k):
            count = defaultdict(int)
            left = 0
            ans = 0
            for right in range(len(nums)):
                count[nums[right]] += 1
                while len(count) > k:
                    count[nums[left]] -= 1
                    if count[nums[left]] == 0:
                        count.pop(nums[left])

                    left += 1

                ans += right - left + 1

            return ans

        return slidingWindows(nums, k) - slidingWindows(nums, k - 1)
 
Java: 
class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return subarraysAtMostKDistinct(nums, k) - subarraysAtMostKDistinct(nums, k-1);
    }

    public int subarraysAtMostKDistinct(int[] nums, int k) {
        if(k == 0)
            return 0;
        int len=nums.length, left=0, right=0, countSubArr = 0;
        Map<Integer, Integer> frequency = new HashMap<>();
        while(right < len){
            int num = nums[right];
            int count = frequency.containsKey(num) ? frequency.get(num) : 0;
            frequency.put(num, count + 1);
            if(frequency.size() > k){
                while(frequency.size() > k && left < right){
                    if(frequency.get(nums[left]) == 1)
                        frequency.remove(nums[left]);
                    else
                        frequency.put(nums[left], frequency.get(nums[left]) - 1);
                    left++;
                }
            }
            countSubArr += right - left + 1;
            right++;
        }
        return countSubArr;
    }
}
 
cmajor said:
Đọc sai đề nên làm mãi mới ra :go:
Python: 
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        counter = Counter(nums)
        # print(counter)
        max_val = max(counter.keys())
        # print(max_val)
        if k > counter[max_val]:
            return 0
        count = 0
        ans = 0
        j = 0
        for i in range(n):
            if nums[i] == max_val:
                count += 1
            while j <= i and count >= k:
                ans += n - i
                j += 1
                if nums[j-1] == max_val:
                    count -= 1
        return ans
Không liên quan, mà muốn luyện hackerrank để phỏng vấn live-codeing thì vào mục nào vậy các thím? Solve leetcode dùng ide nên debug dễ quá
Click to expand...
nạp card mới dùng được debugger mà thím
 
Python: 
class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        counter = {}
        left = 0
        result, count_most_k, count_most_k_minus_one = 0, 0, 0

        for right, num in enumerate(nums):
            counter[num] = counter.get(num, 0) + 1

            while len(counter) > k:
                if counter[nums[left]] > 1:
                    counter[nums[left]] -= 1
                else:
                    del counter[nums[left]]
                left += 1
            count_most_k += (right - left + 1)

        counter = {}
        left = 0
        for right, num in enumerate(nums):
            counter[num] = counter.get(num, 0) + 1

            while len(counter) > k-1:
                if counter[nums[left]] > 1:
                    counter[nums[left]] -= 1
                else:
                    del counter[nums[left]]
                left += 1
            count_most_k_minus_one += (right - left + 1)
        
        result = count_most_k - count_most_k_minus_one
        return result
 
C++: 
class Solution {
public:
    int subMost(vector<int>& nums, int k) {
        auto re = 0;
        auto s = 0;
        unordered_map<int, int> fre;
        for (auto e = 0; e < nums.size(); ++e) {
            ++fre[nums[e]];
            while ((s <= e) && (fre.size() > k)) {
                auto tmp = nums[s];
                if (--fre[tmp] == 0) {
                    fre.erase(tmp);
                }
                ++s;
            }
            re += (e - s + 1);
        }
        return re;
    }
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return subMost(nums, k) - subMost(nums, k - 1);
    }
};
 
JavaScript: 
var subarraysWithKDistinct = function(nums, k) {
    let ans = u = uu = v = vv = 0, uuu = {}, vvv = {};
    for (const [i, j] of nums.entries()) {
        uuu[j] = (uuu[j] ?? 0) + 1;
        vvv[j] = (vvv[j] ?? 0) + 1;
        if (uuu[j] === 1) {
            uu++;
            while (uu > k) {
                if (!--uuu[nums[u++]]) {
                    uu--;
                }
            }
        }
        if (vvv[j] === 1) {
            vv++;
            while (vv >= k) {
                if (!--vvv[nums[v++]]) {
                    vv--;
                }
            }
        }
        ans += v - u;
    }
    return ans;
};
 
Java: 
class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return subArraysWithAMostKDistinct(nums, k) - subArraysWithAMostKDistinct(nums, k - 1);
    }

    public int subArraysWithAMostKDistinct(int[] nums, int k) {
        int left = 0, right = 0, max = 0;
        HashMap<Integer, Integer> map = new HashMap<>();

        while (right < nums.length) {
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);

            while(map.size() > k) {
                if (1 == map.get(nums[left])) map.remove(nums[left]);
                else map.put(nums[left], map.get(nums[left]) - 1);
                left++;
            }
            max += right - left + 1;
            right++;
        }
        return max;
    }
}
 
freedom.9 said:
Bài này quá medium

Code: 
total= (totalSubArrays <= k) - (totalSubArrays <= k - 1)
Click to expand...
+1, nghĩ ra cái Formula này hay đó fen.

Bổ sung thêm cách khác, vẫn là O(n) nhưng tính trực tiếp luôn. K dựa trên fomular bên trên. :beauty:
C++: 
class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        int ret = 0;
        for (int i = 0, j = 0, cur = 0; j < nums.size(); ++j) {
            freq[nums[j]]++;
            while(freq.size() > k ) {
                freq[nums[i]]--;
                if (freq[nums[i]] == 0) freq.erase(nums[i]);
                i++;
                cur = 0;
            }
            while (freq.size() == k && freq[nums[i]] > 1) {
                freq[nums[i]]--;
                i++;
                cur++;
            }
            if (freq.size() == k) ret += cur + 1;
        }
        return ret;
    }
};
 
Java: 
class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return subArrayWithK(nums, k) - subArrayWithK(nums, k-1);
    }
    public int subArrayWithK(int[] nums, int k) {
        Map<Integer,Integer> countNumber = new HashMap<>();
        int right = 0, left = 0, ans = 0, count = 0, n = nums.length;
        while(right < n){
            countNumber.put(nums[right],countNumber.getOrDefault(nums[right],0)+1);
            if(countNumber.get(nums[right]) == 1){
                count++;
            }
            while(count > k){
                countNumber.put(nums[left], countNumber.get(nums[left]) - 1);
                if(countNumber.get(nums[left]) == 0){
                    count--;
                }
                left++;
            }
            ans += right - left + 1;
            right++;
        }
        return ans;
    }
}
 
C#: 
public class Solution
{
    public int SubarraysWithKDistinct(int[] nums, int k)
    {
        return AtMostK(nums, k) - AtMostK(nums, k - 1);
    }
    
    private int AtMostK(int[] nums, int k)
    {
        int count = 0;
        int left = 0;
        Dictionary<int, int> map = new Dictionary<int, int>();

        for (int right = 0; right < nums.Length; right++)
        {
            if (!map.ContainsKey(nums[right]))
            {
                map.Add(nums[right], 0);
            }
            map[nums[right]]++;

            while (k < map.Count)
            {
                if (map[nums[left]] == 1)
                {
                    map.Remove(nums[left]);
                }
                else
                {
                    map[nums[left]]--;
                }
                left++;
            }

            count += right - left + 1;
        }
        return count;
    }
}
 
seastar said:
+1, nghĩ ra cái Formula này hay đó fen.

Bổ sung thêm cách khác, vẫn là O(n) nhưng tính trực tiếp luôn. K dựa trên fomular bên trên. :beauty:
C++: 
class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        int ret = 0;
        for (int i = 0, j = 0, cur = 0; j < nums.size(); ++j) {
            freq[nums[j]]++;
            while(freq.size() > k ) {
                freq[nums[i]]--;
                if (freq[nums[i]] == 0) freq.erase(nums[i]);
                i++;
                cur = 0;
            }
            while (freq.size() == k && freq[nums[i]] > 1) {
                freq[nums[i]]--;
                i++;
                cur++;
            }
            if (freq.size() == k) ret += cur + 1;
        }
        return ret;
    }
};
Click to expand...
Formula này chôm đc từ bài sliding windows này nè fence chứ ai nghĩ ra đâu
zFNuZTA.gif


Loading…

leetcode.com
Còn làm cách fence thì nhanh hơn rồi, tìm cái windows bằng k rồi tìm số subarrays cắt 2 đỉnh windows về phía trái nhỉ
Leetcode nó ra theo series này cũng hay cho ae hiểu kĩ hơn dù hơi chán cho mấy thằng làm lâu rồi
via theNEXTvoz for iPhone
 
hôm nay mãi mới có thời gian ngồi code
Python: 
class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        begin = 0
        count = {}
        diffNum, curCount, result = 0, 0, 0
        for i in range(len(nums)):
            num = nums[i]
            count[num] = count.get(num, 0) + 1
            if count[num] == 1:
                diffNum += 1
            if diffNum > k:
                curCount = 0
                while diffNum > k:
                    numBegin = nums[begin]
                    count[numBegin] -= 1
                    if count[numBegin] == 0:
                        diffNum -= 1
                    begin += 1
            if diffNum == k:
                while count[nums[begin]] > 1:
                    count[nums[begin]] -= 1
                    curCount += 1
                    begin += 1
                result += (curCount + 1)
        return result
 
Mãi mới ra. 3 indices, 3 counters. Beat time 5%, space 37% :too_sad:
Python: 
class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        # print(nums)
        n = len(nums)
        counter = Counter()
        j = 0
        ans = 0
        for i in range(n):
            small_counter = Counter()
            counter[nums[i]] += 1
            while len(counter) == k:
                small_counter[j] += 1
                ans += 1
                counter[nums[j]] -= 1
                if counter[nums[j]] == 0:
                    del counter[nums[j]]
                j += 1
            tmp_counter = counter.copy()
            z = j - 1
            # counter[nums[z + 1]] += 1
            while z >= 0:
                counter[nums[z]] += 1
                if len(counter) == k:
                    if small_counter[z] == 0:
                        ans += 1
                    z -= 1
                if len(counter) > k:
                    break
            counter = tmp_counter
        # print(res)
        # return len(res)
        return ans
 
Java: 
class Solution {
    public long count(int[] nums, int minK, int maxK) {
        long res = 0;
        int s = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > maxK || nums[i] < minK) {
                s = i + 1;
                continue;
            }
            res += (i - s + 1);
        }
        return res;
    }
    public long countSubarrays(int[] nums, int minK, int maxK) {
        return count(nums, minK, maxK) - count(nums, minK + 1, maxK)
                - count(nums, minK, maxK - 1) + count(nums, minK + 1, maxK - 1);
    }
}
Cũng formula, làm tuyến tính handle edge case khó quá
iJEQwtF.gif
 
Last edited:
GD-Cuong said:
Java: 
class Solution {
    public long count(int[] nums, int minK, int maxK) {
        long res = 0;
        int s = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > maxK || nums[i] < minK) {
                s = i + 1;
                continue;
            }
            res += (i - s + 1);
        }
        return res;
    }
    public long countSubarrays(int[] nums, int minK, int maxK) {
        return count(nums, minK, maxK) - count(nums, minK + 1, maxK)
                - count(nums, minK, maxK - 1) + count(nums, minK + 1, maxK - 1);
    }
}
Cũng formula, làm tuyến tính handle edge case khó quá
iJEQwtF.gif
Click to expand...
Java: 
class Solution {
    public boolean inRange(int num, int minK, int maxK) {
        return num >= minK && num <= maxK;
    }
    public long countSubarrays(int[] nums, int minK, int maxK) {
        boolean upperBound = false;
        boolean lowerBound = false;
        int l = 0;
        int r=0;
        int lastMax=0;
        int lastMin=0;
        int count = 1;
        long ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (inRange(nums[i], minK, maxK)) {
                if (nums[i] == minK) {
                    lowerBound = true;
                    lastMin = i;
                    r=lastMax;
                }
                if (nums[i] == maxK) {
                    upperBound=true;
                    lastMax=i;
                    r = lastMin;
                }
                if (lowerBound && upperBound) {
                    while(l<r) {
                        l++;
                        count++;
                    }
                    ans += count;
                }
            } else {
                lowerBound = false;
                upperBound=false;
                count = 1;
                l = i + 1;
            }
        }
        return ans;
    }
}
 
Last edited:
JavaScript: 
var countSubarrays = function(nums, minK, maxK) {
    const n = nums.length;
    let j = 0, l = null, h = null, ans = 0;
    for (let i = 0; i < n; i++) {
        if (nums[i] < minK || nums[i] > maxK) {
            j = i + 1;
            l = h = null;
            continue;
        }
        if (nums[i] === minK) {
            l = i;
        }
        if (nums[i] === maxK) {
            h = i;
        }
        if (l !== null && h !== null) {
            ans += Math.min(l, h) - j + 1;
        }
    }
    return ans;
};
 
Code chạy được thôi chứ xem giải của chúng nó nhìn mượt hơn hẳn :sad:
Python: 
class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        begin, result = 0, 0
        count = {}
        curCount = 0
        for idx in range(len(nums)):
            num = nums[idx]
            if num < minK or num > maxK:
                count = {}
                begin = idx + 1
                curCount = 0
            else:
                count[num] = count.get(num, 0) + 1
                if count.get(minK, 0) > 0 and count.get(maxK, 0) > 0:
                    while (nums[begin] != minK and nums[begin] != maxK) or (nums[begin] == minK and count[minK] > 1) or (nums[begin] == maxK and count[maxK] > 1):
                        count[nums[begin]] -= 1
                        curCount += 1
                        begin += 1
                    result += (curCount + 1)
        return result
 
LmaoSuVuong said:
Java: 
class Solution {
    public boolean inRange(int num, int minK, int maxK) {
        return num >= minK && num <= maxK;
    }
    public long countSubarrays(int[] nums, int minK, int maxK) {
        boolean upperBound = false;
        boolean lowerBound = false;
        int l = 0;
        int r=0;
        int lastMax=0;
        int lastMin=0;
        int count = 1;
        long ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (inRange(nums[i], minK, maxK)) {
                if (nums[i] == minK) {
                    lowerBound = true;
                    lastMin = i;
                    r=lastMax;
                }
                if (nums[i] == maxK) {
                    upperBound=true;
                    lastMax=i;
                    r = lastMin;
                }
                if (lowerBound && upperBound) {
                    while(l<r) {
                        l++;
                        count++;
                    }
                    ans += count;
                }
            } else {
                lowerBound = false;
                upperBound=false;
                count = 1;
                l = i + 1;
            }
        }
        return ans;
    }
}
Click to expand...
Code chạy được thì không khó, nhưng sắp xếp logic cho gọn thì rối rắm phết
JhHSQ2y.gif
 
JavaScript: 
function countSubarrays(nums: number[], minK: number, maxK: number): number {
    let res = 0, start = 0, minFound = false, maxFound = false;
    let minStart = 0, maxStart = 0;

    for (let i = 0; i < nums.length; i++) {
        let num = nums[i]
        if (num > maxK || num < minK) {
            start = i + 1
            minFound = false;
            maxFound = false
        }

        if (num === minK) {
            minStart = i;
            minFound = true;
        }

        if (num === maxK) {
            maxStart = i;
            maxFound = true
        }

        if (minFound && maxFound) {
            res += Math.min(minStart, maxStart) - start + 1
        }
    }

    return res
};
 

Similar threads

Masterchiefs
8 tờ báo Mỹ kiện OpenAI và Microsoft
Replies
9
Views
731
porpro84
porpro84
T
kiến thức Kèo play to earn miễn phí - Delabs Game
Replies
4
Views
110
Tranviethai98
T
T
kiến thức Kèo play to earn miễn phí - Delabs Games
Replies
4
Views
209
Tranviethai98
T
elementary
Ta thay đổi trước khi Google thay đổi
2 3
Replies
58
Views
4K
ProfessorX
ProfessorX
Masterchiefs
Núi lửa ở Nam Cực phun vàng thật mỗi ngày
2
Replies
24
Views
3K
xuccam2
xuccam2

Share this page

Back
Top