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

LmaoSuVuong · 2/8/25

anoldvozer1710.v2 đã nói:
sau khi đọc đề bài và lên voz thấy các vozer giải như rồng như hổ, tôi đã ngậm ngùi tắt tab và mở youtube bật
Women bu yiyang

giờ ngta test khả năng prompt ai giải algo rùi bác

gõ chay giải tay khổ răm quá dị

e biết mỗi reverse linked list thôi mà đã hoàn thành 800 câu lc r

ligerre · 2/8/25

Python:

0
        last_p = len(pos)-1
        
        while (first_p<=last_p) and (first_n<=last_n):
            if neg[first_n][0]>=2*minkey and pos[first_p][0]>=2*minkey:
                ans+=minkey*total_dif
                break
            if neg[first_n][0]<pos[first_p][0]:
                ans+=neg[first_n][0]
                neg[first_n][1]+=2
                pos[last_p][1]-=2
                total_dif-=2
                if neg[first_n][1]==0:
                    first_n+=1
                if pos[last_p][1]==0:
                    last_p-=1
            else:
                ans+=pos[first_p][0]
                pos[first_p][1]-=2
                neg[last_n][0]+=2
                total_dif-=2
                if pos[first_p][1]==0:
                    first_p+=1
                if neg[last_n][1]==0:
                    last_n-=1
        return ans

bài này hay phết mà miss vụ có thể cứ đổi với thằng nhỏ nhất nên lần đầu fail test 20.

aNotHeRNo0b · 2/8/25

Bài hôm nay tricky ở chỗ dùng cost bé nhất làm trung gian để chuyển

:>

Java:

class Solution {
    public long minCost(int[] basket1, int[] basket2) {
        TreeMap<Integer, Integer> totalFreq = getTotalFreq(basket1, basket2);
        for (Map.Entry<Integer, Integer> costFreq : totalFreq.entrySet()) {
            int appearence = costFreq.getValue();
            if (appearence % 2 == 1) {
                return -1;
            }
        }

        TreeMap<Integer, Integer> basket1Freq = new TreeMap<>();
        for (int cost : basket1) {
            basket1Freq.put(cost, basket1Freq.getOrDefault(cost, 0) + 1);
        }

        int numSwap = 0;
        for (Map.Entry<Integer, Integer> costFreq : totalFreq.entrySet())  {
            int cost = costFreq.getKey();
            int freq = costFreq.getValue();
            basket1Freq.put(cost, basket1Freq.getOrDefault(cost, 0) - freq / 2);

            if (basket1Freq.get(cost) > 0) {
                numSwap += basket1Freq.get(cost);
            }

            if (basket1Freq.get(cost) == 0) {
                basket1Freq.remove(cost);
            }
        }
        int minSwapCost = totalFreq.firstKey();

        long minCost = 0;
        for (Map.Entry<Integer, Integer> costFreq : basket1Freq.entrySet()) {
            int swapTime = Math.min(numSwap, Math.abs(costFreq.getValue()));
            int cost = costFreq.getKey();
            minCost += Math.min(1L * cost * swapTime, swapTime * 2L * minSwapCost);
            numSwap -= swapTime;
        }

        return minCost;
    }

    public TreeMap<Integer, Integer> getTotalFreq(int[] basket1, int[] basket2) {
        TreeMap<Integer, Integer> freq = new TreeMap<>();
        for (int cost : basket1) {
            freq.put(cost, freq.getOrDefault(cost, 0) + 1);
        }

        for (int cost : basket2) {
            freq.put(cost, freq.getOrDefault(cost, 0) + 1);
        }

        return freq;
    }
}

aNotHeRNo0b · 2/8/25

freedom.9 đã nói:
Bài cũng ko trap mấy, đm đang làm có cái loa thông báo emergency phải bỏ chạy giữa đêm cứ tưởng cháy mà chắc là có thằng nào bắn súng cmnr.
Có 2 case, 1 là direct swap. 2 là indirect qua thằng min, greedy thôi

