Leetcode 200 - Luyện thuật toán với chuyên gia

14.1.1. Giới thiệu Union Find

Cuộc sống là kết nối

14.2.1. Giới thiệu hợp đơn giản 

14.2.2. Hợp đơn giản chi tiết

14.2.3. Code hợp đơn giản

Hợp đơn giản

14.3.1 Giới thiệu hợp qua cha

14.3.2. Hợp qua cha chi tiết

[LC] 14.4.3. Bạn đánh giá độ phức tạp của tìm cha

Hợp thông qua cha

[LC] 14.4.1. Hợp theo cấp độ

14.4.2. Nén đường khi hợp

Hợp qua cấp độ

 Leetcode 547 - Tìm nhóm

Dạng bài tìm nhóm

Gợi ý Leetcode 684 - Kết nối thừa

Dạng bài kết nối thừa

14. Union Find.pdf

Slide bài giảng

Leetcode 547 - Number of Provinces

Leetcode 684 - Redundant Connection

Leetcode 1319 - Number of Operations to Make Network Connected

Leetcode 1579 - Remove Max Number of Edges to Keep Graph Fully Traversable

Bài tập

Một cấu trúc dữ liệu giúp ta có thể phân cụm các phần tử có kết nối với nhau trong đồ thị.

Đây là một trong những cấu trúc mạnh mẽ giúp giải quyết nhiều bài toán thú vị bao gồm

- Bài toán tìm nhóm / kết nối thừa

Video | Slide | Notebook


Cấu trúc dữ liệu Union Find

Bài tập thực hành trên Leetcode

~~~python
print('Good luck')
~~~

Điểm tối đa: 80

[LC] Day 1 - Leetcode Introduction

<p>Hình thức: Video **Nội dung:** - Giảng viên giới thiệu về lớp học Leetcode, từ nội dung đến cách thức lập trình trên Leetcode. **Chi tiết:** - Giới thiệu về Lớp học Leetcode - Lời chào từ giảng viên - Một số chú ý của lớp học - Ngôn ngữ lập trình chính của khóa học - Hướng dẫn công cụ lập trình - Hướng dẫn làm bài tập - Hướng dẫn sử dụng Leetcode **Bài tập:** Bài tập làm quen với Leetcode.</p>

Giới thiệu về lớp học + cách luyện thuật toán trên Leetcode

[LC] Day 2 - BigO

Hình thức: Video

Phân tích thuật toán là một trong những kỹ năng quan trọng để đánh giá tốc độ của dòng code mà chúng ta viết.

Trong bài này chúng ta cùng tìm hiểu khái niệm BigO, cách tìm BigO của một thuật số thuật toán phổ thông.

**Chi tiết:**
- Giới thiệu về buổi học BigO
- Thuật toán và BigO
- Đào sâu vào phân tích thuật toán
- O(1)
- Mối quan hệ tuyến tính
- Mối quan hệ bậc hai
- Mối quan hệ Logarit
- Cách rút gọn BigO
- Luyện tập đánh giá độ phức tạp
- Chứng minh công thức BigO
- Độ phức tạp bài tập Two Sum


Đào sâu vào phân tích thuật toán

[LC] Day 3 - String

Hình thức: Video

Chuỗi là một trong những cấu trúc dữ liệu vô cùng quan trọng giúp lưu trữ văn bản.

Trong bài học này chúng ta cùng tìm hiểu cách tiếp cận một bài thuật toán liên quan tới chuỗi.

Chi tiết nội dung:
- Vì sao xử lý chuỗi quan trọng?
- Đảo ngược chuỗi sử dụng vòng For
- Đảo ngược chuỗi sử dụng 2 con trỏ
- Leetcode 345 - Đảo ngược nguyên âm trong chuỗi
- Chuỗi Palindrome
- Khái niệm chuỗi con và dãy con
- Kỹ thuật đếm





Các dạng bài Leetcode thường gặp:

