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 Cách tiếp cận này liên quan đến việc giải quyết càng nhiều vấn đề 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. "nghiền ngẫm". LeetCode 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ư , , , 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. 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 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 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. 15 mẫu mã hóa hàng đầu 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 của chúng tôi tại Chúng tôi cũng đề cập đến các chủ đề quan trọng như , và thậm chí cả . Khóa học Chuẩn bị Phỏng vấn Viết mã Toàn diện Techinterviews.io. cấu trúc dữ liệu phỏng vấn hành vi đà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: Bắt đầu bằng cách xác định ba biến: , và . Đặ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ó. current previous next Mặc dù biến hiện tại không phải là , hãy tiến hành như sau: None Lưu nút vào một biến tạm thời. tiếp theo Đảo ngược con trỏ của nút để trỏ đến nút . hiện tại trước đó Cập nhật là nút hiện tại và là nút . trước đó hiện tại tiếp theo Cuối cùng, đặt 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 . phần đầu 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 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. Tìm kiếm nhị phâ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: Bắt đầu bằng cách xác định điểm giữa giữa vị trí và . Để tránh khả năng tràn số nguyên, sẽ an toàn hơn khi tính số ở giữa như sau: . bắt đầu kết thúc middle = start + (end - start) / 2 Kiểm tra xem khóa có khớp với phần tử ở chỉ mục không. Nếu có, hãy trả về chỉ số làm kết quả. ở giữa ở giữa Nếu khóa không khớp với phần tử ở chỉ mục , hãy chuyển sang các bước tiếp theo. ở giữa Đánh giá xem khóa có nhỏ hơn phần tử ở chỉ mục 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 thành . ở giữa end middle - 1 Ngược lại, nếu khóa lớn hơn phần tử ở chỉ mục , 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 thành . middle start 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ỏ 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. Kỹ thuật Hai con trỏ Ư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ừ xuống . O(n^2) O(n) Mẫu 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 , và một phương pháp duy nhất được gọi là thường được gọi là kỹ thuật , 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ỳ. "Hai con trỏ" cùng hướng hướng ngược nhau "nhanh và chậm", "rùa và thỏ" 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 ), hãy cân nhắc sử dụng Hai con trỏ. O(n^2 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 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. Kỹ thuật Cửa sổ trượt 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 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: 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). 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 topKElements(int[] arr, int k) { PriorityQueue 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 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: 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. Sử dụng hai đống: Đ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ố đó. Điền vào Min Heap với nửa số sau để xác định số nhỏ nhất trong phần này. 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 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.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 minHeap; // Right heap to store larger half private PriorityQueue 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 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] 0 && stack[stack.length - 1] 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 , hay , 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. DFS Tìm kiếm theo chiều sâu Để 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: 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ừ sang . trái phải cho từng nút con, đi sâu hơn vào cây. Áp dụng đệ quy quy trình DFS Khi tất cả các nút con đã được truy cập, lại nút cha. hãy quay 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. Lặp lại các bước 1-3 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ư và . 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. Sự khác biệt với DFS trên biểu đồ: đánh dấu các nút đã truy cập xử lý việc quay lui một cách thích hợp 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: 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. nút gốc vào hàng đợi. Đưa Nhập một vòng lặp cho đến khi hàng đợi trống: Dequeue nút ở phía trước hàng đợi. 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 đó). Xếp tất cả các nút con của nút (nếu có) vào hàng đợi. cho đến khi hàng đợi trống. Lặp lại các bước 3a-3c 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 , 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 độ. theo cấp độ 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 đồ. Sự khác biệt với BFS trên Đồ thị: 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 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 , còn được gọi là , đượ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 Disjoint Set Union (DSU) Union Find được triển khai như sau: 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ộ. Khởi tạo: Để 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ả. Phép toán hợp: 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. Thao tác tìm: 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 đồ. Phát hiện chu kỳ: 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. Tối ưu hóa: 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 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. là một thuật toán để sắp xếp các nút của biểu đồ chu kỳ có hướng ( ) 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. Sắp xếp cấu trúc liên kết DAG Dưới đây là bảng phân tích từng bước về Sắp xếp tôpô: Bắt đầu bằng biểu đồ chu kỳ có hướng ( ) 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. Khởi tạo: DAG 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ô. Tính toán theo cấp độ: 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. Làm đầy hàng đợi ban đầu: Trong khi hàng đợi không trống, hãy thực hiện các bước sau: Vòng lặp sắp xếp cấu trúc liên kết: Dequeue một nút từ phía trước hàng đợi. Xử lý nút (ví dụ: thêm nó vào danh sách đã sắp xếp). Đố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. 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. 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ệ. Hoàn thành: 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. Phát hiện chu kỳ: 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 findIndegree(Map > graph) { Map 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 topologicalSort(Map > graph) { List result = new ArrayList<>(); Queue queue = new LinkedList<>(); Map 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ố) 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. Trie Đây là cách triển khai Trie: 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. Khởi tạo: Để 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ừ: Chèn: 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. Nếu có, hãy chuyển đến nút con. 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 đó. Để 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. Hoàn thành 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ố. Tìm kiếm tiền tố: Để 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. Xóa: 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 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à 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ể. Lập trình động 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: 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. Xác định các bài toán con: 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. Giải pháp đệ quy: Để 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ớ hoặc lập bảng: 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 . Ghi nhớ: từ trên xuố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 . 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. Lập bảng: từ dưới lên 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ời giải tối ưu: 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ách tiếp cận từ dưới lên, Từ trên xuống, Ghi nhớ, Lập bảng Các khái niệm quan trọ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 memo = new HashMap<>(); // Memoization map to store calculated results return dp(initialState, memo); } private int dp(StateType state, Map 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 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. Quay lui 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: 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. Khám phá không gian vấn đề: 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. Cấu trúc đệ quy: Ở 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ò. Điểm quyết định: 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. Xác thực giải pháp: Việc quay lui tiếp tục cho đến khi đáp ứng một trong hai điều kiện: Điều kiện chấm dứt: 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. Để 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ắt tỉa: 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: Các khoảng thường được biểu diễn dưới dạng cặp điểm và điểm (ví dụ: ). Biểu diễn khoảng: bắt đầu kết thúc [bắt đầu, kết thúc] Để 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. Sắp xếp: 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: Quá trình hợp nhất: 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ả. 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. Hoàn thành: 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 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 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ư , , và thậm chí cả . 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. techinterviews.io cấu trúc dữ liệu thuật toán phỏng vấn hành vi đàm phán lương 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 của chúng tôi với mức giảm giá $30! TECH30 Hình ảnh nổi bật của @Limarc “một nhà phát triển đang viết mã” Đồ họa được làm bằng Okso.app