Bản đồ tần suất JavaScript

ví dụ

Trả về một mảng mới với căn bậc hai của tất cả các giá trị phần tử

const số = [4, 9, 16, 25];
const newArr = số. bản đồ (Toán. sqrt)

Nhân tất cả các giá trị trong một mảng với 10

const số = [65, 44, 12, 4];
const newArr = số. bản đồ(myFunction)

function myFunction(num) {
  return num * 10;
}

Thêm ví dụ bên dưới

Định nghĩa và cách sử dụng

map() tạo một mảng mới từ việc gọi một hàm cho mọi phần tử mảng

map() gọi một hàm một lần cho mỗi phần tử trong một mảng

map() không thực thi chức năng cho các phần tử trống

map() không thay đổi mảng ban đầu

cú pháp

mảng. map(function(currentValue, index, arr), thisValue)

Thông số

Giá trị trả về

Thêm ví dụ

Lấy tên đầy đủ cho mỗi người

const people = [
  {firstname. "Malcolm", họ. "Reynolds"},
  {firstname. "Kaylee", họ. "Frye"},
  {firstname. "Jayne", họ. "Cobb"}
];

người. bản đồ (getFullName);

function getFullName(item) {
  return [item. tên, mục. họ]. tham gia(" ");
}

Hỗ trợ trình duyệt

map() là một tính năng ECMAScript5 (ES5)

ES5 (JavaScript 2009) được hỗ trợ đầy đủ trên mọi trình duyệt

Vấn đề này xuất phát từ LeetCode. Không thiếu các vấn đề thực hành ngoài kia, nhưng LeetCode là một trong những nền tảng phổ biến nhất để trau dồi kỹ năng thiết kế thuật toán của bạn. Với các vấn đề thực tế, giải pháp và cơ sở người dùng lành mạnh để thảo luận về các vấn đề, LeetCode là một nguồn tài nguyên tuyệt vời

Giải pháp vấn đề

Mấu chốt của vấn đề này là ánh xạ các ký tự theo tần suất xuất hiện của chúng trong chuỗi. Bất cứ khi nào bạn gặp phải vấn đề trong đó từ “tần suất” được sử dụng, rất có thể bản đồ sẽ là công cụ phù hợp cho công việc

Sau khi tất cả các ký tự được ánh xạ, chúng ta cần ngoại suy các ký tự riêng lẻ thành các chuỗi chứa ký tự được lặp lại với số lần thích hợp. Sau đó, chúng ta có thể sắp xếp các chuỗi đó và nối chúng thành một chuỗi cuối cùng

Hãy chia logic thành các phần nhỏ hơn, dễ hiểu hơn

Đếm ký tự

Thay vì cố gắng nhóm và sắp xếp các ký tự này tại chỗ một cách không hiệu quả, thay vào đó, việc đếm tần suất ký tự và sau đó tạo các nhóm ký tự mà chúng ta muốn xem sau sẽ dễ dàng hơn nhiều. Cấu trúc dữ liệu bản đồ đặc biệt hữu ích ở đây vì nó được triển khai theo cách cho phép chúng ta tra cứu thời gian liên tục (i. e. O(1)). Vì vậy, bằng cách sử dụng bản đồ, khi chúng tôi muốn thêm vào kiểm đếm của một ký tự, chúng tôi sẽ tra cứu nhanh để kiểm tra xem chúng tôi đã có ký tự đó trong bản đồ chưa

Vì vậy, chúng tôi có thể lặp lại các ký tự của mình và kiểm tra xem chúng đã tồn tại trong bản đồ của chúng tôi chưa. Nếu đúng như vậy, chúng tôi sẽ tăng số lần kiểm đếm cho ký tự đó lên 1 và nếu không, chúng tôi sẽ thêm ký tự đó vào bản đồ với giá trị kiểm đếm ban đầu là 1

Ngoại suy và Sắp xếp

Ngoại suy ký tự thành một chuỗi bao gồm ký tự được lặp lại theo tần số của nó có thể là phần riêng của nó trong thuật toán này, nhưng hầu hết các ngôn ngữ lập trình trưởng thành đều có cách khai báo tích hợp sẵn để thực hiện việc này. Trong JavaScript, chúng ta có thể sử dụng String.prototype.repeat để thực hiện điều này

Với logic ngoại suy đã được xử lý, logic của chúng ta như sau. lặp qua bản đồ, ngoại suy ký tự và đẩy chuỗi ngoại suy đó vào cấu trúc dữ liệu có thể sắp xếp, sau đó sắp xếp. Chìa khóa ở đây là sử dụng cấu trúc dữ liệu dễ sắp xếp. Trong JavaScript, các mảng có một phương thức gốc Array.prototype.sort có thể được sử dụng để sắp xếp các mục một cách khai báo, vì vậy chúng tôi sẽ sử dụng một phương thức để lưu trữ các chuỗi ngoại suy của mình

tham gia

Sau khi chúng tôi đã sắp xếp các chuỗi của mình, chúng tôi chỉ cần nối chúng lại với nhau thành chuỗi kết quả cuối cùng của chúng tôi. Một lần nữa, JavaScript có một phương thức nguyên mẫu khai báo có tên là map()0 sẽ làm điều này cho chúng ta. Nếu bạn muốn tự thực hiện logic nối, bạn chỉ cần lặp qua mảng và nối từng chuỗi thành chuỗi kết quả

