thảo luận Leetcode contest, đường tới Guardian

vicejuniordev · 29/1/24

Q3 chỉ cần làm phép tính dựa vào Length là được. Vì đây là dãy số tự nhiên liên tiếp

via theNEXTvoz for iPhone

freedom.9 · 29/1/24

vicejuniordev đã nói:
Q3 chỉ cần làm phép tính dựa vào Length là được. Vì đây là dãy số tự nhiên liên tiếp

via theNEXTvoz for iPhone

Chỉ cần return m*n/2 được rồi fence, mình viết thế này trong contests cho khỏi phải xài math thôi chứ ko cần 2 vòng for.
Bài này thì dễ mà đọc đề hơn khó hiểu tí

via theNEXTvoz for iPhone

NahSama · 2/2/24

Mã:

class Solution {
    public long flowerGame(int n, int m) {
        long left_even = ((n % 2 == 0? n : n - 1) - 2) / 2 + 1;
        long left_odd = ((n % 2 == 0 ? n - 1: n) - 1) / 2 + 1;
    
        long right_even = ((m % 2 == 0? m : m - 1) - 2) / 2 + 1;
        long right_odd = ((m % 2 == 0? m - 1: m) - 1) / 2 + 1;
        return left_even * right_odd + left_odd * right_even;
    }
}

Dạo này mình k tham gia contest để giữ rating :cry:

, chỉ đợi đề của contest để làm thôi :sleep:

Violet_7 · 3/2/24

NahSama đã nói:

Mã:

class Solution {
    public long flowerGame(int n, int m) {
        long left_even = ((n % 2 == 0? n : n - 1) - 2) / 2 + 1;
        long left_odd = ((n % 2 == 0 ? n - 1: n) - 1) / 2 + 1;
   
        long right_even = ((m % 2 == 0? m : m - 1) - 2) / 2 + 1;
        long right_odd = ((m % 2 == 0? m - 1: m) - 1) / 2 + 1;
        return left_even * right_odd + left_odd * right_even;
    }
}

Dạo này mình k tham gia contest để giữ rating :cry:

, chỉ đợi đề của contest để làm thôi :sleep:

Thế tối nay làm không ngài nah

Violet_7 · 3/2/24

Contest cx khá dễ :big_smile:

, mà vừa nói chuyện vs gái xong làm nên hơi mất tập trung. Ăn 4 bugs :beat_brick:

Leona.Guy · 3/2/24

contest tối nay khá dễ

C++:

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        map<int, long long> f;
        long long sum = 0, ans = LLONG_MIN;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            if (f.count(nums[i] - k)) {
                ans = max(ans, sum - f[nums[i] - k] + nums[i] - k);
            }
          
            if (f.count(nums[i] + k)) {
                ans = max(ans, sum - f[k + nums[i]] + k + nums[i]);
            }
          
            if (f.count(nums[i])) {
                f[nums[i]] = min(f[nums[i]], sum);
            } else {
                f[nums[i]] = sum;
            }
        }
      
        return (ans == LLONG_MIN)?0:ans;
    }
};

C++:

int numberOfPairs(vector<vector<int>>& points) {
        int n = points.size();
        int ans = 0;
        sort(points.begin(), points.end(), [](auto a, auto b) {
            if (a[0] == b[0]) return a[1] >= b[1];
            return a[0] < b[0];
        });
      
      
        for (int i = 1; i < n; ++i) {
            int b = INT_MAX;
            for (int j = i - 1; j >= 0; --j) {
                if (points[j][1] >= points[i][1] && points[j][1] < b) {
                    ans++;
                    b = points[j][1];
                }
            }
        }
      
        return ans;
    }

Violet_7 · 3/2/24

Leona.Guy đã nói:

contest tối nay khá dễ
Câu 3

C++:

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        map<int, long long> f;
        long long sum = 0, ans = LLONG_MIN;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            if (f.count(nums[i] - k)) {
                ans = max(ans, sum - f[nums[i] - k] + nums[i] - k);
            }
           
            if (f.count(nums[i] + k)) {
                ans = max(ans, sum - f[k + nums[i]] + k + nums[i]);
            }
           
            if (f.count(nums[i])) {
                f[nums[i]] = min(f[nums[i]], sum);
            } else {
                f[nums[i]] = sum;
            }
        }
       
        return (ans == LLONG_MIN)?0:ans;
    }
};

Câu 4

C++:

