Phá Kén

23 min
1 năm ago
1

Mô tả vấn đề Bạn được trình bày với một mảng số nguyên gọi là height biểu thị chiều cao của các đường thẳng đứng được đặt tại các vị trí được lập chỉ mục từ 1 đến n (được lập chỉ mục 0 […]

Tagged #ctdl&gt, #seriesLeetCode

Mô tả vấn đề

Bạn được trình bày với một mảng số nguyên gọi là height biểu thị chiều cao của các đường thẳng đứng được đặt tại các vị trí được lập chỉ mục từ 1 đến n (được lập chỉ mục 0 trong mảng). Hãy tưởng tượng rằng mỗi height[i] được liên kết với một đường trên biểu đồ kéo dài lên từ trục x đến một điểm (i, height[i]). Nhiệm vụ của bạn là tìm hai đường cùng với trục x bao quanh diện tích lớn nhất có thể, biểu thị lượng nước tối đa có thể bị giữ lại giữa chúng mà không để nước tràn ra các cạnh của đường (thùng chứa không được nghiêng) . Mục đích là tính toán và trả về diện tích nước bị bẫy tối đa này.

Trực giác

Để giải quyết vấn đề này một cách hiệu quả, chúng tôi sử dụng kỹ thuật hai con trỏ. Chúng tôi đặt một con trỏ ở đầu mảng và con trỏ kia ở cuối mảng và những con trỏ này biểu thị các ranh giới vùng chứa tiềm năng. Ở mỗi bước, lượng nước bị bẫy được xác định bằng khoảng cách giữa các con trỏ (là chiều rộng của thùng chứa) và chiều cao của đường nhỏ hơn (vì mực nước không thể cao hơn đường nhỏ hơn của hai ranh giới). Đây là khu vực có khả năng đạt mức tối đa.

Để tối đa hóa diện tích, sau khi tính toán lượng nước bị mắc kẹt ở mỗi bước và so sánh nó với mức tối đa mà chúng ta đã thấy cho đến nay, chúng ta di chuyển con trỏ ở đường ngắn hơn về phía con trỏ kia. Điều này là do việc giữ con trỏ ở đường cao hơn cố định và di chuyển con trỏ ngắn hơn có thể khiến chúng ta tìm thấy đường cao hơn và do đó có diện tích lớn hơn. Không có lợi ích gì khi di chuyển con trỏ cao hơn trước vì nó sẽ chỉ làm giảm độ rộng tiềm năng mà không đảm bảo đường cao hơn sẽ tăng chiều cao. Chúng tôi lặp lại quá trình tính toán này, cập nhật diện tích nước tối đa và di chuyển con trỏ dòng ngắn hơn về phía con trỏ khác cho đến khi Hai con trỏ gặp nhau, tại thời điểm đó chúng tôi đã xem xét mọi thùng chứa có thể và lượng nước dự trữ tối đa đã được tìm thấy.

Bằng cách tiếp cận vấn đề này với mỗi bước được tối ưu hóa để duy trì hoặc cải thiện diện tích tối đa tiềm năng, chúng tôi có thể đi đến giải pháp một cách hiệu quả, dẫn đến thuật toán chạy theo thời gian tuyến tính so với số lượng dòng.

Cách tiếp cận giải pháp

Việc thực hiện giải pháp tuân theo cách tiếp cận hai con trỏ. Dưới đây là hướng dẫn từng bước về cách hoạt động của giải pháp:

Khởi tạo Hai con trỏ: i được đặt ở đầu mảng (0), Và j được đặt ở cuối mảng (len(height) - 1).
Khởi tạo một biến ans để theo dõi diện tích tối đa được phát hiện cho đến nay. Ban đầu, ans được đặt thành 0.
Nhập một vòng lặp tiếp tục cho đến khi i ít hơn j. Vòng lặp này cho phép chúng ta khám phá tất cả các kết hợp có thể có của các dòng từ i ĐẾN j để tối đa hóa diện tích.
Bên trong vòng lặp, tính diện tích bị kẹt giữa các dòng tại con trỏ i Và j sử dụng công thức: area = (j - i) * min(height[i], height[j]). Điều này tính toán chiều rộng của container (j - i) và nhân nó với chiều cao, giá trị nhỏ hơn trong hai chiều cao tại height[i] Và height[j].
Cập nhật ans với giá trị lớn nhất hiện tại và diện tích tính toán. ans = max(ans, area) đảm bảo rằng ans giữ giá trị cao nhất của diện tích nước bị bẫy ở mỗi bước.
Xác định con trỏ nào sẽ di chuyển. Chúng ta cần di chuyển con trỏ tương ứng với dòng ngắn hơn vì đây là hệ số giới hạn chiều cao của phần nước bị mắc kẹt. Chúng tôi làm điều này bằng cách sử dụng một câu lệnh có điều kiện:
- Nếu như height[i] < height[j], sau đó chúng tôi tăng lên i (i += 1) để có khả năng tìm thấy một dòng cao hơn.
- Ngược lại thì giảm j (j -= 1) vì lý do tương tự từ đầu bên kia.
Tiếp tục lặp cho đến khi các con trỏ gặp nhau. Tại thời điểm này, ans sẽ có diện tích tối đa có thể bị mắc kẹt giữa hai dòng bất kỳ.

Giải pháp này sử dụng một cách tiếp cận này, và tính hiệu quả của nó bắt nguồn từ thực tế là ở mỗi giai đoạn, bước đi được thực hiện là bước đi tốt nhất có thể để tăng hoặc ít nhất là duy trì tiềm năng của diện tích tối đa. Bằng cách điều chỉnh tăng dần chiều rộng và chiều cao của vùng chứa đang xem xét, nó sẽ thu hẹp một cách hiệu quả để đạt được giải pháp tối ưu.

Thuật toán có độ phức tạp theo thời gian tuyến tính, O(n), vì mỗi phần tử được truy cập nhiều nhất một lần và có một lượng công việc không đổi được thực hiện trong vòng lặp.

Hướng dẫn ví dụ

Hãy minh họa cách tiếp cận giải pháp bằng một ví dụ nhỏ.

Xét mảng số nguyên height = [1, 8, 6, 2, 5, 4, 8, 3, 7].

Chúng tôi bắt đầu với hai con trỏ: i lúc bắt đầu (0), đại diện cho dòng đầu tiên, và j ở cuối (8), đại diện cho dòng cuối cùng. Như vậy, i chỉ vào height[0] đó là 1, Và j chỉ vào height[8] đó là 7.
Chúng tôi thiết lập ans = 0, vì chúng tôi chưa tính diện tích nào.
Bây giờ chúng ta bắt đầu vòng lặp của mình ở đâu i < j. Từ 0 < 8, chúng tôi bước vào vòng lặp.
Chúng tôi tính diện tích giữa các dòng tại con trỏ i Và j. Chiều rộng là j - i đó là 8 - 0 = 8, và chiều cao là giá trị nhỏ hơn trong hai độ cao tại height[i] Và height[j], Vì thế min(1, 7) = 1. Như vậy diện tích là 8 * 1 = 8.
Chúng tôi cập nhật ans là giá trị lớn nhất của giá trị hiện tại và diện tích tính toán. Vì thế, ans = max(0, 8) = 8.
Từ height[i] ít hơn height[j], chúng tôi di chuyển i con trỏ sang bên phải để có thể tìm thấy dòng cao hơn. Hiện nay i trở thành 1.
Hai con trỏ của chúng tôi hiện đang ở i = 1 Và j = 8. Chúng ta sẽ tiếp tục quá trình này cho đến khi i Và j gặp.
Lặp lại các bước 4-6:
- Vùng mới tại con trỏ i = 1 Và j = 8: area = (8 - 1) * min(8, 7) = 7 * 7 = 49.
- Cập nhật ans được max(8, 49) = 49.
- Từ height[1] lớn hơn height[8], chúng tôi di chuyển j bên trái (bây giờ j là 7).
Tiếp tục lặp lại:
- Vùng mới tại con trỏ i = 1 Và j = 7: area = (7 - 1) * min(8, 3) = 6 * 3 = 18.
- ans còn lại 49 Từ 49 > 18.
- height[1] lớn hơn height[7], vì vậy chúng tôi di chuyển j bên trái (bây giờ j là 6).
Quá trình tiếp tục theo cách này, luôn di chuyển con trỏ ở độ cao ngắn hơn cho đến khi i Và j đều bình đẳng.

Vào cuối những lần lặp lại này, ans giữ diện tích tối đa có thể bị mắc kẹt, trong ví dụ này là 49. Đây là lượng nước lớn nhất có thể bị giữ lại giữa hai dòng mà không bị đổ.

C++

#include <vector> 2#include <algorithm> // Include algorithm for std::min and std::max 3 4class Solution { 5public: 6 int maxArea(vector<int>& heights) { 7 int left = 0; // Starting from the leftmost index 8 int right = heights.size() - 1; // Starting from the rightmost index 9 int maxArea = 0; // Initialize the maximum area to 0 10 11 // Continue looping until the left and right pointers meet 12 while (left < right) { 13 // Calculate the current area with the minimum of the two heights 14 int currentArea = std::min(heights[left], heights[right]) * (right - left); 15 // Update the maximum area if the current area is larger 16 maxArea = std::max(maxArea, currentArea); 17 18 // Move the pointers inward. If left height is less than right height 19 // then we move the left pointer to right hoping to find a greater height 20 if (heights[left] < heights[right]) { 21 ++left; 22 } else { // Otherwise, move the right pointer to the left 23 --right; 24 } 25 } 26 27 return maxArea; // Return the maximum area found 28 } 29};

Độ phức tạp về thời gian và không gian

Mã Python đã cho triển khai kỹ thuật hai con trỏ để tìm diện tích nước tối đa có thể chứa giữa hai dòng, với một mảng chiều cao của dòng.

Độ phức tạp thời gian

Hàm khởi tạo hai con trỏ ở đầu và cuối mảng tương ứng và lặp vào bên trong cho đến khi chúng gặp nhau, thực hiện một số thao tác không đổi cho mỗi cặp chỉ mục. Vì các con trỏ bao phủ mỗi phần tử nhiều nhất một lần, phép lặp tuyến tính tương ứng với số phần tử n trong height Mảng.

Do đó, độ phức tạp về thời gian là O(n).

Độ phức tạp của không gian

Mã sử dụng một số biến số nguyên cố định (i, j, ans, Và t) và không phân bổ bất kỳ bộ nhớ bổ sung nào có tỷ lệ theo kích thước của mảng đầu vào.

Do đó, độ phức tạp của không gian là O(1).

Tổng Kết

Mô tả bài toán: Cho một mảng height[] đại diện cho chiều cao của các cột dọc theo trục hoành, bài toán yêu cầu tìm diện tích của vùng chứa nước lớn nhất mà hai cột có thể tạo ra. Diện tích được tính bằng công thức:

Trong đó, width là khoảng cách giữa hai chỉ số i và j, còn min(height[i], height[j]) là chiều cao của vùng chứa nước (vì nước không thể vượt qua chiều cao thấp hơn giữa hai cột).

Ví dụ:

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Giải thích: Vùng chứa nước lớn nhất được tạo ra giữa chỉ số 1 và chỉ số 8, diện tích là (8 - 1) * min(8, 7) = 7 * 7 = 49.
Input: height = [1,1] Output: 1 Giải thích: Vùng chứa nước chỉ có thể là diện tích giữa hai cột, diện tích là 1 * 1 = 1.

Phân tích giải pháp:

Giải pháp sử dụng kỹ thuật hai con trỏ (two-pointer technique) để tối ưu hóa việc tìm diện tích lớn nhất.

Các bước thực hiện:

Khởi tạo hai con trỏ:
- Một con trỏ ở đầu mảng (left = 0).
- Một con trỏ ở cuối mảng (right = height.length - 1).
Tính diện tích:
- Tính diện tích của vùng chứa nước giữa hai con trỏ: Area=(right−left)×min⁡(height[left],height[right])\text{Area} = (\text{right} – \text{left}) \times \min(\text{height[left]}, \text{height[right]})
- Cập nhật diện tích lớn nhất nếu cần.
Di chuyển con trỏ:
- Nếu height[left] nhỏ hơn height[right], ta di chuyển con trỏ left sang phải để tăng chiều cao (giảm khả năng bị giới hạn bởi cột thấp bên trái).
- Nếu height[left] lớn hơn hoặc bằng height[right], ta di chuyển con trỏ right sang trái để tìm một cột có chiều cao cao hơn.
Dừng lại khi con trỏ gặp nhau.

Mã giải thuật trong JavaScript:

var maxArea = function(height) { let left = 0; // Con trỏ trái let right = height.length - 1; // Con trỏ phải let maxArea = 0; // Diện tích lớn nhất while (left < right) { // Tính diện tích const currentArea = (right - left) * Math.min(height[left], height[right]); // Cập nhật diện tích lớn nhất maxArea = Math.max(maxArea, currentArea); // Di chuyển con trỏ if (height[left] < height[right]) { left++; // Di chuyển con trỏ trái sang phải để tăng chiều cao } else { right--; // Di chuyển con trỏ phải sang trái để tăng chiều cao } } return maxArea; }; // Test ví dụ const height1 = [1, 8, 6, 2, 5, 4, 8, 3, 7]; console.log(maxArea(height1)); // Output: 49 const height2 = [1, 1]; console.log(maxArea(height2)); // Output: 1

Giải thích chi tiết:

Khởi tạo con trỏ:
- left = 0: Bắt đầu từ chỉ số đầu tiên của mảng.
- right = height.length - 1: Bắt đầu từ chỉ số cuối cùng của mảng.
Tính diện tích hiện tại: const currentArea = (right - left) * Math.min(height[left], height[right]);
- Diện tích giữa các cột được tính bằng công thức: chiều rộng là khoảng cách giữa hai chỉ số left và right, chiều cao là giá trị nhỏ hơn giữa height[left] và height[right].
Cập nhật diện tích lớn nhất: maxArea = Math.max(maxArea, currentArea);
- Cập nhật diện tích lớn nhất mỗi khi tìm được diện tích lớn hơn.
Di chuyển con trỏ:
- Nếu chiều cao của cột tại left nhỏ hơn chiều cao tại right, di chuyển con trỏ trái sang phải (mục tiêu là tăng chiều cao).
- Nếu chiều cao tại right nhỏ hơn hoặc bằng chiều cao tại left, di chuyển con trỏ phải sang trái.
Điều kiện dừng:
- Khi left gặp right, thuật toán dừng lại, vì lúc này không còn cặp cột nào để tính diện tích.

Độ phức tạp:

Thời gian: O(n), vì thuật toán chỉ duyệt qua mảng một lần với hai con trỏ di chuyển từ hai đầu về giữa.
Không gian: O(1), vì chỉ sử dụng một vài biến phụ để lưu trữ các con trỏ và diện tích lớn nhất.

Các tình huống đặc biệt:

Nếu mảng chỉ có một phần tử hoặc hai phần tử, không thể tạo ra một vùng chứa nước, trả về diện tích là 0.

LeetCode Bài 15. 3Sum (3 số tổng bằng 0 trong mảng)

19 min
1 năm ago

Mô tả vấn đề Bài toán này yêu cầu chúng ta tìm tất cả các bộ ba duy nhất trong một mảng có thể kết hợp để cho tổng bằng 0. Bộ ba trong ngữ cảnh này được định nghĩa là một […]

Tagged #ctdl&gt, #seriesLeetCode

Mô tả vấn đề

Bài toán này yêu cầu chúng ta tìm tất cả các bộ ba duy nhất trong một mảng có thể kết hợp để cho tổng bằng 0. Bộ ba trong ngữ cảnh này được định nghĩa là một bộ ba số [nums[i], nums[j], nums[k]] trong đó mỗi số đến từ một vị trí khác nhau trong mảng, được biểu thị bằng i, j, Và k. Điều quan trọng là chúng ta cần đảm bảo rằng:

Các chỉ số i, j, Và k tất cả đều khác nhau.
Tổng các số tại các chỉ số đó bằng 0 (nums[i] + nums[j] + nums[k] == 0).
Không có bộ ba nào được lặp lại trong kết quả.

Mục tiêu của chúng tôi là xác định tất cả các kết hợp như vậy, đảm bảo rằng mỗi kết hợp của ba số là duy nhất trong tập kết quả. Vấn đề này là một ví dụ kinh điển về một thách thức liên quan đến thao tác mảng và xác định các mẫu cụ thể trong một tập hợp số..

Trực giác

Để đi đến giải pháp cho vấn đề này, chúng ta sẽ thực hiện theo cách tiếp cận hai bước. Đầu tiên chúng ta sắp xếp mảng theo thứ tự không giảm. các sắp xếp giúp chúng ta theo hai cách: nó giúp chúng ta dễ dàng tránh thêm các bộ ba trùng lặp và cho phép chúng ta sử dụng kỹ thuật hai con trỏ một cách hiệu quả.

Sau đó sắp xếp, mảng được xử lý bằng một vòng lặp để thử từng số một cách hiệu quả như một ứng cử viên tiềm năng cho số đầu tiên của bộ ba. Ứng viên này được gọi là nums[i]. Bắt đầu từ i = 0, chúng tôi sẽ kiểm tra xem nums[i], khi được thêm vào bất kỳ hai số nào khác trong mảng ở bên phải của nó, tổng bằng 0.

Để đẩy nhanh quá trình và tránh việc kiểm tra các kết hợp được đảm bảo là không thành công hoặc dư thừa, chúng tôi sử dụng những thông tin chi tiết sau:

Nếu số hiện tại nums[i] lớn hơn 0, vì mảng đã được sắp xếp nên mọi kết hợp liên quan đến số này và các số tiếp theo sẽ lớn hơn 0. Vì không có tổng nào có tổng dương có thể bằng 0 nên chúng ta có thể thoát khỏi vòng lặp sớm.
Nếu như nums[i] giống với số trước đó nums[i-1], chúng tôi bỏ qua giá trị hiện tại để ngăn việc xử lý cùng một kịch bản bộ ba, điều này sẽ dẫn đến trùng lặp.

Một khi hợp lệ nums[i] được chọn, chúng tôi sử dụng vòng lặp while bằng cách sử dụng Hai con trỏ, j Và k, bắt đầu sau i (vì j) và ở cuối mảng (đối với k). Chúng tôi tính tổng của nums[i], nums[j], Và nums[k]. Nếu tổng là:

Nhỏ hơn 0, chúng tôi di chuyển j ở bên phải để tăng tổng (nums[j] sẽ lớn hơn).
Lớn hơn 0, chúng ta dịch chuyển k sang trái để giảm tổng (vì nums[k] sẽ nhỏ hơn).
Chính xác là không, chúng tôi đã tìm thấy một bộ ba hợp lệ và thêm nó vào bộ giải pháp của chúng tôi. Sau đó chúng tôi di chuyển cả hai j Và k con trỏ, bỏ qua bất kỳ bản sao nào để tìm kiếm các bộ ba bổ sung bắt đầu bằng nums[i].

Chúng tôi lặp lại quá trình này cho mọi chỉ mục i cho đến phần tử cuối cùng thứ hai và thu thập tất cả các bộ ba duy nhất mang lại cho chúng ta tổng bằng 0.

Cách tiếp cận giải pháp

Mã thực hiện chiến lược sắp xếp và hai con trỏ để tìm tất cả các bộ ba duy nhất có tổng bằng 0 trong nums mảng. Dưới đây là các bước chi tiết được thực hiện trong quá trình triển khai, tuân theo Phương pháp tiếp cận giải pháp tham khảo:

Sắp xếp mảng: Đầu tiên, chúng ta sắp xếp mảng bằng cách sử dụng nums.sort(). sắp xếp có lợi vì nó sắp xếp các phần tử, cho phép chúng ta sử dụng phương pháp hai con trỏ một cách hiệu quả và giúp tránh trùng lặp dễ dàng hơn vì các giá trị trùng lặp sẽ nằm liền kề trong một mảng được sắp xếp.
Lặp lại các phần tử đầu tiên có thể có của bộ ba: Chúng ta xét từng số trong nums mảng (cho đến phần tử thứ ba đến phần tử cuối cùng) là phần tử đầu tiên tiềm năng của bộ ba của chúng tôi. Điều này đạt được bằng vòng lặp for: for i in range(n - 2).
Nghỉ sớm và tiếp tục: Bên trong vòng lặp này, chúng ta có một số điều kiện giúp chúng ta loại bỏ những bước kiểm tra không cần thiết:
- Nếu số hiện tại nums[i] lớn hơn 0 thì chúng ta có thể thoát khỏi vòng lặp. Điều này là do bất kỳ bộ ba nào có số bắt đầu dương sẽ có tổng lớn hơn 0.
- Nếu số hiện tại giống với số trước đó (và i không phải là 0), chúng tôi sử dụng continue chuyển sang lần lặp tiếp theo để tránh kiểm tra trùng lặp.
Kỹ thuật hai con trỏ: Đối với mỗi i, chúng tôi sử dụng Hai con trỏ, j Và k, khởi tạo để i + 1 Và n - 1 (cuối mảng) tương ứng. Sau đó chúng ta bước vào một vòng lặp while, vòng lặp này sẽ tiếp tục cho đến khi j ít hơn k.
Tìm bộ ba: Trong vòng lặp while, chúng ta tính tổng x của nums[i], nums[j], Và nums[k] và so sánh nó với số không:
- Nếu như x nhỏ hơn 0, chúng ta tăng j vì chúng ta cần một số lớn hơn để tăng tổng.
- Nếu như x lớn hơn 0 thì chúng ta giảm k vì chúng ta cần một số nhỏ hơn để giảm tổng.
- Nếu như x bằng 0, chúng tôi đã tìm thấy một bộ ba hợp lệ và chúng tôi thêm [nums[i], nums[j], nums[k]] ĐẾN ans. Sau khi lưu trữ bộ ba, chúng tôi di chuyển cả hai j Và k vượt qua bất kỳ bản sao nào để đảm bảo chúng tôi không tìm thấy bản sao trong các lần lặp tiếp theo.
Trả kết quả: Khi tất cả các số đã được xem xét cho phần tử đầu tiên của bộ ba và tất cả đều hợp lệ j, k cặp đã được đánh giá, chúng tôi quay trở lại ans. Danh sách này chứa tất cả các bộ ba duy nhất có tổng bằng 0.

Giải pháp này có độ phức tạp về thời gian là O(n^2) và độ phức tạp về không gian là O(log n) do thao tác sắp xếp, giả sử rằng sort() phương thức được sử dụng chiếm không gian O(log n) cho ngăn xếp bên trong trong một sắp xếp thuật toán như quicksort hoặc mergesort. Tuy nhiên, nếu việc sắp xếp không chiếm thêm không gian thì độ phức tạp về không gian sẽ chỉ là O(1), đó là không gian được lấy bởi mảng đầu ra và các con trỏ được sử dụng.

Hướng dẫn ví dụ

Hãy cùng tìm hiểu cách tiếp cận giải pháp bằng một ví dụ nhỏ. Hãy xem xét mảng nums = [-1, 0, 1, 2, -1, -4].

Thực hiện theo các bước trong cách tiếp cận giải pháp:

Sắp xếp mảng: Chúng tôi bắt đầu bằng việc sắp xếp nums, dẫn đến [-4, -1, -1, 0, 1, 2].
Lặp lại các phần tử đầu tiên có thể có của bộ ba: Chúng tôi bắt đầu xem xét mảng để tìm các phần tử đầu tiên tiềm năng của bộ ba. Vòng lặp chạy từ đầu mảng đến n - 3, Ở đâu n là độ dài của mảng nums được sắp xếp.
Nghỉ sớm và tiếp tục: Khi lặp lại, nếu chúng ta tìm thấy một số lớn hơn 0 (nums[i] > 0), chúng ta có thể thoát ra khỏi vòng lặp. Trong ví dụ của chúng tôi, tất cả các số từ chỉ số 0 đến n - 3 sẽ được xem xét vì điều kiện ngắt không trở thành đúng.

Chúng ta cũng bỏ qua phần tử thứ hai, đó là -1, giống như lần đầu tiên, sử dụng continue để tránh trùng lặp.

Kỹ thuật hai con trỏ: Chúng tôi bắt đầu quá trình hai con trỏ với i, j, Và k như sau:
- i = 0: Chúng tôi chọn -4 là phần tử đầu tiên.
- j = i + 1: j bắt đầu lúc -1 (phần tử ngay sau -4).
- k = n - 1: k bắt đầu lúc 2 (phần tử cuối cùng).
Tìm bộ ba: Trong vòng lặp while, chúng ta tìm thấy tổng của nums[i] + nums[j] + nums[k] và điều chỉnh j Và k tương ứng:
- Tổng đầu tiên là -4 + -1 + 2 = -3, đó là ít hơn không. Chúng tôi tăng j để chuyển sang số lớn hơn tiếp theo, đó là một số khác -1.
- Bây giờ, tổng số tiền là -4 + -1 + 2 = -3, vẫn nhỏ hơn không. Chúng tôi tăng j một lần nữa và chuyển đến 0.
- với j TRÊN 0, tổng số tiền là -4 + 0 + 2 = -2, và chúng tôi tiếp tục tăng j di chuyển đến 1.
- Tổng số bây giờ là -4 + 1 + 2 = -1, vẫn nhỏ hơn 0, nên chúng ta di chuyển j một lần nữa, nhưng bây giờ chúng ta đã đi đến cuối và vòng lặp while kết thúc cho việc này i.

Tiếp theo, với i = 1, chúng tôi tìm thấy:

i = 1 (nhưng điều này bị bỏ qua vì nó giống như i = 0).
i = 2, chúng ta có phần tử đầu tiên là -1, j = 3 Và k = 5, vì vậy chúng tôi kiểm tra sự kết hợp -1 + 0 + 2, tổng cộng là 1. Tổng lớn hơn 0 nên giảm k.
Hiện nay, k là 4, Và j là 3, vì vậy chúng tôi kiểm tra -1 + 0 + 1, tổng cộng là 0. Chúng tôi đã tìm thấy một bộ ba hợp lệ [-1, 0, 1].

Mỗi lần chúng tôi tìm thấy một bộ ba, chúng tôi di chuyển cả hai j Và k trong khi chúng trỏ đến cùng một số để tránh trùng lặp. Trong trường hợp này, không có sự trùng lặp nào và chúng tôi đã hoàn thành việc lặp lại này.

Trả kết quả: Sau khi đánh giá tất cả các điểm bắt đầu tiềm năng, giải pháp trả về danh sách các bộ ba duy nhất được tìm thấy. Trong trường hợp này, [[-1, 0, 1]] là bộ ba duy nhất có tổng bằng 0.

Việc thực hiện sẽ trở lại [[−1, 0, 1]] như đầu ra.

Theo quy trình đã phác thảo, chúng ta có thể tìm thấy tất cả các bộ ba duy nhất có thể có trong mảng có thể kết hợp để tạo ra tổng bằng 0.

C++

#include <vector> 2#include <algorithm> 3 4class Solution { 5public: 6 std::vector<std::vector<int>> threeSum(std::vector<int>& nums) { 7 // First, we sort the numbers. 8 std::sort(nums.begin(), nums.end()); 9 10 // This will hold the unique triplets. 11 std::vector<std::vector<int>> result; 12 13 // Calculate the number of elements. 14 int numElements = nums.size(); 15 16 // Start the first pointer `i` from the beginning of the array 17 // and iterate over the numbers as long as there are at least 18 // two more elements after it and the current element is not positive. 19 for (int i = 0; i < numElements - 2 && nums[i] <= 0; ++i) { 20 // If this is not the first element and it's the same as the one before, 21 // we skip it to avoid duplicate solutions. 22 if (i > 0 && nums[i] == nums[i - 1]) { 23 continue; 24 } 25 26 // Pointers `j` and `k` initialize to elements after `i` and the last element respectively. 27 int j = i + 1, k = numElements - 1; 28 29 // While `j` is before `k` we look for valid triplets. 30 while (j < k) { 31 int sum = nums[i] + nums[j] + nums[k]; 32 33 // If current sum is less than zero, increment `j` to get closer to zero. 34 if (sum < 0) { 35 ++j; 36 } 37 // If current sum is greater than zero, decrement `k` to get closer to zero. 38 else if (sum > 0) { 39 --k; 40 } 41 // If the sum is zero, we found a triplet. 42 else { 43 // Add the current triplet to the result. 44 result.push_back({nums[i], nums[j], nums[k]}); 45 46 // Increment `j` and decrement `k` to find the next unique triplet. 47 ++j; 48 --k; 49 50 // Skip duplicate values from `j` and `k` for the unique triplet. 51 while (j < k && nums[j] == nums[j - 1]) { 52 ++j; 53 } 54 while (j < k && nums[k] == nums[k + 1]) { 55 --k; 56 } 57 } 58 } 59 } 60 61 // Return the set of triplets found. 62 return result; 63 } 64};

Độ phức tạp về thời gian và không gian

Độ phức tạp thời gian

Độ phức tạp về thời gian của mã đã cho là O(n^2). Điều này là do có một vòng lặp lồng nhau trong đó vòng lặp bên ngoài chạy cho n lần (giảm đi 2 để tránh các lần lặp cuối cùng không cần thiết do bộ ba) và trong vòng lặp này, có hai con trỏ đang di chuyển độc lập về phía nhau, tổng cộng sẽ dẫn đến n lặp lại trong trường hợp xấu nhất. Không có vòng lặp lồng nhau bên trong vòng lặp while, do đó các phép toán bên trong có thời gian không đổi bất chấp các điều kiện while cũng vậy. O(n). Nhân chúng với nhau sẽ cho chúng ta n * n = n^2, Kể từ đây O(n^2).

Độ phức tạp của không gian

Độ phức tạp về không gian của mã là O(log n) nếu chúng ta không xem xét đến không gian đầu ra, điều đó sẽ O(n). Độ phức tạp về không gian phát sinh do không gian được sử dụng bởi thuật toán sắp xếp, thường là O(log n) cho các thuật toán thường được sử dụng như QuickSort hoặc MergeSort trong nhiều thư viện lập trình tiêu chuẩn.

Tổng Kết

Mô tả bài toán: Bài toán yêu cầu tìm tất cả các bộ ba phần tử trong mảng sao cho tổng của chúng bằng 0. Cần lưu ý rằng các bộ ba kết quả phải không trùng nhau.

Ví dụ:

Input: nums = [-1, 0, 1, 2, -1, -4] Output: [[-1, -1, 2], [-1, 0, 1]] Giải thích: Các bộ ba có tổng bằng 0 là [-1, -1, 2] và [-1, 0, 1].
Input: nums = [0, 1, 1] Output: [] Giải thích: Không có bộ ba nào có tổng bằng 0.

Phân tích giải pháp:

Để giải bài toán này, ta sẽ sử dụng phương pháp hai con trỏ (two-pointer technique) kết hợp với việc sắp xếp mảng trước.

Các bước thực hiện:

Sắp xếp mảng: Đầu tiên, ta sẽ sắp xếp mảng để có thể sử dụng kỹ thuật hai con trỏ.
Duyệt mảng: Ta sẽ duyệt từng phần tử nums[i] (cố định phần tử đầu tiên của bộ ba).
Tìm các bộ ba: Dùng hai con trỏ left và right để tìm cặp phần tử còn lại sao cho tổng của ba phần tử là 0.
- Nếu tổng của ba phần tử là 0, ta thêm bộ ba này vào kết quả.
- Nếu tổng nhỏ hơn 0, ta tăng con trỏ trái (left++) để làm tổng lớn hơn.
- Nếu tổng lớn hơn 0, ta giảm con trỏ phải (right--) để làm tổng nhỏ hơn.
Tránh trùng lặp: Sau khi tìm được bộ ba, cần đảm bảo không có bộ ba trùng nhau bằng cách bỏ qua các phần tử giống nhau.

Mã giải thuật trong JavaScript:

var threeSum = function(nums) { nums.sort((a, b) => a - b); // Sắp xếp mảng const result = []; for (let i = 0; i < nums.length; i++) { // Tránh trùng lặp phần tử đầu tiên if (i > 0 && nums[i] === nums[i - 1]) { continue; } let left = i + 1; let right = nums.length - 1; while (left < right) { const sum = nums[i] + nums[left] + nums[right]; if (sum === 0) { result.push([nums[i], nums[left], nums[right]]); // Tránh trùng lặp phần tử thứ hai while (left < right && nums[left] === nums[left + 1]) { left++; } // Tránh trùng lặp phần tử thứ ba while (left < right && nums[right] === nums[right - 1]) { right--; } // Di chuyển con trỏ left++; right--; } else if (sum < 0) { left++; // Tổng quá nhỏ, tăng left để tăng tổng } else { right--; // Tổng quá lớn, giảm right để giảm tổng } } } return result; }; // Test ví dụ const nums1 = [-1, 0, 1, 2, -1, -4]; console.log(threeSum(nums1)); // Output: [[-1, -1, 2], [-1, 0, 1]] const nums2 = [0, 1, 1]; console.log(threeSum(nums2)); // Output: []

Giải thích chi tiết:

Sắp xếp mảng: nums.sort((a, b) => a - b);
- Sắp xếp mảng nums để dễ dàng áp dụng thuật toán hai con trỏ và tránh trùng lặp.
Duyệt mảng: for (let i = 0; i < nums.length; i++) {
- Duyệt qua từng phần tử của mảng. Mỗi lần duyệt, chúng ta sẽ cố định một phần tử nums[i] làm phần tử đầu tiên của bộ ba.
Tránh trùng lặp: if (i > 0 && nums[i] === nums[i - 1]) { continue; }
- Kiểm tra nếu phần tử hiện tại nums[i] giống phần tử trước đó, ta bỏ qua để tránh tạo bộ ba trùng lặp.
Dùng hai con trỏ: let left = i + 1; let right = nums.length - 1;
- Khởi tạo hai con trỏ left và right để tìm phần tử thứ hai và thứ ba sao cho tổng của ba phần tử bằng 0.
Điều chỉnh con trỏ: while (left < right) { const sum = nums[i] + nums[left] + nums[right];
- Tính tổng của ba phần tử.
- Nếu tổng bằng 0, ta thêm bộ ba này vào kết quả và điều chỉnh con trỏ để tránh trùng lặp.
- Nếu tổng nhỏ hơn 0, ta tăng con trỏ left để tăng tổng.
- Nếu tổng lớn hơn 0, ta giảm con trỏ right để giảm tổng.
Tránh trùng lặp: while (left < right && nums[left] === nums[left + 1]) { left++; } while (left < right && nums[right] === nums[right - 1]) { right--; }
- Sau khi tìm được bộ ba có tổng bằng 0, ta cần di chuyển con trỏ để tránh các phần tử trùng lặp và tìm các bộ ba khác.

Độ phức tạp:

Thời gian: O(n²), vì ngoài việc sắp xếp mảng (O(n log n)), chúng ta phải duyệt qua tất cả các bộ ba khả thi với mỗi phần tử (O(n) cho mỗi phần tử).
Không gian: O(1) nếu không tính không gian cho kết quả, bởi chúng ta chỉ sử dụng một vài biến phụ cho con trỏ và các phép tính.

Các tình huống đặc biệt:

Nếu mảng có ít hơn 3 phần tử, không thể tìm bộ ba, trả về [].
Các bộ ba trả về cần phải đảm bảo không có trùng lặp.

LeetCode Bài 153. Tìm giá trị tối thiểu trong mảng được sắp xếp xoay (Find Minimum in Rotated Sorted Array)

8 min
1 năm ago

Mô tả vấn đề Bài toán trình bày một mảng chứa một dãy số theo thứ tự tăng dần đã được quay từ 1 đến n lần. Xoay có nghĩa là các phần tử được dịch chuyển sang phải một vị trí […]

Tagged #ctdl&gt, #seriesLeetCode

Mô tả vấn đề

Bài toán trình bày một mảng chứa một dãy số theo thứ tự tăng dần đã được quay từ 1 đến n lần. Xoay có nghĩa là các phần tử được dịch chuyển sang phải một vị trí và phần tử cuối cùng được chuyển sang vị trí đầu tiên. Nhiệm vụ là tìm phần tử nhỏ nhất trong mảng được xoay này. Thách thức là đạt được điều này bằng thuật toán chạy trong thời gian O(log n), điều này gợi ý rằng Tìm kiếm nhị phân nên sử dụng phương pháp này vì tìm kiếm nhị phân có độ phức tạp về thời gian logarit và thường được áp dụng cho các mảng được sắp xếp để nhanh chóng tìm thấy một phần tử cụ thể.

Tổng Quan

Chìa khóa để giải quyết vấn đề này nằm ở việc hiểu phép quay ảnh hưởng như thế nào đến mảng đã được sắp xếp. Mặc dù xoay, một phần của mảng vẫn được sắp xếp. Nếu mảng không được xoay hoặc đã được xoay toàn bộ chu kỳ (n lần) thì phần tử nhỏ nhất sẽ ở đầu. Nếu nó được xoay, mảng gồm hai dãy tăng dần và phần tử nhỏ nhất là phần tử đầu tiên của dãy thứ hai.

Vì vậy, chúng ta có thể sử dụng Tìm kiếm nhị phân để nhanh chóng xác định điểm xảy ra quá trình chuyển đổi từ giá trị cao hơn sang giá trị thấp hơn, điểm này cho biết phần tử nhỏ nhất. Tìm kiếm nhị phân được sửa đổi ở đây để so sánh phần tử ở giữa với phần tử đầu tiên và quyết định vị trí di chuyển tiếp theo:

Nếu phần tử ở giữa lớn hơn phần tử đầu tiên thì giá trị nhỏ nhất phải ở bên phải phần tử ở giữa. Do đó, chúng tôi tìm kiếm nửa bên phải của mảng.
Nếu phần tử ở giữa nhỏ hơn phần tử đầu tiên thì giá trị nhỏ nhất sẽ nằm ở đâu đó ở bên trái của phần tử ở giữa hoặc có thể chính là phần tử ở giữa. Ở đây, chúng tôi tìm kiếm nửa bên trái.

Bằng cách áp dụng logic này một cách đệ quy cho các nửa, điểm tồn tại của phần tử nhỏ nhất có thể được tìm thấy một cách hiệu quả, đáp ứng độ phức tạp về thời gian cần thiết..

Cách tiếp cận giải pháp

Việc thực hiện giải pháp thúc đẩy một Tìm kiếm nhị phân thuật toán tìm phần tử nhỏ nhất trong mảng đã quay. Dưới đây là các bước chi tiết của thuật toán:

Đầu tiên, giải pháp kiểm tra xem phần tử đầu tiên của mảng có nhỏ hơn hoặc bằng phần tử cuối cùng hay không. Nếu đúng, điều này cho biết mảng không được xoay hoặc được xoay toàn bộ chu kỳ. Do đó, phần tử đầu tiên đã là giá trị tối thiểu và chúng ta có thể trả về nó ngay lập tức.if nums[0] <= nums[-1]: return nums[0]
Nếu lần kiểm tra trước không thành công, giải pháp sẽ đặt hai con trỏ, left Và right, ở đầu và cuối mảng tương ứng. Những con trỏ này được sử dụng để thu hẹp vùng tìm kiếm một cách linh hoạt trong khi thực hiện Tìm kiếm nhị phân.left, right = 0, len(nums) - 1
Thuật toán đi vào một vòng lặp tiếp tục cho đến khi left con trỏ nhỏ hơn right con trỏ. Mục đích của vòng lặp này là liên tục thu hẹp không gian tìm kiếm cho đến khi xác định được phần tử tối thiểu..while left < right:
Bên trong vòng lặp, giải pháp tính toán mid điểm giữa con trỏ trái và phải. Điểm giữa này được sử dụng để so sánh các phần tử và quyết định nửa nào của mảng sẽ tìm kiếm tiếp theo.mid = (left + right) >> 1
Bước tiếp theo là so sánh phần tử tại mid chỉ mục với phần tử đầu tiên trong mảng. Nếu như nums[mid] lớn hơn nums[0], chúng ta biết rằng phần tử nhỏ nhất phải ở bên phải mid, vì vậy chúng tôi di chuyển left con trỏ tới mid + 1.if nums[0] <= nums[mid]: left = mid + 1
Ngược lại, nếu nums[mid] ít hơn nums[0], phần tử tối thiểu nằm ở bên trái của mid, hoặc nó có thể là mid chính nó, vì vậy chúng tôi di chuyển right con trỏ tới mid.else: right = mid
Vòng lặp tiếp tục cho đến khi left Và right con trỏ hội tụ về chỉ số của phần tử tối thiểu. Lúc này, chúng ta có thể quay lại nums[left] là phần tử tối thiểu của mảng.return nums[left]

Cách tiếp cận này đảm bảo rằng thời gian chạy sẽ là O(log n) vì nó liên tục loại bỏ một nửa không gian tìm kiếm trong mỗi lần lặp, đây là đặc điểm của phương pháp Tìm kiếm nhị phân.

Hướng dẫn ví dụ

Hãy xem xét một ví dụ nhỏ để minh họa cách tiếp cận giải pháp. Giả sử chúng ta có mảng xoay sau:

nums = [4, 5, 6, 7, 0, 1, 2]

Ban đầu, chúng tôi kiểm tra xem mảng chưa được xoay hay đã được xoay toàn bộ chu kỳ:

if nums[0] <= nums[-1]: return nums[0]

Tuy nhiên, nums[0] là 4 Và nums[-1] là 2, vì vậy chúng tôi không trở lại nums[0] vì mảng đã được xoay.

Tiếp theo, chúng tôi thiết lập left Và right con trỏ:

left, right = 0, len(nums) - 1

Kể từ đây, left = 0 Và right = 6.

Bước vào vòng lặp, chúng ta tính toán mid chỉ số:

mid = (left + right) >> 1

Điều này giúp chúng tôi mid = 3, với nums[mid] = 7.

Bây giờ chúng ta so sánh nums[mid] với nums[0]. Từ 7 (phần tử ở giữa) lớn hơn 4 (phần tử đầu tiên), chúng tôi cập nhật left ĐẾN mid + 1:

left = mid + 1

Hiện nay, left = 4 Và right = 6.

Ở lần lặp tiếp theo, mid = (4 + 6) >> 1 = 5. giá trị nums[mid] là 1, đó là ít hơn nums[0].

Từ nums[mid] ít hơn nums[0], chúng tôi cập nhật right con trỏ tới mid:

right = mid

Hiện nay, left = 4 Và right = 5.

Tiếp tục vòng lặp, chúng ta tính toán tiếp theo mid:

mid = (left + right) >> 1 = (4 + 5) >> 1 = 4

Giá trị tại mid chỉ số là 0, đó là ít hơn nums[0]. Vì vậy, chúng tôi cập nhật right con trỏ tới mid lại:

right = mid

Kể từ bây giờ cả hai left Và right là 4, vòng lặp kết thúc và chúng tôi trả về giá trị nums[left] đó là 0, phần tử nhỏ nhất trong mảng được xoay:

return nums[left]

Do đó, theo cách tiếp cận được cung cấp, chúng tôi tìm thấy phần tử tối thiểu một cách hiệu quả trong một mảng được sắp xếp xoay trong thời gian O(log n).

C++

#include <vector> // Include the vector header for using the vector data structure 2 3class Solution { 4public: 5 // Function to find the minimum element in a rotated sorted array 6 int findMin(std::vector<int>& nums) { 7 int size = nums.size(); // Get the size of the vector 8 9 // If the first element is less than or equal to the last element, 10 // then the array is not rotated, so return the first element 11 if (nums[0] <= nums[size - 1]) { 12 return nums[0]; 13 } 14 15 int left = 0; // Initialize left pointer to the start of the array 16 int right = size - 1; // Initialize right pointer to the end of the array 17 18 // Binary search to find the pivot, the smallest element 19 while (left < right) { 20 int mid = left + (right - left) / 2; // Find the mid index to prevent overflow 21 22 // If the first element is less than or equal to the mid element, 23 // then the smallest value must be to the right of mid 24 if (nums[0] <= nums[mid]) { 25 left = mid + 1; 26 } else { // Otherwise, it is to the left of mid 27 right = mid; 28 } 29 } 30 31 // At this point, left is the index of the smallest element 32 return nums[left]; 33 } 34};

Độ phức tạp về thời gian và không gian

Mã Python được cung cấp triển khai thuật toán tìm kiếm nhị phân để tìm phần tử tối thiểu trong một mảng được sắp xếp xoay. Đây là phân tích về độ phức tạp về thời gian và không gian của nó:

Độ phức tạp thời gian:

Độ phức tạp về thời gian của thuật toán là O(log n), Ở đâu n là độ dài của danh sách đầu vào nums. Điều này là do thuật toán sử dụng phương pháp tìm kiếm nhị phân, trong đó nó liên tục chia khoảng thời gian tìm kiếm thành một nửa. Ở mỗi bước, thuật toán so sánh phần tử ở giữa với các phần tử biên để xác định nửa mảng cần tìm kiếm tiếp theo. Do đó, số bước cần thiết để tìm mức tối thiểu sẽ tỷ lệ thuận với logarit của kích thước mảng.

Độ phức tạp của không gian:

Độ phức tạp không gian của thuật toán là O(1), vì nó chỉ sử dụng một lượng không gian bổ sung không đổi. Các biến left, right, Và mid được sử dụng để duy trì giới hạn của không gian tìm kiếm và không có cấu trúc dữ liệu bổ sung nào được phân bổ phụ thuộc vào kích thước của danh sách đầu vào. Do đó, yêu cầu bộ nhớ không đổi bất kể kích thước đầu vào.

LeetCode Bài 238. Product of Array Except Self giải bằng Javascript

14 min
1 năm ago
1

Tagged #ctdl&gt, #seriesLeetCode

Bài toán này thách thức chúng ta tìm tích của tất cả các phần tử trong một mảng ngoại trừ phần tử hiện tại, mà không sử dụng phép chia. Mặc dù phương pháp brute-force để tính tích của tất cả các phần tử rồi chia cho từng phần tử là đơn giản, nhưng nó không tối ưu về mặt độ phức tạp về thời gian hoặc không gian.

Trong bài viết này, chúng ta sẽ khám phá các cách tiếp cận khác nhau để giải quyết vấn đề này một cách hiệu quả. Đến cuối bài viết này, bạn sẽ hiểu rõ hơn về cách giải quyết vấn đề này và được trang bị một số cách tiếp cận để tối ưu hóa giải pháp của mình.

Vấn đề:

Cho một mảng số nguyên nums, trả về một mảng answer sao cho answer[i] bằng tích của tất cả các phần tử của nums except nums[i] .

Bạn phải viết một thuật toán chạy theo O(n)thời gian và không sử dụng phép chia.

Cách tiếp cận 1: (Brute Force)

Chúng ta chỉ cần sử dụng hai vòng lặp lồng nhau để tính tích của tất cả các phần tử ngoại trừ phần tử hiện tại trong mảng đầu vào.
Lưu trữ sản phẩm trong một mảng mới và trả về mảng đó.

// Hàm mũi tên ES6 
const productExceptSelf = nums => { 
 const result = []; 
 for ( let i = 0 ; i < nums.length ; i++) { 
 let product = 1 ; 
 for ( let j = 0 ; j < nums.length ; j++) { 
 if (i !== j) { product * =
 nums[j]; 
 } 
 } 
 result.push (product); } return result; }

Độ phức tạp thời gian: O(N²)

Độ phức tạp không gian: O(N)

Lưu ý: Đây có thể là giải pháp rất đơn giản cho vấn đề này nhưng lại không hiệu quả đối với lượng dữ liệu đầu vào lớn hơn.

Cách tiếp cận 2: (Two-Pass Solution) Giải pháp hai lần

Đầu tiên, chúng ta tìm tích của tất cả các phần tử ở bên trái mỗi phần tử trong mảng đầu vào ở lần duyệt đầu tiên.
Sau đó, chúng ta tìm tích của tất cả các phần tử ở bên phải mỗi phần tử trong lần duyệt thứ hai.
Sau đó, nhân tích trái và tích phải để có được tích cuối cùng.

// Hàm mũi tên ES6 
const productExceptSelf = nums => { 
 const result = []; 

 // Lần truyền đầu tiên 
 let product = 1 ; 
 for ( let i = 0 ; i < nums. length ; i++) { 
 result[i] = product; 
 product *= nums[i]; 
 } 

 // Lần truyền thứ hai
 product = 1 ; 
 for ( let i = nums. length - 1 ; i >= 0 ; i--) { 
 result[i] *= product; 
 product *= nums[i]; 
 } 

 return result; 
}

Độ phức tạp thời gian: O(N)

Độ phức tạp không gian: O(N)

Cách tiếp cận 3: (Prefix and Suffix Products) Tiền tố và Hậu tố Tích

Trong phương pháp này, chúng tôi tính toán và lưu trữ các tích tiền tố trong một mảng và các tích hậu tố trong một mảng khác.
Tích tiền tố – Tích của tất cả các phần tử cho đến từng phần tử trong mảng đầu vào.
Tích hậu tố – Tích của tất cả các phần tử sau mỗi phần tử trong mảng đầu vào.
Sau đó, nhân các tích tiền tố và hậu tố tương ứng để có được tích cuối cùng.

// Hàm mũi tên ES6 
const productExceptSelf = nums => { 
 const prefix = [], suffix = [], result = []; 

 // tính toán các tích tiền tố
 prefix[ 0 ] = 1 ; 
 for ( let i = 1 ; i < nums. length ; i++) { 
 prefix[i] = prefix[i - 1 ] * nums[i - 1 ]; 
 } 

 // tính toán các tích hậu tố
 suffix[nums. length - 1 ] = 1 ; 
 for ( let i = nums. length - 2 ; i >= 0 ; i--) { 
 suffix[i] = suffix[i + 1 ] * nums[i + 1 ]; 
 } 

 // tích của hậu tố và tiền tố để tìm kết quả cuối cùng 
 for ( let i = 0 ; i < nums. length ; i++) { 
 result[i] = prefix[i] * suffix[i]; 
 } 

 return result; 
}

Độ phức tạp thời gian: O(N)

Độ phức tạp không gian: O(N)

Cách tiếp cận 4: (Optimized Prefix and Suffix Products) Tích tiền tố và hậu tố được tối ưu hóa

Phương pháp tích tiền tố và hậu tố được tối ưu hóa bao gồm việc tìm tích tiền tố và hậu tố tại chỗ bằng cách sử dụng mảng đầu ra để lưu trữ tích tiền tố và một biến để lưu trữ tích hậu tố.

// Hàm mũi tên ES6 
const productExceptSelf = nums => { 
 const result = []; 
 let product = 1 ; 

 // Tìm các tiền tố products và lưu trữ chúng trong mảng đầu ra
 result[ 0 ] = 1 ; 
 for ( let i = 1 ; i < nums. length ; i++) { 
 result[i] = result[i - 1 ] * nums[i - 1 ]; 
 } 

 // Tìm các hậu tố products tại chỗ và nhân chúng với các tiền tố products 

 for ( let i = nums. length - 1 ; i >= 0 ; i--) { 
 result[i] *= product; 
 product *= nums[i]; 
 } 

 return result; 
}

Độ phức tạp thời gian: O(N)

Độ phức tạp không gian: O(1)

Tổng Kết

Mô tả bài toán:

Cho một mảng nums có n phần tử, bạn cần trả về một mảng result sao cho:

result[i] = product(nums[0] * nums[1] * ... * nums[i-1] * nums[i+1] * ... * nums[n-1]).

Điều kiện:

Bạn không được sử dụng phép chia.
Bạn phải tính toán kết quả trong thời gian O(n) và không sử dụng thêm không gian O(n) (trừ không gian đầu ra).

Phương pháp giải quyết:

Sử dụng mảng kết quả:
- Tạo mảng result với cùng độ dài như mảng nums.
- Đầu tiên, chúng ta tính toán sản phẩm từ phía bên trái của mỗi phần tử. Duyệt qua mảng từ trái sang phải và lưu giá trị tích lũy vào result[i].
- Sau đó, tính toán sản phẩm từ phía bên phải. Duyệt từ phải sang trái, và cập nhật lại mảng result[i] bằng cách nhân với tích từ phía bên phải.
Giải thích chi tiết:
- Bước 1: Lưu sản phẩm của tất cả các phần tử phía bên trái của mỗi phần tử.
- Bước 2: Tính sản phẩm từ phía bên phải và nhân vào result[i].

Mã giải thuật trong JavaScript:

var productExceptSelf = function(nums) {
 const n = nums.length;
 const result = new Array(n); // Mảng kết quả

 // Bước 1: Tính sản phẩm các phần tử bên trái của nums[i]
 result[0] = 1; // Không có phần tử bên trái đầu tiên, nên đặt là 1
 for (let i = 1; i < n; i++) {
 result[i] = result[i - 1] * nums[i - 1];
 }

 // Bước 2: Tính sản phẩm các phần tử bên phải của nums[i] và cập nhật vào result[i]
 let rightProduct = 1; // Không có phần tử bên phải của phần tử cuối cùng
 for (let i = n - 2; i >= 0; i--) {
 rightProduct *= nums[i + 1]; // Tính tích từ phía bên phải
 result[i] *= rightProduct; // Cập nhật giá trị vào result[i]
 }

 return result;
};

// Test ví dụ
const nums = [1, 2, 3, 4];
console.log(productExceptSelf(nums)); // Output: [24, 12, 8, 6]

Giải thích từng dòng:

const result = new Array(n);: Tạo mảng result với cùng kích thước mảng nums để lưu kết quả cuối cùng.
result[0] = 1;: Ban đầu, sản phẩm các phần tử bên trái của phần tử đầu tiên là 1 (vì không có phần tử nào phía bên trái).
Duyệt từ trái qua phải:javascriptSao chép mãfor (let i = 1; i < n; i++) { result[i] = result[i - 1] * nums[i - 1]; }
- result[i] lưu trữ sản phẩm của tất cả các phần tử từ nums[0] đến nums[i-1]. Đối với phần tử đầu tiên, result[0] đã được gán giá trị 1 trước đó.
Duyệt từ phải qua trái:javascriptSao chép mãlet rightProduct = 1; for (let i = n - 2; i >= 0; i--) { rightProduct *= nums[i + 1]; result[i] *= rightProduct; }
- Biến rightProduct lưu trữ tích các phần tử bên phải của phần tử i.
- result[i] *= rightProduct; cập nhật mảng kết quả bằng cách nhân với sản phẩm từ phía bên phải.

Kết quả:

Khi nums = [1, 2, 3, 4], kết quả là [24, 12, 8, 6].
- Giải thích:
  - Đối với phần tử 1: Sản phẩm các phần tử còn lại là 2 * 3 * 4 = 24.
  - Đối với phần tử 2: Sản phẩm các phần tử còn lại là 1 * 3 * 4 = 12.
  - Đối với phần tử 3: Sản phẩm các phần tử còn lại là 1 * 2 * 4 = 8.
  - Đối với phần tử 4: Sản phẩm các phần tử còn lại là 1 * 2 * 3 = 6.

Độ phức tạp:

Thời gian: O(n), vì chúng ta chỉ cần duyệt qua mảng hai lần.
Không gian: O(1), không tính không gian đầu ra (vì ta chỉ sử dụng thêm một biến rightProduct).

Đề xuất cải tiến:

Bạn có thể thêm các kiểm tra đầu vào (chẳng hạn như kiểm tra mảng rỗng hoặc mảng có một phần tử) nếu cần.

LeetCode Bài 217. Contains Duplicate (javascript solution) Mảng Chứa Trùng Lặp

5 min
1 năm ago

Cho một mảng số nguyên số, quay lại đúng nếu bất kỳ giá trị nào xuất hiện ít nhất hai lần trong mảng và trả về sai nếu mọi phần tử đều khác biệt. Ví dụ 1: Thoạt nhìn, vấn đề có vẻ khá đơn giản. Ý […]

Tagged #ctdl&gt

Cho một mảng số nguyên số, quay lại đúng nếu bất kỳ giá trị nào xuất hiện ít nhất hai lần trong mảng và trả về sai nếu mọi phần tử đều khác biệt.

Ví dụ 1:

Input: nums = [1,2,3,1] Output: true

Thoạt nhìn, vấn đề có vẻ khá đơn giản. Ý tưởng ở đây là lặp lại mảng và tìm bất kỳ bản sao nào. Có một chút mã gian lận mà chúng ta có thể sử dụng với JavaScript trong phần này.

Giải pháp đầu tiên (cheating)

Đối tượng tập hợp là tập hợp các giá trị. Bạn có thể lặp qua các phần tử của một tập hợp theo thứ tự chèn. Một giá trị trong Tập hợp chỉ có thể xuất hiện một lần; nó là duy nhất trong Bộ sưu tập của Set.

Biết được điều này, điều duy nhất chúng ta cần làm là chuyển mảng của mình thành Tập hợp và so sánh độ dài của nó với độ dài mảng số ban đầu.

var containsDuplicate = function(nums) { const set = new Set([...nums]); return set.size != nums.length; };

Việc chuyển đổi một mảng thành Tập hợp rất đơn giản, chỉ cần trải mảng đó thành một mảng mới trong hàm tạo Set. Nó có thuộc tính tính toán kích thước (số lượng mục). Chúng ta chỉ cần so sánh nó với độ dài của mảng ban đầu, nums.

return set.size != nums.length;

Giải pháp thứ hai

Giống như của chúng ta (giải pháp đầu tiên) chúng ta có thể tạo một bảng băm của mảng khi lặp lại và đánh giá nó tại chỗ.

var containsDuplicate = function(nums) { const hashTable = new Map(); for(let i = 0; i < nums.length; i++) { if(hashTable.has(nums[i])) return true; else hashTable.set(nums[i], true); } return false; };

Để chia nhỏ điều này một chút: trước tiên chúng ta lặp lại mảng số. Nếu bản đồ đã có giá trị thì chúng ta trả về true. Chúng ta kiểm tra điều này với thuộc tính .has của map s

if(hashtable.has(nums[i]) return true;

Nếu không, chúng ta sẽ thêm nó vào bản đồ và tiếp tục.

else hashTable.set(nums[i], true);

Tổng Kết

Chúng ta có thể rút ra 1 cách làm ngắn gọn như sau:

Giải pháp:

Độ phức tạp thời gian: O(n)
Độ phức tạp của không gian: O(n)

var containsDuplicate = function(nums) { const map = {} for(const num of nums) { // If we have seen this num before return true if(map[num]) return true map[num] = true } return false };

Qua đây, hy vọng bạn có thêm chút kiến thức về giải thuật và nâng cao quá trình coding của mình nhé bạn ơi. Chúc các bạn làm việc hiệu quả :>

LeetCode – Rotate Image

1 min
1 năm ago
2

Vấn đề Bạn được cấp một nxn 2D ma trận đại diện cho một hình ảnh, xoay hình ảnh bằng cách 90 độ (theo chiều kim đồng hồ). Bạn phải xoay hình ảnh tại chỗ, điều đó có nghĩa là bạn phải sửa đổi trực tiếp ma trận 2D […]

Tagged #ctdl&gt

Vấn đề

Bạn được cấp một nxn 2D ma trận đại diện cho một hình ảnh, xoay hình ảnh bằng cách 90 độ (theo chiều kim đồng hồ).

Bạn phải xoay hình ảnh tại chỗ, điều đó có nghĩa là bạn phải sửa đổi trực tiếp ma trận 2D đầu vào. KHÔNG phân bổ một ma trận 2D khác và thực hiện phép quay.

Câu hỏi được lấy từ: https://leetcode.com/problems/rotate-image

Ví dụ 1:

Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Ví dụ 2:

Input: matrix = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]] Output: [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]

Ví dụ 3:

Input: matrix = [[1]] Output: [[1]]

Ví dụ 4:

Input: matrix = [[1, 2], [3, 4]] Output: [[3, 1], [4, 2]]

Hạn chế:

- matrix.length == n - matrix[i].length == n - 1 <= n <= 20 - -1000 <= matrix[i][j] <= 1000

Giải thích

Xoay nhóm bốn ô

Giải pháp đầu tiên chúng ta có thể nghĩ đến là xoay bốn góc của ma trận. Chúng tôi cũng lặp lại điều này với các ô tiếp theo.

Hãy kiểm tra thuật toán.

- initialize m = matrix.size, tmp - loop for i = 0; i < m / 2; i++ - loop for j = i; j < m - 1 - i; j++ - tmp = matrix[i][j] - matrix[i][j] = matrix[m - 1 - j][i] - matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j] - matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i] - matrix[j][m - 1 - i] = tmp

Độ phức tạp về thời gian của chương trình là O(M) vì mỗi ô sẽ được đọc một lần và được viết một lần. Độ phức tạp của không gian là ồ(1) bởi vì chúng tôi không sử dụng bất kỳ cấu trúc dữ liệu bổ sung nào khác.

giải pháp C++

class Solution { public: void rotate(vector<vector<int>>& matrix) { int m = matrix.size(), tmp; int j = 0; for(int i = 0; i < m/2; i++){ for(int j = i; j < m - 1 - i; j++){ tmp = matrix[i][j]; matrix[i][j] = matrix[m - 1 - j][i]; matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j]; matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]; matrix[j][m - 1 - i] = tmp; } } } };

Giải pháp Golang

func rotate(matrix [][]int) { m := len(matrix) tmp := 0 for i := 0; i < m / 2; i++ { for j := i; j < m - 1 - i; j++ { tmp = matrix[i][j]; matrix[i][j] = matrix[m - 1 - j][i]; matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j]; matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]; matrix[j][m - 1 - i] = tmp; } } }

