<p>Ch&agrave;o mừng c&aacute;c bạn đến với kh&oacute;a học "Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật" tại TEK4.VN!</p>
<p>Bạn đ&atilde; bao giờ tự hỏi rằng để trở th&agrave;nh một lập tr&igrave;nh vi&ecirc;n xuất sắc, bạn cần những kiến thức v&agrave; kỹ năng g&igrave;? Kh&oacute;a học n&agrave;y ch&iacute;nh l&agrave; ch&igrave;a kh&oacute;a để mở ra c&aacute;nh cửa của tri thức đ&oacute;. Với nội dung phong ph&uacute; v&agrave; chi tiết, kh&oacute;a học Cấu tr&uacute;c dữ liệu v&agrave; Giải thuật tại TEK4.VN hứa hẹn sẽ gi&uacute;p bạn x&acirc;y dựng nền tảng vững chắc v&agrave; th&agrave;nh thạo trong lập tr&igrave;nh.</p>
<p>Trong kh&oacute;a học n&agrave;y, ch&uacute;ng ta sẽ tập trung v&agrave;o việc kh&aacute;m ph&aacute; v&agrave; hiểu r&otilde; c&aacute;c cấu tr&uacute;c dữ liệu quan trọng như mảng, chuỗi k&yacute; tự, danh s&aacute;ch li&ecirc;n kết, ngăn xếp, h&agrave;ng đợi, bảng băm, tập hợp, c&acirc;y, đồ thị v&agrave; heap. C&aacute;c cấu tr&uacute;c dữ liệu n&agrave;y l&agrave; nền tảng của lập tr&igrave;nh, gi&uacute;p ch&uacute;ng ta giải quyết c&aacute;c vấn đề phức tạp một c&aacute;ch hiệu quả.</p>
<p>Kh&oacute;a học cũng sẽ gi&uacute;p bạn hiểu r&otilde; c&aacute;c thuật to&aacute;n cơ bản v&agrave; n&acirc;ng cao, bao gồm thuật to&aacute;n sắp xếp, thuật to&aacute;n t&igrave;m kiếm, thuật to&aacute;n t&igrave;m kiếm nhị ph&acirc;n, thuật to&aacute;n t&igrave;m kiếm chuỗi k&yacute; tự, giải thuật tham lam, thuật to&aacute;n quay lui v&agrave; quy hoạch động. Bạn sẽ học c&aacute;ch &aacute;p dụng c&aacute;c thuật to&aacute;n n&agrave;y v&agrave;o c&aacute;c vấn đề thực tế, gi&uacute;p tăng cường kỹ năng giải quyết vấn đề của m&igrave;nh.</p>
<p>Ngo&agrave;i ra, ch&uacute;ng m&igrave;nh sẽ chia sẻ một số kinh nghiệm cần thiết cho buổi phỏng vấn, gi&uacute;p bạn chuẩn bị tốt nhất cho c&aacute;c cơ hội nghề nghiệp li&ecirc;n quan đến lập tr&igrave;nh trong tương lai. Bạn sẽ được học c&aacute;ch hiểu r&otilde; y&ecirc;u cầu của người phỏng vấn, thể hiện kỹ năng lập tr&igrave;nh của m&igrave;nh một c&aacute;ch hiệu quả v&agrave; trả lời c&aacute;c c&acirc;u hỏi một c&aacute;ch tr&ocirc;i chảy. Ch&uacute;ng m&igrave;nh tự tin rằng, sau khi bạn ho&agrave;n th&agrave;nh kh&oacute;a học n&agrave;y, bạn sẽ trở n&ecirc;n nhạy b&eacute;n trong tư duy lập tr&igrave;nh hiệu quả.</p>
<p>H&atilde;y tham gia kh&oacute;a học n&agrave;y để t&igrave;m hiểu s&acirc;u hơn về lập tr&igrave;nh v&agrave; mở rộng kỹ năng của bạn. TEK4.VN rất mong được hỗ trợ bạn trong qu&aacute; tr&igrave;nh học tập n&agrave;y.</p>

Cấu trúc dữ liệu và Giải thuật