int numberOfPairs(vector<vector<int>>& points) {
        int n = points.size();
        int ans = 0;
        sort(points.begin(), points.end(), [](auto a, auto b) {
            if (a[0] == b[0]) return a[1] >= b[1];
            return a[0] < b[0];
        });
       
       
        for (int i = 0; i < n; ++i) {
            if (i == 0) continue;
            int b = INT_MAX;
            for (int j = i - 1; j >= 0; --j) {
                if (points[j][1] >= points[i][1] && points[j][1] < b) {
                    ans++;
                    b = points[j][1];
                }
            }
        }
       
        return ans;
    }

sau post solution sau contest bác, ko ông nào copy xong leetcode nó detect giống source nhau khéo ăn ban đấy bác :look_down:

Leona.Guy · 3/2/24

Violet_7 đã nói:
sau post solution sau contest bác, ko ông nào copy xong leetcode nó detect giống source nhau khéo ăn ban đấy bác

Ah, thanks bác nhé

Violet_7 · 3/2/24

Câu 1:

Đầu tiên, phải check xem 3 cạnh có là tam giác không bằng công thức cấp 3
Sau đó đếm cạnh cho nhanh, nếu max(count) == 2 thì cân, == 3 thì đều

Câu 2:

n = 50 nên max time complex = O(n^3) -> 3 vòng for
2 vòng for đầu tiên lấy 2 điểm bất kì, rồi check xem có thoả mãn các đk ko
vòng for cuối check có điểm nào ở giữa không, có thì result += 1

Câu 3:

n = 10^5 nên time complex = O(n) -> 1 vòng for
có thể dùng hash map cho mảng nums (gọi là index_map) key là num, value là list các index
Duyệt từng số, rồi duyệt các index trong index_map[num - k], index_map[num + k]. Rồi tìm sum lớn nhất
số lượng các cặp thoả mãn đề bài có thể n^2 nên ko dùng hash map rồi duyệt lần lượt các pair đc
vậy how to tối ưu
thôi đoạn này nhìn code dễ hiểu hơn

Python:

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        max_indexes = dict()
        res = -float('inf')
       
        prefix_sum = nums.copy()
        for i in range(1, len(nums)):
            prefix_sum[i] += prefix_sum[i - 1]
       
        def get_prefix_sum(start, end):
            if start == 0:
                return prefix_sum[end]
            return prefix_sum[end] - prefix_sum[start - 1]
       
        for i, num in enumerate(nums):
           
            if num - k in max_indexes:
                res = max(res, get_prefix_sum(max_indexes[num - k], i))
            if num + k in max_indexes:
                res = max(res, get_prefix_sum(max_indexes[num + k], i))
           
            if num not in max_indexes or get_prefix_sum(max_indexes[num], i - 1) < 0:
                max_indexes[num] = i
           
        return 0 if res == -float('inf') else res

Câu 4:

n = 1000 nên max time complex = O(n^2 logn) -> 2 vòng for
cũng khó giải thíchm chắc nhìn code dễ hiểu hơn

Python:

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        n = len(points)
        points.sort(key=lambda x:(x[0], -x[1]))
        pairs_count = 0
       
        for chisato_index in range(n - 1):
            max_previous_takina_y = -float('inf')
            for takina_index in range(chisato_index + 1, n):
                chisato_x, chisato_y = points[chisato_index]
                takina_y, takina_y = points[takina_index]
               
                if chisato_y < takina_y:
                    continue
                   
                if max_previous_takina_y < takina_y:
                    pairs_count += 1

                max_previous_takina_y = max(max_previous_takina_y, takina_y)
                   
        return pairs_count

TLE_WA · 3/2/24

Violet_7 đã nói:
Câu 1:

Đầu tiên, phải check xem 3 cạnh có là tam giác không bằng công thức cấp 3

Sau đó đếm cạnh cho nhanh, nếu max(count) == 2 thì cân, == 3 thì đều

Câu 2:

n = 50 nên max time complex = O(n^3) -> 3 vòng for

2 vòng for đầu tiên lấy 2 điểm bất kì, rồi check xem có thoả mãn các đk ko

vòng for cuối check có điểm nào ở giữa không, có thì result += 1

Câu 3:

n = 10^5 nên time complex = O(n) -> 1 vòng for

có thể dùng hash map cho mảng nums (gọi là index_map) key là num, value là list các index

Duyệt từng số, rồi duyệt các index trong index_map[num - k], index_map[num + k]. Rồi tìm sum lớn nhất

số lượng các cặp thoả mãn đề bài có thể n^2 nên ko dùng hash map rồi duyệt lần lượt các pair đc

vậy how to tối ưu

