station d

Bài viết được sự cho phép của tác giả Kiên Nguyễn

Reverse Array là bài toán phổ biến mà bất cứ kĩ sư phần mềm nào cũng cần phải hiểu rõ và áp dụng thành thục. Mở rộng ra cho cả string và các bài toán khác.

Cùng tìm hiểu một số lời giải cơ bản cho Array ngay thôi nào!

5 điều NÊN và KHÔNG NÊN khi review tăng lương mà lập trình viên nào cũng nên biết!

Code Review Done Right – Đừng để chỉ Chúa mới hiểu code của bạn!

1. Reverse Array với ESTCV Approach

Làm việc với Array tất nhiên phải chú ý tới complexity (độ phức tạp). Arrays provide O(1) lookup by index (Tìm kiếm theo index trên Array luôn có độ phức tạp nhỏ nhất O(1)

Ngoài đảo ngược Array, cũng có một bài toán khác khá hay liên quan tới Array là duplicate item trong array.

Given an array of numbers, replace each even number with two of the same number. e.g, [1,2,5,6,8] -> [1,2,2,5,6,6,8,8]

Cho một danh sách các mảng, thay thế mỗi số chẵn bằng 2 số.

Time Complexity: O(n) aka linear time
Space Complexity: O(1) aka constant space

Độ phức tạp về thời gian là O(n) do duyệt mảng từ đầu tới cuối

package com.src;

public class Main {
public static void main(String[] args) {
// Mảng input sẽ có -1 đại diện cho index sẽ duplicate bằng số chẵn
int[] a = new int[]{2, 4, 1, 0, 3, -1, -1, -1};
cloneEvenNumber(a);
for (int item : a) {
System.out.println(item);
}
}

public static int[] cloneEvenNumber(int[] a) {
if (a == null || a.length == 0) {
return a;
}
int end = a.length;
int i = getLastNumber(a);
while (i >= 0) {
// Mảng chạy từ phải qua trái
if (a[i] % 2 == 0) {
a[--end] = a[i];
}
// Set vào phía sau mảng nếu là số lẻ, lặp nếu là số chẵn
a[--end] = a[i];
i--;
}
return a;
}

// Tìm vị trí i cuối cùng không phải là -1
public static int getLastNumber(int[] a) {
int i = a.length - 1;
while (i >= 0 && a[i] == -1) {
i--;
}
return i;
}
}

2. Traverse từ Both Ends

1) Initialize start and end indexes as start = 0, end = n-1
2) Swap arr[start] with arr[end]
3) Recursively call reverse for rest of the array.

Về ý tưởng cơ bản thì khi muốn đảo ngược array, ta sẽ thực hiện đổi chỗ tuần tự phần tử đầu và cuối. Tiến dần về trong cho tới phần tử ở giữa. Có thể hiện thực code như sau:

package com.src;

public class Main {
public static void main(String[] args) {
int[] a = new int[]{3, 4, 2, 7, 1};
reverse(a);
for (int item : a) {
System.out.println(item);
}
}

public static void reverse(int[] a) {
int start = 0;
int end = a.length - 1;
while (start < end) {
swap(a, start, end);
start++;
end--;
}
}

private static void swap(int[] a, int start, int end) {
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
}

3. Traverse String

Bài toán đảo ngược không những áp dụng cho Array mà còn có thể áp dụng cho String. Cho dãy string “This is Kieblog”, đảo ngược chuỗi với Time Complexity và Space Complexity là O(n)

package com.src;

public class Main {
public static void main(String[] args) {
System.out.println(reverseWord("This is Kieblog"));
}

public static String reverseWord(String s) {
StringBuilder builder = new StringBuilder();
int currentWordEnd = s.length();

for (int i = s.length() - 1; i >= 0; i--) {
// Thêm space nếu có
if (s.charAt(i) == ' ') {
if (builder.length() > 0) {
builder.append(' ');
}
// Lấy từ kí tự cuối từ phải qua trái
builder.append(s.substring(i + 1, currentWordEnd));
currentWordEnd = i;
}
}
String firstWord = s.substring(0, currentWordEnd);
if (builder.length() > 0) {
builder.append(" ");
}
builder.append(firstWord);
return builder.toString();
}
}

Ngoài Reverse Array, cũng có những bài mở rộng hơn là tìm kiếm 2 vị trí trong array sao cho tổng là một số nguyên (target nhất định). Ước định rằng array đã được sort từ ban đầu. Ta cũng có thể lặp từ start tới end, tăng start nếu sum nhỏ hơn target và giảm end nếu sum đã lớn hơn target

package com.src;

public class Main {
public static void main(String[] args) {
int[] a = new int[]{1, 2, 3, 5, 6, 7};
System.out.println(twoSum(a, 11));
}

public static int twoSum(int[] a, int target) {
int start = 0;
int end = a.length - 1;

while (start < end) {
int sum = a[start] + a[end];
if (sum < target) {
start++;
}
if (sum > target) {
end--;
}
if (sum == target)
return a[start] + a[end];
}
return 0;
}
}