Giải pháp Javascript

var rotate = function(matrix) { let m = matrix.length; let tmp = 0; let i, j; for(i = 0; i < m/2; i++){ for(j = i; j < m - 1 - i; j++){ tmp = matrix[i][j]; matrix[i][j] = matrix[m - 1 - j][i]; matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j]; matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]; matrix[j][m - 1 - i] = tmp; } } };

Chạy khô

Hãy chạy thử thuật toán của chúng tôi để xem giải pháp hoạt động như thế nào.

Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Step 1: m = matrix.length m = 3 Step 2: tmp = 0 Step 3: loop i = 0; i < 3/2 0 < 3/2 0 < 1 true j = i; j < 3 - 1 - 0 0 < 2 true tmp = matrix[i][j] tmp = 1 matrix[i][j] = matrix[m - 1 - j][i] matrix[0][0] = matrix[3 - 1 - 0][0] matrix[0][0] = matrix[2][0] matrix[0][0] = 7 matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j] matrix[3 - 1 - 0][0] = matrix[3 - 1 - 0][3 - 1 - 0] matrix[2][0] = matrix[2][2] matrix[2][0] = 9 matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i] matrix[3 - 1 - 0][3 - 1 - 0] = matrix[0][3 - 1 - 0] matrix[2][2] = matrix[0][2] matrix[2][2] = 3 matrix[j][m - 1 - i] = tmp matrix[0][3 - 1 - 0] = 1 matrix[0][2] = 1 j++ j = 1 Step 4: j < 2 1 < 2 true tmp = matrix[0][1] tmp = 2 matrix[i][1] = matrix[m - 1 - j][i] matrix[0][1] = matrix[3 - 1 - 1][0] matrix[0][1] = matrix[1][0] matrix[0][1] = 4 matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - 1] matrix[3 - 1 - 1][0] = matrix[3 - 1 - 0][3 - 1 - 1] matrix[1][0] = matrix[2][1] matrix[1][0] = 8 matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i] matrix[3 - 1 - 0][3 - 1 - 1] = matrix[1][3 - 1 - 0] matrix[2][1] = matrix[1][2] matrix[2][1] = 6 matrix[1][m - 1 - i] = tmp matrix[1][3 - 1 - 0] = 1 matrix[1][2] = 2 j++ j = 2 Step 5: j < 2 2 < 2 false Step 6: i++ i = 1 1 < 3/2 1 < 1 false Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

