Các mẫu mã hóa: Một cách tiếp cận thông minh hơn để chuẩn bị phỏng vấn mã hóa

Chuẩn bị cho các cuộc phỏng vấn viết mã có thể là một thách thức thực sự đối với các nhà phát triển thường dành vài tuần để xem xét và tìm hiểu tài liệu mới.

Sự thật là hầu hết các nhà phát triển chưa bao giờ cảm thấy chuẩn bị đầy đủ cho cuộc phỏng vấn viết mã của họ. Không có gì lạ khi các nhà phát triển dành hàng tuần để giải quyết vấn đề trên LeetCode mà vẫn cảm thấy chưa chuẩn bị. Rõ ràng, có vấn đề với cách tiếp cận này.

Chúng ta hãy xem xét kỹ hơn một số vấn đề liên quan đến việc chuẩn bị phỏng vấn viết mã truyền thống.

Những cạm bẫy của việc chuẩn bị phỏng vấn truyền thống

Một trong những cạm bẫy phổ biến nhất trong quá trình chuẩn bị phỏng vấn truyền thống là thực hành "nghiền ngẫm". Cách tiếp cận này liên quan đến việc giải quyết càng nhiều vấn đề LeetCode càng tốt mà không cần có kế hoạch hoặc chiến lược rõ ràng. Mặc dù đây có vẻ là một chiến lược hiệu quả nhưng nó có một số nhược điểm.

Khi giải quyết vấn đề mà không có cách tiếp cận có cấu trúc, bạn có thể không nhận ra điểm yếu của mình. Không có kế hoạch có chủ ý cho việc học của bạn; mục tiêu chỉ đơn giản là giải quyết càng nhiều vấn đề càng tốt. Kết quả là, bạn có thể cảm thấy như mình đã học được rất nhiều điều, nhưng có thể vẫn còn những lỗ hổng đáng kể trong kiến thức của bạn.

Hơn nữa, vấn đề với điều này là về cơ bản nó xoay quanh việc ghi nhớ các giải pháp cho vô số vấn đề. Cố gắng ghi nhớ giải pháp cho hàng trăm vấn đề mã hóa khác nhau tỏ ra không hiệu quả khi người phỏng vấn đưa ra những câu hỏi thậm chí hơi khác so với những gì bạn đã gặp trước đây. Điều này có thể khiến bạn cảm thấy không được chuẩn bị để xử lý các biến thể của vấn đề.

Vấn đề cuối cùng của tôi với chiến lược này là về lâu dài, nó tạo ra nhiều căng thẳng và đau đầu hơn. Nếu bạn phải trải qua quá trình nhồi nhét kéo dài vài tuần giống nhau mỗi lần bạn muốn chuyển việc, thì lần nào bạn cũng sẽ gặp khó khăn. Bạn sẽ mất hàng tuần để học lại mọi thứ và giải quyết những vấn đề tương tự như trước đây.

Với những thách thức này, phải có một cách tốt hơn.

Một cách tốt hơn: Áp dụng các mẫu mã hóa

Vì vậy, có cách tiếp cận hiệu quả và bền vững hơn để chuẩn bị cho cuộc phỏng vấn lập trình không? Câu trả lời nằm ở việc hiểu và sử dụng các mẫu mã hóa.

Khi chuẩn bị cho các cuộc phỏng vấn viết mã, tôi ưu tiên nắm bắt các dạng vấn đề cơ bản. Các mẫu này, bao gồm các kỹ thuật như Hai con trỏ , Cửa sổ trượt , Tìm kiếm nhị phân được sửa đổi , Sắp xếp cấu trúc liên kết và nhiều kỹ thuật khác, cung cấp một khuôn khổ linh hoạt và mạnh mẽ để giải quyết một loạt các vấn đề về mã hóa. Sự nhấn mạnh chuyển từ việc ghi nhớ các giải pháp sang các kỹ thuật giải quyết vấn đề đã được chứng minh.

Bằng cách tập trung vào các mẫu mã hóa, bạn có thể hợp lý hóa đáng kể quá trình chuẩn bị phỏng vấn của mình, giúp quá trình này hiệu quả hơn.

Hãy nhớ rằng, hãy chuẩn bị thông minh hơn chứ không phải khó khăn hơn.

Những gì mong đợi?

Trong bài viết này tôi đã biên soạn 15 mẫu mã hóa hàng đầu mà bạn cần biết để trả lời bất kỳ câu hỏi mã hóa nào. Tôi sẽ chia nhỏ từng mẫu là gì và nó hoạt động như thế nào. Chia sẻ các chỉ báo chính để giúp bạn xác định mô hình và cuối cùng cung cấp đồ họa chi tiết cùng với mã mẫu để giúp bạn củng cố hiểu biết của mình.

Mặc dù tôi đề cập rất nhiều điều trong bài viết này, nhưng nếu bạn muốn được đào tạo chuyên sâu hơn, giải thích và thực hành viết mã, bạn có thể xem Khóa học Chuẩn bị Phỏng vấn Viết mã Toàn diện của chúng tôi tại Techinterviews.io. Chúng tôi cũng đề cập đến các chủ đề quan trọng như cấu trúc dữ liệu , phỏng vấn hành vi và thậm chí cả đàm phán tiền lương .

Bây giờ chúng ta hãy đi sâu vào các mẫu mã hóa này.

1. Đảo ngược danh sách liên kết

Đảo ngược danh sách liên kết liên quan đến việc thay đổi hướng của con trỏ trong danh sách liên kết để đảo ngược thứ tự các phần tử. Đây là một hoạt động cơ bản trong cấu trúc dữ liệu và thường yêu cầu thao tác cẩn thận với các tham chiếu nút.

Điều này rất hữu ích khi xử lý một danh sách liên kết và hạn chế là phải đảo ngược nó tại chỗ.

Quá trình đảo ngược danh sách liên kết tại chỗ như sau:

1. Bắt đầu bằng cách xác định ba biến: current , previous và next . Đặt hiện tại làm phần đầu của danh sách được liên kết và khởi tạo trước đó và tiếp theo là Không có.

2. Mặc dù biến hiện tại không phải là None , hãy tiến hành như sau:

   1. Lưu nút tiếp theo vào một biến tạm thời.
   2. Đảo ngược con trỏ của nút hiện tại để trỏ đến nút trước đó .
   3. Cập nhật trước đó là nút hiện tại và hiện tại là nút tiếp theo .

3. Cuối cùng, đặt phần đầu của danh sách đảo ngược thành nút cuối cùng đạt được, nút này được lưu trong biến trước đó .

Các chỉ số chính:

• Bạn cần đảo ngược thứ tự các phần tử trong danh sách liên kết.
• Các vấn đề liên quan đến việc kiểm tra các palindromes trong danh sách liên kết.
• Bạn muốn đảo ngược thứ tự các thành phần trong danh sách con cụ thể trong danh sách.

Mã mẫu:

Python

 def reverse_linked_list(head): curr = head prev = None while curr: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev

JS

 function reverseLinkedList(head) { let curr = head; let prev = null; while (curr) { const nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

Java

 public ListNode reverseLinkedList(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode nextNode = curr.next; curr.next = prev; prev = curr; curr = nextNode; } return prev; }

2. Tìm kiếm nhị phân đã sửa đổi

Tìm kiếm nhị phân đã sửa đổi điều chỉnh thuật toán tìm kiếm nhị phân cổ điển để giải quyết các vấn đề khác nhau. Các biến thể bao gồm tìm lần xuất hiện đầu tiên/cuối cùng của một phần tử hoặc tìm kiếm trong các mảng được xoay. Nó đòi hỏi phải xử lý cẩn thận các điểm giữa và các điều kiện.

Nếu bạn đã từng nhận được một mảng, danh sách liên kết hoặc ma trận được sắp xếp, hãy cân nhắc sử dụng tìm kiếm nhị phân đã sửa đổi .

Dưới đây là bảng phân tích cách áp dụng mẫu này cho cấu trúc dữ liệu được sắp xếp:

1. Bắt đầu bằng cách xác định điểm giữa giữa vị trí bắt đầu và kết thúc . Để tránh khả năng tràn số nguyên, sẽ an toàn hơn khi tính số ở giữa như sau: middle = start + (end - start) / 2 .
2. Kiểm tra xem khóa có khớp với phần tử ở chỉ mục ở giữa không. Nếu có, hãy trả về chỉ số ở giữa làm kết quả.
3. Nếu khóa không khớp với phần tử ở chỉ mục ở giữa , hãy chuyển sang các bước tiếp theo.
4. Đánh giá xem khóa có nhỏ hơn phần tử ở chỉ mục ở giữa hay không. Nếu đúng như vậy, hãy thu hẹp phạm vi tìm kiếm của bạn bằng cách cập nhật end thành middle - 1 .
5. Ngược lại, nếu khóa lớn hơn phần tử ở chỉ mục middle , hãy điều chỉnh phạm vi tìm kiếm của bạn bằng cách cập nhật start thành middle + 1 .

Các chỉ số chính:

• Bạn đang làm việc với cấu trúc dữ liệu được sắp xếp.
• Bạn cần tìm các yếu tố, ranh giới hoặc điểm xoay cụ thể một cách hiệu quả.
• Các vấn đề liên quan đến việc tìm kiếm trong các mảng được sắp xếp xoay vòng.

Mã mẫu:

Python

 def binary_search(arr: List[int], target: int) -> int: left, right = 0, len(arr) - 1 first_true_index = -1 # Perform binary search until left and right pointers meet while left <= right: mid = (left + right) // 2 if feasible(mid): # If the condition is true at mid index, update first_true_index first_true_index = mid right = mid - 1 else: # If the condition is false at mid index, narrow down the search space left = mid + 1 return first_true_index

JS

 function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; let firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { const mid = Math.floor((left + right) / 2); if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

Java

 public int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; int firstTrueIndex = -1; // Perform binary search until left and right pointers meet while (left <= right) { int mid = left + (right - left) / 2; if (feasible(mid)) { // If the condition is true at mid index, update firstTrueIndex firstTrueIndex = mid; right = mid - 1; } else { // If the condition is false at mid index, narrow down the search space left = mid + 1; } } return firstTrueIndex; }

3. Hai con trỏ

Kỹ thuật Hai con trỏ liên quan đến việc duy trì hai con trỏ đi qua cấu trúc dữ liệu, điển hình là mảng hoặc danh sách liên kết, thường được sử dụng cho các vấn đề liên quan đến cặp hoặc mảng con. Nó tối ưu hóa cho các vấn đề yêu cầu so sánh giữa các phần tử ở các vị trí khác nhau.

Ưu điểm của kỹ thuật này nằm ở tính đơn giản và hiệu quả, đặc biệt khi xử lý các cấu trúc dữ liệu tuyến tính như mảng hoặc chuỗi mà ban đầu bạn có thể chỉ sử dụng một con trỏ. Bằng cách sử dụng hai con trỏ, bạn có thể tránh các hoạt động dư thừa và nâng cao đáng kể hiệu quả thời gian chạy, có khả năng giảm hiệu suất từ O(n^2) xuống O(n) .

Mẫu "Hai con trỏ" bao gồm một số biến thể, mỗi biến thể được điều chỉnh cho phù hợp với các tình huống cụ thể. Các biến thể này bao gồm cùng hướng , hướng ngược nhau và một phương pháp duy nhất được gọi là "nhanh và chậm", thường được gọi là kỹ thuật "rùa và thỏ" , bao gồm hai con trỏ di chuyển với tốc độ khác nhau thông qua cấu trúc dữ liệu, đặc biệt hữu ích để phát hiện chu kỳ.

Nếu bạn sử dụng nhiều con trỏ để duyệt qua cấu trúc dữ liệu, bạn có thể phân loại cách tiếp cận của mình theo mẫu "Hai con trỏ" .

Các chỉ số chính:

• Bạn cần so sánh hoặc thao tác trên các phần tử ở các vị trí khác nhau.
• Các bài toán yêu cầu tìm kiếm các cặp phần tử trong một mảng đã được sắp xếp.
• Bạn muốn loại bỏ các bản sao khỏi một mảng được sắp xếp một cách hiệu quả.
• Khi xử lý các cấu trúc dữ liệu tuyến tính (mảng, chuỗi hoặc danh sách liên kết) và đối mặt với độ phức tạp thời gian bậc hai (giải pháp lực lượng vũ phu O(n^2 ), hãy cân nhắc sử dụng Hai con trỏ.

Mã mẫu:

Mẫu cho biến thể “hướng ngược lại”

Python

 def two_pointers_opposite(arr): left = 0 right = len(arr) - 1 ans = 0 while left < right: # Perform logic using the left and right pointers if CONDITION: left += 1 else: right -= 1 return ans

JS

 function twoPointersOpposite(arr) { let left = 0; let right = arr.length - 1; let ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

Java

 public int twoPointersOpposite(int[] arr) { int left = 0; int right = arr.length - 1; int ans = 0; while (left < right) { // Perform logic using the left and right pointers if (CONDITION) { left++; } else { right--; } } return ans; }

4. Cửa sổ trượt

Kỹ thuật Cửa sổ trượt liên quan đến việc duy trì một cửa sổ động trên cấu trúc dữ liệu tuyến tính, chẳng hạn như mảng, chuỗi hoặc danh sách liên kết. Kích thước của cửa sổ có thể thay đổi tùy thuộc vào cách triển khai cụ thể và nó cũng có thể được đặt làm giá trị cố định. Mục tiêu chính của cửa sổ này là liên tục theo dõi và thu thập dữ liệu đáp ứng các tiêu chí cụ thể, khiến nó đặc biệt có giá trị để giải quyết hiệu quả các vấn đề về mảng con hoặc chuỗi con.

Mẫu này thường sử dụng bản đồ băm để tạo điều kiện thuận lợi cho việc theo dõi dữ liệu riêng lẻ trong cửa sổ. Tuy nhiên, điều quan trọng cần lưu ý là cách tiếp cận này có thể dẫn đến độ phức tạp về không-thời gian là O(n) .

Các chỉ số chính:

• Bạn cần phân tích các mảng hoặc chuỗi con liền kề hoặc không liền kề.
• Các vấn đề liên quan đến việc theo dõi các chuỗi có độ dài thay đổi trong tập dữ liệu lớn hơn.
• Bạn muốn tìm mảng con tổng tối đa có độ dài cố định.
• Đầu vào của bài toán là một cấu trúc dữ liệu tuyến tính như mảng, danh sách liên kết hoặc chuỗi.

Mã mẫu:

Python

 def slidingWindow(nums): # Initialize necessary variables left = 0 window = [] # Initialize the window ans = 0 # Initialize the answer variable for right in range(len(nums)): window.append(nums[right]) # Expand the window to the right while invalid(window): # Condition to shrink the window from the left until it is valid again window.pop(0) # Remove the left element from the window left += 1 ans = max(ans, len(window)) # Update the answer, can vary on your implementation return ans

JS

 function slidingWindow(nums) { let left = 0; const window = []; // Initialize the window let ans = 0; // Initialize the answer variable for (let right = 0; right < nums.length; right++) { window.push(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.shift(); // Remove the left element from the window left++; } ans = Math.max(ans, window.length); // Update the answer , can vary on your implementation } return ans; }

Java

 public static int slidingWindow(int[] nums) { int left = 0; List<Integer> window = new ArrayList<>(); // Initialize the window int ans = 0; // Initialize the answer variable for (int right = 0; right < nums.length; right++) { window.add(nums[right]); // Expand the window to the right while (invalid(window)) { // Condition to shrink the window from the left until it is valid again window.remove(0); // Remove the left element from the window left++; } ans = Math.max(ans, window.size()); // Update the answer , can vary on your implementation } return ans; }

5. Yếu tố K hàng đầu

Mẫu này liên quan đến việc tìm K phần tử lớn nhất hoặc nhỏ nhất trong bộ sưu tập, thường được triển khai bằng cách sử dụng các cấu trúc dữ liệu như đống hoặc hàng đợi ưu tiên. Việc này rất hữu ích khi chọn một tập hợp con các phần tử dựa trên giá trị hoặc tần số của chúng.

Bất cứ khi nào chúng tôi được yêu cầu tìm các phần tử 'K' thường xuyên nhất, nhỏ nhất hoặc hàng đầu trong một tập dữ liệu nhất định, chúng tôi có thể xem xét sử dụng mẫu này.

Cách thức hoạt động rất đơn giản:

1. Chúng tôi chèn các phần tử 'K' vào vùng heap tối thiểu hoặc tối đa của mình (Điều này phụ thuộc vào việc triển khai).
2. Bất cứ khi nào chúng ta thêm vào heap, chúng ta phải điều chỉnh sao cho các phần tử 'K' thường xuyên/nhỏ nhất/trên cùng luôn được duy trì.

Vẻ đẹp của phương pháp này nằm ở tính hiệu quả của nó; bạn không cần phải sử dụng bất kỳ thuật toán sắp xếp nào vì bản thân vùng heap sẽ duy trì thứ tự cần thiết một cách tự nhiên cho bạn.

Các chỉ số chính:

• Bạn cần xác định K phần tử lớn nhất hoặc nhỏ nhất trong bộ sưu tập.
• Các vấn đề yêu cầu các yếu tố xếp hạng dựa trên các tiêu chí nhất định.
• Bạn muốn tìm K phần tử thường xuyên hàng đầu trong tập dữ liệu.

Mã mẫu:

Python

 import heapq def top_k_elements(arr, k): heap = [] for num in arr: # Define your own criteria and logic to push elements onto the heap # For example, if you want to find the top k largest elements, push (-num, num) onto the heap heapq.heappush(heap, (-CRITERIA, num)) if len(heap) > k: heapq.heappop(heap) return [num for _, num in heap]

JS

 function topKElements(arr, k) { const minHeap = []; for (const num of arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k smallest elements, push num onto the heap minHeap.push(CRITERIA); if (minHeap.length > k) { minHeap.sort((a, b) => a - b).shift(); } } return minHeap.sort((a, b) => a - b); }

Java

 import java.util.*; public List<Integer> topKElements(int[] arr, int k) { PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(a -> -CRITERIA)); for (int num : arr) { // Define your own criteria and logic to push elements onto the heap // For example, if you want to find the top k largest elements, push -num onto the heap heap.offer(-CRITERIA); if (heap.size() > k) { heap.poll(); } } List<Integer> topK = new ArrayList<>(); while (!heap.isEmpty()) { topK.add(-heap.poll()); } Collections.reverse(topK); return topK; }

6. Hai đống

Hai Heap sử dụng hai heap (một heap tối đa và một heap tối thiểu) để tối ưu hóa một số vấn đề nhất định, như tìm giá trị trung bình trong một tập dữ liệu. Mô hình này đặc biệt hữu ích để duy trì một cấu trúc cân bằng.

Đây là cách nó hoạt động:

1. Sử dụng hai đống: Heap tối đa để xác định phần tử lớn nhất và Heap tối thiểu để xác định phần tử nhỏ nhất.
2. Điền vào Max Heap với nửa số đầu tiên, nhằm mục đích tìm số lớn nhất trong số đó.
3. Điền vào Min Heap với nửa số sau để xác định số nhỏ nhất trong phần này.
4. Trung vị của tập hợp số hiện tại có thể được tính bất cứ lúc nào bằng cách kiểm tra các phần tử trên cùng của cả hai vùng.

Các chỉ số chính:

• Bạn cần duy trì một cấu trúc cân bằng để tìm kiếm trung vị hiệu quả.
• Các bài toán liên quan đến việc xử lý bài toán cửa sổ trượt với đường trung tuyến động.
• Bạn muốn ưu tiên các thành phần trong bộ sưu tập dựa trên giá trị của chúng.

Mã mẫu:

Python

 import heapq class TwoHeaps: def __init__(self): self.min_heap = [] # Right heap to store larger half self.max_heap = [] # Left heap to store smaller half def add_num(self, num): if not self.max_heap or num <= -self.max_heap[0]: heapq.heappush(self.max_heap, -num) else: heapq.heappush(self.min_heap, num) # Balance the heaps if necessary if len(self.max_heap) > len(self.min_heap) + 1: heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap)) elif len(self.min_heap) > len(self.max_heap): heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap)) def find_median(self): if len(self.max_heap) == len(self.min_heap): return (-self.max_heap[0] + self.min_heap[0]) / 2.0 else: return -self.max_heap[0] # Usage: two_heaps = TwoHeaps() two_heaps.add_num(1) two_heaps.add_num(2) median = two_heaps.find_median() print("Median:", median)

JS

 class TwoHeaps { constructor() { this.minHeap = []; // Right heap to store larger half this.maxHeap = []; // Left heap to store smaller half } addNumber(num) { if (this.maxHeap.length === 0 || num <= -this.maxHeap[0]) { this.maxHeap.push(-num); } else { this.minHeap.push(num); } // Balance the heaps if necessary if (this.maxHeap.length > this.minHeap.length + 1) { this.minHeap.push(-this.maxHeap.shift()); } else if (this.minHeap.length > this.maxHeap.length) { this.maxHeap.push(-this.minHeap.shift()); } } findMedian() { if (this.maxHeap.length === this.minHeap.length) { return (-this.maxHeap[0] + this.minHeap[0]) / 2; } else { return -this.maxHeap[0]; } } } // Usage: const twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); const median = twoHeaps.findMedian(); console.log("Median:", median);

Java

 import java.util.*; class TwoHeaps { private PriorityQueue<Integer> minHeap; // Right heap to store larger half private PriorityQueue<Integer> maxHeap; // Left heap to store smaller half public TwoHeaps() { minHeap = new PriorityQueue<>(); maxHeap = new PriorityQueue<>(Collections.reverseOrder()); } public void addNumber(int num) { if (maxHeap.isEmpty() || num <= -maxHeap.peek()) { maxHeap.offer(-num); } else { minHeap.offer(num); } // Balance the heaps if necessary if (maxHeap.size() > minHeap.size() + 1) { minHeap.offer(-maxHeap.poll()); } else if (minHeap.size() > maxHeap.size()) { maxHeap.offer(-minHeap.poll()); } } public double findMedian() { if (maxHeap.size() == minHeap.size()) { return (-maxHeap.peek() + minHeap.peek()) / 2.0; } else { return -maxHeap.peek(); } } } // Usage: TwoHeaps twoHeaps = new TwoHeaps(); twoHeaps.addNumber(1); twoHeaps.addNumber(2); double median = twoHeaps.findMedian(); System.out.println("Median: " + median);

7. Ngăn xếp đơn điệu

Đơn điệu - (của một hàm hoặc số lượng) thay đổi theo cách không bao giờ giảm hoặc không bao giờ tăng.

Ngăn xếp đơn điệu duy trì một chồng các phần tử theo thứ tự không tăng hoặc không giảm, thường được sử dụng để tìm các phần tử nhỏ hơn/lớn hơn gần nhất trong một mảng. Đó là một công cụ mạnh mẽ để tối ưu hóa một số vấn đề nhất định.

Thứ tự rất nghiêm ngặt, bất cứ khi nào chúng ta gặp một phần tử nhỏ hơn (hoặc lớn hơn) phần tử ở đầu ngăn xếp thì chúng ta phải bật ra từ ngăn xếp đơn điệu cho đến khi phần tử chúng ta muốn thêm là phần tử nhỏ nhất (hoặc lớn nhất) trong số đó. họ.

Các chỉ số chính:

• Bạn cần duy trì các phần tử theo thứ tự không tăng hoặc không giảm.
• Các vấn đề liên quan đến việc tìm phần tử nhỏ hơn hoặc lớn hơn gần nhất.
• Bạn muốn tối ưu hóa các hoạt động dựa trên ngăn xếp trong khi vẫn giữ nguyên trật tự.

Mã mẫu:

Python

 def monotonic_stack(items): stack = [] for item in items: # Adjust the condition for comparisons to suit your needs while stack and stack[-1] <= item: stack.pop() # Do something with the popped item here stack.append(item)

JS

 function monotonicStack(items) { const stack = []; for (const item of items) { // Adjust the condition for comparisons to suit your needs while (stack.length > 0 && stack[stack.length - 1] <= item) { stack.pop(); // Do something with the popped item here } stack.push(item); } return stack; }

Java

 import java.util.*; public static int[] monotonicStack(int[] items) { Deque<Integer> stack = new ArrayDeque<>(); for (int item : items) { // Adjust the condition for comparisons to suit your needs while (!stack.isEmpty() && stack.peekLast() <= item) { stack.pollLast(); // Do something with the popped item here } stack.offerLast(item); } int[] result = new int[stack.size()]; int i = stack.size() - 1; while (!stack.isEmpty()) { result[i--] = stack.pollLast(); } return result; }

8. Tìm kiếm theo chiều sâu

DFS , hay Tìm kiếm theo chiều sâu , là một phương pháp truyền tải trong đó bạn khám phá càng sâu càng tốt dọc theo một nhánh trước khi quay lui; nó được áp dụng rộng rãi trong các bài toán liên quan đến cây và đồ thị, đặc biệt là các phép toán duyệt và tìm kiếm.

Để thực hiện DFS trên cây, bạn cần bắt đầu từ gốc. Sau đó làm theo các bước dưới đây:

1. Khám phá nút hiện tại bằng cách truy cập các nút con của nó, thường là từ trái sang phải .
2. Áp dụng đệ quy quy trình DFS cho từng nút con, đi sâu hơn vào cây.
3. Khi tất cả các nút con đã được truy cập, hãy quay lại nút cha.
4. Lặp lại các bước 1-3 cho mỗi nút con chưa được truy cập của nút hiện tại cho đến khi tất cả các nút trong cây đã được truy cập.

Sự khác biệt với DFS trên biểu đồ: Sự khác biệt chính giữa DFS cây và DFS biểu đồ nằm ở sự hiện diện của các chu trình. Trong một cây, theo định nghĩa không có chu kỳ, vì vậy DFS cây đảm bảo rằng mỗi nút được truy cập chính xác một lần và nó tự nhiên chấm dứt khi toàn bộ cây được duyệt qua. Ngược lại, đồ thị DFS phải kết hợp các biện pháp bổ sung để xử lý các cấu trúc tuần hoàn trong đồ thị. Để tránh truy cập lại các nút trong một chu kỳ vô thời hạn, biểu đồ DFS yêu cầu các cơ chế như đánh dấu các nút đã truy cập và xử lý việc quay lui một cách thích hợp . Sự khác biệt này làm cho DFS đồ thị phức tạp hơn DFS cây do khả năng xảy ra các vòng lặp vô hạn khi có chu trình.

Các chỉ số chính:

• Bạn đang xử lý các cấu trúc cây và cần khám phá các thứ tự truyền tải cụ thể.
• Các vấn đề liên quan đến việc tìm đường đi, tính toán độ sâu hoặc thực hiện truyền tải theo thứ tự trước/theo thứ tự/sau thứ tự.
• Bạn muốn kiểm tra xem có tồn tại đường dẫn giữa hai nút hay không.

Mã mẫu:

Python

 def dfs(root, target): if root is None: # Base case: Check if the current node is None return None if root.val == target: # Base case: Check if the current node value matches the target return root left = dfs(root.left, target) # Recursively search the left subtree if left is not None: # If the target is found in the left subtree, return the result return left return dfs(root.right, target) # Recursively search the right subtree

JS

 function dfs(root, target) { if (root === null) { // Base case: Check if the current node is null return null; } if (root.val === target) { // Base case: Check if the current node value matches the target return root; } let left = dfs(root.left, target); // Recursively search the left subtree if (left !== null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

Java

 public TreeNode dfs(TreeNode root, int target) { if (root == null) { // Base case: Check if the current node is null return null; } if (root.val == target) { // Base case: Check if the current node value matches the target return root; } TreeNode left = dfs(root.left, target); // Recursively search the left subtree if (left != null) { // If the target is found in the left subtree, return the result return left; } return dfs(root.right, target); // Recursively search the right subtree }

9. Tìm kiếm theo chiều rộng

BFS là một kỹ thuật duyệt cây và đồ thị giúp khám phá tất cả các nút ở độ sâu hiện tại trước khi chuyển sang cấp độ tiếp theo.

Để thực hiện BFS trên cây, bạn cần bắt đầu từ gốc. Sau đó làm theo các bước dưới đây:

1. Khởi tạo cấu trúc dữ liệu hàng đợi trống để theo dõi các nút sẽ được truy cập.

2. Đưa nút gốc vào hàng đợi.

3. Nhập một vòng lặp cho đến khi hàng đợi trống:

   1. Dequeue nút ở phía trước hàng đợi.
   2. Xử lý nút đã được loại bỏ hàng đợi (ví dụ: truy cập hoặc thực hiện một số thao tác trên nút đó).
   3. Xếp tất cả các nút con của nút (nếu có) vào hàng đợi.

4. Lặp lại các bước 3a-3c cho đến khi hàng đợi trống.

5. Quá trình truyền tải BFS hoàn tất khi tất cả các nút trong cây đã được truy cập theo cấp độ, từ trái sang phải.

Về bản chất, BFS trên cây khám phá các nút theo cấp độ , bắt đầu từ gốc và di chuyển đến các nút con trước khi chuyển sang cấp độ tiếp theo. Điều này đảm bảo rằng các nút ở mỗi cấp độ được truy cập trước khi chuyển sang cấp độ tiếp theo, khiến nó đặc biệt hữu ích cho các tác vụ như tìm đường đi ngắn nhất trong cây không có trọng số hoặc khám phá cây theo cấp độ.

Sự khác biệt với BFS trên Đồ thị: Tương tự như DFS, Đồ thị BFS thích ứng với sự hiện diện của các chu trình và nhiều đường dẫn giữa các nút. Nó sử dụng các cơ chế như đánh dấu các nút đã truy cập và các điều kiện kết thúc chuyên biệt để điều hướng hiệu quả mạng lưới các mối quan hệ phức tạp trong biểu đồ.

Các chỉ số chính:

• Bạn cần phải đi qua một cây theo cấp độ.
• Các vấn đề liên quan đến việc tìm đường đi ngắn nhất trong đồ thị không có trọng số.
• Bạn muốn khám phá một cái cây hoặc đồ thị theo chiều rộng.

Mã mẫu:

Python

 from collections import deque def bfs(root): # Create a queue and initialize it with the root node queue = deque([root]) # Perform breadth-first search until the queue is empty while len(queue) > 0: # Dequeue the front node from the queue node = queue.popleft() # Process the current node for child in node.children: if is_goal(child): # If the goal condition is satisfied, return the child node return FOUND(child) # Enqueue the child node to explore it in the next iterations queue.append(child) # Return NOT_FOUND if the goal is not reached return NOT_FOUND

JS

 function bfs(root) { const queue = []; // Create a queue and initialize it with the root node queue.push(root); while (queue.length > 0) { // Perform breadth-first search until the queue is empty const node = queue.shift(); // Dequeue the front node from the queue for (const child of node.children) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return `FOUND ${child}`; } queue.push(child); // Enqueue the child node to explore it in the next iterations } } return 'NOT_FOUND'; // Return NOT_FOUND if the goal is not reached }

Java

 import java.util.LinkedList; import java.util.Queue; public String bfs(Node root) { Queue<Node> queue = new LinkedList<>(); // Create a queue and initialize it with the root node queue.offer(root); while (!queue.isEmpty()) { // Perform breadth-first search until the queue is empty Node node = queue.poll(); // Dequeue the front node from the queue for (Node child : node.getChildren()) { // Process the current node if (isGoal(child)) { // If the goal condition is satisfied, return the child node return "FOUND(child)"; } queue.offer(child); // Enqueue the child node to explore it in the next iterations } } return "NOT_FOUND"; // Return NOT_FOUND if the goal is not reached }

10. Union Find (Liên minh rời rạc)

Cấu trúc dữ liệu Union-Find , còn được gọi là Disjoint Set Union (DSU) , được sử dụng để quản lý và giải quyết hiệu quả các vấn đề liên quan đến các tập hợp rời rạc hoặc các thành phần được kết nối. Nó cung cấp các hoạt động để hợp nhất các tập hợp (kết hợp) và xác định tập hợp mà một phần tử thuộc về (tìm). Union-Find thường được sử dụng trong các thuật toán như Cây kéo dài tối thiểu của Kruskal và phát hiện chu kỳ trong biểu đồ.

Union Find được triển khai như sau:

1. Khởi tạo: Bắt đầu với một tập hợp các phần tử, mỗi phần tử được coi là một tập hợp riêng biệt. Chỉ định một đại diện duy nhất (thường là chính phần tử đó) cho mỗi bộ.
2. Phép toán hợp: Để hợp nhất hai tập hợp, hãy thực hiện phép toán hợp. Chọn đại diện của một tập hợp (thường dựa trên một số tiêu chí, như thứ hạng hoặc kích thước) và đặt nó làm đại diện của tập hợp kia. Điều này kết nối hai bộ một cách hiệu quả.
3. Thao tác tìm: Khi bạn cần xác định tập hợp mà một phần tử thuộc về, hãy sử dụng thao tác tìm. Bắt đầu với phần tử được đề cập, duyệt cây đi lên để tìm nút gốc (đại diện) của tập hợp của nó. Kỹ thuật nén đường dẫn có thể được áp dụng ở đây để tối ưu hóa các hoạt động tìm kiếm trong tương lai bằng cách làm cho các phần tử dọc theo đường dẫn trỏ trực tiếp đến thư mục gốc.
4. Phát hiện chu kỳ: Union-Find thường được sử dụng để phát hiện các chu trình trong biểu đồ. Khi thực hiện thao tác hợp, nếu cả hai phần tử thuộc cùng một tập hợp (nghĩa là chúng có cùng đại diện), điều đó cho thấy việc thêm một cạnh giữa các nút sẽ tạo ra một chu trình trong biểu đồ.
5. Tối ưu hóa: Các kỹ thuật tối ưu hóa khác nhau có thể được áp dụng để nâng cao hiệu quả của các hoạt động Union-Find, chẳng hạn như nén theo thứ hạng và nén đường dẫn.

Mã mẫu:

Python

 class UnionFind: def __init__(self): self.id = {} def find(self, x): y = self.id.get(x, x) if y != x: self.id[x] = y = self.find(y) return y def union(self, x, y): self.id[self.find(x)] = self.find(y)

JS

 class UnionFind { constructor() { this.id = {}; } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @returns The root parent of the element. */ find(x) { let y = this.id[x] || x; if (y !== x) { this.id[x] = y = this.find(y); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ union(x, y) { this.id[this.find(x)] = this.find(y); } }

Java

 import java.util.*; class UnionFind { private Map<String, String> id; public UnionFind() { id = new HashMap<>(); } /** * Find the root parent of an element in the set. * Implements path compression for better efficiency. * @param x The element to find the root parent for. * @return The root parent of the element. */ public String find(String x) { String y = id.getOrDefault(x, x); if (!y.equals(x)) { id.put(x, find(y)); } return y; } /** * Union two elements into the same set. * @param x The first element. * @param y The second element. */ public void union(String x, String y) { id.put(find(x), find(y)); } }

11. Sắp xếp tôpô

Đồ thị có hướng không theo chu kỳ (DAG) là đồ thị có hướng không có chu trình có hướng.

Sắp xếp cấu trúc liên kết là một thuật toán để sắp xếp các nút của biểu đồ chu kỳ có hướng ( DAG ) theo thứ tự tuyến tính, trong đó mỗi nút xuất hiện trước các nút kế tiếp của nó. Nó rất quan trọng đối với các tác vụ như lập lịch các phần phụ thuộc, biên dịch mã và phân tích mức độ ưu tiên của các tác vụ trong các ứng dụng khác nhau.

Dưới đây là bảng phân tích từng bước về Sắp xếp tôpô:

1. Khởi tạo: Bắt đầu bằng biểu đồ chu kỳ có hướng ( DAG ) biểu thị các nhiệm vụ hoặc nút có phần phụ thuộc. Khởi tạo hàng đợi để giữ các nút được sắp xếp.

2. Tính toán theo cấp độ: Tính toán theo cấp độ (số cạnh đến) cho mỗi nút trong biểu đồ. Các nút có bậc bằng 0 không có sự phụ thuộc và phù hợp làm điểm bắt đầu của việc sắp xếp tôpô.

3. Làm đầy hàng đợi ban đầu: Xếp hàng tất cả các nút có giá trị bằng 0 vào hàng đợi. Các nút này có thể được xử lý đầu tiên.

4. Vòng lặp sắp xếp cấu trúc liên kết: Trong khi hàng đợi không trống, hãy thực hiện các bước sau:

   1. Dequeue một nút từ phía trước hàng đợi.
   2. Xử lý nút (ví dụ: thêm nó vào danh sách đã sắp xếp).
   3. Đối với mỗi nút lân cận của nút (các nút mà nó trỏ tới), hãy giảm mức độ của chúng đi 1.
   4. Nếu mức độ của hàng xóm trở thành 0 do giảm dần, hãy đưa nó vào hàng đợi.

5. Hoàn thành: Khi vòng lặp sắp xếp cấu trúc liên kết hoàn tất, hàng đợi sẽ trống và danh sách được sắp xếp sẽ chứa tất cả các nút theo thứ tự cấu trúc liên kết hợp lệ.

6. Phát hiện chu kỳ: Nếu tại bất kỳ thời điểm nào trong quá trình sắp xếp tôpô, không có nút nào có giá trị bằng 0 trong hàng đợi, điều đó cho biết sự hiện diện của các chu kỳ trong biểu đồ, khiến việc sắp xếp tôpô không thể thực hiện được.

Kết quả của Sắp xếp cấu trúc liên kết là thứ tự tuyến tính của các nút tôn trọng sự phụ thuộc của chúng, làm cho nó phù hợp để lập lịch các tác vụ hoặc phân tích thứ tự thực hiện trong các ứng dụng khác nhau.

Các chỉ số chính:

• Vấn đề liên quan đến việc lập kế hoạch hoặc sắp xếp các nhiệm vụ có sự phụ thuộc.
• Bạn đang làm việc với biểu đồ chu kỳ có hướng (DAG).
• Các nhiệm vụ cần được thực hiện theo một thứ tự cụ thể trong khi vẫn tuân thủ các phụ thuộc của chúng.

Mã mẫu:

Python

 from collections import deque def find_indegree(graph): # Calculate the indegree of each node in the graph indegree = {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: indegree[neighbor] += 1 return indegree def topological_sort(graph): result = [] queue = deque() indegree = find_indegree(graph) # Add nodes with 0 indegree to the queue for node in indegree: if indegree[node] == 0: queue.append(node) while queue: node = queue.popleft() result.append(node) # Update the indegree of neighboring nodes for neighbor in graph[node]: indegree[neighbor] -= 1 if indegree[neighbor] == 0: queue.append(neighbor) # If all nodes are visited, return the result if len(graph) == len(result): return result else: return None

JS

 /** * Finds the indegree of each node in the graph. * @param {object} graph - The input graph. * @returns {object} - The indegree of each node. */ function findIndegree(graph) { const indegree = {}; for (const node in graph) { indegree[node] = 0; } for (const node in graph) { for (const neighbor of graph[node]) { indegree[neighbor]++; } } return indegree; } /** * Performs topological sorting on the given graph. * @param {object} graph - The input graph. * @returns {array|null} - The sorted nodes in topological order or null if a cycle is detected. */ function topologicalSort(graph) { const result = []; const queue = []; const indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (const node in indegree) { if (indegree[node] === 0) { queue.push(node); } } while (queue.length > 0) { const node = queue.shift(); result.push(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (const neighbor of graph[node]) { indegree[neighbor]--; if (indegree[neighbor] === 0) { queue.push(neighbor); } } } // Check if all nodes have been visited (no cycles) if (Object.keys(graph).length === result.length) { return result; } else { return null; } }

Java

 import java.util.*; /** * Finds the indegree of each node in the graph. * @param graph - The input graph. * @return The indegree of each node. */ public Map<String, Integer> findIndegree(Map<String, List<String>> graph) { Map<String, Integer> indegree = new HashMap<>(); for (String node : graph.keySet()) { indegree.put(node, 0); } for (String node : graph.keySet()) { for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.getOrDefault(neighbor, 0) + 1); } } return indegree; } /** * Performs topological sorting on the given graph. * @param graph - The input graph. * @return The sorted nodes in topological order or null if a cycle is detected. */ public List<String> topologicalSort(Map<String, List<String>> graph) { List<String> result = new ArrayList<>(); Queue<String> queue = new LinkedList<>(); Map<String, Integer> indegree = findIndegree(graph); // Add nodes with no incoming edges to the queue for (String node : indegree.keySet()) { if (indegree.get(node) == 0) { queue.offer(node); } } while (!queue.isEmpty()) { String node = queue.poll(); result.add(node); // Decrement the indegree of neighbors and enqueue if indegree becomes zero for (String neighbor : graph.get(node)) { indegree.put(neighbor, indegree.get(neighbor) - 1); if (indegree.get(neighbor) == 0) { queue.offer(neighbor); } } } // Check if all nodes have been visited (no cycles) if (graph.size() == result.size()) { return result; } else { return null; } }

12. Thử (Cây tiền tố)

Trie là một cấu trúc dữ liệu dạng cây được sử dụng để khớp chuỗi và lưu trữ các từ một cách hiệu quả. Nó vượt trội trong các vấn đề mà bạn cần lưu trữ và tìm kiếm các chuỗi có tiền tố phổ biến.

Đây là cách triển khai Trie:

1. Khởi tạo: Bắt đầu bằng một Trie trống, thường bao gồm một nút gốc không có ký tự liên quan.

2. Chèn: Để chèn một từ vào Trie, bắt đầu từ nút gốc và duyệt xuống cây, mỗi lần một ký tự. Với mỗi ký tự trong từ:

   1. Kiểm tra xem nút con có ký tự đó có tồn tại dưới nút hiện tại hay không.
   2. Nếu có, hãy chuyển đến nút con.
   3. Nếu không, hãy tạo một nút con mới có ký tự đó và di chuyển đến nút đó.

3. Hoàn thành từ: Để kiểm tra xem một từ có tồn tại trong Trie hay không, duyệt qua nó theo cách tương tự như chèn. Đảm bảo rằng mỗi ký tự trong từ tương ứng với nút con của nút hiện tại. Nếu quá trình truyền tải đến cuối từ và có điểm đánh dấu kết thúc hợp lệ (ví dụ: cờ boolean) ở nút ký tự cuối cùng, thì từ đó tồn tại trong Trie.

4. Tìm kiếm tiền tố: Trie vượt trội trong việc tìm kiếm tiền tố. Để tìm tất cả các từ có tiền tố nhất định, hãy bắt đầu duyệt tại nút gốc và di chuyển xuống cây theo các ký tự của tiền tố. Khi bạn đạt đến ký tự cuối cùng của tiền tố, bạn có thể thực hiện tìm kiếm theo chiều sâu (DFS) từ nút đó để tìm tất cả các từ có chung tiền tố.

5. Xóa: Để xóa một từ khỏi Trie, hãy thực hiện tìm kiếm từ đó. Khi đến cuối từ, hãy xóa dấu kết thúc (nếu có). Nếu nút không có nút con nào khác, bạn có thể loại bỏ toàn bộ nhánh của Trie, đại diện cho từ một cách an toàn.

Việc thử có thể tốn nhiều bộ nhớ, đặc biệt đối với những từ vựng lớn. Để tối ưu hóa bộ nhớ, có thể áp dụng các kỹ thuật như nén (ví dụ: sử dụng bản đồ thay vì mảng ký tự trong mỗi nút) và cắt tỉa (loại bỏ các nút không có nút con).

Các lần thử đặc biệt hữu ích để khớp chuỗi hiệu quả, đề xuất tự động hoàn thành, trình kiểm tra chính tả và lập chỉ mục các từ có tiền tố phổ biến. Chúng cung cấp một cách nhanh chóng và tiết kiệm không gian để lưu trữ và tìm kiếm các từ hoặc chuỗi có tiền tố được chia sẻ trong cấu trúc giống như cây.

Các chỉ số chính:

• Bạn đang xử lý các chuỗi và cần kết hợp chuỗi hiệu quả.
• Các vấn đề liên quan đến đề xuất tự động hoàn thành, trình kiểm tra chính tả hoặc tìm kiếm các từ có tiền tố phổ biến.
• Bạn muốn lưu trữ và tìm kiếm từ ngữ một cách hiệu quả.

Mã mẫu:

Python

 class TrieNode: def __init__(self, value): self.value = value self.children = {} def insert(self, s, idx): # idx: index of the current character in s if idx != len(s): self.children.setdefault(s[idx], TrieNode(s[idx])) self.children.get(s[idx]).insert(s, idx + 1)

JS

 class TrieNode { constructor(value) { this.value = value; this.children = {}; } insert(s, idx) { // idx: index of the current character in s if (idx !== s.length) { if (!this.children[s[idx]]) { this.children[s[idx]] = new TrieNode(s[idx]); } this.children[s[idx]].insert(s, idx + 1); } } }

Java

 import java.util.*; class TrieNode { char value; Map<Character, TrieNode> children; TrieNode(char value) { this.value = value; this.children = new HashMap<>(); } void insert(String s, int idx) { // idx: index of the current character in s if (idx != s.length()) { char c = s.charAt(idx); if (!children.containsKey(c)) { children.put(c, new TrieNode(c)); } children.get(c).insert(s, idx + 1); } } }

13. Lập trình động

Lập trình động là một kỹ thuật giải quyết vấn đề mạnh mẽ được sử dụng trong khoa học máy tính và toán học để giải quyết một cách hiệu quả nhiều vấn đề phức tạp. Nó đặc biệt có giá trị khi một bài toán có thể được chia thành các bài toán con đơn giản hơn và lời giải cho các bài toán con này có thể được kết hợp để giải quyết bài toán tổng thể.

Dưới đây là các đặc điểm chính của nó và cách thức hoạt động:

Cấu trúc tối ưu:

• Đặc điểm này đề cập đến đặc tính là một giải pháp tối ưu cho một vấn đề lớn hơn có thể được xây dựng từ các giải pháp tối ưu cho các vấn đề con nhỏ hơn của nó.
• Nói cách khác, các bài toán DP thể hiện một cấu trúc đệ quy, trong đó lời giải tối ưu cho một bài toán dựa trên lời giải tối ưu của các bài toán con của nó.
• Ví dụ, khi tìm đường đi ngắn nhất giữa hai điểm trong đồ thị, đường đi ngắn nhất giữa hai điểm trung gian bất kỳ cũng phải là đường đi tối ưu.

Các vấn đề con chồng chéo:

• Các bài toán con chồng chéo xảy ra khi các bài toán con giống nhau được giải nhiều lần trong quá trình tính toán, dẫn đến công việc dư thừa.
• Lập trình động nhằm mục đích giải quyết vấn đề này bằng cách lưu trữ giải pháp cho các bài toán con trong cấu trúc dữ liệu (thường là bảng hoặc mảng ghi nhớ) để tránh tính toán lại chúng.
• Việc lưu trữ và tái sử dụng các giải pháp bài toán con này làm giảm đáng kể độ phức tạp về thời gian của thuật toán.

Cách thức hoạt động của lập trình động:

1. Xác định các bài toán con: Bước đầu tiên để giải một bài toán bằng DP là xác định các bài toán con. Chia vấn đề thành các vấn đề nhỏ hơn, dễ quản lý hơn, khi được giải quyết sẽ góp phần giải quyết vấn đề chính.
2. Giải pháp đệ quy: Phát triển một giải pháp đệ quy thể hiện giải pháp của một vấn đề lớn hơn dưới dạng giải pháp cho các vấn đề con nhỏ hơn. Công thức đệ quy này nắm bắt được cấu trúc con tối ưu.
3. Ghi nhớ hoặc lập bảng: Để giải quyết các bài toán con chồng chéo, bạn có thể chọn giữa hai kỹ thuật phổ biến:
   • Ghi nhớ: Lưu trữ kết quả của các bài toán con trong cấu trúc dữ liệu (thường là mảng hoặc bảng băm) khi chúng được tính toán. Khi gặp lại một bài toán con, hãy lấy lời giải của nó từ bộ lưu trữ thay vì tính toán lại. Đây còn được gọi là cách tiếp cận từ trên xuống .
   • Lập bảng: Tạo một bảng (thường là mảng 2D) để lưu trữ lời giải cho các bài toán con theo kiểu từ dưới lên . Bắt đầu bằng cách giải các bài toán con nhỏ nhất và dần dần phát triển bài toán chính.
4. Lời giải tối ưu: Khi tất cả các bài toán con được giải quyết, lời giải của bài toán chính có thể thu được bằng cách kết hợp lời giải của các bài toán con theo cấu trúc đệ quy của bài toán.

Lập trình động được áp dụng cho nhiều vấn đề, bao gồm tìm đường đi ngắn nhất trong biểu đồ, tối ưu hóa phân bổ tài nguyên, đếm các tổ hợp, giải các bài toán về chiếc ba lô, v.v. Khả năng tối ưu hóa các giải pháp bằng cách chia nhỏ các vấn đề phức tạp thành các phần đơn giản hơn và tránh tính toán dư thừa khiến nó trở thành một kỹ thuật cơ bản trong thiết kế và tối ưu hóa thuật toán.

Các khái niệm quan trọng: Cách tiếp cận từ dưới lên, Từ trên xuống, Ghi nhớ, Lập bảng

Các chỉ số chính:

• Vấn đề có thể được chia thành các vấn đề con chồng chéo nhỏ hơn.
• Cần phải tối ưu hóa bằng cách lưu trữ và sử dụng lại lời giải cho các bài toán con.
• Bạn muốn giải quyết các vấn đề liên quan đến tối ưu hóa hoặc đếm.

Mã mẫu:

Mẫu ghi nhớ từ trên xuống là một trong nhiều cách để triển khai lập trình động.

Python

 def top_down_memo(arr): def dp(state): # Base case(s): Define your own base case(s) for the problem if base_case: return 0 # Check if the state has already been memoized if state in memo: return memo[state] # Calculate the result using recurrence relation and memoize it result = recurrence_relation(state) memo[state] = result return result memo = {} # Memoization table to store calculated results return dp(initial_state)

JS

 function topDownMemo(arr) { function dp(state) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.has(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it const result = recurrenceRelation(state); memo.set(state, result); return result; } const memo = new Map(); // Memoization map to store calculated results return dp(initialState); }

Java

 import java.util.HashMap; import java.util.Map; public int topDownMemo(int[] arr) { Map<StateType, Integer> memo = new HashMap<>(); // Memoization map to store calculated results return dp(initialState, memo); } private int dp(StateType state, Map<StateType, Integer> memo) { // Base case(s): Define your own base case(s) for the problem if (baseCase) { return 0; } // Check if the state has already been memoized if (memo.containsKey(state)) { return memo.get(state); } // Calculate the result using recurrence relation and memoize it int result = recurrenceRelation(state); memo.put(state, result); return result; }

14. Quay lại

Quay lui là một kỹ thuật thuật toán chung để giải quyết vấn đề theo từng bước bằng cách thử các khả năng khác nhau và hủy bỏ chúng nếu chúng không dẫn đến giải pháp. Nó được sử dụng khi cần tìm kiếm toàn diện.

Dưới đây là một cái nhìn sâu sắc về cách thức hoạt động của việc quay lui:

1. Khám phá không gian vấn đề: Quay lại khám phá không gian vấn đề bằng cách xây dựng dần dần từng giải pháp một. Ở mỗi bước, nó đưa ra quyết định và tiến về phía trước.
2. Cấu trúc đệ quy: Quay lui thường liên quan đến đệ quy. Nó bắt đầu với một giải pháp từng phần ban đầu và khám phá tất cả các cách có thể để mở rộng nó. Quá trình này tiếp tục đệ quy cho đến khi tìm thấy một giải pháp hoàn chỉnh hoặc nó trở nên rõ ràng rằng không có giải pháp hợp lệ nào tồn tại.
3. Điểm quyết định: Ở mỗi bước, có những điểm quyết định mà thuật toán phải chọn từ các tùy chọn có sẵn. Những lựa chọn này dẫn đến sự phân nhánh trong quá trình thăm dò.
4. Xác thực giải pháp: Sau khi đưa ra lựa chọn, thuật toán sẽ kiểm tra xem giải pháp từng phần hiện tại có hợp lệ hay không. Nếu nó hợp lệ, thuật toán sẽ chuyển sang bước tiếp theo. Nếu không, nó sẽ quay lại, hoàn tác lựa chọn trước đó và khám phá các lựa chọn khác.
5. Điều kiện chấm dứt: Việc quay lui tiếp tục cho đến khi đáp ứng một trong hai điều kiện:
   • Một giải pháp hợp lệ được tìm thấy, trong trường hợp đó thuật toán dừng và trả về giải pháp.
   • Nó được xác định rằng không có giải pháp hợp lệ nào tồn tại, tại thời điểm đó, thuật toán quay lại điểm quyết định trước đó và khám phá các tùy chọn khác nhau.
6. Cắt tỉa: Để tối ưu hóa việc tìm kiếm, việc quay lại thường bao gồm các chiến lược cắt tỉa. Việc cắt tỉa liên quan đến việc tránh việc khám phá các đường dẫn được đảm bảo dẫn đến các giải pháp không hợp lệ, làm giảm đáng kể không gian tìm kiếm.

Các ứng dụng của Quay lui:

Quay lui được sử dụng trong nhiều lĩnh vực có vấn đề khác nhau, bao gồm:

• Giải các câu đố như Sudoku và N-Queens.
• Tạo hoán vị và kết hợp.
• Tìm kiếm đường đi trong đồ thị và cây.
• Các vấn đề hạn chế sự hài lòng (ví dụ, vấn đề nhân viên bán hàng du lịch).
• Các thuật toán chơi trò chơi (ví dụ AI cờ vua).

Các chỉ số chính:

• Vấn đề liên quan đến việc khám phá nhiều khả năng theo từng bước.
• Có những điểm quyết định hoặc những ràng buộc đòi hỏi phải thử các lựa chọn khác nhau.
• Bạn cần tìm tất cả các giải pháp khả thi hoặc đáp ứng các điều kiện cụ thể thông qua tìm kiếm toàn diện.

Mã mẫu:

Python

 def backtrack(curr, OTHER_ARGUMENTS...): if BASE_CASE: # Modify the answer according to the problem's requirements return ans = 0 for ITERATE_OVER_INPUT: # Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS...) # Undo the modification of the current state (backtrack) return ans

JS

 function backtrack(curr, ...OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } let ans = 0; for (let i = 0; i < ITERATE_OVER_INPUT.length; i++) { const item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, ...OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

Java

 public int backtrack(StateType curr, OtherArgumentType... OTHER_ARGUMENTS) { if (BASE_CASE) { // Modify the answer according to the problem's requirements return; } int ans = 0; for (int i = 0; i < ITERATE_OVER_INPUT.length; i++) { ItemType item = ITERATE_OVER_INPUT[i]; // Modify the current state according to the problem's requirements ans += backtrack(curr, OTHER_ARGUMENTS); // Undo the modification of the current state (backtrack) } return ans; }

15. Hợp nhất các khoảng thời gian

Việc hợp nhất các khoảng thời gian liên quan đến việc kết hợp các khoảng thời gian chồng chéo hoặc liền kề thành một tập hợp hợp nhất, thường được sử dụng trong các vấn đề liên quan đến khoảng thời gian hoặc lập kế hoạch. Nó đơn giản hóa các hoạt động dựa trên khoảng thời gian.

Dưới đây là cái nhìn sâu hơn về cách hoạt động của khoảng thời gian hợp nhất:

1. Biểu diễn khoảng: Các khoảng thường được biểu diễn dưới dạng cặp điểm bắt đầu và điểm kết thúc (ví dụ: [bắt đầu, kết thúc] ).
2. Sắp xếp: Để hợp nhất các khoảng thời gian một cách hiệu quả, hãy bắt đầu bằng cách sắp xếp chúng dựa trên điểm bắt đầu của chúng. Điều này đảm bảo rằng các khoảng chồng chéo hoặc liền kề nằm liền kề trong danh sách được sắp xếp.
3. Quá trình hợp nhất: Khởi tạo một danh sách trống để giữ các khoảng thời gian đã hợp nhất. Sau đó, lặp lại từng khoảng thời gian được sắp xếp:
   • Nếu khoảng thời gian hiện tại không trùng với khoảng thời gian trước đó, hãy thêm khoảng thời gian đó vào danh sách các khoảng thời gian đã hợp nhất.
   • Nếu có sự trùng lặp, hãy cập nhật điểm cuối của khoảng thời gian được hợp nhất trước đó để bao gồm cả khoảng thời gian hiện tại và trước đó, hợp nhất chúng một cách hiệu quả.
4. Hoàn thành: Sau khi xử lý tất cả các khoảng, danh sách các khoảng được hợp nhất sẽ chứa các khoảng không chồng chéo và hợp nhất.

Các ứng dụng của khoảng thời gian hợp nhất:

Khoảng thời gian hợp nhất thường được sử dụng trong:

• Ứng dụng lập kế hoạch và quản lý thời gian.
• Phát hiện sự kiện chồng chéo trong hệ thống lịch.
• Phân tích dữ liệu dựa trên khoảng thời gian, chẳng hạn như trong các truy vấn cơ sở dữ liệu.
• Giải quyết các vấn đề liên quan đến phân bổ nguồn lực và lập lịch họp.

Bằng cách hợp nhất các khoảng chồng chéo, kỹ thuật này đơn giản hóa các hoạt động dựa trên khoảng thời gian và nâng cao hiệu quả trong các ứng dụng khác nhau.

Các chỉ số chính:

• Bạn đang xử lý các khoảng thời gian hoặc dữ liệu dựa trên thời gian.
• Các vấn đề liên quan đến việc hợp nhất các khoảng chồng chéo hoặc liền kề.
• Bạn muốn đơn giản hóa các hoạt động dựa trên khoảng thời gian hoặc tối ưu hóa việc lập kế hoạch sự kiện.

Mã mẫu:

Python

 def merge_intervals(intervals): # 1. Sort the intervals based on their start values. intervals.sort(key=lambda x: x[0]) # 2. Initialize an empty list to store merged intervals. merged_intervals = [] # 3. Iterate through the sorted intervals. for interval in intervals: # 4. If the merged_intervals list is empty or the current interval does not overlap with the last merged interval: if not merged_intervals or interval[0] > merged_intervals[-1][1]: merged_intervals.append(interval) else: # 5. If the current interval overlaps with the last merged interval, merge them. merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1]) # 6. Return the merged_intervals list. return merged_intervals

JS

 function mergeIntervals(intervals) { // 1. Sort the intervals based on their start values. intervals.sort((a, b) => a[0] - b[0]); // 2. Initialize an empty array to store merged intervals. const mergedIntervals = []; // 3. Iterate through the sorted intervals. for (const interval of intervals) { // 4. If the mergedIntervals array is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.length === 0 || interval[0] > mergedIntervals[mergedIntervals.length - 1][1]) { mergedIntervals.push(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals[mergedIntervals.length - 1][1] = Math.max(mergedIntervals[mergedIntervals.length - 1][1], interval[1]); } } // 6. Return the mergedIntervals array. return mergedIntervals; }

Java

 public class MergeIntervals { public int[][] merge(int[][] intervals) { // 1. Sort the intervals based on their start values. Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // 2. Create a list to store merged intervals. List<int[]> mergedIntervals = new ArrayList<>(); // 3. Iterate through the sorted intervals. for (int[] interval : intervals) { // 4. If the mergedIntervals list is empty or the current interval does not overlap with the last merged interval: if (mergedIntervals.isEmpty() || interval[0] > mergedIntervals.get(mergedIntervals.size() - 1)[1]) { mergedIntervals.add(interval); } else { // 5. If the current interval overlaps with the last merged interval, merge them. mergedIntervals.get(mergedIntervals.size() - 1)[1] = Math.max(mergedIntervals.get(mergedIntervals.size() - 1)[1], interval[1]); } } // 6. Convert the list to an array and return it. return mergedIntervals.toArray(new int[mergedIntervals.size()][]); } }

Muốn tìm hiểu thêm?

Nếu bạn muốn tìm hiểu thêm về các mẫu này và cách bạn có thể triển khai chúng hiệu quả hơn trong cuộc phỏng vấn viết mã tiếp theo, hãy xem techinterviews.io ngay hôm nay! Chúng tôi cung cấp một chương trình giảng dạy toàn diện để bạn chuẩn bị cho cuộc phỏng vấn viết mã tiếp theo, bao gồm các chủ đề như cấu trúc dữ liệu , thuật toán , phỏng vấn hành vi và thậm chí cả đàm phán lương . Chúng tôi thậm chí còn có không gian làm việc viết mã tích hợp sẵn để bạn thực hành.

Hãy tăng cường quá trình chuẩn bị cho cuộc phỏng vấn viết mã của bạn ngay hôm nay với mã khuyến mãi TECH30 của chúng tôi với mức giảm giá $30!