- Đảo ngược chuỗi
- Chuỗi Palindrome
- Phát hiện nguyên âm
- Bài toán đếm sử dụng mảng đếm


Chuỗi - String

Hình thức: Zoom

Nội dung: Giảng viên giải đáp thắc mắc về bài tập phân tích thuật toán cũng như lý thuyết bài tập chuỗi.

Chữa bài tập phân tích thuật toán

Bài tập trên lớp cho bài mảng. Bài tập về nhà sẽ được bổ sung vào 19:00 ngày 22/03/2022.

[LC] Day 4 - Array [In Class]

Trong bài này có 2 bài là dạng bài chúng ta có thể sử dụng chỉ mục âm. Bạn hãy cứ làm theo ý tưởng của mình, trong buổi nói chuyện thứ năm tuần này, mình sẽ trình bày cách sử dụng **chỉ mục âm** với dạng bài này.

[LC] Day 4 - Array [Homework]

Mảng trong Python giúp chúng ta lưu trữ nhiều kiểu dữ liệu liền nhau theo thứ tự.

Chi tiết:
- Giới thiệu về mảng
- Kỹ thuật sử dụng tổng dồn / tích dồn
- Ma trận
- Xoay ma trận với độ phức tạp không gian thêm O(1)

Một số dạng Leetcode hay gặp:

- Bài tập tìm 2 hoặc 3 phần tử có tổng bằng K cho trước
- Làm việc với ma trận 2 chiều
- Các bài toán tổng dồn / tích dồn
- Bài tập phần tử lặp lại, phần tử biến mất và phép tối ưu sao cho độ phức tạp không gian thấp.


Mảng - Array

[LC] Day 5 - Two Pointers [In class]

[LC] Day 5 - Two Pointers [Homework]

Kỹ thuật 2 con trỏ là một trong những kỹ thuật điển hình để tìm ra mảng con/ chuỗi con thỏa mãn một điều kiện cho trước.

Chi tiết:

- Giới thiệu kỹ thuật hai con trỏ
- Cách phát hiện những bài toán có thể áp dụng hai con trỏ
- Bài toán tìm mảng con có tổng bằng K
- So sánh thuật toán thường và hai con trỏ

Một số dạng Leetcode hay gặp:

- Chuỗi con / Mảng con thỏa mãn một điều kiện cho trước
- Chuỗi con / Mảng con ngắn/ dài nhất thỏa mãn một điều kiện cho trước



Hai con trỏ - Two Pointers

Chữa bài tập Chuỗi + Mảng

[LC] Day 6 - Stack [In Class]

[LC] Day 6 - Stack [Homework]

Ngăn xếp có rất nhiều ứng dụng trong tiền xử lý trong trí tuệ nhân tạo.

Các hệ thống chat real time sử dụng hàng đợi để xây dựng cơ chế truyền tải tin nhắn.

Trong bài học này chúng ta cùng rút ra một số quy luật khi gặp dạng bài Leetcode này.

- Dạng bài kiểm tra chuỗi 
- Dạng bài duỗi / nén chuỗi
- Dạng bài tìm phần tử trước và sau các phần tử trong mảng thỏa mãn một điều kiện cho trước

Video | Slide | Notebook


Ngăn xếp và Hàng đợi - Stack & Queue 

[LC] Day 7 - Recursion [In Class]

Đề bài cho bạn không truy cập được vào câu hỏi.

### 544. Output Contest Matches
----

During the NBA playoffs, we always set the rather strong team to play with the rather weak team, like make the rank 1 team play with the rank $$n^{th}$$ team, which is a good strategy to make the contest more interesting.

Given n teams, return their final contest matches in the form of a string.

The n teams are labeled from 1 to n, which represents their initial rank (i.e., Rank 1 is the strongest team and Rank n is the weakest team).

We will use parentheses `'(', and ')' and commas ','` to represent the contest team pairing. We use the parentheses for pairing and the commas for partition. During the pairing process in each round, you always need to follow the strategy of making the rather strong one pair with the rather weak one.

**Example 1:**