thôi đoạn này nhìn code dễ hiểu hơn

Python:

class Solution: def maximumSubarraySum(self, nums: List[int], k: int) -> int: max_indexes = dict() res = -float('inf') prefix_sum = nums.copy() for i in range(1, len(nums)): prefix_sum[i] += prefix_sum[i - 1] def get_prefix_sum(start, end): if start == 0: return prefix_sum[end] return prefix_sum[end] - prefix_sum[start - 1] for i, num in enumerate(nums): if num - k in max_indexes: res = max(res, get_prefix_sum(max_indexes[num - k], i)) if num + k in max_indexes: res = max(res, get_prefix_sum(max_indexes[num + k], i)) if num not in max_indexes or get_prefix_sum(max_indexes[num], i - 1) < 0: max_indexes[num] = i return 0 if res == -float('inf') else res

Câu 4:

n = 1000 nên max time complex = O(n^2 logn) -> 2 vòng for

cũng khó giải thíchm chắc nhìn code dễ hiểu hơn

Python:

class Solution: def numberOfPairs(self, points: List[List[int]]) -> int: n = len(points) points.sort(key=lambda x:(x[0], -x[1])) pairs_count = 0 for chisato_index in range(n - 1): max_previous_takina_y = -float('inf') for takina_index in range(chisato_index + 1, n): chisato_x, chisato_y = points[chisato_index] takina_y, takina_y = points[takina_index] if chisato_y < takina_y: continue if max_previous_takina_y < takina_y: pairs_count += 1 max_previous_takina_y = max(max_previous_takina_y, takina_y) return pairs_count

Tên biến

Violet_7 · 3/2/24

TLE_WA đã nói:
Tên biến

CLEAN CODE :look_down:

freedom.9 · 3/2/24

Câu 3 mình giải thế này TLE là sao ta, sao thấy mấy thằng giải bằng c++ lại pass?

Python:

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        prefixSum = [nums[0]]*len(nums)
        
        for i in range(1,len(nums)):
            prefixSum[i] = nums[i] + prefixSum[i - 1]

        counts = {}
        sum = 0
        ans = -inf
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] - k in counts:
                print(i)
                for j in counts[nums[i] - k]:
                    if i == 0:
                        ans = max(prefixSum[j], ans)
                    else:
                        ans = max(prefixSum[j] - prefixSum[i - 1], ans)
                    
            if k + nums[i] in counts:
                for j in counts[k + nums[i]]:
                    if i == 0:
                        ans = max(prefixSum[j], ans)
                    else:
                        ans = max(prefixSum[j] - prefixSum[i - 1], ans)
                
            if not nums[i] in counts:
                counts[nums[i]] = []
                
            counts[nums[i]].append(i)
            
        if ans == -inf:
            return 0
        
        return ans

TLE_WA · 3/2/24

freedom.9 đã nói:

Câu 3 mình giải thế này TLE là sao ta, sao thấy mấy thằng giải bằng c++ lại pass?

Python:

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        prefixSum = [nums[0]]*len(nums)
       
        for i in range(1,len(nums)):
            prefixSum[i] = nums[i] + prefixSum[i - 1]

        counts = {}
        sum = 0
        ans = -inf
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] - k in counts:
                print(i)
                for j in counts[nums[i] - k]:
                    if i == 0:
                        ans = max(prefixSum[j], ans)
                    else:
                        ans = max(prefixSum[j] - prefixSum[i - 1], ans)
                   
            if k + nums[i] in counts:
                for j in counts[k + nums[i]]:
                    if i == 0:
                        ans = max(prefixSum[j], ans)
                    else:
                        ans = max(prefixSum[j] - prefixSum[i - 1], ans)
               
            if not nums[i] in counts:
                counts[nums[i]] = []
               
            counts[nums[i]].append(i)
           
        if ans == -inf:
            return 0
       
        return ans

Họ update sao cho counts bé nhất thôi anh append vào list tất cả index giờ em cho 1 array full 1 thì tle là chắc.

freedom.9 · 3/2/24

Giải bằng C# lại pass, éo hiểu kiểu gì. Bài 3 mình giải có tí mà ko hiểu sao ko pass với python

C#:

public class Solution {
    public long MaximumSubarraySum(int[] nums, int k) {
        int n = nums.Length;
        long[] prefixSum = new long[n];
        prefixSum[0] = nums[0];

        for (int i = 1; i < n; ++i) {
            prefixSum[i] = (long)nums[i] + prefixSum[i - 1];
        }

        Dictionary<long, List<int>> counts = new Dictionary<long, List<int>>();
        long ans = long.MinValue;

        for (int i = n - 1; i >= 0; --i) {
            if (counts.ContainsKey(nums[i] - k)) {
                foreach (var item in counts[nums[i] - k]) {
                    if (i == 0) {
                        ans = Math.Max(prefixSum[item], ans);
                    } else {
                        ans = Math.Max(prefixSum[item] - (i > 0 ? prefixSum[i - 1] : 0), ans);
                    }
                }
            }

            if (counts.ContainsKey(k + nums[i])) {
                foreach (var item in counts[k + nums[i]]) {
                    if (i == 0) {
                        ans = Math.Max(prefixSum[item], ans);
                    } else {
                        ans = Math.Max(prefixSum[item] - (i > 0 ? prefixSum[i - 1] : 0), ans);
                    }
                }
            }

            if (!counts.ContainsKey(nums[i])) {
                counts[nums[i]] = new List<int>();
            }

            counts[nums[i]].Add(i);
        }

        if (ans == long.MinValue) {
            return 0;
        }

        return ans;
    }
}

freedom.9 · 3/2/24

TLE_WA đã nói:
Họ update sao cho counts bé nhất thôi anh append vào list tất cả index giờ em cho 1 array full 1 thì tle là chắc.

Quan trọng là với đoạn code này mình convert qua C# nó lại pass =((

freedom.9 · 3/2/24

TLE_WA đã nói:
Họ update sao cho counts bé nhất thôi anh append vào list tất cả index giờ em cho 1 array full 1 thì tle là chắc.

Ừ đúng rồi mình ko nghĩ ra, đáng ra chỉ cần lưu lại index có giá trị nhỏ nhất và index có giá trị lớn nhất vào cái counts thôi đúng ko fence nhỉ

TLE_WA · 3/2/24

freedom.9 đã nói:
Ừ đúng rồi mình ko nghĩ ra, đáng ra chỉ cần lưu lại index có giá trị nhỏ nhất và index có giá trị lớn nhất vào cái counts thôi đúng ko fence nhỉ

Không phải là id nhỏ nhất và id lớn nhất đâu anh, anh chỉ cần quan tâm tới tổng hiện tại thôi. Tổng đoạn cần tìm = current_sum - sum[0->index thỏa mãn - 1] => vậy mình muốn cái sum từ 0 đến index thỏa mãn -1 đó nhỏ nhất có thể. Vậy thì chỉ cần lưu f[num] = min(f[num],cur)

Anh có thể thử tham khảo code của em

Python:

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        have_ans = False
        inf = 10**16
        ans = -inf
        n = len(nums)
        # abs(nums[i] - nums[j]) == k
        f = {}
        cur = 0
        for x in nums:
            y = x - k
            z = x + k
            
            if x in f:
                f[x] = min(f[x], cur)
            else:
                f[x] = cur
            cur += x
            
            
            if y in f:
                print(ans)
                ans = max(ans, cur - f[y])
            if z in f:
                print(ans)
                ans = max(ans, cur - f[z])


        return ans if ans != -inf else 0

freedom.9 · 3/2/24

TLE_WA đã nói:
Không phải là id nhỏ nhất và id lớn nhất đâu anh, anh chỉ cần quan tâm tới tổng hiện tại thôi. Tổng đoạn cần tìm = current_sum - sum[0->index thỏa mãn - 1] => vậy mình muốn cái sum từ 0 đến index thỏa mãn -1 đó nhỏ nhất có thể. Vậy thì chỉ cần lưu f[num] = min(f[num],cur)

Anh có thể thử tham khảo code của em

Python:

class Solution: def maximumSubarraySum(self, nums: List[int], k: int) -> int: have_ans = False inf = 10**16 ans = -inf n = len(nums) # abs(nums[i] - nums[j]) == k f = {} cur = 0 for x in nums: y = x - k z = x + k if x in f: f[x] = min(f[x], cur) else: f[x] = cur cur += x if y in f: print(ans) ans = max(ans, cur - f[y]) if z in f: print(ans) ans = max(ans, cur - f[z]) return ans if ans != -inf else 0

À mình hiểu rồi, thì ra là thế :ah:

thanks fence

Janety · 4/2/24

không biết sắp tới như nào , đặt gạch hóng ae

Violet_7 · 8/2/24

Cay éo chịu đc :ah:

thảo luận Leetcode contest, đường tới Guardian

Senior Member

Senior Member

Senior Member

Member

Member

Senior Member

Member

Senior Member

Member

Junior Member

Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Junior Member

Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này