NỘI DUNG BÀI VIẾT
Khi giải quyết các vấn đề về mã hóa, hiệu quả là điều tối quan trọng – từ số giờ mã hóa đến thời gian chạy, đến dung lượng bộ nhớ dành cho một giải pháp. Rất may, các lập trình viên JavaScript sử dụng nhiều cấu trúc dữ liệu được thiết lập trước được thiết kế để giải quyết các nhu cầu chung và giải quyết các vấn đề trong thế giới thực.
Thành thạo cấu trúc dữ liệu là yếu tố chính đánh dấu sự khác biệt giữa một lập trình viên mới và một cựu chiến binh có thể thuê được.
Có thể bạn chỉ mới bắt đầu với cấu trúc dữ liệu, hoặc có thể bạn đã viết code trong nhiều năm và chỉ cần nâng cấp. Hôm nay, tôi sẽ hướng dẫn bạn 6 cấu trúc dữ liệu hàng đầu mà bất kỳ lập trình viên JS nào cũng cần biết.
Cấu trúc dữ liệu là gì?
Cấu trúc dữ liệu, ở cấp độ cao, là các kỹ thuật lưu trữ và tổ chức dữ liệu giúp sửa đổi, điều hướng và truy cập dễ dàng hơn. Cấu trúc dữ liệu xác định cách dữ liệu được thu thập, các chức năng chúng ta có thể sử dụng để truy cập nó và mối quan hệ giữa các dữ liệu.
Cấu trúc dữ liệu được sử dụng trong hầu hết các lĩnh vực khoa học máy tính và lập trình, từ hệ điều hành đến code vanilla cơ bản cho đến trí tuệ nhân tạo.
Cấu trúc dữ liệu cho phép bạn:
- Quản lý và sử dụng tập dữ liệu lớn
- Tìm kiếm dữ liệu cụ thể từ cơ sở dữ liệu
- Thiết kế các thuật toán phù hợp với các chương trình cụ thể
- Xử lý nhiều yêu cầu từ người dùng cùng một lúc
- Đơn giản hóa và tăng tốc độ xử lý dữ liệu
Cấu trúc dữ liệu rất quan trọng để giải quyết vấn đề hiệu quả trong thế giới thực. Xét cho cùng, cách chúng ta tổ chức dữ liệu có rất nhiều tác động đến hiệu suất và khả năng sử dụng. Trên thực tế, hầu hết các công ty hàng đầu đều yêu cầu sự hiểu biết sâu về cấu trúc dữ liệu.
Bất kỳ ai muốn bẻ khóa cuộc phỏng vấn viết mã sẽ cần phải nắm vững cấu trúc dữ liệu.
JavaScript có cấu trúc dữ liệu nguyên thủy và không nguyên thủy.
Các cấu trúc dữ liệu nguyên thủy và kiểu dữ liệu có nguồn gốc từ ngôn ngữ lập trình. Chúng bao gồm boolean, null, number, string, v.v.
Các cấu trúc dữ liệu không nguyên thủy không được định nghĩa bởi ngôn ngữ lập trình mà là bởi người lập trình. Chúng bao gồm cấu trúc dữ liệu tuyến tính, cấu trúc dữ liệu tĩnh và cấu trúc dữ liệu động, như hàng đợi và danh sách được liên kết.
1. Mảng
Cơ bản nhất của tất cả các cấu trúc dữ liệu, một mảng lưu trữ dữ liệu trong bộ nhớ để sử dụng sau này. Mỗi mảng có một số lượng ô cố định được quyết định khi tạo và mỗi ô có một chỉ mục số tương ứng được sử dụng để chọn dữ liệu của nó. Bất cứ khi nào bạn muốn sử dụng mảng, tất cả những gì bạn cần là các chỉ số mong muốn và bạn có thể truy cập bất kỳ dữ liệu nào bên trong.
Thuận lợi
- Đơn giản để tạo và sử dụng.
- Khối xây dựng nền tảng cho cấu trúc dữ liệu phức tạp
Nhược điểm
- Kích thước cố định
- Đắt tiền để chèn / xóa hoặc gửi lại các giá trị
- Không hiệu quả để sắp xếp
Nơi áp dụng
2. Hàng đợi
Về mặt khái niệm, hàng đợi tương tự như ngăn xếp; cả hai đều là cấu trúc tuần tự, nhưng xếp hàng các phần tử xử lý theo thứ tự chúng được nhập thay vì phần tử gần đây nhất.
Do đó, hàng đợi có thể được coi như một phiên bản FIFO (First In, First Out) của ngăn xếp. Chúng hữu ích như một bộ đệm cho các yêu cầu, lưu trữ từng yêu cầu theo thứ tự mà nó được nhận cho đến khi nó có thể được xử lý.
Để có hình ảnh, hãy xem xét đường hầm một làn: ô tô đầu tiên đi vào là ô tô đầu tiên đi ra. Nếu các xe khác muốn đi ra, nhưng xe đầu tiên dừng lại, thì tất cả các xe sẽ phải đợi xe đầu tiên thoát ra trước khi có thể đi tiếp.
Thuận lợi
- Kích thước động
- Đặt hàng dữ liệu theo thứ tự nó đã được nhận
- Thời gian chạy thấp
Nhược điểm
- Chỉ có thể truy xuất phần tử cũ nhất
Nơi áp dụng
- Hiệu quả như một bộ đệm khi nhận dữ liệu thường xuyên
- Cách thuận tiện để lưu trữ dữ liệu nhạy cảm với đơn đặt hàng, chẳng hạn như thư thoại được lưu trữ
- Đảm bảo dữ liệu cũ nhất được xử lý trước
3. Danh sách liên kết
Danh sách được liên kết là một cấu trúc dữ liệu, không giống như ba cấu trúc trước, không sử dụng vị trí vật lý của dữ liệu trong bộ nhớ. Điều này có nghĩa là, thay vì chỉ mục hoặc vị trí, danh sách được liên kết sử dụng hệ thống tham chiếu: các phần tử được lưu trữ trong các nút có chứa một con trỏ đến nút tiếp theo, lặp lại cho đến khi tất cả các nút được liên kết.
Hệ thống này cho phép chèn và loại bỏ các mục một cách hiệu quả mà không cần phải tổ chức lại.
Thuận lợi
- Chèn và loại bỏ hiệu quả các phần tử mới
- Ít phức tạp hơn là tái cấu trúc một mảng
Nhược điểm
- Sử dụng nhiều bộ nhớ hơn mảng
- Không hiệu quả để truy xuất một phần tử cụ thể
- Không hiệu quả để duyệt ngược danh sách
Nơi áp dụng
4. Cây cối
Cây là một cấu trúc dữ liệu dựa trên quan hệ khác, chuyên thể hiện cấu trúc phân cấp. Giống như một danh sách được liên kết, các nút chứa cả phần tử dữ liệu và con trỏ đánh dấu mối quan hệ của nó với các nút ngay lập tức.
Mỗi cây có một nút “gốc”, tất cả các nút khác sẽ phân nhánh. Gốc chứa các tham chiếu đến tất cả các phần tử ngay bên dưới nó, được gọi là “các nút con” của nó. Điều này tiếp tục, với mỗi nút con, phân nhánh thành nhiều nút con hơn.
Các nút có nút con được liên kết được gọi là nút bên trong trong khi những nút không có nút con là nút bên ngoài. Một loại cây phổ biến là “cây tìm kiếm nhị phân” được sử dụng để dễ dàng tìm kiếm dữ liệu được lưu trữ.
Các hoạt động tìm kiếm này có hiệu quả cao, vì thời lượng tìm kiếm của nó không phụ thuộc vào số lượng nút mà phụ thuộc vào số cấp của cây.
Loại cây này được xác định bởi bốn quy tắc nghiêm ngặt:
- Cây con bên trái chỉ chứa các nút có phần tử nhỏ hơn gốc.
- Cây con bên phải chỉ chứa các nút có phần tử lớn hơn gốc.
- Các cây con trái và phải cũng phải là một cây tìm kiếm nhị phân. Họ phải tuân theo các quy tắc trên với “gốc” của cây của họ.
- Không thể có các nút trùng lặp, tức là không thể có hai nút nào có cùng giá trị.
Thuận lợi
- Lý tưởng để lưu trữ các mối quan hệ phân cấp
- Kích thước động
- Thao tác chèn và xóa nhanh chóng
- Trong cây tìm kiếm nhị phân, các nút được chèn được sắp xếp theo trình tự ngay lập tức.
- Cây tìm kiếm nhị phân có hiệu quả trong việc tìm kiếm; chiều dài chỉO (chiều cao)O ( h e i g h t ).
Nhược điểm
- Chậm sắp xếp lại các nút
- Các nút con không có thông tin gì về nút cha của chúng
- Cây tìm kiếm nhị phân không nhanh bằng bảng băm phức tạp hơn
- Cây tìm kiếm nhị phân có thể suy biến thành tìm kiếm tuyến tính (quét tất cả các phần tử) nếu không được thực hiện với các cây con cân bằng.
Nơi áp dụng
- Lưu trữ dữ liệu phân cấp chẳng hạn như vị trí tệp.
- Cây tìm kiếm nhị phân rất tuyệt vời cho các tác vụ cần tìm kiếm hoặc sắp xếp thứ tự dữ liệu.
5. Đồ thị
Đồ thị là một cấu trúc dữ liệu dựa trên mối quan hệ hữu ích để lưu trữ các mối quan hệ giống như web. Mỗi nút hoặc đỉnh, như chúng được gọi trong đồ thị, có một tiêu đề (A, B, C, v.v.), một giá trị được chứa bên trong và danh sách các liên kết (được gọi là các cạnh) mà nó có với các đỉnh khác.
Trong ví dụ trên, mỗi đường tròn là một đỉnh và mỗi đường là một cạnh. Nếu được viết bằng văn bản, cấu trúc này sẽ giống như sau:
V = {a, b, c, d}
E = {ab, ac, bc, cd}
Mặc dù khó hình dung lúc đầu, nhưng cấu trúc này vô giá trong việc truyền tải biểu đồ mối quan hệ ở dạng văn bản, bất kỳ thứ gì từ mạch điện đến mạng lưới tàu.
Thuận lợi
- Có thể nhanh chóng truyền tải hình ảnh qua văn bản
- Có thể sử dụng để lập mô hình cho một số lượng đa dạng các đối tượng miễn là chúng chứa một cấu trúc quan hệ
Nhược điểm
- Ở cấp độ cao hơn, văn bản có thể tốn nhiều thời gian để chuyển đổi thành hình ảnh.
- Có thể khó nhìn thấy các cạnh hiện có hoặc bao nhiêu cạnh mà một đỉnh nhất định đã kết nối với nó
Nơi áp dụng
6. Bảng băm (Bản đồ)
Bảng băm là một cấu trúc dữ liệu phức tạp có khả năng lưu trữ lượng lớn thông tin và truy xuất các phần tử cụ thể một cách hiệu quả. Cấu trúc dữ liệu này dựa trên khái niệm về các cặp khóa / giá trị, trong đó “khóa” là một chuỗi được tìm kiếm và “giá trị” là dữ liệu được ghép nối với khóa đó.
Mỗi khóa được tìm kiếm được chuyển đổi từ dạng chuỗi của nó thành một giá trị số, được gọi là hàm băm, sử dụng hàm băm xác định trước. Sau đó, băm này trỏ đến một nhóm lưu trữ – một nhóm con nhỏ hơn trong bảng. Sau đó, nó tìm kiếm trong thùng để tìm khóa đã nhập ban đầu và trả về giá trị được liên kết với khóa đó.
Thuận lợi
- Khóa có thể ở bất kỳ dạng nào, trong khi các chỉ số của mảng phải là số nguyên
- Chức năng tìm kiếm hiệu quả cao
- Số lượng hoạt động không đổi cho mỗi lần tìm kiếm
- Chi phí không đổi cho các hoạt động chèn hoặc xóa
Nhược điểm
- Xung đột: lỗi xảy ra khi hai khóa chuyển đổi thành cùng một code băm hoặc hai code băm trỏ đến cùng một giá trị.
- Những lỗi này có thể phổ biến và thường yêu cầu đại tu hàm băm.
Nơi áp dụng
- Cơ sở dữ liệu lưu trữ
- Tra cứu địa chỉ theo tên
Mỗi bảng băm có thể rất khác nhau, từ loại khóa và giá trị, đến cách hoạt động của các hàm băm của chúng. Do những khác biệt này và các khía cạnh nhiều lớp của bảng băm, nên nói chung là gần như không thể đóng gói được.
Câu hỏi phỏng vấn về cấu trúc dữ liệu
Đối với nhiều lập trình viên, cấu trúc dữ liệu là quan trọng nhất để bẻ khóa các cuộc phỏng vấn viết code Javascript . Các câu hỏi và vấn đề về cấu trúc dữ liệu là cơ bản cho các cuộc phỏng vấn viết code ngày nay. Trên thực tế, họ có rất nhiều điều để nói về khả năng tuyển dụng và tỷ lệ đầu vào của bạn với tư cách là một ứng viên.
Hôm nay, cùng mình xem xét 7 câu hỏi phỏng vấn viết code phổ biến cho cấu trúc dữ liệu JavaScript, một câu hỏi dành cho mỗi cấu trúc dữ liệu mà chúng ta đã thảo luận ở trên. Mỗi bên cũng sẽ thảo luận về độ phức tạp về thời gian của nó dựa trên lý thuyết ký hiệu BigO .
Mảng: Xóa tất cả các số nguyên chẵn khỏi một mảng
Câu lệnh vấn đề: Thực hiện một hàm removeEven(arr), lấy một mảng arr trong đầu vào của nó và xóa tất cả các phần tử chẵn khỏi một mảng nhất định.
Đầu vào: Một mảng các số nguyên ngẫu nhiên
[1,2,4,5,10,6,3]
Đầu ra: một mảng chỉ chứa các số nguyên lẻ
[1,5,3]
Code language: JSON / JSON with Comments (json)Có hai cách bạn có thể giải quyết vấn đề mã hóa này trong một cuộc phỏng vấn. Hãy thảo luận về từng cái.
Giải pháp số 1: Làm điều đó “bằng tay”
function removeEven(arr) {
var odds = []
for (let number of arr) {
if (number % 2 != 0) // Check if the item in the list is NOT even ('%' is the modulus symbol!)
odds.push(number) //If it isn't even append it to the empty list
}
return odds // Return the new list
}
console.log(removeEven([3, 2, 41, 3, 34]))Code language: JavaScript (javascript)Cách tiếp cận này bắt đầu với phần tử đầu tiên của mảng. Nếu phần tử hiện tại đó không chẵn, nó sẽ đẩy phần tử này vào một mảng mới. Nếu nó là chẵn, nó sẽ chuyển sang phần tử tiếp theo, lặp lại cho đến khi nó đến cuối mảng. Về độ phức tạp thời gian, vì toàn bộ mảng phải được lặp lại, giải pháp này là O(n) O(n).
Giải pháp # 2: Sử dụng hàm filter () và lambda
function removeEven(arr) {
return arr.filter((v => (v % 2) != 0))
}
console.log(removeEven([3,2,41,3,34]))Code language: JavaScript (javascript)Giải pháp này cũng bắt đầu với phần tử đầu tiên và kiểm tra xem nó có chẵn không. Nếu nó là số chẵn, nó sẽ lọc ra phần tử này. Nếu không, hãy chuyển đến phần tử tiếp theo, lặp lại quá trình này cho đến khi nó đến cuối mảng.
Bộ lọc sử dụng hàm lambda hoặc hàm mũi tên, sử dụng cú pháp ngắn hơn, đơn giản hơn. Bộ lọc lọc ra phần tử mà hàm lambda trả về false. Độ phức tạp về thời gian của giải pháp này cũng giống như độ phức tạp về thời gian của giải pháp trước đó.
Ngăn xếp: Kiểm tra các dấu ngoặc đơn cân bằng bằng cách sử dụng một ngăn xếp
Câu lệnh bài toán: Thực hiện hàm isBalanced() lấy một chuỗi chỉ chứa các dấu ngoặc nhọn {}, vuông [] và tròn (). Hàm sẽ cho chúng ta biết nếu tất cả các dấu ngoặc trong chuỗi là cân bằng. Điều này có nghĩa là mọi dấu ngoặc mở sẽ có một dấu đóng. Ví dụ, {[]} là cân bằng, nhưng {[}] không.
Đầu vào : Một chuỗi chỉ bao gồm (, ), {, }, [ và ]
exp = "{[({})]}"Code language: JavaScript (javascript)Đầu ra: Trả về False nếu biểu thức không có dấu ngoặc cân bằng. Nếu đúng, hàm sẽ trả về True.
TrueCode language: PHP (php)Để giải quyết vấn đề này, chúng ta có thể chỉ cần sử dụng một chồng ký tự. Nhìn vào mã bên dưới để xem nó hoạt động như thế nào.
"use strict";
module.exports = class Stack {
constructor() {
this.items = [];
this.top = null;
}
getTop() {
if (this.items.length == 0)
return null;
return this.top;
}
isEmpty() {
return this.items.length == 0;
}
size() {
return this.items.length;
}
push(element) {
this.items.push(element);
this.top = element;
}
pop() {
if (this.items.length != 0) {
if (this.items.length == 1) {
this.top = null;
return this.items.pop();
} else {
this.top = this.items[this.items.length - 2];
return this.items.pop();
}
} else
return null;
}
}Code language: JavaScript (javascript)"use strict";
const Stack = require('./Stack.js');
function isBalanced(exp) {
var myStack = new Stack();
//Iterate through the string exp
for (var i = 0; i < exp.length; i++) {
//For every closing parenthesis check for its opening parenthesis in stack
if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']') {
if (myStack.isEmpty()) {
return false
}
let output = myStack.pop();
//If you can't find the opening parentheses for any closing one then returns false.
if (((exp[i] == "}") && (output != "{")) || ((exp[i] == ")") && (output != "(")) || ((exp[i] == "]") && (output != "["))) {
return false;
}
} else {
//For each opening parentheses, push it into stack
myStack.push(exp[i]);
}
}
//after complete traversal of string exp, if there's any opening parentheses left
//in stack then also return false.
if (myStack.isEmpty() == false) {
return false
}
//At the end return true if you haven't encountered any of the above false conditions.
return true
}
var inputString = "{[()]}"
console.log(inputString)
console.log(isBalanced(inputString))
inputString = "{[([({))]}}"
console.log(inputString)
console.log(isBalanced(inputString))Code language: JavaScript (javascript)Quá trình này sẽ lặp lại trên chuỗi một ký tự tại một thời điểm. Chúng tôi có thể xác định rằng chuỗi không cân bằng dựa trên hai yếu tố:
- Ngăn xếp trống.
- Phần tử trên cùng trong ngăn xếp không phải là loại phù hợp.
Nếu một trong hai điều kiện này là đúng, chúng tôi quay trở lại False. Nếu dấu ngoặc đơn là dấu ngoặc mở, nó được đẩy vào ngăn xếp. Nếu cuối cùng tất cả đều cân bằng, ngăn xếp sẽ trống. Nếu nó không có sản phẩm nào, chúng tôi quay trở lại False. Vì chúng ta duyệt chuỗi exp chỉ một lần nên độ phức tạp về thời gian là O(n) .
Hàng đợi: Tạo Số nhị phân từ 1 đến n
Câu lệnh vấn đề: Thực hiện một hàm findBin(n), hàm này sẽ tạo ra các số nhị phân từ 1đến ndưới dạng một chuỗi bằng cách sử dụng một hàng đợi.
Đầu vào: Một số nguyên dương n
n = 3Đầu ra: Trả về số nhị phân dưới dạng chuỗi từ 1 đến n
result = ["1","10","11"]Code language: JavaScript (javascript)Cách dễ nhất để giải quyết vấn đề này là sử dụng hàng đợi để tạo ra các số mới từ các số trước đó. Hãy phá vỡ điều đó.
"use strict";
const Queue = require('./Queue.js');
function findBin(n) {
let result = [];
let myQueue = new Queue();
var s1, s2;
myQueue.enqueue("1");
for (var i = 0; i < n; i++) {
result.push(myQueue.dequeue());
s1 = result[i] + "0";
s2 = result[i] + "1";
myQueue.enqueue(s1);
myQueue.enqueue(s2);
}
return result;
}
console.log(findBin(10))
Code language: JavaScript (javascript)"use strict";
module.exports = class Queue {
constructor() {
this.items = [];
this.front = null;
this.back = null;
}
isEmpty() {
return this.items.length == 0;
}
getFront() {
if (this.items.length != 0) {
return this.items[0];
} else
return null;
}
size() {
return this.items.length;
}
enqueue(element) {
this.items.push(element);
}
dequeue() {
if (this.items.length == 0) {
return null;
} else {
return this.items.shift();
}
}
}Code language: JavaScript (javascript)Chìa khóa là tạo các số nhị phân liên tiếp bằng cách thêm 0 và 1 vào các số nhị phân trước đó. Làm rõ,
- 10 và 11 có thể được tạo nếu 0 và 1 được nối với 1.
- 100 và 101 được tạo nếu 0 và 1 được nối với 10.
Khi chúng ta tạo một số nhị phân, nó sẽ được xếp vào hàng đợi để các số nhị phân mới có thể được tạo ra nếu chúng ta thêm 0 và 1 khi số đó sẽ được xếp vào hàng đợi.
Vì một hàng đợi tuân theo thuộc tính First-In First-Out , nên các số nhị phân xếp hàng đợi được định vị lại để mảng kết quả chính xác về mặt toán học.
Nhìn vào đoạn mã trên. Trên dòng 7, 1 được xếp hàng. Để tạo chuỗi số nhị phân, một số được định giá lại và được lưu trữ trong mảng result. Trên dòng 11-12, chúng tôi thêm vào 0và 1để tạo ra các số tiếp theo.
Những con số mới đó cũng được xếp vào hàng 14-15. Hàng đợi sẽ nhận các giá trị số nguyên, vì vậy nó chuyển đổi chuỗi thành số nguyên khi nó được xếp vào hàng đợi.
Độ phức tạp về thời gian của giải pháp này là O(n)O(n) vì các phép toán thời gian không đổi được thực hiện trong n lần.
Danh sách được Liên kết: Đảo ngược một danh sách được liên kết
Câu lệnh vấn đề: Viết reversehàm lấy một danh sách liên kết đơn lẻ và đảo ngược vị trí của nó.
Đầu vào: một danh sách được liên kết đơn lẻ
LinkedList = 0->1->2->3-4Đầu ra: một danh sách liên kết ngược
LinkedList = 4->3->2->1->0Cách dễ nhất để giải quyết vấn đề này là sử dụng thao tác con trỏ lặp đi lặp lại.
"use strict";
const LinkedList = require('./LinkedList.js');
const Node = require('./Node.js');
//Access HeadNode => list.getHead()
//Set the value of HeadNode => list.getHead()
//Check if list is empty => list.isEmpty()
//Insert at head => list.insertAtHead(value)
//Delete at head => list.deleteAtHead()
//Insert at tail => list.insertAtTail(value)
//Search for element => list.search(value)
//Delete by value => list.deleteVal(value)
//Node class { data ; Node nextElement;}
function reverse(list) {
let previousNode = null;
let currentNode = list.getHead(); // The current node
let nextNode = null; // The next node in the list
//Reversal
while (currentNode != null) {
nextNode = currentNode.nextElement;
currentNode.nextElement = previousNode;
previousNode = currentNode;
currentNode = nextNode;
}
//Set the last element as the new head node
list.setHead(previousNode);
}
let list = new LinkedList();
list.insertAtHead(4);
list.insertAtHead(9);
list.insertAtHead(6);
list.insertAtHead(1);
list.insertAtHead(0);
list.printList();
reverse(list);
list.printList();Code language: JavaScript (javascript)"use strict";
const Node = require('./Node.js');
module.exports = class LinkedList {
constructor() {
this.head = null;
}
//Insertion At Head
insertAtHead(newData) {
let tempNode = new Node(newData);
tempNode.nextElement = this.head;
this.head = tempNode;
return this; //returning the updated list
}
isEmpty() {
return (this.head == null);
}
//function to print the linked list
printList() {
if (this.isEmpty()) {
console.log("Empty List");
return false;
} else {
let temp = this.head;
while (temp != null) {
process.stdout.write(String(temp.data));
process.stdout.write(" -> ");
temp = temp.nextElement;
}
console.log("null");
return true;
}
}
getHead() {
return this.head;
}
setHead(newHead) {
this.head = newHead;
return this;
}
getListStr() {
if (this.isEmpty()) {
console.log("Empty List");
return "null";
} else {
let st = "";
let temp = this.head
while (temp != null) {
st += String(temp.data);
st += " -> ";
temp = temp.nextElement;
}
st += "null";
return st;
}
}
insertAtTail(newData) {
//Creating a new Node with data as newData
let node = new Node(newData);
//check for case when list is empty
if (this.isEmpty()) {
//Needs to Insert the new node at Head
this.head = node;
return this;
}
//Start from head
let currentNode = this.head;
//Iterate to the last element
while (currentNode.nextElement != null) {
currentNode = currentNode.nextElement;
}
//Make new node the nextElement of last node of list
currentNode.nextElement = node;
return this;
}
search(value) {
//Start from the first element
let currentNode = this.head;
//Traverse the list until you find the value or reach the end
while (currentNode != null) {
if (currentNode.data == value) {
return true; //value found
}
currentNode = currentNode.nextElement
}
return false; //value not found
}
deleteAtHead() {
//if list is empty, do nothing
if (this.isEmpty()) {
return this;
}
//Get the head and first element of the list
let firstElement = this.head;
//If list is not empty, link head to the nextElement of firstElement
this.head = firstElement.nextElement;
return this;
}
deleteVal(value) {
let deleted = null; //True or False
//Write code here
//if list is empty return false
if (this.isEmpty()) {
return false;
}
//else get pointer to head
let currentNode = this.head;
// if first node's is the node to be deleted, delete it and return true
if (currentNode.data == value) {
this.head = currentNode.nextElement;
return true;
}
// else traverse the list
while (currentNode.nextElement != null) {
// if a node whose next node has the value as data, is found, delete it from the list and return true
if (currentNode.nextElement.data == value) {
currentNode.nextElement = currentNode.nextElement.nextElement;
return true;
}
currentNode = currentNode.nextElement;
}
//else node was not found, return false
deleted = false;
return deleted;
}
deleteAtTail() {
// check for the case when linked list is empty
if (this.isEmpty()) {
return this;
}
//if linked list is not empty, get the pointer to first node
let firstNode = this.head;
//check for the corner case when linked list has only one element
if (firstNode.nextElement == null) {
this.deleteAtHead();
return this;
}
//otherwise traverse to reach second last node
while (firstNode.nextElement.nextElement != null) {
firstNode = firstNode.nextElement;
}
//since you have reached second last node, just update its nextElement pointer to point at null, skipping the last node
firstNode.nextElement = null;
return this;
}
}Code language: JavaScript (javascript)"use strict";
module.exports = class Node {
constructor(data) {
this.data = data;
this.nextElement = null;
}
}Code language: JavaScript (javascript)Chúng tôi sử dụng một vòng lặp để lặp qua danh sách đầu vào. Đối với một currentnút, liên kết của nó với previousnút bị đảo ngược. sau đó, next lưu trữ nút tiếp theo trong danh sách. Hãy chia nhỏ điều đó theo từng dòng.
- Dòng 22- Lưu trữ nút
currentnextElementtrongnext - Dòng 23 – Đặt
currentnútnextElementthànhprevious - Dòng 24 – Tạo
currentnút mớipreviouscho lần lặp tiếp theo - Dòng 25 – Sử dụng
nextđể đi đến nút tiếp theo - Dòng 29 – Chúng tôi đặt lại
headcon trỏ để trỏ đến nút cuối cùng
Vì danh sách chỉ được duyệt một lần nên thuật toán chạy trong O (n) .
Cây: Tìm Giá trị Tối thiểu trong Cây Tìm kiếm Nhị phân
Tuyên bố vấn đề: Sử dụng findMin(root)hàm để tìm giá trị nhỏ nhất trong Cây tìm kiếm nhị phân.
Đầu vào: một nút gốc cho cây tìm kiếm nhị phân
bst = {
6 -> 4,9
4 -> 2,5
9 -> 8,12
12 -> 10,14
}
where parent -> leftChild,rightChildCode language: PHP (php)Đầu ra: giá trị số nguyên nhỏ nhất từ cây tìm kiếm nhị phân đó
2
Hãy xem một giải pháp dễ dàng cho vấn đề này.
Giải pháp: Lặp lại findMin( )
Giải pháp này bắt đầu bằng cách kiểm tra xem gốc có phải là không null. Nó trả về nullnếu vậy. Sau đó, nó di chuyển sang cây con bên trái và tiếp tục với nút con bên trái của mỗi nút cho đến khi đạt đến nút con ngoài cùng bên trái.
"use strict";
const BinarySearchTree = require('./BinarySearchTree.js');
const Node = require('./Node.js');
function findMin(rootNode)
{
if(rootNode == null)
return null;
else if(rootNode.leftChild == null)
return rootNode.val
else
return findMin(rootNode.leftChild)
}
var BST = new BinarySearchTree(6)
BST.insertBST(20)
BST.insertBST(-1)
console.log(findMin(BST.root)) Code language: JavaScript (javascript)"use strict";
const Node = require('./Node.js');
module.exports = class BinarySearchTree {
constructor(rootValue) {
this.root = new Node(rootValue);
}
insert(currentNode, newValue) {
if (currentNode === null) {
currentNode = new Node(newValue);
} else if (newValue < currentNode.val) {
currentNode.leftChild = this.insert(currentNode.leftChild, newValue);
} else {
currentNode.rightChild = this.insert(currentNode.rightChild, newValue);
}
return currentNode;
}
insertBST(newValue) {
if(this.root==null){
this.root=new Node(newValue);
return;
}
this.insert(this.root, newValue);
}
preOrderPrint(currentNode) {
if (currentNode !== null) {
console.log(currentNode.val);
this.preOrderPrint(currentNode.leftChild);
this.preOrderPrint(currentNode.rightChild);
}
}
inOrderPrint(currentNode) {
if (currentNode !== null) {
this.inOrderPrint(currentNode.leftChild);
console.log(currentNode.val);
this.inOrderPrint(currentNode.rightChild);
}
}
postOrderPrint(currentNode) {
if (currentNode !== null) {
this.postOrderPrint(currentNode.leftChild);
this.postOrderPrint(currentNode.rightChild);
console.log(currentNode.val);
}
}
search(currentNode, value) {
if (currentNode !== null) {
if (value == currentNode.val) {
return currentNode;
} else if (value < currentNode.val) {
return this.search(currentNode.leftChild, value)
} else {
return this.search(currentNode.rightChild, value)
}
} else {
return null;
}
}
searchBST(value) {
return this.search(this.root, value);
}
delete(currentNode, value) {
if (currentNode == null) {
return false;
}
var parentNode;
while (currentNode && (currentNode.val != value)) {
parentNode = currentNode;
if (value < currentNode.val) {
currentNode = currentNode.leftChild;
} else {
currentNode = currentNode.rightChild;
}
}
if (currentNode === null) {
return false;
} else if (currentNode.leftChild == null && currentNode.rightChild == null) {
if(currentNode.val==this.root.val){
this.root=null;
return true;
}
else if (currentNode.val < parentNode.val) {
parentNode.leftChild = null;
return true;
} else {
parentNode.rightChild = null;
return true;
}
} else if (currentNode.rightChild == null) {
if(currentNode.val==this.root.val){
this.root=currentNode.leftChild;
return true;
}
else if (currentNode.leftChild.val < parentNode.val) {
parentNode.leftChild = currentNode.leftChild;
return true;
} else {
parentNode.rightChild = currentNode.leftChild;
return true;
}
} else if (currentNode.leftChild == null) {
if(currentNode.val==this.root.val){
this.root = currentNode.rightChild;
return true;
}
else if (currentNode.rightChild.val < parentNode.val) {
parentNode.leftChild = currentNode.rightChild;
return true;
} else {
parentNode.rightChild = currentNode.rightChild;
return true;
}
} else {
var minRight = currentNode.rightChild;
while (minRight.leftChild !== null) {
minRight = minRight.leftChild;
}
var temp=minRight.val;
this.delete(this.root, minRight.val);
currentNode.val = temp;
return true;
}
}
}
Code language: JavaScript (javascript)"use strict";
module.exports = class Node {
constructor(value) {
this.val = value;
this.leftChild = null;
this.rightChild = null;
}
}Code language: JavaScript (javascript)Biểu đồ: Xóa cạnh
Câu lệnh vấn đề: Thực hiện hàm removeEdge để lấy nguồn và đích làm đối số. Nó sẽ phát hiện xem có tồn tại một cạnh nào giữa chúng hay không.
Đầu vào: Biểu đồ, nguồn và đích
Đầu ra: Một đồ thị có cạnh giữa nguồn và đích bị loại bỏ.
removeEdge(graph, 2, 3)
Giải pháp cho vấn đề này khá đơn giản: chúng tôi sử dụng Lập chỉ mục và xóa.
"use strict";
const LinkedList = require('./LinkedList.js');
const Node = require('./Node.js');
const Graph = require('./Graph.js');
function removeEdge(graph, source, dest){
if(graph.list.length == 0){
return graph;
}
if(source >= graph.list.length || source < 0){
return graph;
}
if(dest >= graph.list.length || dest < 0){
return graph;
}
graph.list[source].deleteVal(dest);
return graph;
}
let g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(4, 0);
console.log("Before removing edge")
g.printGraph();
removeEdge(g, 1, 3);
console.log("\nAfter removing edge")
g.printGraph();Code language: JavaScript (javascript)"use strict";
const LinkedList = require('./LinkedList.js');
const Node = require('./Node.js');
module.exports = class Graph {
constructor(vertices) {
this.vertices = vertices;
this.list = [];
var it;
for (it = 0; it < vertices; it++) {
let temp = new LinkedList();
this.list.push(temp);
}
}
addEdge(source, destination) {
if (source < this.vertices && destination < this.vertices)
this.list[source].insertAtHead(destination);
return this;
}
printGraph() {
console.log(">>Adjacency List of Directed Graph<<");
var i;
for (i = 0; i < this.list.length; i++) {
process.stdout.write("|" + String(i) + "| => ");
let temp = this.list[i].getHead();
while (temp != null) {
process.stdout.write("[" + String(temp.data) + "] -> ");
temp = temp.nextElement;
}
console.log("null ");
}
}
strGraph() {
let str = "";
var i;
for (i = 0; i < this.list.length; i++) {
str = str + "|" + String(i) + "| => ";
let temp = this.list[i].getHead();
while (temp != null) {
str += ("[" + String(temp.data) + "] -> ");
temp = temp.nextElement;
}
str += "null ";
}
return str;
}
}Code language: JavaScript (javascript)"use strict";
const Node = require('./Node.js');
module.exports = class LinkedList {
constructor() {
this.head = null;
}
//Insertion At Head
insertAtHead(newData) {
let tempNode = new Node(newData);
tempNode.nextElement = this.head;
this.head = tempNode;
return this; //returning the updated list
}
isEmpty() {
return (this.head == null);
}
//function to print the linked list
printList() {
if (this.isEmpty()) {
console.log("Empty List");
return false;
} else {
let temp = this.head;
while (temp != null) {
process.stdout.write(String(temp.data));
process.stdout.write(" -> ");
temp = temp.nextElement;
}
console.log("null");
return true;
}
}
getHead() {
return this.head;
}
setHead(newHead) {
this.head = newHead;
return this;
}
getListStr() {
if (this.isEmpty()) {
console.log("Empty List");
return "null";
} else {
let st = "";
let temp = this.head
while (temp != null) {
st += String(temp.data);
st += " -> ";
temp = temp.nextElement;
}
st += "null";
return st;
}
}
insertAtTail(newData) {
//Creating a new Node with data as newData
let node = new Node(newData);
//check for case when list is empty
if (this.isEmpty()) {
//Needs to Insert the new node at Head
this.head = node;
return this;
}
//Start from head
let currentNode = this.head;
//Iterate to the last element
while (currentNode.nextElement != null) {
currentNode = currentNode.nextElement;
}
//Make new node the nextElement of last node of list
currentNode.nextElement = node;
return this;
}
search(value) {
//Start from the first element
let currentNode = this.head;
//Traverse the list until you find the value or reach the end
while (currentNode != null) {
if (currentNode.data == value) {
return true; //value found
}
currentNode = currentNode.nextElement
}
return false; //value not found
}
deleteAtHead() {
//if list is empty, do nothing
if (this.isEmpty()) {
return this;
}
//Get the head and first element of the list
let firstElement = this.head;
//If list is not empty, link head to the nextElement of firstElement
this.head = firstElement.nextElement;
return this;
}
deleteVal(value) {
let deleted = null; //True or False
//Write code here
//if list is empty return false
if (this.isEmpty()) {
return false;
}
//else get pointer to head
let currentNode = this.head;
// if first node's is the node to be deleted, delete it and return true
if (currentNode.data == value) {
this.head = currentNode.nextElement;
return true;
}
// else traverse the list
while (currentNode.nextElement != null) {
// if a node whose next node has the value as data, is found, delete it from the list and return true
if (currentNode.nextElement.data == value) {
currentNode.nextElement = currentNode.nextElement.nextElement;
return true;
}
currentNode = currentNode.nextElement;
}
//else node was not found, return false
deleted = false;
return deleted;
}
deleteAtTail() {
// check for the case when linked list is empty
if (this.isEmpty()) {
return this;
}
//if linked list is not empty, get the pointer to first node
let firstNode = this.head;
//check for the corner case when linked list has only one element
if (firstNode.nextElement == null) {
this.deleteAtHead();
return this;
}
//otherwise traverse to reach second last node
while (firstNode.nextElement.nextElement != null) {
firstNode = firstNode.nextElement;
}
//since you have reached second last node, just update its nextElement pointer to point at null, skipping the last node
firstNode.nextElement = null;
return this;
}
}Code language: JavaScript (javascript)"use strict";
module.exports = class Node {
constructor(data) {
this.data = data;
this.nextElement = null;
}
}Code language: JavaScript (javascript)Vì các đỉnh của chúng ta được lưu trữ trong một mảng, chúng ta có thể truy cập vào sourcedanh sách được liên kết. Sau đó, chúng tôi gọi deletehàm cho danh sách được liên kết. Độ phức tạp về thời gian cho giải pháp này là O (E) vì chúng ta có thể phải đi qua các cạnh E.
Bảng băm: Chuyển đổi Max-Heap thành Min-Heap
Tuyên bố vấn đề: Thực hiện chức năng convertMax(maxHeap)chuyển đổi max-heap nhị phân thành min-heap nhị phân. maxHeapphải là một mảng trong maxHeapđịnh dạng, tức là phần cha lớn hơn phần con của nó.
Đầu vào: a Max-Heap
maxHeap = [9,4,7,1,-2,6,5]
Đầu ra: trả về mảng đã chuyển đổi
result = [-2,1,5,9,4,6,7]
Để giải quyết vấn đề này, chúng ta phải tối thiểu hóa tất cả các nút cha.
function minHeapify(heap, index) {
var left = index * 2;
var right = (index * 2) + 1;
var smallest = index;
if ((heap.length > left) && (heap[smallest] > heap[left])) {
smallest = left
}
if ((heap.length > right) && (heap[smallest] > heap[right]))
smallest = right
if (smallest != index) {
var tmp = heap[smallest]
heap[smallest] = heap[index]
heap[index] = tmp
minHeapify(heap, smallest)
}
return heap;
}
function convertMax(maxHeap) {
for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--)
maxHeap = minHeapify(maxHeap, i)
return maxHeap
}
var maxHeap = [9,4,7,1,-2,6,5]
console.log(convertMax(maxHeap))Code language: JavaScript (javascript)Chúng tôi coi maxHeapnó là một mảng thông thường và sắp xếp lại nó để thể hiện chính xác một min-heap. Bạn có thể thấy điều này được thực hiện trong đoạn mã trên. Sau convertMax()đó, hàm khôi phục thuộc tính heap trên tất cả các nút từ nút cha thấp nhất bằng cách gọi minHeapify()hàm. Liên quan đến độ phức tạp về thời gian, giải pháp này cần thời gian O(nlog(n))O(nlog (n)) .
Kết luận
Rõ ràng có rất nhiều thứ để học khi nói đến cấu trúc dữ liệu trong JavaScript. Thực hành thực hành là chìa khóa để thành công với các cuộc phỏng vấn viết mã. Điều quan trọng là phải vượt ra ngoài lý thuyết và áp dụng những khái niệm này vào các giải pháp trong thế giới thực.
Chúc các bạn học tập vui vẻ!
Cảm ơn bạn đã theo dõi bài viết!
Các bạn có thể tham khảo các bài viết hay về JavaScript tại đây.
Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.
TỔNG HỢP TÀI LIỆU HỌC LẬP TRÌNH CƠ BẢN CHO NGƯỜI MỚI BẮT ĐẦU
KHOÁ HỌC BOOTCAMP JAVA/JAVASCRIPT/PHP TRỞ THÀNH LẬP TRÌNH VIÊN TRONG 5-6 THÁNG
