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.
btw ae code java cho e hỏi chút, có unwritten law nào về việc dùng keyword var ko nhỉ? em thấy mấy ông java cti em thì rất ít ông dùng var, toàn khai type tường minh luôn (meanwhile c# toàn dùng var ._. )
7obgkeK.gif
 
Gặp mấy bài này ăn bug sml :doubt: đi interview code ẩu ko cover edge cases chắc tạch sml. Cơ mà ngu quá xài 2 pointers như editorial đỡ phải pop phát mệt
Python: 
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        increasing = [0]
        n = len(arr)
        for i in range(1, n):
            if arr[i] >= arr[i - 1]:
                increasing.append(i)
            else:
                break

        ans = n - len(increasing)
        for j in range(n - 1, -1, -1):
            if j != n - 1 and arr[j] > arr[j + 1]:
                break

            while increasing and (increasing[-1] >= j or arr[increasing[-1]] > arr[j]):
                increasing.pop()

            if increasing:
                ans = min(ans, j - increasing[-1] - 1)
          
            ans = min(ans, j)
      
        return ans
 
freedom.9 đã nói:
Gặp mấy bài này ăn bug sml :doubt: đi interview code ẩu ko cover edge cases chắc tạch sml. Cơ mà ngu quá xài 2 pointers như editorial đỡ phải pop phát mệt
Python: 
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        increasing = [0]
        n = len(arr)
        for i in range(1, n):
            if arr[i] >= arr[i - 1]:
                increasing.append(i)
            else:
                break

        ans = n - len(increasing)
        for j in range(n - 1, -1, -1):
            if j != n - 1 and arr[j] > arr[j + 1]:
                break

            while increasing and (increasing[-1] >= j or arr[increasing[-1]] > arr[j]):
                increasing.pop()

            if increasing:
                ans = min(ans, j - increasing[-1] - 1)
         
            ans = min(ans, j)
     
        return ans
Nhấp để mở rộng...
hoá ra monotonic stack là như này :hungry:
 
anoldvozer1710.v2 đã nói:
dis bài làm cũng căng đét, lỗi lên lỗi xuống.
Nhìn cái topic còn có cả bs, monotonic stack???:ops::misdoubt::nosebleed:

JavaScript: 
function findLengthOfShortestSubarray(arr: number[]): number {
    const n = arr.length;
    let l = 0, r = n - 1;
    while (l + 1 < n && arr[l] <= arr[l + 1]) l++;
    if (l === r) return 0;
    while (r > 0 && arr[r - 1] <= arr[r]) r--;
    let res = Math.min(n - l - 1, r);
    for (let i = 0, j = r; i <= l && j < n;) {
        if (arr[i] <= arr[j]) res = Math.min(res, j - i - 1), i++;
        else j++;
    }
    return res;
};
Nhấp để mở rộng...
Thực ra nếu trong contests thì mình sẽ xài binary search ngay đó éo nói nhiều, vì kiểu gì biết làm On cũng lỗi lên lỗi xuống cho xem.
Còn binary thì khác gì chạy brute force đâu :doubt:
 
freedom.9 đã nói:
Thực ra nếu trong contests thì mình sẽ xài binary search ngay đó éo nói nhiều, vì kiểu gì biết làm On cũng lỗi lên lỗi xuống cho xem.
Còn binary thì khác gì chạy brute force đâu :doubt:
Nhấp để mở rộng...
bài này implement BS như nào thế fen, e chỉ biết úp BS cho mấy cái sorted
LTT2cUR.png
 
bkhoang đã nói:
bài này implement BS như nào thế fen, e chỉ biết úp BS cho mấy cái sorted
LTT2cUR.png
Nhấp để mở rộng...
mình nghĩ là dùng BS trên từng đoạn từ mid to n or từ 0 to mid, rồi tìm xem phần tử nào >= or <= cái half còn lại rồi cộng tính max, cũng khá là khoai, chưa implement đc theo kiểu này.
 
JavaScript: 
var findLengthOfShortestSubarray = function (arr) {
    const n = arr.length;
    let i = 1, j = n, maxLength = 0;
    for (; i < n && arr[i] >= arr[i - 1]; i++);
    for (; i >= 0; i--) {
        const low = i ? arr[i - 1] : -Infinity;
        while (j > i && arr[j - 1] <= (arr[j] ?? Infinity) && arr[j - 1] >= low) {
            j--;
        }
        maxLength = Math.max(maxLength, i + n - j);
    }
    return n - maxLength;
};
 
Hi các bác, Cố mới tái hóa nhập cộng đồng :sexy_girl: Có gì chỉ Cố làm bài nha
Java: 
class Solution {
    public int minimizedMaximum(int n, int[] quantities) {
        int right = IntStream.of(quantities).max().orElseThrow();
        int left = 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (check(mid, n, quantities)) {
                right = mid;
            } else {
                left  = mid + 1;
            }

        }

        return left;
    }

    private boolean check(int mid, int n, int[] quantities) {
        int count = 0;
        for (int num: quantities) {
            count += (num + mid - 1) / mid;
        }

        return count <= n;
    }
}
 