Triển khai JavaScript

Bây giờ chúng ta đã có mô hình tinh thần và thuật toán của mình, việc dịch nó thành mã là khá đơn giản. Hãy xem triển khai JavaScript

Như bạn có thể thấy, logic ánh xạ được triển khai trên các dòng từ 2 đến 7. Chúng tôi tạo một đối tượng trống để hoạt động như bản đồ của mình, sử dụng vòng lặp map()1 để lặp qua chuỗi của chúng tôi và trên mỗi lần lặp, chúng tôi sử dụng phép gán thuộc tính đối tượng cơ bản để cập nhật tần số ký tự của mình

Phép ngoại suy ký tự xảy ra trên các dòng từ 9 đến 14. Bạn sẽ nhận thấy rằng chúng tôi sử dụng vòng lặp map()2 để lặp qua đối tượng của mình và trên mỗi lần lặp, chúng tôi ngoại suy chuỗi của mình bằng phương thức String.prototype.repeat và chúng tôi đẩy nó đến cuối mảng của mình. Sau đó, chúng tôi sử dụng Array.prototype.sort để sắp xếp các chuỗi theo độ dài

Cuối cùng, chúng tôi sử dụng map()0 để kết hợp mảng chuỗi của chúng tôi thành một chuỗi cuối cùng trên dòng 17

Hiệu quả

Một thuật toán chỉ tốt khi hiệu quả của nó. Một thuật toán không hiệu quả chắc chắn tốt hơn là không có gì trong một cuộc phỏng vấn, nhưng thông thường, cách tiếp cận “vũ phu” sẽ không hiệu quả. Vì vậy, điều quan trọng là phải hiểu cách tính toán hiệu quả của thuật toán của bạn và cách truyền đạt thông tin đó cho người khác

Hiệu quả của thuật toán thường được mô tả bằng Ký hiệu Big O và được sử dụng để xác định cả độ phức tạp thời gian và độ phức tạp không gian

Thời gian phức tạp

Đối với bài toán của chúng ta, ánh xạ là tuyến tính (i. e. map()6) và phép nối cũng vậy, nhưng nút cổ chai ở đây là việc sắp xếp. Hiệu quả sắp xếp phụ thuộc vào việc triển khai thời gian chạy JavaScript. Chrome sử dụng công cụ V8, chính công cụ này triển khai Array.prototype.sort bằng cách sử dụng thuật toán Timsort, trung bình thuật toán này tạo ra độ phức tạp về thời gian là String.prototype.repeat1). Bởi vì các hoạt động này là tuần tự và không lồng nhau, nên độ phức tạp lớn nhất sẽ lấn át các hoạt động khác khi String.prototype.repeat2 (số lượng mục trong cấu trúc dữ liệu) tiến tới vô cùng

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

Vốn dĩ, phép ánh xạ chiếm không gian tuyến tính (i. e. map()6) bởi vì, đối với mỗi ký tự trong chuỗi của chúng tôi, chúng tôi đang phân bổ một đoạn bộ nhớ trong bản đồ của chúng tôi. Trung bình, bộ nhớ được sử dụng trong ánh xạ sẽ ít hơn String.prototype.repeat2 vì chúng ta thường có các ký tự lặp lại, nhưng chúng ta thường chỉ quan tâm đến các tình huống xấu nhất trong các bài toán thuật toán. Phần ngoại suy cũng là tuyến tính vì chúng tôi đang thêm một mục vào mảng của mình cho mỗi mục trong bản đồ của chúng tôi. Đây là hai phần duy nhất của hoạt động tiêu thụ bộ nhớ bổ sung và vì cả hai đều tuyến tính nên toàn bộ thuật toán được coi là có tuyến tính (i. e. map()6) độ phức tạp của không gian

Phần kết luận

Các vấn đề về thuật toán là về việc nhận ra khi nào nên sử dụng các mẫu logic cụ thể. Để làm như vậy, bạn cần làm quen với các mẫu và sự kết hợp khác nhau của các mẫu ngoài kia

Ánh xạ các ký tự theo tần suất xuất hiện của chúng là một mẫu phổ biến mà bạn nên làm quen với. Khi bạn hiểu đầy đủ chiến lược và hiệu quả đằng sau nó, bạn sẽ bắt đầu nhận ra các lĩnh vực khác mà nó có thể được sử dụng đúng cách

Michael Stromberg

Michael có nền tảng đa dạng về công nghệ phần mềm, kỹ thuật cơ khí, kinh tế và quản lý. Sau một sự nghiệp thành công trong lĩnh vực kỹ thuật cơ khí, Michael quyết định trở thành một kỹ sư phần mềm và tham dự trại huấn luyện lập trình Hack Reactor. Michael thích viết về kinh nghiệm của mình và giúp đỡ những người khác bắt đầu hành trình phát triển phần mềm của họ

Làm cách nào để tạo bản đồ tần suất trong JavaScript?

Làm cách nào để tìm tần suất của chuỗi trong JavaScript?