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

Nãy code nhanh dùng zip.
Python:
return accumulate([[1]] * numRows, lambda n, _: [sum(p) for p in zip(n + [0], [0] + n)])
Tắt tab rồi mà nghĩ thế nào lại sửa tý cho nó nghe Pythonic hơn.
Python:
return accumulate([[1]] * numRows, lambda n, _: list(map(sum, pairwise([0] + n + [0]))))
 
Thử code ngắn C++.
Trên leetcode chỉ hỗ trợ C++17 nên làm được chừng này là ngắn hết cỡ, vì C++ algorithm làm việc với iterator chứ không phải container.
C++20 hỗ trợ range chắc sẽ có cách ngắn hơn.

Cách này dùng front inserter nên độ phức tạp là O(n^3).

C++:
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
       
        std::vector<std::vector<int>> res(numRows, {1});

        std::transform(res.begin(), res.end() - 1, res.begin() + 1, res.begin() + 1, [](auto &v1, auto &v2) {
            std::adjacent_difference(v1.begin(), v1.end(), std::inserter(v2, v2.begin()), std::plus<int>());
            return std::move(v2);
        });
       
        return res;
    }
};
 
Last edited:
Mấy ngày nay bận nên giờ mới quay lại làm task cùng bà con :byebye:

  • Duyệt qua từng char của s để đánh index => các index array đều đã được sort.
  • Duyệt qua từng char của word, dùng binary search để tìm trong các index array kia.
  • Độ phức tạp O(n*m*log(s)) với n là số lượng words, m là độ dài của word lớn nhất, s là độ dài của s

https://leetcode.com/submissions/detail/751635906/

C#:
public class Solution {
    Dictionary<char, List<int>> index = new ();

    public int NumMatchingSubseq(string s, string[] words) {
        for (char c = 'a'; c <= 'z'; c++)
            index.Add(c, new List<int>());
        for (var i = 0; i < s.Length; i++)
        {
            index[s[i]].Add(i);
        }
       
        int count = 0;
        foreach (var word in words)
        {
            if (isSs(word))
            {
                count++;
            }
        }
        return count;
    }
   
   
    bool isSs(string word)
    {
        int pre = -1;
        foreach (var c in word)
        {
            if (index[c] == null)
                return false;
            int found_index = index[c].BinarySearch(pre+1);
            if (found_index < 0)
                found_index = ~found_index;
            if (found_index >= index[c].Count)
                return false;
            pre = index[c][found_index];
        }
        return true;
    }
}
 
20/07:

  • Dễ thấy vấn đề chính của bài này là kiểm tra xem 1 từ w có phải là subsequence của chuỗi s hay không
  • Tư tưởng greedy là với mỗi ký tự trong w, cần tìm ra index nhỏ nhất của ký tự đó trong s, sao cho vẫn lớn hơn vị trí của các ký tự trước đó trong w.
  • Ví dụ: s = acbacbacd, w = abc
  • Với mỗi ký tự trong w ta sẽ tìm ra vị trí nhỏ nhất tương ứng:
    • a => vị trí 0
    • b => vị trí 2
    • c => vị trí 4 (không tính vị trí s[1] vì nó nhỏ hơn vị trí nhỏ nhất của chữ b đứng trước)
=> Kết luận abc là subseq của chuỗi s
  • Nếu đến một lúc nào đó có một ký tự không thể tìm được index phù hợp => Kết luận không phải là subseq
  • Bài toán trở thành tìm vị trí nhỏ nhất của một ký tự lớn hơn một index cho trước

Để giải bài toán này có 2 cách:

  • Lưu vị trí xuất hiện của các ký tự trong s lại vào mảng, theo mỗi ký tự
  • Ví dụ: s = acbacbacd => Lưu index theo từng ký tự
    • a = [0,3,6]
    • b = [2,5]
    • c = [1,4,7]
    • d = [8]
  • Khi đó mảng index của mỗi ký tự này luôn được sắp xếp tăng dần, nên để tìm vị trí nhỏ nhất lớn hơn index cho trước ta chỉ cần dùng binary search trên mảng tương ứng