Cố Trường Ca đã nói:
Hi các bác, Cố mới tái hóa nhập cộng đồng :sexy_girl: Có gì chỉ Cố làm bài nha
Java: 
class Solution {
    public int minimizedMaximum(int n, int[] quantities) {
        int right = IntStream.of(quantities).max().orElseThrow();
        int left = 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (check(mid, n, quantities)) {
                right = mid;
            } else {
                left  = mid + 1;
            }

        }

        return left;
    }

    private boolean check(int mid, int n, int[] quantities) {
        int count = 0;
        for (int num: quantities) {
            count += (num + mid - 1) / mid;
        }

        return count <= n;
    }
}
Nhấp để mở rộng...
mấy tháng rồi sao vẫn Junior vậy Cố huynh
doubt_kiss.png


via theNEXTvoz for iPhone
 
bkhoang đã nói:
bài này implement BS như nào thế fen, e chỉ biết úp BS cho mấy cái sorted
LTT2cUR.png
Nhấp để mở rộng...
Kiểu thế này nè mấy fen
Python: 
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        left = 0
        while left + 1 < n and arr[left] <= arr[left + 1]:
            left += 1
        if left == n - 1:
            return 0
        right = n - 1
        while right > 0 and arr[right - 1] <= arr[right]:
            right -= 1
        def canRemove(length):
            for i in range(left, -1, -1):
                j = i + length + 1
                if j >= n or (j >= right and arr[i] <= arr[j]):
                    return True
            return False
        low, high = 0, n
        while low <= high:
            mid = low + (high - low) // 2
            if canRemove(mid):
                high = mid - 1
            else:
                low = mid + 1
        return min(right, high + 1)
Hoặc cách này sẽ dễ comeup hơn trong contest, chỉ là vấn đề của việc gõ thôi khỏi phải lo xử lí edge cases
Python: 
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        left = 0
        for i in range(1, n):
            if arr[i] >= arr[i - 1]:
                left = i
            else:
                break
        
        decreasing = set()
        decreasing.add(n - 1)
        right = n - 1
        for i in range(n - 2, -1, -1):
            if arr[i] <= arr[i + 1]:
                right = i
                decreasing.add(i)
            else:
                break

        def canRemove(length):
            for i in range(left, -1, -1):
                j = i + length + 1
                if j >= n or (j in decreasing and arr[j] >= arr[i]):
                    return True

            return False

        low, high = 0, n
        while low <= high:
            mid = low + (high - low) // 2
            if canRemove(mid):
                high = mid - 1
            else:
                low = mid + 1

        return min(right, high + 1)
 
Sửa lần cuối:
noobdev đã nói:
mình nghĩ là dùng BS trên từng đoạn từ mid to n or từ 0 to mid, rồi tìm xem phần tử nào >= or <= cái half còn lại rồi cộng tính max, cũng khá là khoai, chưa implement đc theo kiểu này.
Nhấp để mở rộng...
Ko phải fen, đây gọi là binary search on the answer, giả sử remove đc 10 thằng để tạo ra good array, xong giảm search space xuống 5 thằng để tìm xem có tạo ra good array được ko. Nếu remove 3 thằng mà ko tạo đc sub array thì ans nó phải là remove > 3 thằng. Kiểu thế, chứ ko nhất thiết phải deploy trên 1 sorted array mà là deploy trên tập kết quả. Như bài hôm qua đó
via theNEXTvoz for iPhone
 
