วันนี้ฉันพบคำถามอัลกอริทึมที่น่าสนใจมาก ต่อไปนี้เป็นคำอธิบายอัลกอริทึมซึ่งมาจากคำถามสัมภาษณ์บน Twitter
คำอธิบายอัลกอริทึมของ Twitter Puddles
ดูภาพก่อน
ตัวเลขในรูปด้านบนอธิบายไว้ตามเนื้อหาของอาร์เรย์ ในที่สุดความสูงของผนังจะถูกจำลองตามขนาดของแต่ละหมายเลขและผนังจะถูกสร้างขึ้น ถามคุณเมื่อฝนตกผนังนี้จะเต็มไปด้วยน้ำใน 1 เป็นหน่วยการนับ
นี่คือผนังหลังจากเติมน้ำ
หลังจากอ่านภาพด้านบนคุณรู้สึกว่ามันสนุกหรือไม่? อันที่จริงแล้วลองวิเคราะห์การใช้อัลกอริทึมสั้น ๆ ด้านล่าง
ในความเป็นจริงหลักการนี้ค่อนข้างง่ายมีประเด็นสำคัญสองสามข้อ:
1. ไม่มีน้ำด้านซ้ายและขวาแน่นอน
2. ความสูงของภาระน้ำขึ้นอยู่กับค่าต่ำสุดของค่าสูงสุดสองค่าที่ด้านซ้ายและขวาของตัวเอง
มาใช้ JS เพื่อนำไปใช้อย่างง่าย ๆ :
การคัดลอกรหัสมีดังนี้:
-
* คำนวณจำนวนน้ำที่สามารถติดตั้งบนผนังด้วยเงื่อนไขอาร์เรย์เป็นความสูง
* ตัวอย่างอาร์เรย์ [2,5,1,2,3,4,7,7,7,6,9]
-
ฟังก์ชั่น getwatercounts (arg) {
var i = 0,
j = 0,
นับ = 0;
// ทั้งรายการแรกและรายการสุดท้ายจะต้องได้รับการยกเว้น
สำหรับ (i = 1; i <arg.length - 1; i ++) {
var left = math.max.apply (null, arg.slice (0, i + 1));
var right = math.max.apply (null, arg.slice (i, arg.length));
var min = ซ้าย> = ขวา? ขวา: ซ้าย;
// ค่าสูงสุดของด้านซ้ายและขวาจะเหนือกว่า
// หากค่าปัจจุบันมากกว่าหรือเท่ากับค่านี้ให้ทำอะไรเลย
ถ้า (arg [i] <นาที) {
นับ += นาที - arg [i];
-
-
console.log (นับ);
-
GetwaterCounts ([2,5,1,2,3,4,7,7,7,6,9]); // 11
สรุป
ฮิฮิไม่ใช่การใช้งานที่ง่ายหรือไม่? ในความเป็นจริงตราบใดที่คุณยินดีที่จะคิดคุณสามารถใช้ JS เพื่อใช้สิ่งสนุก ๆ มากมาย