=> Độ phức tạp: O(max(w*k*log(s), s)) - k là số ký tự trung bình của các từ trong words

  • Lưu vị trí xuất hiện của các ký tự tiếp theo kể từ một index cho trước
  • Ví dụ: s = acbacbacd => Lưu index của mỗi ký tự tiếp theo kể từ một index cho trước
    • index 0: a tiếp theo xuất hiện tại vị trí 3, b -> 2, c -> 1, d -> 8
    • index 1: a -> 3, b -> 2, c -> 4, d -> 8
    • index 2: a -> 3, b -> 5, c -> 4, d -> 8
    • ...
  • Dễ thấy lúc này bài toán chỉ việc nhảy theo bảng nextIndex này theo mỗi ký tự của w
=> Độ phức tạp: O(max(w*k, s))
 
Tương tự ý tưởng @_Gia_Cat_Luong_ ở trên đã nói:
Tui dùng index cho từng ký tự và dùng binary search để xác định xem 1 word có phải subsequence của string tổng không.

Đánh vật mãi không cải thiện được performance trên Java.
Cái này hơn được 63% tốc độ và 85% về memory chạy mất 141ms

https://leetcode.com/submissions/detail/751653533/
 
Last edited:
https://leetcode.com/submissions/detail/751666223/

Ý tưởng: Ban đầu gom các word có ký tự đầu giống nhau vào 1 mảng và đánh index. Sau đó duyệt qua chuỗi S tới ký tự nào thì lấy các word trong mảng index đó đem bỏ vào mảng index tiếp theo.
Vd: s = "abcde", words = ["a","bb","acd","ace"]
'a': ["(a)", "(a)cd", "(a)ce"]
'b': ["(b)b"]
---------------------
s="(a)bcde => Lấy mảng 'a' để duyệt
'b': ["(b)b"]
'c': ["a(c)d", "a(c)e"]
result: ["a"]
----------------------------
s="a(b)cde => Lấy mảng 'b' để duyệt
'b': ["b(b)"]
'c': ["a(c)d", "a(c)e"]
result: ["a"]
-------------------------------
s="ab(c)de => Lấy mảng 'c' để duyệt
'b': ["b(b)"]
'd': ["ac(d)"]
'e': ["ac(e)"]
result: ["a"]
-----------------------------
s="abc(d)e
'b': ["b(b)"]
'e': ["ac(e)"]
result: ["a", "acd"]
------------------------------
s="abcd(e)
'b': ["b(b)"]
result: ["a", "acd", "ace]
 
bác có thể đề xuất thuật toán để tính cái này trong thời gian O(s) không?
Đi ngược từ cuối mảng lên nha fen. Với mỗi index thì update lại vị trí của ký tự tương ứng, chi phí thực ra là O(26*s)

Python:
dp = []
nextIndex = [inf for _ in range(26)]
for i in range(len(s) - 1, -1, -1):
    dp.append(nextIndex.copy())
    nextIndex[ord(s[i]) - ord('a')] = i
dp.reverse()
 
One liner mà cứ TLE buồn quá. Nhìn thấy chỗ cần optimize mà không sửa được. T.T
Python:
return [reduce(lambda p, n: p[1:] if p and p[0] == n else p, s, w) == '' for w in words].count(True)
 
Giờ mình mới biết đến topic này hay quá.
Bài hôm nay thì đúng như bác gì ở trên nói, thực chất quy về bài toán nhỏ hơn là: check xem chuỗi s có phải là subsequense của chuỗi t không.
Việc check này có thể dùng 2 pointers như sau:
Java:
public boolean isSubsequence(String s, String t) {
    int i = 0, j = 0;
    while (i < s.length() && j < t.length()) {
           if (s.charAt(i) == t.charAt(j)) i++;
           j++;
    }
    return  i == s.length();
}

Độ phức tạp sẽ là O(s.len + t.len).
 
Đi ngược từ cuối mảng lên nha fen. Với mỗi index thì update lại vị trí của ký tự tương ứng, chi phí thực ra là O(26*s)

Python:
dp = []
nextIndex = [inf for _ in range(26)]
for i in range(len(s) - 1, -1, -1):
    dp.append(nextIndex.copy())
    nextIndex[ord(s[i]) - ord('a')] = i
dp.reverse()

Thử lại thấy không nhanh hơn dùng binary search.
Có lẽ cách này sẽ có tác dụng khi tìm kiếm với số lượng từ lớn.
 
Thử lại thấy không nhanh hơn dùng binary search.
Có lẽ cách này sẽ có tác dụng khi tìm kiếm với số lượng từ lớn.
Chuẩn rồi fen. Một bên là 26*s một bên là log(s). Dễ thấy để mà 26 < log(s) thì s phải dài đến 2^26 = 70tr ký tự. Trong khi bài này chỉ tầm 10k.
 
1 dòng không được thôi đành 2 dòng vậy.

Python:
map = functools.reduce(lambda _, n: d[n[1]].append(n[0]) or d, enumerate(s), d:=defaultdict(list))
return sum(1 for w in words if functools.reduce(lambda p, n: p + [next((i for i in map[n] if i > p[-1]), -1)], w, [-2]).count(-1) == 0)

Giải thuật thì như cụ @_Gia_Cat_Luong_ bày, tạo 1 cái dict index của các chữ cái.
Trick 1 là tạo một cái d:=defaultdict(list) làm seed cho hàm reduce, cái d này sau dùng lại trong hàm lambda được luôn.
Trick 2 là tìm index phù hợp (lớn hơn index của chữ cái trước đó) bằng hàm next, hàm này sẽ trả về kết quả đầu tiên của generator. Nếu không tìm được thì trả về default = -1, đếm số -1 sẽ ra word đó có phải subsequence của s không.
Có thể tối ưu tiếp bằng cách lúc next mà nhảy vào default thì xoá luôn w để reduce() không chạy nữa, tìm qua thấy string nó không có hàm clear() như list, assign kiểu w = '' không dùng được vì python sẽ báo lỗi assign khi chạy reduce, lười tìm hiểu nên kệ. :censored:

Nếu làm như trên kia:
Python:
return [reduce(lambda p, n: p[1:] if p and p[0] == n else p, s, w) == '' for w in words].count(True)
Thì mỗi một word trong words sẽ duyệt lại toàn bộ s. Oẳng vì TLE.

Đã làm thử ngược lại duyệt từng c in s, nếu thấy c ở đầu mỗi word trong words thì xoá luôn chữ cái đó trong word đi, đến khi duyệt xong s thì thằng word nào còn lại '' thì nghĩa là subsequence của s. Tuy nhiên mấy cái cắt đầu của string trên Python hơi chậm, TLE tiếp.

2 dòng kia làm khéo vẫn gộp vào 1 dòng được, nhưng 1 dòng mà dài quá thì không còn ý nghĩa 'one-liner' nữa. :cautious:
 
Last edited:
Bài này có vẻ hơi tricky khi mà test case chứa nhiều words trùng nhau, nên ông nào làm thêm phần xử lí duplicate sẽ nhanh hơn. Không nghĩ ra cách dùng binary search nên xài tạm cách lưu map các kí tự tiếp theo của từng word, rồi check lần lượt các kí tự của source. Độ phức tạp O(s * w)
 
Bài hnay e chỉ có nghĩ đc cách này thôi. Hóng các cao nhân one-pass
Python:
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        first=ListNode(next=head)
        idx=0
        cur=first
        last=None
        # find nodes before left and after right
        while cur:
            if idx==left:
                prev_node=last
            if idx==right:
                next_node=cur.next
            idx+=1
            last=cur
            cur=cur.next
        # reverse left->right and connect
        p1,p2=next_node,prev_node.next
        while True:
            tmp=p2.next
            p2.next=p1
            p1=p2
            p2=tmp
            if p2==next_node:
                break
        prev_node.next=p1
        return first.next
 
Bài hnay e chỉ có nghĩ đc cách này thôi. Hóng các cao nhân one-pass
Python:
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        first=ListNode(next=head)
        idx=0
        cur=first
        last=None
        # find nodes before left and after right
        while cur:
            if idx==left:
                prev_node=last
            if idx==right:
                next_node=cur.next
            idx+=1
            last=cur
            cur=cur.next
        # reverse left->right and connect
        p1,p2=next_node,prev_node.next
        while True:
            tmp=p2.next
            p2.next=p1
            p1=p2
            p2=tmp
            if p2==next_node:
                break
        prev_node.next=p1
        return first.next
One pass dễ mà
1658370167513.png

  • Chọn 1 node bên trái ngay cạnh chuỗi cần reverse
  • Vd ở đây là node 1
  • cái node 2 sẽ là cái node cuối cùng trong đoạn cần reverse sau khi đc reverse
  • từ node 3->4, ở mỗi bước sẽ chuyển từng node về node đầu tiên của đoạn reverse
  • [1, 2, 3, 4, 5] -> [1, 3, 2, 4, 5] -> [1, 4, 3, 2, 5]
  • Code: https://leetcode.com/submissions/detail/752444068/
 
Back
Top