<p dir="ltr" style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ n&oacute;i ngắn gọn về một số cấu tr&uacute;c v&agrave; thủ thuật phổ biến được sử dụng trong c&aacute;c thuật to&aacute;n li&ecirc;n quan đến mảng v&agrave; chuỗi.</p>
<h2 dir="ltr" style="text-align: justify;"><strong>X&acirc;y dựng chuỗi $O(n)$</strong></h2>
<p dir="ltr" style="text-align: justify;">Ta đ&atilde; biết rằng trong hầu hết c&aacute;c ng&ocirc;n ngữ, chuỗi l&agrave; bất biến, nghĩa l&agrave; một thao t&aacute;c nối một k&yacute; tự đơn v&agrave;o chuỗi cần thời gian chạy $O(n)$. Nếu bạn c&oacute; chuỗi d&agrave;i 1 triệu k&yacute; tự v&agrave; muốn th&ecirc;m một k&yacute; tự nữa th&igrave; tất cả 1 triệu k&yacute; tự đ&oacute; cần được sao ch&eacute;p sang một chuỗi kh&aacute;c.</p>
<p dir="ltr" style="text-align: justify;">Nhiều b&agrave;i to&aacute;n sẽ y&ecirc;u cầu trả về chuỗi v&agrave; th&ocirc;ng thường chuỗi n&agrave;y sẽ được x&acirc;y dựng trong thuật to&aacute;n. Thao t&aacute;c nối đơn giản nhưng lại c&oacute; độ phức tạp thuật to&aacute;n&nbsp;$O\left(n^2\right)$&nbsp;nếu bạn đang sử dụng một ng&ocirc;n ngữ x&aacute;c định chuỗi l&agrave; bất biến.</p>
<p dir="ltr" style="text-align: justify;">C&oacute; nhiều phương ph&aacute;p tốt hơn để tạo chuỗi trong thời gian $O(n)$. Thời gian chạy sẽ kh&aacute;c nhau giữa c&aacute;c ng&ocirc;n ngữ. Trong b&agrave;i viết n&agrave;y, ta sẽ n&oacute;i về Python v&agrave; Java. Nếu bạn đang sử dụng một ng&ocirc;n ngữ kh&aacute;c th&igrave; bạn n&ecirc;n nghi&ecirc;n cứu c&aacute;ch tốt nhất để tạo chuỗi trong ng&ocirc;n ngữ đ&oacute;.</p>
<h3 dir="ltr" style="text-align: justify;"><strong>Python</strong></h3>
<ol style="text-align: justify;">
<li dir="ltr">
<p dir="ltr">Khai b&aacute;o danh s&aacute;ch</p>
</li>
<li dir="ltr">
<p dir="ltr">Khi tạo chuỗi th&igrave; đồng thời th&ecirc;m c&aacute;c k&yacute; tự v&agrave;o danh s&aacute;ch. Mỗi thao t&aacute;c chạy trong thời gian $O(n)$.</p>
</li>
<li dir="ltr">
<p dir="ltr">Sau khi ho&agrave;n tất, h&atilde;y chuyển đổi danh s&aacute;ch th&agrave;nh chuỗi bằng c&aacute;ch nhập&nbsp;<code>"".join(list)</code>. Thời gian chạy l&agrave; $O(n)$.</p>
</li>
</ol>
<pre class="language-c" data-content="def%20build_string(s)%3A%0A%C2%A0%C2%A0%C2%A0%C2%A0arr%20%3D%20%5B%5D%0A%C2%A0%C2%A0%C2%A0%C2%A0for%20c%20in%20s%3A%0A%C2%A0%C2%A0%C2%A0%C2%A0%C2%A0%C2%A0%C2%A0%C2%A0arr.append(c)%0A%0A%0A%C2%A0%C2%A0%C2%A0%C2%A0return%20%22%22.join(arr)" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>def build_string(s):
    arr = []
    for c in s:
        arr.append(c)


    return "".join(arr)</code></pre>