Data Structures Cheat Sheet

24 min
1 năm ago
11

Tagged #ctdl&gt

Trong bài viết này, mình sẽ giới thiệu về các cấu trúc dữ liệu, kèm theo ví dụ minh họa cho từng cấu trúc và cách chúng được biểu diễn trong Memgraph. Trong các cấu trúc này, đồ thị nổi bật như một cấu trúc dữ liệu phi tuyến tính bao gồm một tập hợp hữu hạn các nút, được kết nối bởi các mối quan hệ. Đồ thị thường được ứng dụng để giải quyết các vấn đề thực tế trong các lĩnh vực như mạng, đồ thị tri thức hoặc các trường hợp phát hiện gian lận.

Hãy xem qua bảng tham khảo nhanh Data Structures Cheat Sheet để nắm tổng quan về các cấu trúc mà mình sẽ đề cập dưới đây.

Đồ thị là gì?
Để bước vào thế giới cấu trúc dữ liệu, trước tiên chúng ta cần hiểu những khái niệm cơ bản. Như đã đề cập, đồ thị là một cấu trúc dữ liệu bao gồm các nút (đỉnh) và các mối quan hệ (cạnh). Các mối quan hệ kết nối bất kỳ hai nút nào trong đồ thị, và mỗi nút có thể lưu trữ các thuộc tính khác nhau. Ở hình dưới, ta thấy một đồ thị gồm năm nút được kết nối bằng các mối quan hệ có hướng.

