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

  • Người tạo chủ đề Người tạo chủ đề _Gia_Cat_Luong_
  • Ngày bắt đầu Ngày bắt đầu
Trạng thái
Không mở để trả lời thêm.
Java: 
class Solution {
    public boolean checkIfExist(int[] arr) {
        Set<Integer> set = new HashSet<>();
        for (int num : arr) {
            if (set.contains(num * 2)) return true;
            if (num % 2 == 0 && set.contains(num / 2)) return true;
            set.add(num);
        }
        return false;
    }
}
:big_smile:
 
PHP: 
class Solution {
    /**
     * @param Integer[] $arr
     * @return Boolean
     */
    function checkIfExist($arr) {
        $dict = [];
        foreach ($arr as $n) {
            if (isset($dict[$n*2])) return true;
            if (is_int($n/2) && isset($dict[$n/2])) return true;

            $dict[$n] = true;
        }

        return false;
    }
}
 
Sửa lần cuối:
C++: 
class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        auto numbers = unordered_set<int>();
        for (auto const& num : arr) {
            if (numbers.count(num * 2) || 
                ((num & 1) == 0 && numbers.count(num >> 1))) return true;
            numbers.insert(num);
        }
        return false;
    }
};
 
Sửa lần cuối:
Tinh Hoa Đông Lào đã nói:
Cơm thêm https://leetcode.com/problems/find-the-longest-equal-subarray/

Lần đầu tự mò ra beat 100% TC nhưng không hiểu vì sao nó chạy được :big_smile:
Nhấp để mở rộng...
Java: 
class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int l=1;
        int r = nums.size();
        int ans =1;
        while(l<=r){
            int mid = l+(r-l)/2;
            if(condition( nums, mid,k)){
                ans = mid;
                l=mid+1;
            }else{
                r = mid-1;
            }
        }
        return ans;
    }
    public boolean condition(List<Integer> nums, int len, int k){
        Map<Integer,Integer> freq = new HashMap();
        int max=0;
        for(int i =0 ; i < len+k && i<nums.size();i++){
            int num =nums.get(i);
            freq.put(num,freq.getOrDefault(num, 0)+1 );
            max=Math.max(max, freq.get(num));
            if(max>=len) return true;
        }
        for(int i=len+k;i<nums.size();i++){
            int r = nums.get(i);
            int l = nums.get(i-len-k);
            freq.put(r,freq.getOrDefault(r, 0)+1 );
            freq.put(l,freq.get(l)-1 );
            max=Math.max(max, freq.get(r));
            if(max>=len) return true;
        }
        return false;
    }
}
làm cách BS xong nhìn thấy len của cửa sổ = max+k;
Java: 
class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int ans =1;
        int l=0;
        Map<Integer,Integer> freq = new HashMap();
        for(int i =0 ; i<nums.size();i++){
            int num =nums.get(i);
            freq.put(num,freq.getOrDefault(num, 0)+1 );
            while(i-l>ans+k){
                freq.put(nums.get(l),freq.get(nums.get(l))-1 );
                l++;
            }ans=Math.max(ans, freq.get(num));
        }
        return ans;
    }

}
mà sao cơm của bác toàn trượt cửa sổ v :sad:
 
LmaoSuVuong đã nói:
Java: 
class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int l=1;
        int r = nums.size();
        int ans =1;
        while(l<=r){
            int mid = l+(r-l)/2;
            if(condition( nums, mid,k)){
                ans = mid;
                l=mid+1;
            }else{
                r = mid-1;
            }
        }
        return ans;
    }
    public boolean condition(List<Integer> nums, int len, int k){
        Map<Integer,Integer> freq = new HashMap();
        int max=0;
        for(int i =0 ; i < len+k && i<nums.size();i++){
            int num =nums.get(i);
            freq.put(num,freq.getOrDefault(num, 0)+1 );
            max=Math.max(max, freq.get(num));
            if(max>=len) return true;
        }
        for(int i=len+k;i<nums.size();i++){
            int r = nums.get(i);
            int l = nums.get(i-len-k);
            freq.put(r,freq.getOrDefault(r, 0)+1 );
            freq.put(l,freq.get(l)-1 );
            max=Math.max(max, freq.get(r));
            if(max>=len) return true;
        }
        return false;
    }
}
làm cách BS xong nhìn thấy len của cửa sổ = max+k;
Java: 
class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int ans =1;
        int l=0;
        Map<Integer,Integer> freq = new HashMap();
        for(int i =0 ; i<nums.size();i++){
            int num =nums.get(i);
            freq.put(num,freq.getOrDefault(num, 0)+1 );
            while(i-l>ans+k){
                freq.put(nums.get(l),freq.get(nums.get(l))-1 );
                l++;
            }ans=Math.max(ans, freq.get(num));
        }
        return ans;
    }

}
mà sao cơm của bác toàn trượt cửa sổ v :sad:
Nhấp để mở rộng...
đang học trượt cửa sổ, làm gần hết medium rồi, làm lấy số lượng, đấm hết mấy bài 1k5,1k6,1k7, còn lại mấy bài 1k8 với 2k3,2k5 :beat_shot:
1733069918123.png
 