Python:

class Solution: def minCost(self, basket1: List[int], basket2: List[int]) -> int: mn = min(min(basket1), min(basket2)) n = len(basket1) freq = defaultdict(int) for i in range(n): freq[basket1[i]] += 1 freq[basket2[i]] -= 1 total = [] for key, val in freq.items(): if val % 2: return -1 total += [key]*abs(val//2) total = sorted(total) cost = 0 for i in range(len(total)//2): cost += min(2*mn, total[i]) return cost

via theNEXTvoz for iPhone

._. Nếu bác gặp đối tượng xả súng thì quang ngay 1 bài Segment Tree để gây choáng, sau đó bồi thêm một cước DP vào mõm nó. Cuối cùng rút cây dân chủ Greedy ra

freedom.9 · 2/8/25

aNotHeRNo0b đã nói:
._. Nếu bác gặp đối tượng xả súng thì quang ngay 1 bài Segment Tree để gây choáng, sau đó bồi thêm một cước DP vào mõm nó. Cuối cùng rút cây dân chủ Greedy ra

Gặp đối tượng xả chắc đái mẹ ra quần

bữa mới qua cách nhà 5 phút nó xả ở cái outlet 7 mạng ra đi, mãi cũng quen sống chết có số rồi fen

via theNEXTvoz for iPhone

small-lambda · 2/8/25

aNotHeRNo0b đã nói:
._. Nếu bác gặp đối tượng xả súng thì quang ngay 1 bài Segment Tree để gây choáng, sau đó bồi thêm một cước DP vào mõm nó. Cuối cùng rút cây dân chủ Greedy ra

chắc xả súng định kỳ để giá thuê nhà đừng tăng đó, nên thông cảm cho họ

dhl001 · 3/8/25

Java:

class Solution {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int n = fruits.length;
        int[] postLeft = new int[n];
        int[] totalLeft = new int[n];
        int[] postRight = new int[n];
        int[] totalRight = new int[n];
        int[] dp = new int[n];
        int nearestLeft = findLeft(fruits, startPos);
        for (int i = nearestLeft; i >= 0; i--) {
            if ((startPos - fruits[i][0] > k))
                break;
            postLeft[i] = k - Math.abs(startPos - fruits[i][0]);
            totalLeft[i] = ((i < n - 1) ? totalLeft[i + 1] : 0) + fruits[i][1];
        }
        for (int i = (nearestLeft + 1); i < n; i++) {
            if (fruits[i][0] - startPos > k)
                break;
            postRight[i] = k - Math.abs(startPos - fruits[i][0]);
            totalRight[i] = ((i > 0) ? totalRight[i - 1] : 0) + fruits[i][1];
        }
        int max = -1;
        for (int i = nearestLeft; i >= 0; i--) {
            int pos = findLeft(fruits, postLeft[i] + fruits[i][0]);
            int valueRight = totalRight[pos];
            dp[pos] = totalLeft[i] + valueRight;
            if (max < dp[pos]) {
                max = dp[pos];
            }
        }

        for (int i = nearestLeft + 1; i < n; i++) {
            int pos = findRight(fruits, fruits[i][0] - postRight[i]);
            int valueLeft = totalLeft[pos];
            dp[pos] = valueLeft + totalRight[i];
            if (max < dp[pos]) {
                max = dp[pos];
            }
        }

        return max;
    }

    private int findLeft(int[][] fruits, int crrPos) {
        int l = 0;
        int r = fruits.length - 1;
        int res = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (fruits[mid][0] == crrPos)
                return mid;

            if (fruits[mid][0] < crrPos) {
                res = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return res;
    }

    private int findRight(int[][] fruits, int crrPos) {
        int l = 0;
        int r = fruits.length - 1;
        int res = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (fruits[mid][0] == crrPos)
                return mid;

            if (fruits[mid][0] < crrPos) {
                l = mid + 1;
            } else {
                r = mid - 1;
                res = mid;
            }
        }
        return res;
    }
}