LC 1574 GoLang 1.21+
C-like: 
func findLengthOfShortestSubarray(arr []int) int {
    l := len(arr)
    if l <= 1 { return 0 }
    i, j := 0, l-1
    for i < l-1 && arr[i+1] >= arr[i] { i++ }
    for j > 0 && arr[j] >= arr[j-1] { j-- }
    if i >= j { return 0 }
    return bsR(arr, i, j)
}

func bsR(arr []int, i int, j int) int {
    if arr[i] <= arr[j] { return j - i - 1 }
    if i == 0 || j == len(arr)-1 { return j - i }
    return min(bsR(arr, i-1, j), bsR(arr, i, j+1))
}
 
Sửa lần cuối:
freedom.9 đã nói:
Gặp mấy bài này ăn bug sml :doubt: đi interview code ẩu ko cover edge cases chắc tạch sml. Cơ mà ngu quá xài 2 pointers như editorial đỡ phải pop phát mệt
Python: 
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        increasing = [0]
        n = len(arr)
        for i in range(1, n):
            if arr[i] >= arr[i - 1]:
                increasing.append(i)
            else:
                break

        ans = n - len(increasing)
        for j in range(n - 1, -1, -1):
            if j != n - 1 and arr[j] > arr[j + 1]:
                break

            while increasing and (increasing[-1] >= j or arr[increasing[-1]] > arr[j]):
                increasing.pop()

            if increasing:
                ans = min(ans, j - increasing[-1] - 1)
        
            ans = min(ans, j)
    
        return ans
Nhấp để mở rộng...
Code O(n) cũng dễ mà, :D

T code O(n) submit phát ăn ngay, beast 100%

C++: 
class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int j = arr.size() - 1;
        for (; j > 0 && arr[j] >= arr[j-1]; --j);
        int ret = j;
        for (int i = 0; i < j && j <= arr.size(); ++i) {
            if (i > 0 && arr[i] < arr[i-1]) break;
            while (j < arr.size() && arr[i] > arr[j]) ++j;
            ret = min(ret, j - i - 1);
        }
        return ret;
    }
};

1731641004320.png

Có 3 cái submit từ 2022, :rolleyes:
 
seastar đã nói:
Code O(n) cũng dễ mà, :D

T code O(n) submit phát ăn ngay, beast 100%

C++: 
class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int j = arr.size() - 1;
        for (; j > 0 && arr[j] >= arr[j-1]; --j);
        int ret = j;
        for (int i = 0; i < j && j <= arr.size(); ++i) {
            if (i > 0 && arr[i] < arr[i-1]) break;
            while (j < arr.size() && arr[i] > arr[j]) ++j;
            ret = min(ret, j - i - 1);
        }
        return ret;
    }
};

Xem tệp đính kèm 2783071
Có 3 cái submit từ 2022, :rolleyes:
Nhấp để mở rộng...
Code ẩu là sẽ ăn bọ ăn gậy :misdoubt:
1731642105911.png
 
freedom.9 đã nói:
Ko phải fen, đây gọi là binary search on the answer, giả sử remove đc 10 thằng để tạo ra good array, xong giảm search space xuống 5 thằng để tìm xem có tạo ra good array được ko. Nếu remove 3 thằng mà ko tạo đc sub array thì ans nó phải là remove > 3 thằng. Kiểu thế, chứ ko nhất thiết phải deploy trên 1 sorted array mà là deploy trên tập kết quả. Như bài hôm qua đó
via theNEXTvoz for iPhone
Nhấp để mở rộng...
Hiểu rồi bác, em nghĩ vậy thôi chứ chưa code đc cái solution này.
LmaoSuVuong đã nói:
bác này chưa đọc BS chân kinh r @anoldvozer1710.v2
lWWXgbs.gif
Nhấp để mở rộng...
Cũng có đọc rồi bác cơ mà bài này dùng BS thì có vẻ giống tự bắn vào chân quá :D
 
noobdev đã nói:
Hiểu rồi bác, em nghĩ vậy thôi chứ chưa code đc cái solution này.

Cũng có đọc rồi bác cơ mà bài này dùng BS thì có vẻ giống tự bắn vào chân quá :D
Nhấp để mở rộng...
RABuWir.gif
làm theo chuỗi thì gặp bài hôm nay e cũng nghĩ tới bs, còn bụp phát random chắc cũng ko nghĩ BS đâu
O9MF8JV.gif
làm daily thì bài hôm qua cũng có khi là 1 hint của bài hôm nay
 
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