<h3 dir="ltr" style="text-align: justify;"><strong>Java</strong></h3>
<ul style="text-align: justify;">
<li dir="ltr">
<p dir="ltr">Sử dụng lớp <code>StringBuilder</code>.</p>
</li>
<li dir="ltr">
<p dir="ltr">Khi tạo chuỗi th&igrave; đồng thời th&ecirc;m c&aacute;c k&yacute; tự v&agrave;o danh s&aacute;ch. Mỗi thao t&aacute;c chạy trong thời gian $O(1)$.</p>
</li>
<li dir="ltr">
<p dir="ltr">Sau khi ho&agrave;n tất, h&atilde;y chuyển đổi danh s&aacute;ch th&agrave;nh chuỗi bằng c&aacute;ch nhập&nbsp;<code>StringBuilder.toString()</code>. Thời gian chạy l&agrave; $O(n)$.</p>
</li>
</ul>
<pre class="language-c" data-content="public%20string%20buildString(String%20s)%20%7B%0A%C2%A0%C2%A0%C2%A0%C2%A0StringBuilder%20sb%20%3D%20new%20StringBuilder()%3B%0A%C2%A0%C2%A0%C2%A0%C2%A0for%20(int%20i%20%3D%200%3B%20i%20%3C%20s.length()%3B%20i%2B%2B)%20%7B%0A%C2%A0%C2%A0%C2%A0%C2%A0%C2%A0%C2%A0%C2%A0%C2%A0sb.append(s.charAt(i))%3B%0A%C2%A0%C2%A0%C2%A0%C2%A0%7D%0A%0A%0A%C2%A0%C2%A0%C2%A0%C2%A0return%20sb.toString()%3B%0A%7D" data-language="c" data-ace-language="c_cpp" data-name-language="C" data-main-file="main.c"><code>public string buildString(String s) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i &lt; s.length(); i++) {
        sb.append(s.charAt(i));
    }


    return sb.toString();
}</code></pre>
<h2 dir="ltr" style="text-align: justify;"><strong>Mảng con/chuỗi con, d&atilde;y con v&agrave; tập con</strong></h2>
<p dir="ltr" style="text-align: justify;">H&atilde;y c&ugrave;ng thảo luận về sự kh&aacute;c biệt v&agrave; những điều cần ch&uacute; &yacute; khi gặp c&aacute;c dạng dữ liệu n&agrave;y trong b&agrave;i to&aacute;n.</p>
<h3 dir="ltr" style="text-align: justify;"><strong>Mảng con/chuỗi con</strong></h3>
<p dir="ltr" style="text-align: justify;">[___NOTE_<span class="WdYUQQ text-decoration-none text-strikethrough-none">L&agrave; một phần của mảng, sao cho c&aacute;c phần tử </span><strong><span class="WdYUQQ text-decoration-none text-strikethrough-none">liền kề</span></strong><span class="WdYUQQ text-decoration-none text-strikethrough-none"><strong> nhau </strong>v&agrave; </span><strong><span class="WdYUQQ text-decoration-none text-strikethrough-none">theo thứ tự</span></strong>._NOTE___]</p>
<p dir="ltr" style="text-align: justify;">Nếu b&agrave;i to&aacute;n đưa ra điều kiện r&otilde; r&agrave;ng như:</p>
<ul style="text-align: justify;">
<li dir="ltr">
<p dir="ltr">Tổng lớn hơn hoặc nhỏ hơn&nbsp;<code>k</code></p>
</li>
<li dir="ltr">
<p dir="ltr">Giới hạn đối với c&aacute;c phần tử, chẳng hạn như tối đa&nbsp;<code>k</code>&nbsp;phần tử duy nhất hoặc kh&ocirc;ng cho ph&eacute;p tr&ugrave;ng lặp</p>
</li>
</ul>
<p dir="ltr" style="text-align: justify;">V&agrave;/hoặc y&ecirc;u cầu:</p>
<ul style="text-align: justify;">
<li dir="ltr">
<p dir="ltr">Độ d&agrave;i tối thiểu hoặc tối đa</p>
</li>
<li dir="ltr">
<p dir="ltr">Số mảng con/chuỗi con thỏa m&atilde;n</p>
</li>
<li dir="ltr">
<p dir="ltr">Tổng tối đa hoặc tối thiểu</p>
</li>
</ul>
<p dir="ltr" style="text-align: justify;">H&atilde;y suy nghĩ đến việc sử dụng kỹ thuật cửa sổ trượt. Lưu &yacute; rằng kh&ocirc;ng phải tất cả c&aacute;c b&agrave;i to&aacute;n c&oacute; những đặc điểm n&agrave;y đều c&oacute; thể được giải quyết bằng cửa sổ trượt v&agrave; kh&ocirc;ng phải tất cả c&aacute;c b&agrave;i to&aacute;n về cửa sổ trượt đều c&oacute; những đặc điểm n&agrave;y. Những đặc điểm tr&ecirc;n chỉ n&ecirc;n được coi như một hướng dẫn chung.</p>
<p dir="ltr" style="text-align: justify;">Nếu input của b&agrave;i to&aacute;n l&agrave; một mảng số nguy&ecirc;n v&agrave; bạn cần t&iacute;nh tổng nhiều mảng con, h&atilde;y xem x&eacute;t việc tạo mảng cộng dồn.</p>
<p dir="ltr" style="text-align: justify;">K&iacute;ch thước của mảng con giữa chỉ số&nbsp;<code>i</code>&nbsp;v&agrave;&nbsp;<code>j</code>&nbsp;(bao gồm&nbsp;<code>i</code>&nbsp;v&agrave;<code>&nbsp;j</code>) l&agrave;&nbsp;<code>j - i + 1</code>. Đ&acirc;y cũng l&agrave; số mảng con kết th&uacute;c tại&nbsp;<code>j</code>, bắt đầu từ&nbsp;<code>i</code>&nbsp;trở l&ecirc;n.</p>
<h3 dir="ltr" style="text-align: justify;"><strong>D&atilde;y con</strong></h3>
<p dir="ltr" style="text-align: justify;">[___NOTE_<span class="WdYUQQ text-decoration-none text-strikethrough-none">Gồm c&aacute;c phần tử của mảng, tuy kh&ocirc;ng cần liền kề nhau nhưng vẫn </span><strong><span class="WdYUQQ text-decoration-none text-strikethrough-none">theo thứ tự</span></strong>._NOTE___]</p>
<p dir="ltr" style="text-align: justify;"><strong>V&iacute; dụ:</strong> c&aacute;c d&atilde;y con của&nbsp;<code>[1, 2, 3, 4]</code>&nbsp;l&agrave;:&nbsp;<code>[1, 3],&nbsp;[4],&nbsp;[],&nbsp;[2, 3]</code>, nhưng kh&ocirc;ng phải l&agrave;&nbsp;<code>[3, 2],&nbsp;[5],&nbsp;[4, 1]</code>.</p>
<p dir="ltr" style="text-align: justify;">C&aacute;c b&agrave;i to&aacute;n về d&atilde;y con thường kh&oacute; hơn. Bởi v&igrave; đ&acirc;y chỉ l&agrave; chương đầu ti&ecirc;n n&ecirc;n rất kh&oacute; để n&oacute;i về c&aacute;c dạng b&agrave;i về d&atilde;y con ngay. D&atilde;y con sẽ xuất hiện trong phần c&ograve;n lại của kh&oacute;a học n&agrave;y. V&iacute; dụ, lập tr&igrave;nh động được sử dụng để giải quyết rất nhiều b&agrave;i to&aacute;n về d&atilde;y con.</p>
<p dir="ltr" style="text-align: justify;">Trong c&aacute;c dạng ta đ&atilde; học đến nay, kỹ thuật phổ biến nhất li&ecirc;n quan đến chuỗi con l&agrave; hai con trỏ, khi input l&agrave; hai mảng/chuỗi. Mảng cộng dồn v&agrave; cửa sổ trượt kh&ocirc;ng được &aacute;p dụng với d&atilde;y con.</p>
<h2 dir="ltr" style="text-align: justify;"><strong>Tập con</strong></h2>
<p dir="ltr" style="text-align: justify;">[___NOTE_<span class="WdYUQQ text-decoration-none text-strikethrough-none">Gồm c&aacute;c phần tử của mảng, sắp xếp t&ugrave;y &yacute; kh&ocirc;ng cần theo vị tr&iacute; hay thứ tự</span>._NOTE___]</p>
<p dir="ltr" style="text-align: justify;"><strong>V&iacute; dụ:</strong><em><strong> </strong></em>cho&nbsp;<code>[1, 2, 3, 4]</code>, tất cả c&aacute;c tập sau đều l&agrave; tập con:&nbsp;<code>[3, 2],&nbsp;[4, 1, 2],&nbsp;[1]</code>.</p>
<p dir="ltr" style="text-align: justify;">[___WARNING_Lưu &yacute;: c&aacute;c tập con chứa phần tử như nhau được coi l&agrave; một, v&iacute; dụ&nbsp;<code>[1, 2, 4]</code>&nbsp;c&ugrave;ng l&agrave; một tập con với&nbsp;<code>[4, 1, 2]</code>._WARNING___]</p>
<p dir="ltr" style="text-align: justify;">C&oacute; thể bạn đang thắc mắc sự kh&aacute;c biệt giữa chuỗi con v&agrave; tập con l&agrave; g&igrave; nếu c&aacute;c tập con c&oacute; c&ugrave;ng c&aacute;c phần tử được coi l&agrave; giống nhau? X&eacute;t trong b&agrave;i to&aacute;n thuật to&aacute;n, điều n&agrave;y thường c&oacute; nghĩa l&agrave; ta c&oacute; thể sắp xếp input ngay từ đầu, do đ&oacute; ta c&oacute; thể sử dụng những phương ph&aacute;p như hai con trỏ, thuật to&aacute;n tham lam hoặc thậm ch&iacute; l&agrave; cửa sổ trượt.</p>
<p dir="ltr" style="text-align: justify;">Nhắc lại, v&igrave; ta đang ở chương đầu ti&ecirc;n n&ecirc;n kh&oacute; c&oacute; thể thảo luận chi tiết về tập con. Ta sẽ thấy tập con được sử dụng trong chương thuật to&aacute;n quay lui.</p>
<p dir="ltr" style="text-align: justify;">Một điều cần lưu &yacute; l&agrave; nếu b&agrave;i to&aacute;n c&oacute; li&ecirc;n quan đến d&atilde;y con, nhưng thứ tự của d&atilde;y con kh&ocirc;ng thực sự quan trọng (giả sử ta cần t&iacute;nh tổng của c&aacute;c d&atilde;y con), th&igrave; bạn c&oacute; thể coi n&oacute; như tập con v&agrave; thực hiện.</p>
<p dir="ltr" style="text-align: center;"><iframe src="https://www.youtube.com/embed/Rstrwx8Fuyc" width="560" height="314" allowfullscreen="allowfullscreen"></iframe></p>
<h2 dir="ltr" style="text-align: justify;"><strong>Tổng kết</strong></h2>
<p dir="ltr" style="text-align: justify;">Như vậy ta đ&atilde; đi qua hết nội dung của chương <em><strong>mảng v&agrave; chuỗi</strong></em>. Do t&iacute;nh chất đơn giản của chủ đề n&ecirc;n rất kh&oacute; để đi s&acirc;u v&agrave;o c&aacute;c b&agrave;i to&aacute;n chuy&ecirc;n m&ocirc;n hơn. Cấu tr&uacute;c của kh&oacute;a học n&agrave;y l&agrave; x&acirc;y dựng kiến ​​thức dần dần. V&iacute; dụ: c&oacute; v&ocirc; số b&agrave;i to&aacute;n về cửa sổ trượt tr&ecirc;n TEK4.VN chưa được đề cập ở đ&acirc;y v&igrave; ta chưa học về bảng băm. Hầu hết c&aacute;c b&agrave;i to&aacute;n (kh&ocirc;ng phải dạng c&acirc;y/đồ thị/danh s&aacute;ch li&ecirc;n kết) đều c&oacute; mảng hoặc chuỗi trong input n&ecirc;n chắc chắn ta sẽ gặp lại những kỹ thuật n&agrave;y trong c&aacute;c chương tiếp theo.</p>
<p dir="ltr" style="text-align: justify;">Trước khi chuyển sang chủ đề tiếp theo, h&atilde;y kiểm tra kiến ​​thức của bạn với một số c&acirc;u trắc nghiệm nh&eacute;.</p>
<div id="tudienjp">
<div class="o-search-mobile" style="top: 0px; left: 0px; display: none;">&nbsp;</div>
<div class="o-popup-tag o-bg-white o-border o-rounded o-shadow" style="width: 400px; top: 0px; left: 0px; display: none;">
<div><button class="btn-sm o-btn-close o-position-absolute o-top-0 o-end-0 o-mt-1 o-me-1" type="button" aria-label="Close"></button>
<ul class="o-nav o-nav-tabs o-pop-nav" role="tablist">
<li class="o-nav-item" role="presentation">
<div class="o-nav-link active" data-bs-toggle="tab" aria-selected="true">Từ vựng</div>
</li>
<li class="o-nav-item" role="presentation">
<div class="o-nav-link" data-bs-toggle="tab" aria-selected="false">H&aacute;n tự</div>
</li>
<li class="o-nav-item" role="presentation">
<div class="o-nav-link" data-bs-toggle="tab" aria-selected="false">Dịch</div>
</li>
</ul>
<div class="o-selected-result o-pt-1">
<div>Đang t&igrave;m kiếm ...</div>
<div class="o-fs-6 o-mt-2" style="line-height: 1.7;">
<div class="o-float-start">
<div class="o-form-check"><input id="flexCheckTudienjpLang" class="o-form-check-input" type="checkbox" /><label for="flexCheckTudienjpLang"> Tiếng Anh </label></div>
</div>
<div class="o-float-end o-me-1"><a class="o-link-secondary o-text-decoration-none" href="https://tudienjp.com/" target="_blank" rel="noopener">Từ điển JP</a></div>
</div>
</div>
</div>
</div>
</div>
<div id="tudienjpOff"></div>

Một số cấu trúc phổ biến