Mắt Xích Yếu · 3/8/25

bài hôm nay sao nhìn cách giải thì ko khó mà implement sai nhiều v~ :sweat:

cop sol luôn cho lẹ

Bo_MinhAnh · 3/8/25

LC 3477

Java:

class Solution {
    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        return Arrays.stream(fruits).map(f -> IntStream.range(0, baskets.length).filter(
            j -> f <= baskets[j]).map(j -> baskets[j] = 0).findFirst().orElse(1)).sum();
    }
}

dhl001 · 3/8/25

freedom.9 đã nói:
Gặp đối tượng xả chắc đái mẹ ra quần

bữa mới qua cách nhà 5 phút nó xả ở cái outlet 7 mạng ra đi, mãi cũng quen sống chết có số rồi fen

via theNEXTvoz for iPhone

thím ở đâu mà nguy hiểm thế

anoldvozer1710.v2 · 3/8/25

Bài này tôi tính ra 4 tình huống là trái hết, phải hết, sang trái rồi sang phải, sang phải rồi sang trái.

Mà lúc tính vào cứ bị nhầm mấy chỗ lower bound, upper bound, <=, >=

Tắt cụ đi nhìn ngứa cả mắt

ligerre · 3/8/25

Python:

class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        def check_dis(start,end):
            if end<startPos:
                return startPos-start
            elif start>startPos:
                return end-startPos
            else:
                return end-start + min(startPos-start,end-startPos)
        
        j=0
        ans = 0
        total = 0
        for i in range(len(fruits)):
            if i>0:
                total-=fruits[i-1][1]
            if j<=i:
                total=0
                j=i
            while j<len(fruits) and check_dis(fruits[i][0],fruits[j][0])<=k:
                total+=fruits[j][1]
                
                j+=1
            ans=max(ans,total)
        return ans

lười tạo prefix sum nên lỗi 1 ít nên lần nộp 2 mới AC. Thôi đi làm viên thuốc cảm.

dhl001 · 4/8/25

đầu tuần ez

Java:

class Solution {
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        int l = 0;
        int r = 0;
        Map<Integer, Integer> counter = new HashMap<>();
        int res = -1;
        while (r < n) {
            counter.compute(fruits[r], (k, v) -> v == null ? 1 : v + 1);
            while (counter.size() > 2) {
                var crr = counter.get(fruits[l]);
                if (crr == 1) {
                    counter.remove(fruits[l]);
                } else
                    counter.put(fruits[l], crr - 1);
                l++;
            }
            res = Math.max(res, r - l + 1);
            r++;
        }
        return res;
    }
}

nchhnchh · 4/8/25

Python:

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        result = 0
        left = 0
        n = len(fruits)
        fruit_map = defaultdict(int)

        for right in range(n):
            if not fruits[right] in fruit_map:
                while len(fruit_map) == 2:
                    if fruit_map[fruits[left]] == 1:
                        del fruit_map[fruits[left]]
                    else:
                        fruit_map[fruits[left]] -= 1
                    left += 1
            fruit_map[fruits[right]] += 1
            result = max(result, right - left + 1)
        return result

Mắt Xích Yếu · 4/8/25

C-like:

func totalFruit(fruits []int) int {
    freq := make(map[int]int)
    l:=0
    cnt:=0
    res :=1
    for r, v := range fruits {
        if freq[v] == 0 {
            cnt++
        }
        freq[v]++
        for cnt>2{
            freq[fruits[l]]--
            if freq[fruits[l]] == 0 {
                cnt--
            }
            l++
        }
        res = max(res,r-l+1)
    }
    return res
 
}

cái map trong go hiệu suất hơi cùi nhỉ, xài map cái từ code vài ms lên code 30ms
đã từng có bài e spam so sánh value của 2 giá trị trong map (bỏ trong điều kiện while loop), thuật toán tính chỗ đó O(1) thôi mà submit ăn tle. đổi code đó y chang sang java thì pass :adore:

