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

freedom.9 · 8/2/24

Violet_7 đã nói:
Xem tệp đính kèm 2329090
Cay éo chịu đc

Đúng rồi hợp lí, mấy thằng code C++ non optimal solution thì lại pass :shame:

via theNEXTvoz for iPhone

freedom.9 · 11/2/24

Tự dưng năm mới tới nay cảm giác sẽ rank cao :shame:

via theNEXTvoz for iPhone

Violet_7 · 11/2/24

Dạo gần đây bọn lít cốt nó cứ thích mấy câu partern matching nhỉ :sweat:

. Thế cứ ốp KMP vs Z-function thôi :big_smile:

freedom.9 · 11/2/24

Bài 3 đếm rồi greedy nhỉ :ah:

Làm ko ra huhu, ko nhìn ra và chứng minh được greedy rule =((

hay có cách nào khác ta

Violet_7 · 11/2/24

freedom.9 đã nói:
Bài 3 đếm rồi greedy nhỉ

yes

freedom.9 · 11/2/24

Violet_7 đã nói:
yes

Nhìn ko ra greedy rules my fence =((

chắc xử lí theo độ dài mỗi từ từ trên xuống dưới

billy_don · 11/2/24

bài 2 ngốn thời gian quá, sai vặt mà hoảng tìm mãi k ra chỗ sai :beat_brick:

. Lần đầu contest mà đc có 2 bài à =((

freedom.9 · 11/2/24

Đúng là counts và xử lí từ trên xuống dưới, nhưng mà ko cần quan tâm tới mấy thằng số lẻ :ah:

Nghĩ phức tạp quá làm ko ra, vl thật.
Rank 3k4 cmnr =((

quá chán

freedom.9 · 11/2/24

billy_don đã nói:
bài 2 ngốn thời gian quá, sai vặt mà hoảng tìm mãi k ra chỗ sai . Lần đầu contest mà đc có 2 bài à

Từ từ rồi trải nghiệm, nay bài 3 nhìn ra patterns rồi mà lại nghĩ phức tạp quá ko tìm ra cách giải.
May múc lại được bài 4 :ah:

Bài 2 cứ làm brute force thôi fence

Python:

class Solution:
    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
        ans = 0
        n = len(nums)
        m = len(pattern)
        for i in range(n - m):
            matches = True
            for k in range(m):
                if pattern[k] == 1 and nums[i + k + 1] > nums[i + k]:
                    continue
               
                if pattern[k] == 0 and nums[i + k + 1] == nums[i + k]:
                    continue
                   
                if pattern[k] == -1 and nums[i + k + 1] < nums[i + k]:
                    continue
                   
                matches = False
                break

            if matches == True:
                ans += 1
               
        return ans

Còn bài 4 thì xài KMP search, cơ mà copy paste cái KMP search vô cho nhanh nên phải convert từ number qua string coi như trick workaround haha

Python:

class Solution:
    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
        ans = 0
        def longest_prefix_suffix(pattern: str):
            lps = [0] * len(pattern)
            length = 0  # length of the previous longest prefix suffix
            i = 1
            while i < len(pattern):
                if pattern[i] == pattern[length]:
                    length += 1
                    lps[i] = length
                    i += 1
                else:
                    if length != 0:
                        length = lps[length - 1]
                    else:
                        lps[i] = 0
                        i += 1
            return lps
        
        def kmp_search(text: str, pattern: str):
            nonlocal ans
            if pattern == "":
                return []
            lps = longest_prefix_suffix(pattern)
            i = 0  # index for text
            j = 0  # index for pattern
            result = []
            while i < len(text):
                if pattern[j] == text[i]:
                    i += 1
                    j += 1
                if j == len(pattern):
                    ans += 1
                    j = lps[j - 1]
                elif i < len(text) and pattern[j] != text[i]:
                    if j != 0:
                        j = lps[j - 1]
                    else:
                        i += 1
            return ans
        
        n = len(nums)
        text = ""
        for i in range(n - 1):
            if(nums[i + 1] > nums[i]):
                text+= "1" 
            if(nums[i + 1] == nums[i]):
                text += "0"
            if(nums[i + 1] < nums[i]):
                text += "2"
                

        patterns = ""
        for i in pattern:
            if i == 0:
                patterns += "0"
            if i == 1:
                patterns += "1"
            if i == -1:
                patterns += "2"
                
        
        return kmp_search(text, patterns)

trinity · 11/2/24

freedom.9 đã nói:

Từ từ rồi trải nghiệm, nay bài 3 nhìn ra patterns rồi mà lại nghĩ phức tạp quá ko tìm ra cách giải.
May múc lại được bài 4 :ah:

Bài 2 cứ làm brute force thôi fence

Python:

class Solution:
    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
        ans = 0
        n = len(nums)
        m = len(pattern)
        for i in range(n - m):
            matches = True
            for k in range(m):
                if pattern[k] == 1 and nums[i + k + 1] > nums[i + k]:
                    continue
              
                if pattern[k] == 0 and nums[i + k + 1] == nums[i + k]:
                    continue
                  
                if pattern[k] == -1 and nums[i + k + 1] < nums[i + k]:
                    continue
                  
                matches = False
                break

            if matches == True:
                ans += 1
              
        return ans

Còn bài 4 thì xài KMP search, cơ mà copy paste cái KMP search vô cho nhanh nên phải convert từ number qua string coi như trick workaround haha

Python:

class Solution:
    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
        ans = 0
        def longest_prefix_suffix(pattern: str):
            lps = [0] * len(pattern)
            length = 0  # length of the previous longest prefix suffix
            i = 1
            while i < len(pattern):
                if pattern[i] == pattern[length]:
                    length += 1
                    lps[i] = length
                    i += 1
                else:
                    if length != 0:
                        length = lps[length - 1]
                    else:
                        lps[i] = 0
                        i += 1
            return lps
       
        def kmp_search(text: str, pattern: str):
            nonlocal ans
            if pattern == "":
                return []
            lps = longest_prefix_suffix(pattern)
            i = 0  # index for text
            j = 0  # index for pattern
            result = []
            while i < len(text):
                if pattern[j] == text[i]:
                    i += 1
                    j += 1
                if j == len(pattern):
                    ans += 1
                    j = lps[j - 1]
                elif i < len(text) and pattern[j] != text[i]:
                    if j != 0:
                        j = lps[j - 1]
                    else:
                        i += 1
            return ans
       
        n = len(nums)
        text = ""
        for i in range(n - 1):
            if(nums[i + 1] > nums[i]):
                text+= "1"
            if(nums[i + 1] == nums[i]):
                text += "0"
            if(nums[i + 1] < nums[i]):
                text += "2"
               

        patterns = ""
        for i in pattern:
            if i == 0:
                patterns += "0"
            if i == 1:
                patterns += "1"
            if i == -1:
                patterns += "2"
               
       
        return kmp_search(text, patterns)

sao bác ko dùng luôn array (không cần phải convert sang string) ấy, convert nums sang dạng {-1,0,1} giống pattern là đc

freedom.9 · 11/2/24

Bà mẹ ngu quá sửa lại cái KMP search để nó chạy trên array thì đã đỡ mất 2 lần submit sai thay vì convert qua string rồi =((

thi context panic thật

trinity đã nói:
sao bác ko dùng luôn array (không cần phải convert sang string) ấy, convert nums sang dạng {-1,0,1} giống pattern là đc

Đúng rồi fence, lúc thi context mình cứ nghĩ phức tạp vấn đề lên ấy, convert qua string dính edge case sml mất luôn 2 lần submit sai =((

Cái bài 3 đúng dễ, nghĩ ra là đếm rồi greedy rồi mà cuối cùng cũng ko làm ra loay hoay cả tiếng đồng hồ. Thôi từ từ cải thiện tính suy nghĩ phức tạp lên vậy =((

Sửa lại bài 4 cái

Python:

class Solution:
    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
        def longest_prefix_suffix(pattern: str):
            lps = [0] * len(pattern)
            length = 0  # length of the previous longest prefix suffix
            i = 1
            while i < len(pattern):
                if pattern[i] == pattern[length]:
                    length += 1
                    lps[i] = length
                    i += 1
                else:
                    if length != 0:
                        length = lps[length - 1]
                    else:
                        lps[i] = 0
                        i += 1
            return lps
      
        def kmp_search(text, pattern):
            ans = 0
            if pattern == "":
                return []
            lps = longest_prefix_suffix(pattern)
            i = 0  # index for text
            j = 0  # index for pattern
            result = []
            while i < len(text):
                if pattern[j] == text[i]:
                    i += 1
                    j += 1
                if j == len(pattern):
                    ans += 1
                    j = lps[j - 1]
                elif i < len(text) and pattern[j] != text[i]:
                    if j != 0:
                        j = lps[j - 1]
                    else:
                        i += 1
            return ans
      
        n = len(nums)
        formed_text = [0]*(n - 1)
        for i in range(n - 1):
            if(nums[i + 1] > nums[i]):
                formed_text[i] = 1
            if(nums[i + 1] == nums[i]):
                formed_text[i] = 0
            if(nums[i + 1] < nums[i]):
                formed_text[i] = -1
              

        return kmp_search(formed_text, pattern)

Violet_7 · 11/2/24

trinity đã nói:
sao bác ko dùng luôn array (không cần phải convert sang string) ấy, convert nums sang dạng {-1,0,1} giống pattern là đc

solution kmp sẵn là string, nên convert sang string cho nó cẩn thẩn :big_smile:

freedom.9 · 17/2/24

Contest ae ơi, nay 2 contests gáng vô top 2k :adore:

via theNEXTvoz for iPhone

Violet_7 · 17/2/24

Contest dễ nhất quả đất :ah:

. 25 phút ko bug :beauty:

freedom.9 · 17/2/24

Lùm mé bài 3 code topdown quên thêm lru cache vô sai mẹ 1 lần submit, bài 2 cũng sai 1 lần submit do ko đọc kĩ đề :ah:

chít mẹ r

anoldvozer1710.v2 · 17/2/24

Lam dc 3 cau, thay cau 4 Hard deo them lam nua

chiyeuemthoi · 17/2/24

ăn 4 phát sai submit ạ dc hôm sub 3 bài

Violet_7 · 17/2/24

anoldvozer1710.v2 đã nói:
Lam dc 3 cau, thay cau 4 Hard deo them lam nua

làm đi bác. Có 5 dòng thôi :shame:

anoldvozer1710.v2 · 17/2/24

Violet_7 đã nói:
làm đi bác. Có 5 dòng thôi

that ah

Violet_7 · 17/2/24

anoldvozer1710.v2 đã nói:
that ah

nhầm, em đếm lại thì 6 dòng bác :shame:

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

Senior Member

Senior Member

Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Member

Senior Member

Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này