Tinh Hoa Đông Lào đã nói:
Cơm thêm: https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum
bài này medium mà khoai, ko giải ra :too_sad:
Nhấp để mở rộng...
Java: 
class Solution {
    public static final int INF = 1_000_000_000;
    public int minSumOfLengths(int[] arr, int target) {
        List<int[]> subArray = new ArrayList<>();
        int end = -1;
        int n = arr.length;
        int[] lasting = new int[n + 1];
        Arrays.fill(lasting, INF);
        List<int[]> subsequence = new ArrayList<>();
        int sum = 0;
        for (int begin = 0; begin < n; begin++) {
            while (end + 1 < n) {
                if (sum >= target) {
                    break;
                }

                end++;
                sum += arr[end];
            }

            if (sum == target) {
                lasting[begin] = end - begin + 1;
                subsequence.add(new int[]{begin, end});
            }
            sum -= arr[begin];
        }

        for (int i = n - 1; i >= 0; i--) {
            lasting[i] = Math.min(
                lasting[i],
                lasting[i + 1]
            );
        }

        int minimum = INF;
        for (int[] sequence : subsequence) {
            int begin = sequence[0];
            end = sequence[1];
            minimum = Math.min(
                end - begin + 1 + lasting[end + 1],
                minimum
            );
        }

        if (minimum == INF) {
            return -1;
        }
        
        return minimum;
    }
}
Code hơi lòng vòng :big_smile: :big_smile: :big_smile:
 

Bác @freedom.9 có premium cho e lời giải thích cho lời giải bài này, cực khó hiểu, O(N)

Python: 
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        l = 0
        max_freq = 0
        d = defaultdict(int)

        for i in range(len(s)):
            d[s[i]] += 1

            if max_freq < d[s[i]]:
                max_freq = d[s[i]]

            if i - l + 1 - max_freq > k:
                d[s[l]] -= 1
                l += 1
       
        return len(s) - l
 
LmaoSuVuong đã nói:
4 bài hôm nay e giải dc hết, nhưng mà mình Q3 hết tiếng rưỡi r bác. vào live lại gia nhập 2q gang feed cho bác @freedom.9 :canny:
Nhấp để mở rộng...
Đã từ lâu toy ko còn hứng thú kêu Vozers vô contest nữa rồi :doubt:
Tinh Hoa Đông Lào đã nói:
Cơm thêm: https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum
bài này medium mà khoai, ko giải ra :too_sad:
Nhấp để mở rộng...
Python: 
class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        n = len(arr)
        def rightToLeft():
            dp = [-1]*n
            count = defaultdict(int)
            count[0] = n
            sumSofar = 0
            currentMin = inf
            for i in range(n - 1, -1, -1):
                sumSofar += arr[i]
                count[sumSofar] = i
                if sumSofar - target in count:
                    currentMin = min(currentMin, count[sumSofar - target] - i)

                dp[i] = currentMin

            return dp
        
        rightToLeftDp = rightToLeft()
        count = defaultdict(int)
        count[0] = -1
        sumSofar = 0
        currentMin = inf
        ans = inf
        for i in range(n - 1):
            sumSofar += arr[i]
            count[sumSofar] = i
            if sumSofar - target in count and rightToLeftDp[i + 1] != inf:
                ans = min(ans, i - count[sumSofar - target] + rightToLeftDp[i + 1])
                
        return -1 if ans == inf else ans
 
Tinh Hoa Đông Lào đã nói:

Bác @freedom.9 có premium cho e lời giải thích cho lời giải bài này, cực khó hiểu, O(N)

Python: 
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        l = 0
        max_freq = 0
        d = defaultdict(int)

        for i in range(len(s)):
            d[s[i]] += 1

            if max_freq < d[s[i]]:
                max_freq = d[s[i]]

            if i - l + 1 - max_freq > k:
                d[s[l]] -= 1
                l += 1
  
        return len(s) - l
Nhấp để mở rộng...

Approach 3: Sliding Window (Fast)​

Intuition​

