Đệ quy mảng javascript

Question

Tôi đã trải qua một vài lần thử mặc dù phương pháp của tôi dường như quay trở lại sớm sau khi chỉ vượt qua một cấp độ

Nội dung chính Show

Đệ quy là gì?
Cách suy nghĩ theo cách đệ quy
Chỉ số 0, Giá trị = 1
Chỉ số 1, Giá trị = 2
Chỉ mục 2, Giá trị = [ 3, 4 ]
Giải pháp cho vấn đề
Phần kết luận

nỗ lực mới nhất của tôi là

Có thể ai đó xin vui lòng chỉ cho tôi đi đúng hướng

function findType(col, id) {


                    for (i = 0; i < col.length; i++) {

                        if (col[i].id == id) {
                            return col[i];

                        }

                        if (col[i].children.length > 0) {
                           return findType(col[i].children, id);

                        }
                    }

                    return null;

                }

Tôi đang cố gắng tìm một đối tượng mà một id nhất định khớp với nhau, vì vậy việc tìm kiếm id 1 sẽ trả về toàn bộ đối tượng có tên Parent 1. Nếu tìm kiếm id 31 thì toàn bộ đối tượng có id 31 và tên Child 1 sẽ được trả về

Điều này sẽ dịch thành

var t = findType(collection, 1);

hoặc là

var t = findType(collection, 31);

Lưu ý rằng tôi muốn trợ giúp về giải pháp JavaScript thuần túy chứ không phải plugin hoặc thư viện khác. Mặc dù chúng có thể ổn định hơn, nhưng nó sẽ không giúp ích gì cho quá trình học tập. Thanks

You can not get collect sub array count when use the key on only one sub array in an array:

