Hướng dẫn equal levels two signals hackerrank solution javascript - cấp bằng nhau hai tín hiệu hackerrank giải pháp javascript

Là một sinh viên tốt nghiệp mã hóa gần đây, tôi nhanh chóng nhận ra rằng tôi cần phải thoải mái hơn với các cấu trúc dữ liệu và thuật toán nếu tôi muốn trao đổi dịch vụ của mình với tư cách là một kỹ sư để kiếm tiền. Vì vậy, tôi bắt đầu luyện tập. Hàng ngày (gần như- hãy để có thể là playoffs thực tế!). Và thực hành nhiều hơn. Bài đăng trên blog này các tính năng và giải thích giải pháp của tôi cho Hackerrank, cân bằng vấn đề mảng.

Vấn đề nói rằng chúng ta sẽ nhận được một mảng làm đầu vào (ví dụ: [3,3,2,1,3]) và chúng ta cần tìm ra mức độ xóa thấp nhất mà chúng ta cần thực hiện để tất cả các yếu tố giống nhau. Trong trường hợp này, đó sẽ là 2, vì việc xóa 2 và 1 trong mảng này sẽ khiến chúng ta có [3, 3, 3] - tất cả đều bằng nhau. Làm thế nào để chúng ta làm điều này với mã?

SPOILER ALERT - Giải pháp dưới đây!

function equalizeArray(arr) {
  let arrObj = {};
  let maxCount = 0;for (let num of arr) {
    arrObj[num] = arrObj[num] + 1 || 1;
  }for (let value in arrObj) {
    if (arrObj[value] > maxCount) {
      maxCount = arrObj[value];
    }
  }return (arr.length - maxCount);}

Gần đây tôi đã học được một cách tuyệt vời để giải mã các vấn đề thuật toán:

1. Vẽ nó ra; và làm nó theo cách thủ công như một con người
2. Thực hiện các bước đó và viết nó ra, hoặc giả mã nó thành các bước
3. Sau đó bắt đầu dịch nó thành mã.

Hãy để tiếp cận với cách tiếp cận này với vấn đề này.

Bằng cách nhìn vào mảng [3,3,2,1,3] như một con người, tôi có thể thấy ngay một số số được lặp lại. Vì vậy, sẽ có ý nghĩa để loại bỏ các số khác với số lặp đi lặp lại, để làm cho tất cả giống nhau. Vì vậy, hãy để cho phép máy tính theo dõi số lần mỗi số hiển thị trong mảng. Đó là những gì mã này làm:

let arrObj = {};
for (let num of arr) {
    arrObj[num] = arrObj[num] + 1 || 1;
  }

Trước tiên chúng tôi khởi tạo một bản đồ băm trống. Sau đó, đối với mỗi số hiển thị trong mảng, chúng tôi đặt một khóa trong bản đồ băm đó và tăng 1 (nếu mã đã thấy số đó trước đó) hoặc đặt nó thành một (nếu mã chưa bao giờ thấy số đó trước).

Ở cuối phần đó, chúng tôi có một đối tượng trông như thế này:

arrObj = {
  1:1,
  2:1,
  3:3 
}

Tiếp theo, tôi cần loại bỏ các số hiển thị ít nhất. làm sao chúng ta làm việc đó bây giờ? Chúng ta cần cho biết mã số nào trong mảng gốc hiển thị nhiều nhất. Nói cách khác, khóa nào trong đối tượng bản đồ băm của chúng tôi có giá trị lớn nhất. Đó là những gì mã này làm:key in our hash map object has the largest value. That’s what this piece of code does:

let maxCount = 0;
for (let value in arrObj) {
    if (arrObj[value] > maxCount) {
      maxCount = arrObj[value];
    }
  }

Điều này lặp lại thông qua bản đồ băm Arrobj mà chúng tôi đã tạo và xem xét từng giá trị. Nếu giá trị đó lớn hơn giá trị của MaxCount, lúc đầu là 0, thì nó sẽ đặt MaxCount thành số đó. Vì số đầu tiên mà nó thấy là 1 và 1 lớn hơn 0, tối đa hiện được đặt thành 1. Sau đó, nó nhìn vào 2. Vì 1 không lớn hơn 1, nên nó bỏ qua nó. Trên lần lặp cuối cùng, nó nhìn vào 3. 3 chắc chắn lớn hơn một, vì vậy ở cuối Maxcount được đặt thành 3.

Bây giờ, tất cả những gì chúng ta phải làm là trừ MaxCount, số lần số lần thường xuyên nhất xuất hiện, từ tổng số phần tử mà mảng có, vì đây sẽ là số lượng xóa tối thiểu cần thiết để làm cho tất cả các số giống nhau. Và tất nhiên, don không quên trả lại số. Đó là những gì mã này làm

________ 4 đó là tất cả những gì cô ấy đã viết