```python
Input: n = 4
Output: "((1,4),(2,3))"
Explanation:
In the first round, we pair the team 1 and 4, the teams 2 and 3 together, as we need to make the strong team and weak team together.
And we got (1, 4),(2, 3).
In the second round, the winners of (1, 4) and (2, 3) need to play again to generate the final winner, so you need to add the paratheses outside them.
And we got the final answer ((1,4),(2,3)).
```
**Example 2:**

```python
Input: n = 8
Output: "(((1,8),(4,5)),((2,7),(3,6)))"
Explanation:
First round: (1, 8),(2, 7),(3, 6),(4, 5)
Second round: ((1, 8),(4, 5)),((2, 7),(3, 6))
Third round: (((1, 8),(4, 5)),((2, 7),(3, 6)))
Since the third round will generate the final winner, you need to output the answer (((1,8),(4,5)),((2,7),(3,6))).
```

**Constraints:**

```
n == 2**x where x in in the range [1, 12].
```

[LC] Day 7 - Recursion [Homework]

Cùng tìm cách học đệ quy một cách dễ hình dung nhất.

Chi tiết:

- Giới thiệu đệ quy
- Đệ quy chiều xuôi
- Đệ quy chiều ngược
- Quy tắc đệ quy


Đệ quy

Chữa các bài tập

- Hai con trỏ: Leetcode 845 + 3 + 1234
- Ngăn xếp: Leetcode 856 + 739 + 503


Chữa bài hai con trỏ + ngăn xếp

### 252. Meeting Rooms
---

Given an array of meeting time `intervals` where `intervals[i] = [start_i, end_i]`, determine if a person could attend all meetings.

**Example 1:**

```
Input: intervals = [[0,30],[5,10],[15,20]]
Output: false
```

**Example 2:**

```
Input: intervals = [[7,10],[2,4]]
Output: true
```

**Constraints:**

```
0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start_i < end_i <= 10^6
```

### 253. Meeting Rooms II
---

Given an array of meeting time `intervals` intervals where `intervals[i] = [start_i, end_i]`, return the **minimum** number of conference rooms required.

**Example 1:**
```
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
```

**Example 2:**

```
Input: intervals = [[7,10],[2,4]]
Output: 1
```

**Constraints:**

```
1 <= intervals.length <= 10^4
0 <= start_i < end_i <= 10^6
```








[LC] Day 8 - Sort + Greedy [In Class]

Bài tập sắp xếp + Giải thuật tham lam

[LC] Day 8 - Sort + Greedy [Homework]

Giải thuật tham lam

Đôi khi chúng ta sử dụng giải thuật giam lam trong lập trình mà không hề hay biết.

Ví dụ mua chanh là một trong ví dụ dễ hiệu để mô tả thuật toán này. Khi học xong thuật toán này bạn có thể xử lý được những dạng bài Leetcode như sau:

- Các bài toán tối ưu sắp xếp công việc và thời gian
- Các bài tạo chuỗi / mảng theo một điều kiện cho trước

Video | Slide | Notebook

Thuật toán sắp xếp - Giải thuật tham lam

Bài tập trên lớp: Dạng bài tìm K phần tử lớn nhất/nhỏ nhất trong mảng

[LC] Day 9 - Heap [In Class]

Trong này có hai bài sắp xếp dựa trên trọng số sử dụng Heap