Tạo nút và mối quan hệ
Giờ hãy tạo đồ thị trong hình minh họa trên bằng Memgraph. Đảm bảo rằng bạn đã có một phiên bản Memgraph đang chạy. Nếu chưa cài đặt, bạn có thể tham khảo hướng dẫn cài đặt trong tài liệu của Memgraph. Cách nhanh nhất để trải nghiệm Memgraph Platform (bao gồm cơ sở dữ liệu Memgraph, thư viện MAGE và Memgraph Lab) là chạy một trong các lệnh sau với Docker:

Trên Linux/macOS:

 curl https://install.memgraph.com | sh

Trên Windows:

 iwr https://windows.memgraph.com | iex

Từ hình trên, ta thấy có năm nút, mỗi nút được đánh dấu bởi một số. Hãy tạo các nút với nhãn là Node và các số là thuộc tính name trong các nút đó, kèm theo mối quan hệ có hướng :TO giữa chúng:

CREATE (n1:Node {name: '1'}), (n2:Node {name: '2'}), (n3:Node {name: '3'}), (n4:Node {name: '4'}), (n5:Node {name: '5'}), (n1)-[:TO]->(n4), (n3)-[:TO]->(n2), (n2)-[:TO]->(n4), (n4)-[:TO]->(n5)

