Tháng 12 2024 - Trang 2 trên 2

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

Cấu Trúc Dữ Liệu & Giải Thuật

Lập Trình

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ả :>

Flutter Vs React Native : So Sánh Performance Benchmarks Bạn Không Thể Bỏ Lỡ !

Uncategorized

16 min
1 năm ago
7

Khi nói đến phát triển ứng dụng di động, sự lựa chọn giữa Flutter và React Native thường xoay quanh việc cân nhắc hiệu suất. Mặc dù cả hai khung đều có những người ủng hộ, nhưng kết quả điểm chuẩn thực […]

Leetcode 121: Giải bài Best Time to Buy and Sell Stock bằng JavaScript LeetCode

Cấu Trúc Dữ Liệu & Giải Thuật

Lập Trình

5 min
1 năm ago
5

Giải thích và mã giả: Để giải quyết vấn đề này, trước tiên người ta sử dụng một Cách tiếp cận thuật toán Brute Force. chúng tôi sẽ thử tất cả lợi nhuận có thể có được từ các giá trị nhất định […]

Tagged #seriesLeetCode

LeetCode – Rotate Image

Cấu Trúc Dữ Liệu & Giải Thuật

Lập Trình

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]]

Phá Kén

Tháng: Tháng 12 2024

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

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

Flutter Vs React Native : So Sánh Performance Benchmarks Bạn Không Thể Bỏ Lỡ !

Leetcode 121: Giải bài Best Time to Buy and Sell Stock bằng JavaScript LeetCode

LeetCode – Rotate Image