Phó GOAT · 4/8/25

Java:

class Solution {
    public int totalFruit(int[] fruits) {
        int res = 0, n = fruits.length;
        Map<Integer, Integer> cnt = new HashMap<>();
        int l = 0, r = 0;
        while (r < n) {
            cnt.put(fruits[r], cnt.getOrDefault(fruits[r], 0) + 1);
            while (cnt.size() > 2) {
                cnt.put(fruits[l], cnt.get(fruits[l]) - 1);
                if (cnt.get(fruits[l]) == 0) cnt.remove(fruits[l]);
                l++;
            }
            res = Math.max(res, r - l + 1);
            r++;
        }
        return res;
    }
}

dhl001 · 4/8/25

Mắt Xích Yếu đã nói:
C-like:

func totalFruit(fruits []int) int { freq := make(map[int]int) l:=0 cnt:=0 res :=1 for r, v := range fruits { if freq[v] == 0 { cnt++ } freq[v]++ for cnt>2{ freq[fruits[l]]-- if freq[fruits[l]] == 0 { cnt-- } l++ } res = max(res,r-l+1) } return res }

cái map trong go hiệu suất hơi cùi nhỉ, xài map cái từ code vài ms lên code 30ms
đã từng có bài e spam so sánh value của 2 giá trị trong map (bỏ trong điều kiện while loop), thuật toán tính chỗ đó O(1) thôi mà submit ăn tle. đổi code đó y chang sang java thì pass

O(1) về lý thuyết, thực tế sẽ còn overhead nữa.
bài này dùng mảng int[] để count thì nhanh khỏi bàn

aNotHeRNo0b · 4/8/25

Java:

class Solution {
    public static final int MAX_FRUIT = 100_001;
    public int totalFruit(int[] fruits) {
        int[] counter = new int[MAX_FRUIT];
        int numDistinctFruit = 0;
        int n = fruits.length;

        int end = 0;
        int maxFruit = 0;
        for (int begin = 0; begin < n; begin += 1) {
            while (end < n && numDistinctFruit <= 2) {
                maxFruit = Math.max(maxFruit, end - begin);

                counter[fruits[end]] += 1;
                if (counter[fruits[end]] == 1) {
                    numDistinctFruit += 1;
                }
                end += 1;
            }

            if (numDistinctFruit <= 2) {
                maxFruit = Math.max(maxFruit, end - begin);
            }

            counter[fruits[begin]] -= 1;
            if (counter[fruits[begin]] == 0) {
                numDistinctFruit -= 1;
            }
        }

        return maxFruit;
    }
}

Loay hoay mãi mới giải được @@

LmaoSuVuong · 4/8/25

aNotHeRNo0b đã nói:

Java:

class Solution {
    public static final int MAX_FRUIT = 100_001;
    public int totalFruit(int[] fruits) {
        int[] counter = new int[MAX_FRUIT];
        int numDistinctFruit = 0;
        int n = fruits.length;

        int end = 0;
        int maxFruit = 0;
        for (int begin = 0; begin < n; begin += 1) {
            while (end < n && numDistinctFruit <= 2) {
                maxFruit = Math.max(maxFruit, end - begin);

                counter[fruits[end]] += 1;
                if (counter[fruits[end]] == 1) {
                    numDistinctFruit += 1;
                }
                end += 1;
            }

            if (numDistinctFruit <= 2) {
                maxFruit = Math.max(maxFruit, end - begin);
            }

            counter[fruits[begin]] -= 1;
            if (counter[fruits[begin]] == 0) {
                numDistinctFruit -= 1;
            }
        }

        return maxFruit;
    }
}

Loay hoay mãi mới giải được @@

bác này giởn goài

aNotHeRNo0b · 4/8/25

LmaoSuVuong đã nói:
bác này giởn goài

Gặp mấy bài này em bị lựu @@ không biết nên chọn vòng for bên ngoài là begin hay end @@

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

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Member

Đã tốn tiền

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này