Nếu bạn sử dụng giao diện trực quan của Memgraph là Memgraph Lab, bạn có thể xem đồ thị vừa tạo bằng cách chạy lệnh:

MATCH p=(()-[]-()) RETURN p;

Tạo chỉ mục
Giống như các hàm băm có chỉ mục, Memgraph cũng hỗ trợ tạo chỉ mục trên một số kết hợp giữa nhãn Node hoặc Node+Property để quét qua cơ sở dữ liệu và truy xuất nút nhanh hơn khi có một tập dữ liệu lớn. Ví dụ, nếu có nhiều nhãn khác nhau và một tập dữ liệu lớn, bạn có thể tạo chỉ mục trên nhãn Node bằng cách:

CREATE INDEX ON :Node

Cấu trúc dữ liệu

Trong khoa học máy tính, cấu trúc dữ liệu là cách tổ chức, quản lý và lưu trữ dữ liệu nhằm truy cập dữ liệu hiệu quả hơn. Nói cụ thể hơn, một cấu trúc dữ liệu là tập hợp các giá trị dữ liệu, các mối quan hệ giữa chúng, và các hàm hoặc thao tác có thể áp dụng lên dữ liệu. Có nhiều loại cấu trúc dữ liệu khác nhau, và trong bài viết này, mình sẽ đề cập đến Danh sách liên kết, Ma trận, Hàng đợi, Ngăn xếp và Cấu trúc cây.

Danh sách liên kết

Danh sách liên kết là một cấu trúc dữ liệu tuyến tính, trong đó các phần tử không được lưu trữ tại vị trí liên tiếp mà được liên kết thông qua các con trỏ. Nó tổ chức các mục theo thứ tự, với mỗi mục chứa một con trỏ đến mục tiếp theo. Một mục trong danh sách liên kết được gọi là nút. Nút đầu tiên gọi là “head” và nút cuối gọi là “tail.”

Biểu diễn Danh sách liên kết trong Memgraph

Tương tự như vậy, trong Memgraph, mình cũng sẽ biểu diễn các mục trong danh sách liên kết bằng các nút, nhưng mình không cần lưu trữ thông tin về địa chỉ của nút tiếp theo, mà chỉ cần sử dụng đồ thị có hướng để thực hiện điều đó. Hãy tạo lại danh sách liên kết từ hình minh họa bên trên, với mối quan hệ là LINKED_TO:

CREATE (n1:Node {name: 'A'}), (n2:Node {name: 'B'}), (n3:Node {name: 'C'}), (n4:Node {name: 'D'}), (n1)-[:LINKED_TO]->(n2)-[:LINKED_TO]->(n3)-[:LINKED_TO]->(n4)

Ngoài ra, bạn có thể lưu trữ các thuộc tính khác bên trong các nút của mình, như IDcode, tên khác của các nút hoặc bất kỳ thông tin bổ sung nào khác.

Khi chạy truy vấn sau, chúng ta có thể trực quan hóa dữ liệu đã tạo và dễ dàng truy cập vào các thuộc tính của nó bằng cách nhấp vào một nút cụ thể:

MATCH p=(()-[]-()) RETURN p;

Nếu bạn có một đồ thị lớn hơn và muốn, ví dụ, lấy thông tin về nơi mà nút có tên C liên kết tới, bạn có thể dùng truy vấn sau:

MATCH (:Node {name: 'C'})-[:LINKED_TO]->(m) RETURN m;

Hàng đợi

Hàng đợi là một cấu trúc dữ liệu tuyến tính mở ở cả hai đầu và các thao tác được thực hiện theo thứ tự vào trước ra trước (FIFO).

Chúng ta định nghĩa hàng đợi là một danh sách trong đó tất cả các bổ sung vào danh sách đều được thực hiện ở một đầu và tất cả các thao tác xóa khỏi danh sách đều được thực hiện ở đầu kia. Phần tử nào được thêm vào hàng đợi trước, thao tác sẽ được thực hiện trên nó trước.

Biểu diễn Hàng đợi trong Memgraph

Trong Memgraph, mình có thể biểu diễn một hàng đợi bằng cách tạo các nút và kết nối chúng với mối quan hệ chỉ ra nút nào đến trước với mối quan hệ :BEFORE. Tương tự, mình cũng có thể tạo mối quan hệ :AFTER và định hướng các mối quan hệ theo chiều ngược lại, tùy thuộc vào điều gì phù hợp nhất.

Truy vấn sau tạo ra ba nút và mối quan hệ :BEFORE giữa chúng, chỉ ra rằng nút A “đến hàng đợi” trước, sau đó là các nút B và C:

CREATE (n1:Node {name: 'A'}), (n2:Node {name: 'B'}), (n3:Node {name: 'C'}), (n1)-[:BEFORE]->(n2)-[:BEFORE]->(n3);

Các thao tác với Hàng đợi

Nếu muốn tìm phần tử nào ở đầu hàng đợi và loại bỏ nó, giống như chức năng Dequeue(), mình có thể thực hiện với truy vấn sau:

MATCH (a)-[:AFTER]->(b) WHERE NOT exists((b)-[:AFTER]->()) RETURN b;

Tương tự, nếu muốn thêm một phần tử D vào cuối hàng đợi, giả lập chức năng Enqueue():

MATCH (a)-[:AFTER]->(b)
WHERE NOT exists(()-[:AFTER]->(a))
CREATE (n4:Node {name: ‘D’})-[:AFTER]->(a);

Ngăn xếp (Stack)

Ngăn xếp là một cấu trúc dữ liệu tuyến tính theo một thứ tự đặc biệt khi thực hiện các thao tác. Thứ tự này có thể là LIFO (Last In First Out – vào sau ra trước) hoặc FILO (First In Last Out – vào trước ra sau). Với LIFO, phần tử được thêm vào cuối cùng sẽ là phần tử đầu tiên được lấy ra. Với FILO, phần tử đầu tiên được thêm vào sẽ là phần tử cuối cùng được lấy ra.