Cảm ơn vì đã đọc!

Và hãy nhớ: grit> tài năng.

Thật là một thử thách tốt đẹp! Vì vậy, cuối cùng, giải pháp sẽ trông giống như một sự tầm thường đơn giản cho vòng lặp, trong độ phức tạp và không gian không đổi. Những người khác cũng đã tìm ra nó, nhưng mã không có lời giải thích là rất khó hiểu. Tôi sẽ cố gắng giải thích những gì đang xảy ra.

Hãy lấy một ví dụ:

1 1 5 5 5 5 7 9 9. Nó được sắp xếp để thuận tiện, nhưng không cần thiết.

Tại bất kỳ thời điểm nào, bạn chỉ quan tâm đến sự khác biệt giữa mỗi giá trị và mức tối thiểu. Vì vậy, chúng tôi có thể rebase/viết lại như: 0 0 4 4 4 4 6 8 8 8

Bất cứ khi nào bạn thực hiện Opperation (OP), thêm giá trị 1 2 hoặc 5, bạn thường muốn tăng tất cả các giá trị tối thiểu trong mảng . Nếu bạn cố gắng thực sự làm điều này trên giấy tờ, bạn sẽ nhận ra rằng điều này tương đương với việc trừ 1,2 hoặc 5 từ một giá trị duy nhất trong mảng. Ví dụ: chúng ta hãy thêm 2 vào mọi thứ ngoại trừ 4 đầu tiên (ELEM thứ 3):

0 0 4 4 4 4 6 8 8 -> Thêm 2 -> 2 2 4 6 6 6 8 10 10 -> REBASE (trừ mức tối thiểu mới, 2, từ tất cả) -> 0 0 2 4 4 4 6 8 8 8 8 8 8

Kết quả cuối cùng về các điều khoản khác nhau, sau Rebase, là chúng tôi thực sự đã loại bỏ 2 khỏi 4 (phần tử thứ 3). Vì vậy, một OP thực sự là hoạt động của việc trừ 1 2 hoặc 5 từ bất kỳ giá trị không có nào trong mảng được phục hồi.

Dựa trên những điều trên, bạn có thể nghĩ rằng, điều này là tuyệt vời, bây giờ chúng ta chỉ cần lấy tất cả các giá trị và giảm tất cả thành 0 một cách riêng biệt, thông qua một số bước tối thiểu. Đó không hoàn toàn như vậy mặc dù. Chúng ta có thể giảm tất cả chúng một cách riêng biệt ở một mức độ nào đó, bằng cách liên tục trừ tất cả các 5 mà chúng ta có thể (trong khi đếm OPS). Nhưng chúng ta cần đối xử với phần còn lại với sự chăm sóc nhiều hơn. Ví dụ ban đầu của chúng tôi, chúng tôi sẽ kết thúc với những điều sau đây, sau khi trừ tất cả 5s (3 OP cho đến nay):

0 0 4 4 4 4 1 3 3. Bây giờ, chúng ta có thể giảm từng cái một, trong khi bỏ qua những gì xung quanh chúng và chúng ta sẽ nhận được thêm 13 ops (3s và 4s yêu cầu 2 op mỗi và 1 chỉ một op ).

Nhưng có một cách tốt hơn trong trường hợp này, một "thủ thuật": Đầu tiên thêm 1 vào mọi thứ ngoại trừ 0 đầu tiên:

0, Nhưng mặt khác, bây giờ chúng ta có một số thứ bổ sung để dọn dẹp: ví dụ, 0 thứ hai hiện là 1 và sẽ yêu cầu 1 OP bổ sung. Tuy nhiên, nhìn chung, bây giờ chúng ta sẽ cần tổng cộng 11 OP để đưa tất cả đến 0 này. Khi chọn xem có nên thực hiện thủ thuật này không (thêm vào tất cả ngoại trừ tối thiểu), chúng ta cần xem xét các OP bổ sung sẽ được yêu cầu như thế nào so với lợi ích được thêm vào. Ví dụ: so sánh trình tự 0 0 0 4 4 với 0 0 4 4 4. Thủ thuật trên chỉ được trả trong chuỗi thứ hai. Cùng một "thủ thuật" này cũng áp dụng cho 3 giây, bằng cách thêm 2 vào mọi thứ.

Vì vậy, khi nào nên thực hiện "thủ thuật" và khi không ?, Đó là câu hỏi. Tin tốt là chúng ta có thể đưa ra các công thức để tính toán số lượng OP cho từng tình huống và chúng ta chỉ cần biết tần suất của từng giá trị, sau khi trừ tất cả 5s chúng ta có thể. Sau đó, chúng ta chỉ có thể lấy tối thiểu tất cả các tùy chọn. Chúng tôi xây dựng một mảng tần số f, trong đó f [i] = số lượng các phần tử trong mảng được phục hồi, bằng i (sau modulo 5). Đối với ví dụ trên, f = [2,1,0,2,4]. Vì vậy, ví dụ F [4] cho biết chúng tôi đã có bao nhiêu 4.