Let's revisit the first approach, where we apply binary search to different lengths of substrings. Depending on whether a substring meets the specified conditions or not, we increase or decrease the length of the substring. We use a sliding window-based approach to test the validity condition.

Note that the size of the sliding window does not change while it moves across the string. We test to see if the window ever becomes valid. If it does, we try again from the beginning, increasing the window size (or decreasing it if it remains invalid). In this way, we try to find the longest valid window. But do we need to start at the beginning of the string again?

Recall that when a string of length l is valid, all its substrings form a valid string. Let's try looking at it from the other side. Suppose we have identified a valid substring/window of length l−1. To find an even longer valid window, we should try adding the next alphabet. This temporarily increases the size of the window to l. We check whether it forms a valid window or not. If not, we move the beginning of the window to the right, which resets the window size back to l−1 and effectively moves the window to the right.

We keep moving it until we reach a point where we find a valid window of size l. Now, we don't need to stop there. We can continue looking for a valid window of size l+1. We continue this process until the window hits the right edge of the string. The size of the window at the end would be our answer.

The key takeaway here is that once we have found a valid window, we don't need to decrease the size of it. The window keeps moving toward the right. At each step, even if the window becomes invalid, we never decrease its size. We increase the size only when we find a valid window of larger size.

Now let's look at it a bit more formally

We begin with a sliding window of size 0 positioned at the left edge of the string. We consider an empty window as valid.

start points at the first character of the window initially positioned at index 0. end points at the last character of the window initially positioned at index −1. We can see that the window's size is 0 (end+1−start=−1+1−0=0). Here, we also consult our old friend, the frequency map. It stores a map of characters to their frequencies in the window; we call it frequencyMap.

Our objective is to find the longest valid window. So, whenever we see a valid window, we try to expand its size by moving the end pointer forward. As we move the pointer forward, we update the frequencyMap as well. The frequency map helps us keep track of the character that appears most frequently in the window. We compare the frequency of the newly added character with the maximum frequency of any character seen so far - maxFrequency. We update maxFrequency when we find a new maximum.

The window size increases only when maxFrequency finds a new maximum. For this, we always want the following condition to hold true -

windowSize−maxFrequency<=k

We stop moving the end pointer forward, or in other words, stop expanding the window when it becomes invalid. Say the size of the window when it becomes invalid is l. We know the previous window with the size l−1 was valid. So, we move the prior window of length l−1 toward the right. To do so, the start pointer moves one step further. Remember that the end pointer had already moved, so we don't need to move the end pointer again.

At this point, the last valid window has moved one step to the right, but it might still be invalid. As explained earlier, we are only interested in larger windows, so we don't need to decrease the window size. We move the window of size i−1 further and further to the right until it becomes valid again.

If we come across a valid window, we try to expand it as much as possible, and the process continues until the end pointer reaches the rightmost alphabet of the string. At this point, the size of the window indicates the longest valid substring seen yet.

Python: 
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        start = 0
        frequency_map = {}
        max_frequency = 0
        longest_substring_length = 0
        for end in range(len(s)):
            frequency_map[s[end]] = frequency_map.get(s[end], 0) + 1

            # the maximum frequency we have seen in any window yet
            max_frequency = max(max_frequency, frequency_map[s[end]])

            # move the start pointer towards right if the current
            # window is invalid
            is_valid = (end + 1 - start - max_frequency <= k)
            if not is_valid:
                frequency_map[s[start]] -= 1
                start += 1

            # the window is valid at this point, store length
            # size of the window never decreases
            longest_substring_length = end + 1 - start

        return longest_substring_length
Bài này cách làm dễ nhất là cứ sliding window cho mỗi kí tự, có 26 kí tự nên giải chỉ cần 26n là đủ rồi
Cách của mình

Python: 
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        n = len(s)
        def slidingWindow(target):
            ans = k
            left = 0
            currentChange = 0
            for right in range(n):
                if s[right] != target:
                    currentChange += 1
                while currentChange > k:
                    if s[left] != target:
                        currentChange -= 1
                    
                    left += 1
                ans = max(ans, right - left  + 1)
            
            return ans
        ans = 0
        letters = set(s)
        for char in letters:
            ans = max(ans, slidingWindow(char))
        return ans
 
Sửa lần cuối:
e mới làm được 1 bài khá hay mời anh oem :adore:
Python: 
def build_row_graph(mat):
    m = len(mat)
    n = len(mat[0])
    adj = [defaultdict(list) for _ in range(m)]
    for r in range(m):
        pairs = sorted([(mat[r][c], c) for c in range(n)])

        i, j = 0, 0
        while i < n:
            while j < n and pairs[i][0] >= pairs[j][0]:
                j += 1
            if j == n:
                break
            adj[r][pairs[j][0]].append((r, pairs[i][1]))
            i += 1

    return adj