Biểu diễn Ngăn xếp trong Memgraph

Trong Memgraph, mình có thể biểu diễn ngăn xếp tương tự như cách biểu diễn hàng đợi. Truy vấn sau tạo ra các nút và mối quan hệ :ON_TOP giữa chúng, cho thấy rằng nút A vào ngăn xếp đầu tiên, tiếp theo là các nút B và C. Vì ngăn xếp hoạt động theo nguyên tắc First In Last Out, ta chỉ có thể truy cập nút vào cuối cùng, trong trường hợp này là nút C.

CREATE (n1:Node {name: 'A'}), (n2:Node {name: 'B'}), (n3:Node {name: 'C'}), (n3)-[:ON_TOP]->(n2)-[:ON_TOP]->(n1)

Các thao tác với Ngăn xếp

Pop: Để lấy phần tử ở đầu ngăn xếp và xóa nó, tương tự như hàm Pop(), ta có thể dùng truy vấn sau: MATCH (a)-[:ON_TOP]->(b) WHERE NOT exists(()-[:ON_TOP]->(a)) DETACH DELETE a Truy vấn này trước tiên khớp với tất cả các nút trên một nút khác và lọc ra nút không có nút nào ở trên cùng, tức là nút đang ở đầu ngăn xếp.
Push: Để thêm một nút mới vào ngăn xếp, tương tự như hàm Push(), ta có thể thực hiện truy vấn sau: MATCH (a)-[:ON_TOP]->(b) WHERE NOT exists(()-[:ON_TOP]->(a)) CREATE (n4:Node {name:'D'})-[:ON_TOP]->(a) Tương tự như truy vấn trước, ta lấy nút ở đầu ngăn xếp rồi tạo nút mới, kết nối với nút đó bằng mối quan hệ :ON_TOP.

Cấu trúc cây

Cây tổ chức các giá trị theo thứ bậc. Mỗi mục trong cây được gọi là một nút và mỗi nút có thể liên kết tới 0 hoặc nhiều nút con. Các nút lá là những nút ở cuối cây (nói cách khác: các nút không có con). Mỗi nút trong cây có độ sâu: số mối quan hệ từ gốc tới nút đó. Chiều cao của cây là số mối quan hệ từ gốc đến nút lá xa nhất (tức là độ sâu lớn nhất của nút).

Cách biểu diễn Cấu trúc cây trong Memgraph

Memgraph đã có cấu trúc tương tự với cây, bao gồm các nút được kết nối với nhau bằng các mối quan hệ, chỉ cần chỉ định kết nối giữa các nút để xác định nút cha và nút con.

Để tạo cây giống như hình minh họa trên, ta có thể chạy truy vấn sau, tạo ra các nút từ A đến I với mối quan hệ :PARENT_OF để chỉ ra kết nối.

CREATE (n1:Node {name: 'A'}), (n2:Node {name: 'B'}), (n3:Node {name: 'C'}), (n4:Node {name: 'D'}), (n5:Node {name: 'E'}), (n6:Node {name: 'F'}), (n7:Node {name: 'G'}), (n8:Node {name: 'H'}), (n9:Node {name: 'I'}), (n1)-[:PARENT_OF]->(n2)-[:PARENT_OF]->(n4), (n2)-[:PARENT_OF]->(n5)-[:PARENT_OF]->(n8), (n5)-[:PARENT_OF]->(n9), (n1)-[:PARENT_OF]->(n3)-[:PARENT_OF]->(n6), (n3)-[:PARENT_OF]->(n7)

Sau khi chạy truy vấn này, chúng ta sẽ có thể trực quan hóa cấu trúc cây mới tạo trong Memgraph.

MATCH p=(()-[]-()) RETURN p;

Duyệt cây (Tree Traversal)

Trong khoa học máy tính, duyệt cây (còn được gọi là tìm kiếm cây) là quá trình ghé thăm từng nút trong cấu trúc dữ liệu cây đúng một lần để truy xuất, cập nhật hoặc xóa. Các phương pháp duyệt cây được phân loại dựa trên thứ tự ghé thăm các nút. Hai thuật toán phổ biến nhất cho duyệt cây là Duyệt theo chiều rộng (Breadth-First Search, BFS) và Duyệt theo chiều sâu (Depth-First Search, DFS).

Table of Contents

Thuật toán Duyệt theo Chiều Rộng (BFS)

Trong duyệt theo chiều rộng, BFS bắt đầu từ một nút duy nhất, và thứ tự của các nút được ghé thăm phụ thuộc vào độ rộng của các nút (tức là khoảng cách từ nút nguồn). Điều này có nghĩa là khi một nút nào đó được ghé thăm, tất cả các nút ở khoảng cách gần hơn từ nút nguồn đã được ghé thăm trước, giúp xác định đường đi ngắn nhất từ nút nguồn đến nút vừa ghé thăm.

Ví dụ, với cây mẫu, các nút được gán nhãn theo thứ tự BFS như hình bên dưới:

Thực thi BFS trong Memgraph
Trong Memgraph, BFS được triển khai dựa trên cú pháp mở rộng mối quan hệ, có một số lợi ích so với hàm chuyên biệt. Cú pháp này cho phép lọc nút và mối quan hệ ngay trên đường đi, tìm nhiều đường đến nhiều nút đích, và duyệt qua vùng lân cận của một nút theo thứ tự BFS.

Truy vấn sau đây sẽ hiển thị đường đi ngắn nhất giữa các nút A và H:

MATCH path=(a {name: 'A'})-[*BFS]->(h {name: 'H'}) RETURN path;

Để lấy danh sách các mối quan hệ, thêm biến trước *BFS và trả về kết quả:

MATCH (a {name: 'A'})-[relationships *BFS]->(h {name: 'H'}) RETURN relationships;

Thuật toán Duyệt theo Chiều Sâu (DFS)

DFS là một thuật toán duyệt cây bằng cách khám phá các nút lân cận càng xa càng tốt. Khi đạt đến điểm cuối (dead-end), thuật toán sẽ quay lại tìm một nút mới chưa được khám phá, sau đó tiếp tục duyệt từ nút này để tìm các nút chưa được khám phá. Theo cách này, thuật toán duyệt qua tất cả các nút trong cây.

Ví dụ, DFS sẽ duyệt qua cây mẫu như hình bên dưới:

Thực thi DFS trong Memgraph
DFS trong Memgraph cũng được triển khai dựa trên cú pháp mở rộng mối quan hệ, cho phép tìm nhiều mối quan hệ giữa hai nút nếu tồn tại.

Truy vấn sau đây hiển thị tất cả các đường đi từ nút A đến nút H:

MATCH path=(a {name: 'A'})-[*]->(h {name: 'H'}) RETURN path;

Để lấy danh sách tất cả các mối quan hệ, thêm biến trong dấu ngoặc vuông và trả về kết quả:

MATCH (a {name: 'A'})-[relationships *]->(h {name: 'H'}) RETURN relationships;

Duyệt cây theo BFS và DFS trong Memgraph cho phép trực quan hóa cấu trúc và tính liên kết của các nút một cách hiệu quả, đặc biệt khi phân tích dữ liệu lớn và tìm kiếm đường đi trong các cấu trúc cây phức tạp.

DSA: All things about Strings (Full 50 Interview Questions)

24 min
2 năm ago
11

Basic String Concepts in JavaScript 1. What is a String in Data Structures? Explanation:A string in data structures is a sequence of characters used to represent text. In JavaScript, strings are primitive data types and immutable, meaning their content cannot be changed […]

Tagged #ctdl&gt, #dsa, #interview

Basic String Concepts in JavaScript

1. What is a String in Data Structures?

Explanation:
A string in data structures is a sequence of characters used to represent text. In JavaScript, strings are primitive data types and immutable, meaning their content cannot be changed after creation.

Example:

let str = "Hello, World!"; console.log(str); // Output: Hello, World!

2. Compare Strings and Character Arrays.

Explanation:

Strings:
In JavaScript, strings are immutable and provide various built-in methods for manipulation.
Cannot change individual characters directly; instead, a new string must be created for modifications.
Character Arrays:
In JavaScript, arrays of characters can be used to represent strings.
Arrays are mutable, allowing individual elements to be changed directly.

Example:

// String in JavaScript let str = "Hello"; str = str + ", World!"; console.log(str); // Output: Hello, World! // Character array in JavaScript let charArray = ['H', 'e', 'l', 'l', 'o']; charArray.push(', ', 'W', 'o', 'r', 'l', 'd', '!'); console.log(charArray.join('')); // Output: Hello, World!

3. What is a Null-Terminated String?

Explanation:
In some programming languages like C, a null-terminated string is a character array where the end of the string is marked by a special null character ('\0'). JavaScript does not use null-terminated strings since it handles strings differently.

Example in JavaScript:
JavaScript does not directly use null-terminated strings. Instead, it handles strings as objects with various methods and properties.

let str = "Hello, World!"; console.log(str.length); // Output: 13

4. Explain Mutability and Immutability in the context of Strings.

Explanation:

Mutable Strings:
Strings that can be changed after creation (not applicable in JavaScript).
Immutable Strings:
Strings in JavaScript are immutable. Any modification results in a new string.

Example:

let str = "Hello"; str[0] = 'J'; // This will not change the string console.log(str); // Output: Hello // To change the string, create a new one str = "J" + str.slice(1); console.log(str); // Output: Jello

5. How do different programming languages implement and manipulate Strings?

Explanation:
Different programming languages have different ways of implementing and manipulating strings. In JavaScript, strings are immutable and provide various methods for manipulation.

JavaScript String Manipulation:

Concatenation: Using the + operator or concat method.
Substring Extraction: Using slice, substring, or substr.
Replacing Content: Using replace or replaceAll.
Splitting and Joining: Using split and join.

Example:

let str = "Hello, World!"; // Concatenation let newStr = str + " How are you?"; console.log(newStr); // Output: Hello, World! How are you? // Substring Extraction let subStr = str.slice(0, 5); console.log(subStr); // Output: Hello // Replacing Content let replacedStr = str.replace("World", "JavaScript"); console.log(replacedStr); // Output: Hello, JavaScript! // Splitting and Joining let words = str.split(" "); console.log(words); // Output: ["Hello,", "World!"] let joinedStr = words.join(" "); console.log(joinedStr); // Output: Hello, World!

String Properties & Operations

6. Why are Character arrays preferred over Strings for passwords?

Character arrays (char[]) are preferred over strings (String) for passwords because:

Immutability: In many programming languages, strings are immutable, meaning once created, they cannot be changed. If a string is used to store a password, it remains in memory until garbage collected, potentially leading to security risks as the password can linger in memory.
Memory Management: Character arrays can be explicitly cleared after use. You can overwrite the array with random data to ensure the password is not left in memory.
Garbage Collection: Strings are managed by the garbage collector, which means you have less control over when the memory is freed. Character arrays can be manually managed, providing more control over memory.

Example in JavaScript:

// Using string (Not recommended for passwords) let passwordString = "SuperSecretPassword123"; // The string remains in memory until garbage collected // Using character array (Recommended) let passwordArray = ['S', 'u', 'p', 'e', 'r', 'S', 'e', 'c', 'r', 'e', 't', 'P', 'a', 's', 's', 'w', 'o', 'r', 'd', '1', '2', '3']; // Clear the password array after use passwordArray.fill('*');

7. Discuss how indexing works in Strings and how it affects various operations.

Indexing in strings allows access to individual characters in a string using their position. This enables operations like searching, slicing, and modifying parts of the string.

Example in JavaScript:

let str = "Hello, World!"; console.log(str[0]); // Output: 'H' // Slicing let slice = str.slice(0, 5); // Output: 'Hello' // Modifying (Strings are immutable in JavaScript) let modifiedStr = str.substring(0, 5) + " Everyone"; // Output: 'Hello Everyone'

8. What are Pascal Strings?

Pascal strings are a type of string data structure that includes a length byte as the first element. This length byte specifies the number of characters in the string, making it easier to handle string operations without relying on a null terminator.

Example in JavaScript (Simulated):

// Pascal string simulation in JavaScript function createPascalString(str) { let length = str.length; return [length, ...str.split('')]; } let pascalStr = createPascalString("Hello"); console.log(pascalStr); // Output: [5, 'H', 'e', 'l', 'l', 'o']

9. Explain how String Concatenation works and the time complexity associated with it.

String concatenation involves joining two or more strings end-to-end. In many languages, including JavaScript, strings are immutable. Thus, concatenation creates a new string each time, copying the content of the original strings, which can be inefficient for large strings.

Example in JavaScript:

let str1 = "Hello"; let str2 = "World"; let concatenatedStr = str1 + ", " + str2 + "!"; // Output: 'Hello, World!' // Using join for better performance in large scale concatenation let words = ["Hello", "World", "from", "JavaScript"]; let joinedStr = words.join(" "); // Output: 'Hello World from JavaScript'

The time complexity of string concatenation in JavaScript is generally (O(n + m)) where (n) and (m) are the lengths of the strings being concatenated. For multiple concatenations, using Array.join is more efficient.

10. Describe the Time Complexity of substring search in Strings.

Substring search involves finding if and where a substring exists within a string. The simplest method is to check each position in the string, which can have a time complexity of (O(n \times m)) for a string of length (n) and a substring of length (m). More efficient algorithms like the Knuth-Morris-Pratt (KMP) algorithm have a time complexity of (O(n + m)).

Example in JavaScript:

let str = "Hello, World!"; let substring = "World"; // Simple substring search (built-in method) let index = str.indexOf(substring); // Output: 7 console.log(index); // Position of 'World' in 'Hello, World!'

Advanced String Data Structures

11. What is a Rope data structure?

A Rope is a binary tree used to represent a string. It is particularly useful for efficiently performing operations such as concatenation, substring, insertion, and deletion. Instead of storing the string as a contiguous block of memory, a rope stores it in smaller, manageable chunks (nodes) with each node holding a reference to a left and right child.

12. Name key Advantages and Limitations of Ropes.

Advantages:

Efficient Concatenation: Concatenating two ropes is efficient, typically (O(\log n)), as it involves linking two trees together.
Efficient Substring Extraction: Extracting a substring can be performed in (O(\log n)) time.
Memory Management: Ropes allow for more efficient memory usage, especially for large strings.
Immutability: Ropes are often used in functional programming where immutability is preferred.

Limitations:

Complex Implementation: Ropes are more complex to implement compared to traditional strings.
Overhead: There is overhead due to the tree structure and nodes, which might not be ideal for very small strings or simple applications.
Cache Efficiency: Accessing characters in a rope can be less cache-efficient compared to contiguous arrays due to tree traversal.

13. What are some Practical Applications of Ropes?

Text Editors: Ropes are used in text editors for efficient text manipulation (insertions, deletions, and concatenations).
Version Control Systems: Managing large diffs and merging changes efficiently.
String Manipulation Libraries: Libraries that need to handle large and complex string operations efficiently.

14. Compare Ropes vs. StringBuilders.

Ropes:

Structure: Tree-based data structure.
Operations: Efficient for concatenation, substring, and insertion operations.
Use Cases: Suitable for applications requiring frequent and complex string manipulations, such as text editors.

StringBuilders:

Structure: Contiguous array that grows dynamically.
Operations: Efficient for appending and modifying strings.
Use Cases: Suitable for applications where strings are modified frequently in a simple manner.

15. Compare the performance of Strings vs. Ropes.

Strings:

Concatenation: Typically (O(n)) for each concatenation as it often involves creating a new string and copying.
Immutability: Strings are immutable, leading to more memory usage when modified frequently.
Memory Management: Less efficient for large strings due to repeated allocations and copying.

Ropes:

Concatenation: (O(\log n)) due to tree structure.
Mutability: Designed for efficient modifications, making it more suitable for applications with frequent string manipulations.
Memory Management: More efficient for large strings as it avoids repeated allocations and copying.

Example Implementation of Ropes in JavaScript:

Here is a simplified example to demonstrate the concept:

class RopeNode { constructor(left = null, right = null, value = '') { this.left = left; this.right = right; this.value = value; this.weight = value.length; } } class Rope { constructor(value) { this.root = new RopeNode(null, null, value); } concatenate(rope) { return new RopeNode(this.root, rope.root); } getSubstring(start, length) { const result = []; this._getSubstring(this.root, start, length, result); return result.join(''); } _getSubstring(node, start, length, result) { if (!node || length <= 0) return; if (start < node.weight) { this._getSubstring(node.left, start, length, result); const len = Math.min(node.weight - start, length); result.push(node.value.substring(start, start + len)); length -= len; start = 0; } else { start -= node.weight; } this._getSubstring(node.right, start, length, result); } } // Example usage let rope1 = new Rope('Hello, '); let rope2 = new Rope('World!'); let concatenatedRope = rope1.concatenate(rope2); console.log(concatenatedRope.getSubstring(0, 12)); // Output: 'Hello, World!'

String Searching Algorithms

16. Explain the Boyer-Moore Algorithm.

The Boyer-Moore algorithm is an efficient string-searching algorithm that preprocesses the pattern and skips sections of the text, making it faster than some other methods. It uses two heuristics: the Bad Character Heuristic and the Good Suffix Heuristic.

Bad Character Heuristic: If a mismatch occurs, the algorithm skips alignments to move the pattern past the bad character found in the text.
Good Suffix Heuristic: If a mismatch occurs, the algorithm shifts the pattern to align with the next occurrence of the matched suffix in the pattern.

Example in JavaScript:

function boyerMoore(text, pattern) { const badCharTable = createBadCharTable(pattern); const goodSuffixTable = createGoodSuffixTable(pattern); let s = 0; // shift of the pattern with respect to text while (s <= text.length - pattern.length) { let j = pattern.length - 1; while (j >= 0 && pattern[j] === text[s + j]) { j--; } if (j < 0) { console.log("Pattern found at index " + s); s += goodSuffixTable[0]; } else { s += Math.max(goodSuffixTable[j], j - badCharTable[text.charCodeAt(s + j)]); } } } function createBadCharTable(pattern) { const table = Array(256).fill(-1); for (let i = 0; i < pattern.length; i++) { table[pattern.charCodeAt(i)] = i; } return table; } function createGoodSuffixTable(pattern) { const m = pattern.length; const table = Array(m).fill(m); let lastPrefixIndex = m; for (let i = m - 1; i >= 0; i--) { if (isPrefix(pattern, i + 1)) { lastPrefixIndex = i + 1; } table[m - 1 - i] = lastPrefixIndex - i + m - 1; } for (let i = 0; i < m - 1; i++) { const slen = suffixLength(pattern, i); table[slen] = m - 1 - i + slen; } return table; } function isPrefix(pattern, p) { for (let i = p, j = 0; i < pattern.length; i++, j++) { if (pattern[i] !== pattern[j]) return false; } return true; } function suffixLength(pattern, p) { let len = 0; for (let i = p, j = pattern.length - 1; i >= 0 && pattern[i] === pattern[j]; i--, j--) { len++; } return len; } // Usage boyerMoore("HERE IS A SIMPLE EXAMPLE", "EXAMPLE");

17. Compare Knuth-Morris-Pratt, Boyer-Moore, and Rabin-Karp search algorithms.

Knuth-Morris-Pratt (KMP):

Complexity: (O(n + m))
Preprocessing: Computes a partial match table (LPS array) to avoid re-examining characters.
Usage: Efficient for patterns with repetitions and in cases where multiple searches of the same pattern are needed.

Boyer-Moore:

Complexity: Average case (O(n / m)), worst case (O(n \cdot m))
Preprocessing: Builds bad character and good suffix tables.
Usage: Very efficient for large alphabets and long patterns.

Rabin-Karp:

Complexity: Average case (O(n + m)), worst case (O(n \cdot m))
Preprocessing: Computes hash values of the pattern and substrings of the text.
Usage: Useful for multiple pattern searches or when the patterns are short.

18. Implement and discuss the complexity of the Z-algorithm for pattern searching.

The Z-algorithm constructs a Z-array that stores the length of the longest substring starting from a given position that matches the prefix of the string. It can be used to find occurrences of a pattern within a text in linear time.

Example in JavaScript:

function zAlgorithm(text, pattern) { const concat = pattern + '$' + text; const Z = calculateZ(concat); const result = []; for (let i = 0; i < Z.length; i++) { if (Z[i] === pattern.length) { result.push(i - pattern.length - 1); } } return result; } function calculateZ(str) { const Z = Array(str.length).fill(0); let L = 0, R = 0, K; for (let i = 1; i < str.length; i++) { if (i > R) { L = R = i; while (R < str.length && str[R] === str[R - L]) R++; Z[i] = R - L; R--; } else { K = i - L; if (Z[K] < R - i + 1) { Z[i] = Z[K]; } else { L = i; while (R < str.length && str[R] === str[R - L]) R++; Z[i] = R - L; R--; } } } return Z; } // Usage console.log(zAlgorithm("abracadabra", "abra")); // Output: [0, 7]

Complexity: The Z-algorithm runs in (O(n + m)) time where (n) is the length of the text and (m) is the length of the pattern.

19. How does the BNDM algorithm work for string matching?

The BNDM (Backward Nondeterministic DAWG Matching) algorithm is an advanced string matching algorithm that is particularly efficient for small alphabets and long patterns. It is an extension of the Boyer-Moore algorithm that uses bitwise operations to match multiple characters simultaneously.

Working:

Preprocessing: Builds a bitmask for each character in the pattern.
Searching: Scans the text from right to left, using the bitmasks to match characters efficiently.

Unfortunately, due to the complexity of implementing the BNDM algorithm and its specific use of bitwise operations, a full implementation is beyond this brief explanation. However, the algorithm is known for its efficiency in certain contexts, especially when dealing with binary data or DNA sequences.

String Manipulation Challenges

20. Check the String for Balanced Parentheses, using Linear Time and Constant Space.

To check for balanced parentheses using linear time and constant space, we can use a counter. We increment the counter for an opening parenthesis and decrement for a closing parenthesis. If the counter ever goes negative or is not zero at the end, the string is unbalanced.

Example in JavaScript:

function isBalanced(s) { let count = 0; for (let char of s) { if (char === '(') { count++; } else if (char === ')') { count--; if (count < 0) { return false; } } } return count === 0; } // Usage console.log(isBalanced("(()())")); // Output: true console.log(isBalanced("(()")); // Output: false

21. Remove the Minimum Number of parentheses to make a String valid.

To remove the minimum number of parentheses to make a string valid, we can use a stack to track the positions of invalid parentheses and then remove them.

Example in JavaScript:

function minRemoveToMakeValid(s) { let stack = []; let result = s.split(''); for (let i = 0; i < result.length; i++) { if (result[i] === '(') { stack.push(i); } else if (result[i] === ')') { if (stack.length === 0) { result[i] = ''; } else { stack.pop(); } } } while (stack.length > 0) { result[stack.pop()] = ''; } return result.join(''); } // Usage console.log(minRemoveToMakeValid("a)b(c)d")); // Output: "ab(c)d" console.log(minRemoveToMakeValid("))((")); // Output: ""

22. Reverse a String using Stack.

To reverse a string using a stack, we push all characters onto the stack and then pop them off in reverse order.

Example in JavaScript:

function reverseString(s) { let stack = []; for (let char of s) { stack.push(char); } let reversed = ''; while (stack.length > 0) { reversed += stack.pop(); } return reversed; } // Usage console.log(reverseString("hello")); // Output: "olleh"

23. Solve the String Compression problem.

To solve the string compression problem, we can iterate through the string, counting consecutive characters and appending the count along with the character to the result.

Example in JavaScript:

function compressString(s) { let compressed = ''; let count = 1; for (let i = 0; i < s.length; i++) { if (i < s.length - 1 && s[i] === s[i + 1]) { count++; } else { compressed += s[i] + (count > 1 ? count : ''); count = 1; } } return compressed.length < s.length ? compressed : s; } // Usage console.log(compressString("aaabccddd")); // Output: "a3bc2d3"

24. Write an algorithm to find the Longest Palindromic Substring within a given string.

To find the longest palindromic substring, we can use the expand around center approach. We expand from each possible center and keep track of the longest palindrome found.

Example in JavaScript:

function longestPalindrome(s) { if (s.length === 0) return ""; let start = 0, end = 0; for (let i = 0; i < s.length; i++) { let len1 = expandAroundCenter(s, i, i); let len2 = expandAroundCenter(s, i, i + 1); let len = Math.max(len1, len2); if (len > end - start) { start = i - Math.floor((len - 1) / 2); end = i + Math.floor(len / 2); } } return s.substring(start, end + 1); } function expandAroundCenter(s, left, right) { while (left >= 0 && right < s.length && s[left] === s[right]) { left--; right++; } return right - left - 1; } // Usage console.log(longestPalindrome("babad")); // Output: "bab" or "aba"

These examples provide efficient solutions to common string manipulation challenges using JavaScript.

String Pattern Problems

25. Check if a String is a Palindrome.

To check if a string is a palindrome, you can compare the string to its reverse.

Example in JavaScript:

function isPalindrome(s) { let cleaned = s.replace(/[^A-Za-z0-9]/g, '').toLowerCase(); let reversed = cleaned.split('').reverse().join(''); return cleaned === reversed; } // Usage console.log(isPalindrome("A man, a plan, a canal: Panama")); // Output: true console.log(isPalindrome("race a car")); // Output: false

26. Find all Permutations of a String.

To find all permutations of a string, we can use a recursive approach.

Example in JavaScript:

function permute(str) { let results = []; if (str.length === 1) { results.push(str); return results; } for (let i = 0; i < str.length; i++) { let char = str[i]; let remainingChars = str.slice(0, i) + str.slice(i + 1); let remainingPerms = permute(remainingChars); for (let perm of remainingPerms) { results.push(char + perm); } } return results; } // Usage console.log(permute("abc")); // Output: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

27. Check if two Strings are Anagrams.

To check if two strings are anagrams, we can sort the characters in both strings and compare them.

Example in JavaScript:

function areAnagrams(str1, str2) { let normalize = str => str.replace(/[^\w]/g, '').toLowerCase().split('').sort().join(''); return normalize(str1) === normalize(str2); } // Usage console.log(areAnagrams("listen", "silent")); // Output: true console.log(areAnagrams("hello", "world")); // Output: false

28. Find the Longest Repeating Subsequence in a String.

To find the longest repeating subsequence, we can use dynamic programming.

Example in JavaScript:

function longestRepeatingSubsequence(str) { let n = str.length; let dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0)); for (let i = 1; i <= n; i++) { for (let j = 1; j <= n; j++) { if (str[i - 1] === str[j - 1] && i !== j) { dp[i][j] = 1 + dp[i - 1][j - 1]; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[n][n]; } // Usage console.log(longestRepeatingSubsequence("aabb")); // Output: 2 console.log(longestRepeatingSubsequence("axxxy")); // Output: 2

29. Implement a solution to find the Shortest Palindrome that can be formed by adding characters to the beginning of a given string.

To find the shortest palindrome, we can use the KMP algorithm to find the longest palindromic prefix and then append the reverse of the remaining suffix to the beginning of the string.

Example in JavaScript:

function shortestPalindrome(s) { let rev = s.split('').reverse().join(''); let l = s + '#' + rev; let p = new Array(l.length).fill(0); for (let i = 1; i < l.length; i++) { let j = p[i - 1]; while (j > 0 && l[i] !== l[j]) { j = p[j - 1]; } if (l[i] === l[j]) { j++; } p[i] = j; } return rev.substring(0, s.length - p[l.length - 1]) + s; } // Usage console.log(shortestPalindrome("aacecaaa")); // Output: "aaacecaaa" console.log(shortestPalindrome("abcd")); // Output: "dcbabcd"

These solutions provide efficient methods for common string pattern problems using JavaScript.

Reversal & Transformation

30. Reverse the ordering of words in a String.

To reverse the ordering of words in a string, we can split the string by spaces, reverse the array of words, and then join them back together.

Example in JavaScript:

function reverseWordsOrder(str) { return str.split(' ').reverse().join(' '); } // Usage console.log(reverseWordsOrder("The quick brown fox")); // Output: "fox brown quick The"

31. Write a function to Reverse each word in a sentence while preserving whitespace and initial word order.

To reverse each word while preserving whitespace and initial word order, we can split the string by spaces, reverse each word, and join them back together.

Example in JavaScript:

function reverseEachWord(str) { return str.split(' ').map(word => word.split('').reverse().join('')).join(' '); } // Usage console.log(reverseEachWord("The quick brown fox")); // Output: "ehT kciuq nworb xof"

32. Transform one string to another using a minimal number of append/delete operations.

To transform one string to another using a minimal number of append/delete operations, we can use dynamic programming to find the edit distance (Levenshtein distance) between the two strings.

Example in JavaScript:

function editDistance(str1, str2) { const m = str1.length; const n = str2.length; const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); for (let i = 0; i <= m; i++) { for (let j = 0; j <= n; j++) { if (i === 0) { dp[i][j] = j; } else if (j === 0) { dp[i][j] = i; } else if (str1[i - 1] === str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]); } } } return dp[m][n]; } // Usage console.log(editDistance("kitten", "sitting")); // Output: 3