Để đưa ra các công thức cho số lượng OP, bạn có thể cố gắng xem xét các tùy chọn mà bạn có và bạn sẽ đến như sau.

a) Giảm 3s và 4s bằng cách trừ đi từ mỗi cá nhân với 2 OP. 1s và 2s sẽ chỉ yêu cầu 1 bước mỗi bước:

F [1] + F [2] + 2*F [3] + 2*F [4]

b) Giảm 3S bằng cách chuyển chúng thành 5s trước. Thêm 2 vào tất cả ngoại trừ một trong các số không (đây là 1 op). Tất cả các số không (trừ một) sẽ trở thành 2 giây và giờ đây sẽ cần 1 op mỗi cái để trở thành số không (đây là f [0] - 1 ops). 1s sẽ trở thành 3S, hai op mỗi (2*f [1] ops). 2s sẽ trở thành 4S, 2 op mỗi. 3s sẽ trở thành 5s, 1 op mỗi. 4S sẽ trở thành 6s, 2 op mỗi. vì thế:

1 + f [0] - 1 + 2*f [1] + 2*f [2] + f [3] + 2*f [4]

c) Tương tự như ở trên, giảm 4S bằng cách thêm 1 vào tất cả ngoại trừ một trong số các số không. Tất cả các số không khác sẽ trở thành 1s và sẽ cần f [0] - 1 ops. Điều khác biệt với phía trên bây giờ, là 1s sẽ trở thành 2 giây và sẽ chỉ cần một op mỗi (không phải hai). vì thế:

1 + f [0] - 1 + f [1] + 2*f [2] + 2*f [3] + f [4]

d) Bạn nên đặt câu hỏi liệu cũng có thể có sự kết hợp của B và C có thể mang lại số lượng OP nhỏ hơn. Có lẽ bạn có thể áp dụng "thủ thuật" cho cả 3S và 4S. Đây là một điều quan trọng để xem xét. Tôi sẽ làm hỏng nó và cho bạn biết rằng điều này không thể dẫn đến số lượng OP nhỏ hơn. Có một vài tình huống ở đây: D.1) Chúng tôi thêm 1 và 2 vào mọi thứ (ngoại trừ một số giá trị 0, đó là 2 OP) và sau đó chúng tôi loại bỏ mọi thứ ở cuối. Điều đó giống như thêm 3 vào mọi thứ. Tất cả các giá trị ban đầu bây giờ sẽ yêu cầu 2 OP (bao gồm 0 ban đầu), ngoại trừ 2S (chúng sẽ trở thành 5s). Nhưng 2s có thể được loại bỏ trong 1 OP dù sao! Vì vậy, sự kết hợp của "thủ thuật" này sẽ không bao giờ dẫn đến số lượng OP nhỏ hơn a). Nó sẽ yêu cầu OPS bổ sung cho 0 và 1 ban đầu. Công thức kết quả cho thấy điều này rõ ràng:

2 + 2*(f [0] - 1) + 2*f [1] + f [2] + 2*F [3] + 2*F [4]

D.2) Nhưng làm thế nào về việc chúng tôi thực hiện một "thủ thuật" trước tiên, chúng tôi loại bỏ một số giá trị kết quả, sau đó chúng tôi áp dụng thủ thuật khác và sau đó loại bỏ tất cả các giá trị còn lại. Điều này tương tự như ở trên, nhưng bây giờ chúng ta có hai giai đoạn loại bỏ, một giai đoạn sau mỗi "thủ thuật". Câu hỏi rộng hơn ở đây là: nếu chúng ta loại bỏ một số giá trị sau "thủ thuật" đầu tiên, thì điều này ít nhất có thể vượt trội hơn D.1) không? Những giá trị nào có thể là? Chúng ta thậm chí có thể tìm thấy bất kỳ ví dụ? Chà, chúng ta không thể: Lấy bất kỳ giá trị nào, nếu chúng ta loại bỏ nó trong Giai đoạn 1 (đó là 1 OP tốt nhất), chúng ta sẽ phải loại bỏ nó một lần nữa trong Giai đoạn 2 (đó là 1 OP khác tốt nhất và đó là 2 OP tốt nhất Tổng cộng), vì chúng tôi sẽ thêm một số giá trị vào nó khi chúng tôi áp dụng Trick 2 (điều gì, thêm 1 hoặc thêm 2, không quan trọng). Vì vậy, bất kỳ giá trị nào chúng tôi chọn để loại bỏ trong giai đoạn đầu tiên, chúng tôi sẽ cần ít nhất 2 ops để loại bỏ từng OPS. Điều đó sẽ không tốt hơn D.1), dù sao thì không tốt hơn a)