Xem gợi ý cách làm của dạng này [tại đây](https://protonx.io/courses/61dff33a4403b00013c4397f/topics/61e008203cc986001a162d9e/lessons/625556b1b0f2a5001b63b9cd/attachments/62556577b0f2a5001b63c3df)

[LC] Day 9 - Heap [Homework]

Heap là một cấu trúc dữ liệu đặc biệt được thiết kế để tối ưu tính toán một số bài toán cụ thể sau. 

- Bài toán tìm K phần tử thỏa mãn một điều kiện với chi phí thấp nhất
- Bài toán sắp xếp dựa trên trọng số

Video | Slide | Notebook


Đống - Heap

[LC] Day 10 - Graph

Nếu bạn có thắc mắc mạng xã hội làm sao có thể đề xuất bạn chung cho bạn, thì đồ thị chính là một trong những mấu chốt mà bạn cần học.

Trong bài học này chúng ta sẽ cùng sử dụng đồ thị để giải một số bài tập thú vị:

- Bài tập tìm chủ làng 
- Bài tập trồng hoa

Video | Slide | Notebook


Đồ thị - Graph

Chữa bài Leetcode

- Sắp xếp + tham lam: 1333 + 252 + 56 + 253 + 1710 + 121



Chữa bài đệ quy + sắp xếp + giải thuật tham lam

Xem hướng dẫn Leetcode 200 [tại đây](https://protonx.io/courses/61dff33a4403b00013c4397f/topics/61e0085b3cc986001a162da8?activeAId=625e869ba9b876001b3bd941)

[LC] Day 11 - BFS

Tìm đường ngắn nhất trong đồ thị là một trong những dạng bài tập có rất nhiều câu hỏi Leetcode liên quan.

Khi bạn học kỹ các dạng bài sau bạn sẽ hiểu tường tận được thuật toán này

- Tìm đường thỏa mãn một điều kiện K cho trước
- Kiểm tra đường
- Các bài toán tìm đường trong ma trận

Video | Slide | Notebook


Thuật toán BFS

[LC] Day 12 - DFS

Bên cạnh thuật toán tìm đường ngắn nhất, thuật toán tìm đường DFS hữu ích trong một số bài toán cụ thể khi bạn có thể lợi dụng tính chất của đệ quy để viết code ngắn gọn hơn.

Tuy nhiên để kiểm soát được thuật toán đệ quy cần có một cách tiếp cận chặt chẽ. Bạn sẽ học được kỹ năng đó trong bài học này.

- Bài toán liên quan đến tìm diện tích một vùng trong ma trận
- Tìm đường thỏa mãn một điều kiện K cho trước
- Bài toán kiểm tra chu trình trong đồ thị
- Dạng bài tô màu đồ thị

Video | Slide | Notebook


Thuật toán DFS

Chữa bài Heap: 692 + 1054 + 767 + 857

Chữa bài đồ thị: 1042


Chữa bài Heap + Đồ thị

[LC] Day 13 - Dijkstra [In Class]

Nếu bạn thắc mắc tính năng tìm đường trên Google Maps đã từng hoạt động như thế nào, thì thuật toán Dijkstra chính là câu trả lời cho bạn.

Video | Slide | Notebook


Thuật toán Dijkstra

[LC] Day 14 - Union Find [In Class]

[LC] Day 14 - Union Find [Homework]

Chữa bài tập BFS + DFS

[LC] Day 15 - Math [In Class]

[LC] Day 15 - Math [Homework]

Làm việc với các phép tính toán lớn yêu cầu bạn cần hiểu một số định luật cơ bản.

Một số dạng Toán sẽ giải quyết

- Các bài toán liên quan tới phép chia có dư
- Bài toán liên quan đến đồng hồ
- Bài toán đồng biến nghịch biến của hàm số

Video | Slide | Notebook


Toán học

[LC] Day 16 - Binary Tree [In Class]

Bài tập Cây:
-  ### 100. Same Tree
-  ### 513. Find Bottom Left Tree Value
-  ### 515. Find Largest Value in Each Tree Row
-  ### 199. Binary Tree Right Side View
-  ### 543. Diameter of Binary Tree
- ### 814. Binary Tree Pruning


[LC] Day 16 - Binary Tree [Homework]

Một trong web chúng ta sử dụng hàng ngày được lưu trữ dưới dạng cây. Hiểu được cấu trúc này bạn sẽ vượt qua rất nhiều thử thách hóc búa từ các công ty công nghệ lớn.

Các dạng bài sẽ giải quyết trong bài học này

Bài toán duyệt/tạo/thay đổi cây
Bài toán liên quan đến khoảng cách trong cây

Video | Slide | Notebook


Cây - Tree

[LC] Day 17 - Binary Search [In Class]

Bài tập tìm kiếm nhị phân về nhà:  1011 + 875 + 153 + 33




[LC] Day 17 - Binary Search [Homework]

Một kỹ thuật tìm kiếm loại trừ hiệu quả trong một số bài toán tối ưu mà bạn cần quan tâm.

Các dạng bài sẽ giải quyết:

- Bài toán tối ưu theo điều kiện K cho trước (Trọng lượng tàu ít nhất để vận chuyển hàng trong D ngày)
- Bài toán tìm kiếm theo một điều kiện K cho trước

Video | Slide | Notebook


Tìm kiếm nhị phân - Binary Search

Bài Dijkstra: 743

Bài Union Find: 684 + 1319 + 1579


Chữa bài Dijkstra + Union Find

[LC] Day 18 - Binary Search Tree [In class]

Dạng cây rất hay bắt gặp trong các bài phỏng vấn. Trong bài này chúng ta cùng tìm hiểu các thao tác cơ bản trên cây này nhé.

Video | Slide | Notebook


Cây tìm kiếm nhị phân - Binary Search Tree

Bài tập Linked List, giúp bạn nắm bắt được cách sử dụng con trỏ.

[LC] Day 19 - Linked List [In class]

Nếu bạn muốn xóa một phần tử khỏi mảng trong thời gian ngắn thì danh sách liên kết chính là một cấu trúc dữ liệu có thể bạn cần.

Sử dụng danh sách liên kết để giải quyết một số bài toán sau:

- Thay đổi node trong danh sách liên kết
- Tạo/duyệt danh sách liên kết

Video | Slide | Notebook


Danh sách liên kết - Linked List

Chữa các bài tập toán bao gồm:

1344 + 1217 + 1716 + 360

Gợi ý các bài liên quan tới cây.

Chữa bài toán + gợi ý các bài cây

Bài tập quy hoạch động
- Leetcode 70: Climbing Stairs
- Leetcode 518. Coin Change 2


[LC] Day 20 - Knapsack 0/1 [In class]

Tìm ra lựa chọn tối ưu trong nhiều lựa chọn khác nhau là mục tiêu của thuật toán này. Tuy nhiên các bài toán ứng dụng được thuật toán này đôi khi ẩn sâu trong nhiều dạng khác nhau mà cần một vài biến đổi trước khi áp dụng được ngay.

Trong bài học này chúng ta sẽ đề cập đến những dạng mà có thể quy về bài toán Knapsack quen thuộc.

Video | Slide | Notebook


Quy hoạch động cơ bản - Knapsack

[LC] Day 21 - Edit Distance

Chúng ta hoàn toàn có thể ứng dụng lập trình quy hoạch động trong một phần bài toán nhận diện âm thanh.

Cùng khám phá ứng dụng này nhé.

Video | Slide | Notebook


Danh sách chủ đề

Cấu trúc dữ liệu Union Find

1. Cuộc sống là kết nối

1.1. 14.1.1. Giới thiệu Union Find

2. Hợp đơn giản

2.1. 14.2.1. Giới thiệu hợp đơn giản

2.2. 14.2.2. Hợp đơn giản chi tiết

2.3. 14.2.3. Code hợp đơn giản

3. Hợp thông qua cha

3.1. 14.3.1 Giới thiệu hợp qua cha

3.2. 14.3.2. Hợp qua cha chi tiết

3.3. 14.3.2. Hợp qua cha chi tiết

4. Hợp qua cấp độ

4.1. [LC] 14.4.1. Hợp theo cấp độ

4.2. 14.4.2. Nén đường khi hợp

5. Dạng bài tìm nhóm

5.1. Leetcode 547 - Tìm nhóm

6. Dạng bài kết nối thừa

6.1. Gợi ý Leetcode 684 - Kết nối thừa

7. Slide bài giảng

7.1. 14. Union Find.pdf

Bài học