33. Implement an in-place algorithm to Reverse a String without using additional buffer space.

To reverse a string in-place without using additional buffer space, we can swap characters from the start and end moving towards the center.

Example in JavaScript:

function reverseStringInPlace(str) { let arr = str.split(''); let left = 0; let right = arr.length - 1; while (left < right) { [arr[left], arr[right]] = [arr[right], arr[left]]; left++; right--; } return arr.join(''); } // Usage console.log(reverseStringInPlace("hello")); // Output: "olleh"

String Comparison & Sorting

34. Explain why String Sorting differs from sorting other types of data and how to optimize it.

String sorting differs from sorting other types of data because it involves lexicographical comparison, which takes into account the alphabetical order of characters. This is different from numerical or date sorting, where values are compared directly based on their magnitude or chronological order.

Optimizations for String Sorting:

Locale-aware Sorting: In JavaScript, localeCompare can be used for locale-aware string sorting.
Radix Sort: For fixed-length strings, radix sort can be very efficient.
Trie-based Sort: Using a trie (prefix tree) can help optimize sorting when dealing with a large set of strings with common prefixes.

Example in JavaScript:

// Basic string sorting const strings = ["banana", "apple", "orange"]; strings.sort(); // Output: ["apple", "banana", "orange"] // Locale-aware sorting const localeStrings = ["résumé", "exposé", "café"]; localeStrings.sort((a, b) => a.localeCompare(b)); // Output: ["café", "exposé", "résumé"]

35. Discuss the Longest Common Prefix algorithm and its applications.

The Longest Common Prefix (LCP) algorithm finds the longest common starting substring among a set of strings. It is useful in:

DNA Sequence Analysis: Finding common subsequences.
Autocomplete Systems: Suggesting completions based on common prefixes.
File Systems: Finding common directory paths.

Example in JavaScript:

function longestCommonPrefix(strs) { if (!strs.length) return ''; let prefix = strs[0]; for (let i = 1; i < strs.length; i++) { while (strs[i].indexOf(prefix) !== 0) { prefix = prefix.slice(0, -1); if (!prefix) return ''; } } return prefix; } // Usage console.log(longestCommonPrefix(["flower", "flow", "flight"])); // Output: "fl"

36. Implement a solution for Grouping Anagrams given an array of strings.

To group anagrams, we can use a hash map where the key is a sorted version of the string and the value is a list of anagrams.

Example in JavaScript:

function groupAnagrams(strs) { const map = new Map(); for (let str of strs) { const sorted = str.split('').sort().join(''); if (!map.has(sorted)) { map.set(sorted, []); } map.get(sorted).push(str); } return Array.from(map.values()); } // Usage console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])); // Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

37. How do you compare version numbers represented as strings?

To compare version numbers represented as strings, we split the strings by the dot character and compare each segment numerically.

Example in JavaScript:

function compareVersion(v1, v2) { const parts1 = v1.split('.').map(Number); const parts2 = v2.split('.').map(Number); const len = Math.max(parts1.length, parts2.length); for (let i = 0; i < len; i++) { const num1 = parts1[i] || 0; const num2 = parts2[i] || 0; if (num1 > num2) return 1; if (num1 < num2) return -1; } return 0; } // Usage console.log(compareVersion("1.2", "1.2.0")); // Output: 0 console.log(compareVersion("1.2.1", "1.2.0")); // Output: 1 console.log(compareVersion("1.2", "1.3")); // Output: -1

Encoding & Encryption String Problems

38. Describe how you would Encode and Decode a string using the Run-Length Encoding algorithm.

Run-Length Encoding (RLE) is a simple compression technique where consecutive occurrences of the same character are replaced by a single character followed by the count of its repetitions.

Example in JavaScript:

// Encoding function function runLengthEncode(str) { let encoded = ''; let count = 1; for (let i = 0; i < str.length; i++) { if (str[i] === str[i + 1]) { count++; } else { encoded += str[i] + count; count = 1; } } return encoded; } // Decoding function function runLengthDecode(encoded) { let decoded = ''; for (let i = 0; i < encoded.length; i += 2) { let char = encoded[i]; let count = parseInt(encoded[i + 1]); decoded += char.repeat(count); } return decoded; } // Usage const original = "aaabbbccdddd"; const encoded = runLengthEncode(original); // Output: "a3b3c2d4" const decoded = runLengthDecode(encoded); // Output: "aaabbbccdddd" console.log(`Original: ${original}`); console.log(`Encoded: ${encoded}`); console.log(`Decoded: ${decoded}`);

39. Implement a simple String Encryption method such as Caesar Cipher and discuss its security.

The Caesar Cipher is a basic encryption technique where each letter in the plaintext is shifted a fixed number of places down or up the alphabet.

Example in JavaScript:

// Encryption function function caesarCipherEncrypt(str, shift) { return str.split('').map(char => { if (char.match(/[a-z]/i)) { let code = char.charCodeAt(0); if ((code >= 65) && (code <= 90)) { return String.fromCharCode(((code - 65 + shift) % 26) + 65); } else if ((code >= 97) && (code <= 122)) { return String.fromCharCode(((code - 97 + shift) % 26) + 97); } } return char; }).join(''); } // Decryption function function caesarCipherDecrypt(str, shift) { return caesarCipherEncrypt(str, 26 - shift); } // Usage const plaintext = "Hello, World!"; const shift = 3; const encrypted = caesarCipherEncrypt(plaintext, shift); // Output: "Khoor, Zruog!" const decrypted = caesarCipherDecrypt(encrypted, shift); // Output: "Hello, World!" console.log(`Plaintext: ${plaintext}`); console.log(`Encrypted: ${encrypted}`); console.log(`Decrypted: ${decrypted}`);

Security Discussion:

The Caesar Cipher is not secure by modern standards because it is vulnerable to frequency analysis and brute force attacks. Since there are only 25 possible shifts (excluding the original text), it can be easily broken with a brute-force approach or by analyzing the frequency of letters in the ciphertext.

40. Explain the challenges of Unicode Encoding and Decoding in strings and how programming languages address these issues.

Challenges:

Variable Length: Unicode characters can be represented with different byte lengths (e.g., UTF-8, UTF-16, UTF-32). This makes encoding and decoding more complex.
Normalization: Different representations of the same character (e.g., composed and decomposed forms) can lead to issues in string comparison and manipulation.
Legacy Systems: Interoperability with systems using different encodings can lead to data corruption or loss if not handled properly.

How Programming Languages Address These Issues:

Standard Libraries: Most modern programming languages provide robust libraries for handling Unicode strings. These libraries handle the intricacies of different encodings and ensure correct encoding and decoding.
Normalization Functions: Functions to normalize strings to a standard form (e.g., NFC, NFD) are provided to ensure consistent representation.
Encoding Detection: Libraries to detect and convert between different encodings help in managing interoperability with legacy systems.

Example in JavaScript:

// Unicode Normalization let str = 'é'; let normalizedNFC = str.normalize('NFC'); let normalizedNFD = str.normalize('NFD'); console.log(normalizedNFC === normalizedNFD); // Output: false console.log(normalizedNFC); // Output: é console.log(normalizedNFD); // Output: é (e followed by a combining acute accent) // Encoding and Decoding using TextEncoder and TextDecoder let encoder = new TextEncoder(); let decoder = new TextDecoder('utf-8'); let encoded = encoder.encode('Hello, World!'); let decoded = decoder.decode(encoded); console.log(encoded); // Output: Uint8Array of UTF-8 encoded bytes console.log(decoded); // Output: "Hello, World!"

Regular Expressions & Pattern Matching

41. How are Regular Expressions used for string pattern matching and validation?

Regular expressions (regex) are sequences of characters that define search patterns. They are used for string pattern matching and validation by specifying rules that a string must follow. Regular expressions are powerful tools for searching, replacing, and extracting data from strings.

Usage Examples in JavaScript:

Pattern Matching: Finding substrings that match a pattern.
Validation: Ensuring strings conform to a specific format (e.g., email addresses, phone numbers).

Example in JavaScript:

let regex = /hello/; let str = "hello world"; console.log(regex.test(str)); // Output: true console.log(str.match(regex)); // Output: ["hello"]

42. Write a regular expression to validate email addresses.

A regular expression to validate email addresses typically checks for the following pattern: username@domain.extension.

Example in JavaScript:

function validateEmail(email) { const regex = /^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$/; return regex.test(email); } // Usage console.log(validateEmail("test@example.com")); // Output: true console.log(validateEmail("invalid-email")); // Output: false

43. Implement a regex matcher to check if a string conforms to a given pattern.

To implement a regex matcher, you can use the RegExp object in JavaScript and its test method.

Example in JavaScript:

function regexMatcher(str, pattern) { const regex = new RegExp(pattern); return regex.test(str); } // Usage console.log(regexMatcher("hello world", "hello")); // Output: true console.log(regexMatcher("goodbye world", "hello")); // Output: false

44. Discuss how strings are handled in a Multilingual Context and the implications for data storage and manipulation.

In a multilingual context, strings need to support multiple languages, character sets, and encodings. This introduces challenges such as:

Unicode Support: Ensuring the system supports Unicode to handle characters from various languages.
Normalization: Different representations of the same character (e.g., accented characters) must be normalized for consistent processing.
Locale-Specific Issues: Sorting, formatting, and displaying strings correctly according to local conventions.

Implications for Data Storage and Manipulation:

Storage: Databases and file systems must support Unicode (e.g., UTF-8) to store multilingual data.
Collation: Sorting and comparison operations need to respect locale-specific rules.
Validation: Input validation must account for different character sets and formats.

Example in JavaScript:

let str = "Café"; let normalized = str.normalize('NFC'); console.log(normalized); // Output: "Café"

45. Explain the concept of Locale-Specific Sorting and how it can affect string comparison algorithms.

Locale-specific sorting takes into account the rules and conventions of a specific language or region when comparing strings. This ensures that strings are sorted in a way that is natural for users from different locales.

Effects on String Comparison Algorithms:

Collation Order: Characters may have different collation orders in different locales.
Case Sensitivity: Some locales may treat uppercase and lowercase characters differently.
Accent Sensitivity: Accented characters may be treated as distinct or equivalent to their base characters.

Example in JavaScript:

let strings = ["résumé", "exposé", "café"]; strings.sort((a, b) => a.localeCompare(b, 'fr')); // French locale sorting console.log(strings); // Output: ["café", "exposé", "résumé"]

Using localeCompare ensures that the strings are sorted according to the rules of the specified locale, which can differ significantly from the default sorting order. This is essential for applications that need to be usable in multiple languages and regions.

Memory Efficient String Processing

46. How can you minimize memory usage when manipulating large strings?

To minimize memory usage when manipulating large strings, consider the following strategies:

In-place Modifications: Modify strings in place where possible to avoid creating multiple copies.
String Builder: Use a StringBuilder or similar construct to accumulate string modifications, which avoids the overhead of repeatedly creating new string objects.
Streaming: Process strings in a streaming manner to handle large data without loading it all into memory at once.
Immutable Data Structures: Be cautious with immutable strings in languages like JavaScript, where each modification creates a new string object. Use mutable alternatives if available.
Avoid Substring Copies: Use views or pointers to subranges of strings instead of creating new substrings.

Example in JavaScript using an array as a string builder:

function concatenateStrings(strings) { return strings.join(''); } let parts = ["This ", "is ", "a ", "large ", "string."]; let largeString = concatenateStrings(parts); console.log(largeString); // Output: "This is a large string."

47. Discuss the use of Flyweight Pattern for memory-efficient string storage.

The Flyweight Pattern is used to minimize memory usage by sharing as much data as possible with similar objects. It involves creating a shared pool of immutable objects that can be reused, reducing the number of individual objects created.

Applications in String Storage:

Interning: Storing only one copy of each distinct string value in memory, thus reusing it whenever the same value is needed.
Substring Sharing: Instead of creating new strings for substrings, pointers to the original string are used.

Example in JavaScript (String Interning):

class StringFlyweight { constructor() { this.strings = new Map(); } get(str) { if (!this.strings.has(str)) { this.strings.set(str, str); } return this.strings.get(str); } } let flyweight = new StringFlyweight(); let str1 = flyweight.get("hello"); let str2 = flyweight.get("hello"); console.log(str1 === str2); // Output: true

48. Detect if a string has any duplicate characters without using additional data structures.

To detect duplicate characters without additional data structures, you can use bitwise operations if the string contains only lowercase English letters.

Example in JavaScript:

function hasDuplicateChars(str) { let checker = 0; for (let i = 0; i < str.length; i++) { let val = str.charCodeAt(i) - 'a'.charCodeAt(0); if ((checker & (1 << val)) > 0) { return true; } checker |= (1 << val); } return false; } // Usage console.log(hasDuplicateChars("abcde")); // Output: false console.log(hasDuplicateChars("hello")); // Output: true

49. Check for an Isomorphic String relationship between two given strings.

Two strings are isomorphic if the characters in one string can be replaced to get the other string, with a one-to-one mapping between characters.

Example in JavaScript:

function isIsomorphic(s, t) { if (s.length !== t.length) return false; let mapS = {}; let mapT = {}; for (let i = 0; i < s.length; i++) { if (!mapS[s[i]] && !mapT[t[i]]) { mapS[s[i]] = t[i]; mapT[t[i]] = s[i]; } else if (mapS[s[i]] !== t[i] || mapT[t[i]] !== s[i]) { return false; } } return true; } // Usage console.log(isIsomorphic("egg", "add")); // Output: true console.log(isIsomorphic("foo", "bar")); // Output: false

50. Implement a string tokenizer that can split a string into tokens based on different delimiters.

A string tokenizer splits a string into substrings (tokens) based on specified delimiters.

Example in JavaScript:

function tokenizeString(str, delimiters) { let regex = new RegExp(`[${delimiters.join('')}]`, 'g'); return str.split(regex).filter(token => token.length > 0); } // Usage let str = "hello,world;this is-a:test"; let delimiters = [',', ';', '-', ':']; let tokens = tokenizeString(str, delimiters); // Output: ["hello", "world", "this", "is", "a", "test"] console.log(tokens);

These examples provide efficient solutions for handling memory usage, detecting duplicates, checking isomorphic relationships, and tokenizing strings using JavaScript.

DSA: Searching Algorithms (Full 59 Interview Questions)