$a = array("a"=>"appple", b"=>array('a'=>array(1,2,3),'b'=>array(1,2,3))); $b = array("a"=>"appple", "b"=>array(array('a'=>array(1,2,3),'b'=>array(1,2,3)), array(1,2,3),'b'=>array(1,2,3)), array('a'=>array(1,2,3),'b'=>array(1,2,3))));

echo count($a['b']); // 2 NOT 1, expect 1 echo count($b['b']); // 3, expected

Tham chiếu JavaScript đóng vai trò là kho lưu trữ dữ kiện về ngôn ngữ JavaScript. Toàn bộ ngôn ngữ được mô tả chi tiết ở đây. Khi bạn viết mã JavaScript, bạn sẽ thường xuyên tham khảo các trang này (do đó, tiêu đề là "Tham khảo JavaScript")

Ngôn ngữ JavaScript nhằm mục đích sử dụng trong một số môi trường lớn hơn, có thể là trình duyệt, tập lệnh phía máy chủ hoặc tương tự. Đối với hầu hết các phần, tài liệu tham khảo này cố gắng không phụ thuộc vào môi trường và không nhắm mục tiêu đến môi trường trình duyệt web

Nếu bạn chưa quen với JavaScript, hãy bắt đầu với hướng dẫn. Khi bạn đã nắm vững các nguyên tắc cơ bản, bạn có thể sử dụng tài liệu tham khảo để biết thêm chi tiết về các đối tượng riêng lẻ và cấu trúc ngôn ngữ

Trong hướng dẫn này, chúng ta sẽ giải quyết một vấn đề mã hóa phổ biến mà người phỏng vấn thích hỏi ứng viên. Hy vọng rằng điều này sẽ giúp bạn hiểu làm thế nào để suy nghĩ thông qua nó và giải quyết nó

Hãy bắt đầu bằng cách hiểu vấn đề. Bạn được cung cấp một mảng chứa các số và các mảng số lồng nhau. Công việc của bạn là trả về một mảng mới chứa tất cả các số theo kiểu tuyến tính mà không cần lồng vào nhau. Hãy nhớ rằng việc lồng nhau có thể sâu ở bất kỳ cấp độ nào

Đây là một ví dụ

Ví dụ đầu vào và đầu ra

Bây giờ, bạn nghĩ đến điều gì khi nghe thấy từ làm tổ?

Đệ quy là gì?

Đệ quy đơn giản có nghĩa là một hàm gọi chính nó. Ngay lập tức, bạn có thể hỏi nếu một chức năng cứ gọi chính nó, nó có phải là một vòng lặp vô hạn không?

Để giải quyết vấn đề đó, chúng tôi sử dụng một số điều kiện (rất có thể là điều kiện if) để dừng các lệnh gọi hàm đệ quy, sau khi chúng tôi hoàn thành nhiệm vụ của mình. Những điều kiện này được gọi là Trường hợp cơ sở

Hãy bắt đầu với một ví dụ. Giả sử tôi muốn in các số từ 1 đến N (đã bao gồm). Thông thường, bạn sẽ viết một vòng lặp for cho nó, phải không?

Chức năng in 1 đến N (Giải pháp lặp lại)

Nếu tôi muốn viết mã để in 1 đến N bằng cách sử dụng đệ quy thì sao?

Để viết một hàm đệ quy cho phần trên, chúng ta phải hỏi hai câu hỏi sau

Hàm đệ quy của chúng ta nên dừng khi nào? . Khi đạt đến N + 1, vì chúng tôi phải in từ 1 đến N
Công việc thực tế mà hàm đệ quy của chúng ta nên làm là gì? . In các giá trị ra bàn điều khiển

Tóm lại, hãy tiếp tục in các giá trị cho đến khi đạt N + 1

Theo câu hỏi thứ hai chúng ta vừa thảo luận, mã của chúng ta sẽ giống như thế này

Đoạn mã trên cũng in 1 đến N (5), phải không? .

Bây giờ, thay vì gọi hàm tương tự theo cách thủ công, hãy để mã làm điều đó cho chúng ta. Một cái gì đó như thế này

Nếu bạn quan sát kỹ đoạn mã trên, dòng 6 print1ToNo(currentValue + 1) đang gọi cùng một hàm với một giá trị mới (bất kể giá trị hiện tại là gì, cộng với 1, i. e giá trị hiện tại + 1). Và nó tiếp tục làm như vậy, cho đến khi Giá trị hiện tại vượt qua VÀ, bởi vì đó là khi chúng tôi yêu cầu nó quay trở lại. Bây giờ, đây là ý nghĩa của đệ quy

Cách suy nghĩ theo cách đệ quy

Bây giờ, hãy quay lại vấn đề chính của chúng ta – chúng ta cần làm phẳng một Array. Giả sử rằng chúng ta chỉ có một mức lồng (tất nhiên, chúng ta có thể có nhiều mức lồng, nhưng bây giờ chúng ta sẽ xử lý một mức). Mảng sẽ trông giống như thế này

Đầu vào ví dụ - lồng 1 cấp

Chúng ta sẽ đi qua chỉ mục mảng đầu vào theo chỉ mục

Chỉ số 0, Giá trị = 1

Chỉ số 0 chứa một số (giá trị = 1). Nó chỉ là một con số và không phải là một mảng. Chúng ta có cần làm phẳng các con số không? . Chúng sẽ là một phần của mảng đầu ra như vậy. Tức là chúng ta không cần làm gì đặc biệt với số, chúng ta chỉ đặc biệt chú ý đến mảng

Vì vậy, quy tắc của chúng tôi là, nếu đó là một số, hãy đẩy nó vào mảng đầu ra và chuyển sang chỉ mục tiếp theo (ở đây là chỉ mục 1)

Chỉ số 1, Giá trị = 2

Chỉ mục 1 cũng chứa một số (giá trị = 2). Chúng ta có cần làm phẳng các con số không? . Chúng sẽ là một phần của mảng đầu ra như vậy

Vì vậy, theo quy tắc của chúng tôi, nếu đó là một số, hãy đẩy nó vào mảng đầu ra và chuyển sang chỉ mục tiếp theo (chỉ mục 2 ở đây)

Chỉ mục 2, Giá trị = [ 3, 4 ]

Bây giờ, chỉ số 2 là một mảng ([ 3, 4 ]) và không phải là một số. Vì vậy, bây giờ chúng ta sẽ phải nghĩ ra một số cách để làm phẳng nó

Điều gì sẽ xảy ra nếu tôi đưa cho bạn một mảng [3, 4] và yêu cầu bạn làm phẳng nó? . Sau đó, bạn có thể nhận ra rằng 3 chỉ là một con số, vì vậy hãy đẩy nó vào mảng đầu ra và chuyển sang chỉ mục tiếp theo

Chà, trong chỉ mục tiếp theo, 4 cũng chỉ là một số, vì vậy hãy đẩy nó vào mảng đầu ra. Và chúng tôi đã hoàn thành. Chà, tại sao bạn không làm điều tương tự trên index 2 ( [ 3, 4 ] ) của mảng đầu vào của chúng ta?

Bạn phải tự hỏi, thật dễ dàng để nói rằng. Làm thế nào để làm điều đó trong mã. ? . Bất cứ khi nào chúng ta gặp một mảng, chúng ta sẽ yêu cầu hàm đệ quy lấy mảng đó làm đầu vào mới và giải quyết nó cho chúng ta

Đặt mọi thứ vào ngữ cảnh, nếu đó chỉ là một số, đừng làm gì cả, chỉ cần đẩy số đó vào mảng đầu ra của chúng tôi và chuyển sang chỉ mục tiếp theo

Nếu đó là một mảng, hãy lấy mảng đó làm đầu vào mới và bắt đầu thực hiện những gì chúng ta đã làm trước đó. (Chúng ta sẽ thực hiện phần này bằng cách sử dụng đệ quy)

Giải pháp cho vấn đề

Được rồi, xin nhắc lại, đây là vấn đề của chúng ta

Bạn được cung cấp một mảng chứa các số và các mảng số lồng nhau. Công việc của bạn là trả về một mảng mới chứa tất cả các số theo kiểu tuyến tính mà không cần lồng vào nhau. Hãy nhớ rằng việc lồng nhau có thể sâu ở bất kỳ cấp độ nào

Đây là giải pháp cho vấn đề của chúng tôi bằng cách sử dụng đệ quy

Giải pháp - Mã

Nếu bạn xem kỹ hàm có tên đệ quy trong đoạn mã trên, chúng ta đang kiểm tra xem phần tử mảng mà chúng ta đang xem có phải là một mảng hay không. Biến có tên index được sử dụng để biểu thị chỉ số hiện tại mà chúng ta đang truy cập, trong inputArray

Nếu nó không phải là một mảng, chúng ta chỉ cần đẩy phần tử đó vào mảng đầu ra của mình và chuyển sang chỉ mục tiếp theo. Mặt khác, chúng ta bắt đầu một lệnh gọi hàm mới (đảo ngược) với mảng được trỏ bởi biến chỉ mục

Đoạn mã này hoạt động với mọi cấp độ lồng nhau, không chỉ 1 cấp độ lồng nhau. Và tại sao vậy?

Vì vậy, bất kể chúng ta có bao nhiêu mảng lồng nhau, đệ quy sẽ tiếp tục cho đến khi chúng ta tìm thấy một số, để chúng ta bắt đầu đẩy nó vào mảng đầu ra

Đây là cách đệ quy hoạt động ở hậu trường (đối với ví dụ trước)

Làm thế nào mọi thứ đang được thực hiện

Phần kết luận

Bây giờ, bạn đã biết cách làm phẳng một mảng bằng đệ quy. Đệ quy là một cách tiếp cận tốn kém khi nói đến sự phức tạp về thời gian và không gian

Ví dụ: không gian bổ sung duy nhất mà chúng tôi đang sử dụng trong giải pháp của mình là outputArray, mà chúng tôi đang sử dụng để lưu trữ câu trả lời cho vấn đề của mình

Nhưng, đó không phải là không gian duy nhất chúng tôi đang sử dụng. Luôn có một không gian ngăn xếp phụ mà chúng ta đang sử dụng khi sử dụng đệ quy

Không gian ngăn xếp phụ trợ này lớn đến mức nào? . Vì vậy, chiều cao tối đa của ngăn xếp (biểu thị mức độ sâu của các cuộc gọi đệ quy của chúng tôi) là thứ bao gồm không gian ngăn xếp phụ trợ. Một cái gì đó như O(h) space, where h is the maximum height of the stack

Bây giờ, khi nói đến độ phức tạp của thời gian, nó phụ thuộc vào đầu vào. Ví dụ. [1 , 2, 3, 4, 5]. Một đầu vào như thế này không cần làm phẳng, nhưng chúng ta vẫn duyệt qua toàn bộ mảng một lần. Vì vậy, độ phức tạp của thời gian là O(n) where n is the number of elements

Bây giờ những gì về ví dụ này? . Nếu đó là một mảng, hãy gọi hàm đệ quy với mảng đó, vì mảng đầu vào mới của chúng ta. Nếu đó là một số, hãy đẩy nó vào mảng đầu ra của chúng tôi và sau đó lặp lại chỉ mục tiếp theo

Vì vậy, độ phức tạp của thời gian sẽ gần như theo cấp số nhân. Đệ quy hiếm khi được sử dụng trong môi trường sản xuất. Nhưng bạn sẽ thấy nó rất nhiều trong các cuộc phỏng vấn kỹ thuật. )

QUẢNG CÁO

đợi KS

Đọc thêm bài viết

Nếu bạn đọc đến đây, hãy tweet cho tác giả để cho họ thấy bạn quan tâm. Tweet một lời cảm ơn

Học cách viết mã miễn phí. Chương trình giảng dạy mã nguồn mở của freeCodeCamp đã giúp hơn 40.000 người có được việc làm với tư cách là nhà phát triển. Bắt đầu

programming javascript