def build_col_graph(mat):
    m = len(mat)
    n = len(mat[0])
    adj = [defaultdict(list) for _ in range(n)]
    for c in range(n):
        pairs = sorted([(mat[r][c], r) for r in range(m)])

        i, j = 0, 0
        while i < m:
            while j < m and pairs[i][0] >= pairs[j][0]:
                j += 1
            if j == m:
                break
            adj[c][pairs[j][0]].append((pairs[i][1], c))
            i += 1

    return adj


class Solution:
    def maxIncreasingCells(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])

        adj_row = build_row_graph(mat)
        adj_col = build_col_graph(mat)

        @lru_cache(maxsize=None)
        def dp_row(r, value):
            d = 1
            for u, v in adj_row[r][value]:
                d = max(d, dp(u, v) + 1)
            return d

        @lru_cache(maxsize=None)
        def dp_col(c, value):
            d = 1
            for u, v in adj_col[c][value]:
                d = max(d, dp(u, v) + 1)
            return d

        @lru_cache(maxsize=None)
        def dp(r, c):
            value = mat[r][c]
            return max(dp_row(r, value), dp_col(c, value))
        
        res = max(
            dp(r, c) for r in range(m) for c in range(n)
        )
        dp_row.cache_clear()
        dp_col.cache_clear()
        dp.cache_clear()
        return res
 
Tinh Hoa Đông Lào đã nói:
Cơm thêm: https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum
bài này medium mà khoai, ko giải ra :too_sad:
Nhấp để mở rộng...
Bài này lấy ý tưởng tìm subarray ngắn nhất tổng bằng target thôi :sexy_girl:
Python: 
class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        INF = 10**9

        def sliding_window(nums):
            d = dict()
            d[0] = -1
            total = 0
            f = [INF] * len(nums)
            for i, num in enumerate(nums):
                total += num
                if total - target in d:
                    f[i] = i - d[total-target]
                d[total] = i
            for i in range(1, len(nums)):
                f[i] = min(f[i-1], f[i])
            return f
        
        l = sliding_window(arr)
        r = list(reversed(sliding_window(list(reversed(arr)))))

        res = INF
        for i in range(len(arr) - 1):
            res = min(res, l[i] + r[i+1])

        return res if res != INF else -1
 
Python: 
class Solution:
    def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
        result = -1
        m = len(searchWord)
        for i, word in enumerate(sentence.split()):
            if m > len(word):
                continue
            if word[:m] == searchWord:
                result = i + 1
                break
        return result
 
JavaScript: 
/**
 * @param {string} sentence
 * @param {string} searchWord
 * @return {number}
 */
var isPrefixOfWord = function(sentence, searchWord) {
    let arr = sentence.split(' ');
    for (let i=0; i<arr.length; i++) {
        if (arr[i].substring(0, searchWord.length) === searchWord)
            return i+1;
    }
    return -1;
};
 
Trạng thái
Không mở để trả lời thêm.
AD · 970×250

Chủ đề tương tự

Thach Sanh Mat Riu
Điều gì xảy ra nếu bạn uống nước chè xanh mỗi ngày?
2
Trả lời
22
Lượt xem
2K
dattenmoi
D
megume
thảo luận Hôm nay, buổi bình minh của AI robot đã đến
Trả lời
4
Lượt xem
1K
Toc Hong
Toc Hong
Lộc Tục
(Dịch) Cuộc điều tra của CBC/Radio-Canada tiết lộ công ty Việt Nam nhắm vào người Canada bằng tin giả AI để kiếm lời
2
Trả lời
30
Lượt xem
5K
dukeng995
dukeng995
Ti Amo
[Dịch] Công ty Việt Nam dùng tin giả do AI tạo ra để kiếm tiền — nhắm vào độc giả Canada
Trả lời
0
Lượt xem
1K
Ti Amo
Ti Amo
Gấu Ted
Độc giả ngày càng tin nhà báo hơn thương hiệu báo chí
Trả lời
10
Lượt xem
918
giayasics
giayasics
AD · 300×600

Thống kê chủ đề

Ngày tạo
_Gia_Cat_Luong_,
Người trả lời cuối
Vipluckystar,
Trả lời
17.755
Lượt xem
1.215.683
AD · 300×600

Chia sẻ trang này

AD · 300×600
Quay lại
Lên đầu trang