Bỏ qua nội dung
Môn học
  • 1 Cơ bản về Java
    1.1

    Lớp, main & đầu ra

    Trang web này biên dịch Java theo các quy tắc ngôn ngữ Java 8. Các ví dụ độc lập này đặt phương thức vào, main, bên trong một lớp. Các lớp hỗ trợ và câu trả lời chỉ có phương thức không cần có riêng main. System.out.println(...) in ra một dòng; System.out.print(...) in ra mà không xuống dòng mới.

    public class Main {
        public static void main(String[] args) {
            System.out.println("Hello, world!");
            System.out.println("I am learning Java.");
        }
    }
    
    • Java được biên dịch: trình biên dịch kiểm tra toàn bộ chương trình, sau đó nó chạy.
    • Các khai báo, gán giá trị, gọi phương thức và các câu return kết thúc bằng dấu chấm phẩy ;. Một khối if, for hoặc while sử dụng ngoặc nhọn; đừng thêm dấu chấm phẩy chỉ vì dấu ngoặc đóng xuất hiện.
    Ví dụ Java 8 độc lập này định nghĩa main bên trong một class
    Ví dụ Java 8 độc lập này định nghĩa main bên trong một class
    1.2

    Biến & kiểu dữ liệu nguyên thủy

    Một biến phải khai báo kiểu của nó. Các kiểu nguyên thủy phổ biến: int (số nguyên), double (số thập phân), boolean (true/false), char (một đơn vị mã UTF-16; một số ký tự cần hai).

    public class Main {
        public static void main(String[] args) {
            int age = 17;
            double price = 9.99;
            boolean passed = true;
            System.out.println(age + " " + price + " " + passed);
        }
    }
    
    1.3

    Bình luận & phong cách

    Một comment là // (một dòng) hoặc /* ... */ (một khối). Thụt lề code bên trong ngoặc nhọn { }. Tên class viết hoa; biến và method dùng camelCase (viết thường chữ đầu).

    public class Main {
        public static void main(String[] args) {
            // greet the user
            String firstName = "Mei";
            System.out.println("Hi, " + firstName);
        }
    }
    

    Lỗi thường gặp

    • Khai báo, gán, gọi phương thức và statement return kết thúc bằng ;; khối kiểm soát luồng không cần dấu chấm phẩy thừa.
    • Sử dụng điểm vào tiêu chuẩn Java 8 là public static void main(String[] args); tên tham số có thể khác, và String... args cũng hợp lệ.
    • println thêm một dòng mới; print thì không.
  • 2 Toán tử & biểu thức
    2.1

    Toán học & gán

    Toán học Java sử dụng + - * / và % (phần dư). Với hai int, / là phép chia số nguyên — nó bỏ phần thập phân. +=, -=, và ++ là các cách tắt.

    public class Main {
        public static void main(String[] args) {
            int a = 7, b = 2;
            System.out.println(a / b);    // 3 (integer division)
            System.out.println(a % b);    // 1
            double x = 7.0 / 2;           // 3.5 (one side is double)
            System.out.println(x);
        }
    }
    
    int/int làm tròn xuống; cần dùng double để có thương số thực
    int/int làm tròn xuống; hãy sử dụng double để có thương chính xác
    2.2

    Sử dụng đối tượng: String, Math, wrappers

    Một số giá trị là các đối tượng có methods. String có .length(), .substring(), .toUpperCase(). Math có Math.max, Math.sqrt, Math.pow. Wrapper classes (Integer, Double) đóng gói một primitive — ví dụ: Integer.parseInt("42").

    public class Main {
        public static void main(String[] args) {
            String s = "Hello";
            System.out.println(s.length());                  // 5
            System.out.println(s.toUpperCase());             // HELLO
            System.out.println(Math.max(3, 9));              // 9
            System.out.println(Integer.parseInt("42") + 1);  // 43
        }
    }
    

    Math.random() trả về một double ngẫu nhiên từ 0.0 trở lên (nhưng không bao gồm) 1.0. Nhân tỷ lệ và cast để lấy số nguyên — đây là idiom của AP:

    public class Main {
        public static void main(String[] args) {
            // a random whole number from 1 to 6 (a dice roll)
            int roll = (int) (Math.random() * 6) + 1;
            System.out.println(roll >= 1 && roll <= 6);   // true
        }
    }
    
    • Integer.MAX_VALUE (2147483647) và Integer.MIN_VALUE là giới hạn của int; vượt qua chúng sẽ bị cuộn vòng lại (overflow).
    • Một biến đối tượng không trỏ vào bất kỳ đối tượng nào chứa null; gọi một method trên nó sẽ ném NullPointerException.
    2.3

    Casting & chuyển đổi kiểu

    Cast thay đổi kiểu của một giá trị. (int) loại bỏ phần thập phân; (double) tránh phép chia số nguyên khi bạn cần kết quả chính xác.

    public class Main {
        public static void main(String[] args) {
            double pi = 3.99;
            System.out.println((int) pi);            // 3
            int total = 7, n = 2;
            System.out.println((double) total / n);  // 3.5
        }
    }
    

    Lỗi thường gặp

    • Phép chia số nguyên: 5 / 2 là 2, không phải 2.5. Cast trước: (double) 5 / 2.
    • So sánh Strings (và các đối tượng khác) với .equals(), không phải ==.
    • == trên hai đối tượng kiểm tra xem chúng có phải là CÙNG một đối tượng hay không, không phải xem chúng có giống nhau về mặt biểu diễn hay không.
  • 3 Boolean & điều kiện
    3.1

    if / else

    if chạy một block khi một điều kiện đúng; else if và else thêm nhiều trường hợp hơn. Điều kiện nằm trong ( ), block nằm trong { }.

    public class Main {
        public static void main(String[] args) {
            int score = 72;
            if (score >= 80) {
                System.out.println("A");
            } else if (score >= 60) {
                System.out.println("B");
            } else {
                System.out.println("fail");
            }
        }
    }
    
    if chọn nhánh true; else chọn nhánh false
    if chọn nhánh true; else chọn nhánh false
    3.2

    Toán tử logic & so sánh

    So sánh với ==, !=, <, >, <=, >= — một phép so sánh cho ra một boolean. Kết hợp với && (and), || (or), ! (not) — các toán tử logic. Đối với Strings, hãy dùng .equals(...), không phải ==.

    public class Main {
        public static void main(String[] args) {
            int age = 16;
            boolean member = true;
            System.out.println(age >= 18 && member);   // false
            String a = "hi";
            System.out.println(a.equals("hi"));        // true
        }
    }
    
    3.3

    công tắc

    switch chọn từ nhiều giá trị cố định. Sử dụng break để thoát khỏi một trường hợp; nếu không, thực thi có thể tiếp tục vào trường hợp tiếp theo. default là giá trị dự phòng.

    public class Main {
        public static void main(String[] args) {
            int day = 3;
            switch (day) {
                case 1: System.out.println("Mon"); break;
                case 3: System.out.println("Wed"); break;
                default: System.out.println("other");
            }
        }
    }
    

    Lỗi thường gặp

    • Một điều kiện phải là một boolean; if (x = 5) sẽ không biên dịch được (hãy dùng ==).
    • Trong switch, break, return hoặc throw có thể ngăn chặn fall-through. Việc đạt đến case tiếp theo mà không có nó sẽ tiếp tục thực thi tại đó.
    • && và || đánh giá ngắn (short-circuit). & và | hoạt động theo bit trên số nguyên; với booleans, chúng đánh giá cả hai toán hạng.
  • 4 Vòng lặp
    4.1

    Vòng lặp while

    Một while loop lặp lại trong khi một điều kiện đúng. Thay đổi thứ gì đó bên trong, hoặc nó sẽ lặp vô tận.

    public class Main {
        public static void main(String[] args) {
            int n = 1;
            while (n <= 3) {
                System.out.println(n);
                n++;
            }
        }
    }
    
    while kiểm tra điều kiện trước mỗi lần lặp thân vòng lặp
    while kiểm tra điều kiện trước mỗi lần lặp thân vòng lặp
    4.2

    Vòng lặp for

    Một for loop gom phần khởi tạo, điều kiện và bước tăng/giảm vào một dòng. Tốt nhất khi bạn biết số lần lặp.

    public class Main {
        public static void main(String[] args) {
            for (int i = 0; i < 5; i++) {
                System.out.print(i + " ");
            }
            System.out.println();   // 0 1 2 3 4
        }
    }
    
    4.3

    Tích lũy

    Mẫu tích lũy: khởi tạo một biến trước loop, sau đó cập nhật nó mỗi lần lặp.

    public class Main {
        public static void main(String[] args) {
            int total = 0;
            for (int i = 1; i <= 5; i++) {
                total += i;
            }
            System.out.println(total);   // 15
        }
    }
    
    4.4

    Vòng lặp lồng nhau

    Một loop bên trong một loop là loop lồng nhau. Loop trong chạy trọn vẹn ở mỗi lần lặp của loop ngoài.

    public class Main {
        public static void main(String[] args) {
            for (int r = 0; r < 3; r++) {
                for (int c = 0; c < 3; c++) {
                    System.out.print("*");
                }
                System.out.println();
            }
        }
    }
    

    Lỗi thường gặp

    • for (int i = 0; i < n; i++) chạy n lần (từ 0 đến n - 1); việc sử dụng <= sẽ chạy thêm một lần nữa.
    • Đừng đặt dấu chấm phẩy ngay sau for (...) hoặc while (...) — nó sẽ tạo ra một loop rỗng.
    • Khai báo biến đếm trong header for để phạm vi của nó kết thúc cùng với loop.
  • 5 Chuỗi ký tự
    5.1

    Các phương thức String

    Một String là văn bản. Các phương thức hữu ích: .length(), .charAt(i), .substring(a, b), .indexOf(x), .toUpperCase(), .equals(...). String bất biến: nội dung của chúng không thể thay đổi. Phương thức có thể trả về số, boolean hoặc string; một String được trả về có thể tái sử dụng đối tượng đã tồn tại.

    public class Main {
        public static void main(String[] args) {
            String s = "Python";
            System.out.println(s.length());          // 6
            System.out.println(s.charAt(0));         // P
            System.out.println(s.substring(0, 3));   // Pyt
            System.out.println(s.toUpperCase());     // PYTHON
        }
    }
    

    Các methods bạn sẽ dùng hàng ngày:

    Method Ý nghĩa Ví dụ → kết quả
    .length() bao nhiêu ký tự "Hi".length() → 2
    .charAt(i) một ký tự "Hi".charAt(0) → H
    .substring(a, b) phần, dừng trước b "Python".substring(0, 3) → Pyt
    .substring(a) từ a đến cuối "Python".substring(3) → hon
    .indexOf(x) vị trí đầu tiên, -1 nếu không có "banana".indexOf("na") → 2
    .equals(s) cùng văn bản? "hi".equals("hi") → true
    .compareTo(s) thứ tự: âm / 0 / dương "apple".compareTo("banana") → âm

    compareTo so sánh các đơn vị mã UTF-16 theo thứ tự từ điển, phân biệt hoa/thường (ví dụ: "Z" đứng trước "a") — đề thi AP sử dụng nó cho câu hỏi sắp xếp:

    public class Main {
        public static void main(String[] args) {
            String a = "apple", b = "banana";
            System.out.println(a.compareTo(b) < 0);    // true (apple comes first)
            System.out.println(a.compareTo("apple"));  // 0 (equal)
        }
    }
    
    Key String methods: length, charAt, substring, equals
    Key String methods: length, charAt, substring, equals
    5.2

    Xây dựng & duyệt chuỗi

    Nối các chuỗi bằng + (nối chuỗi). Duyệt qua từng ký tự bằng một loop và .charAt(i).

    public class Main {
        public static void main(String[] args) {
            String word = "banana";
            int count = 0;
            for (int i = 0; i < word.length(); i++) {
                if (word.charAt(i) == 'a') count++;
            }
            System.out.println(count);   // 3
        }
    }
    

    Khi bạn xây dựng một String dài trong loop, StringBuilder nhanh hơn nhiều: append các mảnh, sau đó gọi .toString() một lần.

    public class Main {
        public static void main(String[] args) {
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i <= 5; i++) {
                sb.append(i).append(" ");
            }
            System.out.println(sb.toString().trim());   // 1 2 3 4 5
        }
    }
    

    Lỗi thường gặp

    • String bất biến: s.toUpperCase() trả về kết quả in hoa mà không thay đổi s, do đó hãy lưu kết quả lại.
    • Đọc một ký tự bằng s.charAt(i); độ dài là s.length() (một method, có ()).
    • Xây dựng String bằng += trong một loop lớn rất chậm; hãy dùng một StringBuilder.
  • 6 Mảng
    6.1

    Mảng 1 chiều

    Một mảng giữ một số lượng giá trị cố định của một kiểu. Index từ 0, và lấy kích thước bằng .length.

    public class Main {
        public static void main(String[] args) {
            int[] scores = {88, 71, 95};
            System.out.println(scores[0]);       // 88
            System.out.println(scores.length);   // 3
            scores[1] = 100;
            System.out.println(scores[1]);       // 100
        }
    }
    
    Giá trị nguyên thủy giữ giá trị; biến mảng giữ tham chiếu đến đối tượng mảng
    Giá trị nguyên thủy giữ giá trị; biến mảng giữ tham chiếu đến đối tượng mảng
    6.2

    Thuật toán mảng

    Duyệt mảng bằng vòng lặp để tìm giá trị lớn nhất, tổng, số lượng hoặc thực hiện tìm kiếm. Vòng lặp for-each (for (int x : a)) đọc từng giá trị theo thứ tự.

    public class Main {
        public static void main(String[] args) {
            int[] a = {3, 9, 2, 7};
            int max = a[0], total = 0;
            for (int x : a) {
                if (x > max) max = x;
                total += x;
            }
            System.out.println(max + " " + total);   // 9 21
        }
    }
    
    6.3

    Mảng 2 chiều

    Mảng 2-D là một lưới gồm các hàng và cột: grid[row][col].

    public class Main {
        public static void main(String[] args) {
            int[][] grid = {{1, 2, 3}, {4, 5, 6}};
            System.out.println(grid[1][2]);   // 6
            for (int[] row : grid) {
                for (int v : row) System.out.print(v + " ");
            }
            System.out.println();             // 1 2 3 4 5 6
        }
    }
    

    Lỗi thường gặp

    • Kích thước của mảng là a.length (không có ngoặc, không có ()), và nó được cố định ngay khi được tạo ra.
    • Các chỉ số hợp lệ nằm từ 0 đến a.length - 1; a[a.length] sẽ gây ra ArrayIndexOutOfBoundsException.
    • Một int[5] mới được điền bằng số không, không để trống.
  • 7 ArrayList
    7.1

    Cơ bản về ArrayList

    Một ArrayList là danh sách có thể thay đổi kích thước — nó mở rộng và thu nhỏ khi bạn thêm hoặc xóa mục. Nó lưu trữ các đối tượng, vì vậy hãy dùng kiểu bao bọc như Integer (không phải int). Phần <Integer> là một kiểu tổng quát. Các phương thức chính: .add(x), .get(i), .set(i, x), .size(), .remove(i).

    import java.util.ArrayList;
    
    public class Main {
        public static void main(String[] args) {
            ArrayList<Integer> nums = new ArrayList<Integer>();
            nums.add(10);
            nums.add(20);
            nums.add(30);
            System.out.println(nums.size());   // 3
            System.out.println(nums.get(1));   // 20
            nums.set(0, 99);
            System.out.println(nums);          // [99, 20, 30]
        }
    }
    
    ArrayList: add, get, size trên danh sách có thể thay đổi kích thước
    ArrayList: add, get, size trên danh sách có thể thay đổi kích thước
    7.2

    Thuật toán ArrayList & lỗi remove

    .remove(i) dịch chuyển mọi phần tử sau về phía trái một vị trí. Nếu bạn xóa trong khi đếm i lên, bạn sẽ bỏ sót phần tử tiếp theo. Cách sửa: lặp ngược, hoặc không tăng i sau khi xóa.

    import java.util.ArrayList;
    
    public class Main {
        public static void main(String[] args) {
            ArrayList<Integer> nums = new ArrayList<Integer>();
            for (int n : new int[]{4, 7, 4, 9, 4}) nums.add(n);
            // Remove every 4 — loop backwards so removals don't skip items.
            for (int i = nums.size() - 1; i >= 0; i--) {
                if (nums.get(i) == 4) nums.remove(i);
            }
            System.out.println(nums);   // [7, 9]
        }
    }
    

    Lỗi thường gặp

    • ArrayList sử dụng .size(), .get(i) và .add(...) — không phải [] mà bạn dùng trên mảng.
    • Xóa phần tử trong khi duyệt theo chỉ số từ đầu đến cuối sẽ bỏ sót phần tử tiếp theo (lỗi remove). Hãy duyệt ngược lại, hoặc sử dụng iterator.
    • Lưu trữ các đối tượng, không phải giá trị nguyên thủy: hãy dùng ArrayList<Integer>, và Java tự động đóng hộp int thành đối tượng.
  • 8 Viết lớp
    8.1

    Trường dữ liệu, constructor & phương thức

    Một lớp là bản thiết kế cho các đối tượng. Các trường của nó lưu dữ liệu, constructor thiết lập một đối tượng mới, và các phương thức là các hành động. this.name có nghĩa là "name của đối tượng này". Tạo một đối tượng với new.

    public class Main {
        public static void main(String[] args) {
            Dog d = new Dog("Rex", 3);
            System.out.println(d.describe());   // Rex is 3 years old
            d.haveBirthday();
            System.out.println(d.describe());   // Rex is 4 years old
        }
    }
    
    class Dog {
        private String name;
        private int age;
    
        public Dog(String name, int age) {   // constructor
            this.name = name;
            this.age = age;
        }
    
        public String describe() {
            return name + " is " + age + " years old";
        }
    
        public void haveBirthday() {
            age++;
        }
    }
    

    Một thành viên static thuộc về lớp đó, không thuộc về bất kỳ đối tượng cụ thể nào. Gọi phương thức tĩnh theo tên lớp — ví dụ Math.max — và một trường tĩnh được chia sẻ bởi mọi đối tượng:

    public class Main {
        public static void main(String[] args) {
            System.out.println(Counter.made());   // 0
            new Counter();
            new Counter();
            System.out.println(Counter.made());   // 2
        }
    }
    
    class Counter {
        private static int count = 0;      // shared by ALL Counter objects
    
        public Counter() { count++; }
    
        public static int made() {         // called on the class: Counter.made()
            return count;
        }
    }
    
    Fields lưu trạng thái; constructor xây dựng; methods thực thi hành động
    Fields lưu trạng thái; constructor xây dựng; methods thực thi hành động
    8.2

    Đóng gói (Encapsulation)

    Encapsulation kiểm soát truy cập vào trạng thái của đối tượng. Đánh dấu các trường private để chặn truy cập trực tiếp từ các class không liên quan; một method truy xuất (getter) đọc trạng thái và một method thay đổi (mutator) chỉnh sửa nó. Một setter là một loại mutator. private không xác thực giá trị: constructors và các method thay đổi cần có các kiểm tra riêng hoặc tiền điều kiện đã nêu. Ví dụ này giả định một start không âm và các phép cộng vừa vặn trong int; phương thức deposit của nó từ chối các khoản gửi không dương.

    public class Main {
        public static void main(String[] args) {
            Account a = new Account(100);
            a.deposit(50);
            a.deposit(-999);                       // rejected by the guard
            System.out.println(a.getBalance());    // 150
        }
    }
    
    class Account {
        private int balance;                       // hidden from outside
    
        public Account(int start) {
            balance = start;
        }
    
        public void deposit(int amount) {
            if (amount > 0) balance += amount;     // this guard checks the deposit amount
        }
    
        public int getBalance() {                  // accessor (getter)
            return balance;
        }
    }
    

    Lỗi thường gặp

    • Constructor có tên lớp và không có kiểu trả về (thậm chí cả void).
    • Sử dụng this.field để phân biệt trường với tham số cùng tên.
    • Khai báo các trường là private và truy cập chúng thông qua các phương thức getter/setter (bao encapsulation).
  • 9 Kế thừa & đa hình
    9.1

    Kế thừa

    Kế thừa cho phép lớp con tái sử dụng lớp cha. Viết class Cat extends Animal và Cat kế thừa các trường hợp và phương thức khả dụng từ Animal. Thành viên riêng tư không được kế thừa; cũng như vậy với constructor. Gọi constructor cha bằng super(...).

    public class Main {
        public static void main(String[] args) {
            Cat c = new Cat("Milo");
            c.eat();      // Milo is eating  (inherited from Animal)
            c.speak();    // Meow            (Cat's own method)
        }
    }
    
    class Animal {
        protected String name;
        public Animal(String name) { this.name = name; }
        public void eat() { System.out.println(name + " is eating"); }
    }
    
    class Cat extends Animal {
        public Cat(String name) { super(name); }     // call Animal's constructor
        public void speak() { System.out.println("Meow"); }
    }
    
    Cat và Dog kế thừa Animal: chúng thừa hưởng các thành viên của nó và thêm vào những cái riêng
    Cat và Dog kế thừa Animal: chúng thừa hưởng các thành viên của nó và thêm vào những cái riêng
    9.2

    Đa hình & toString

    Một lớp con có thể ghi đè một phương thức để thay thế phiên bản của cha. Đa hình có nghĩa là một biến Shape có thể chứa bất kỳ kiểu con nào, và Java chọn đúng toString tại thời gian chạy. System.out.println(obj) tự động gọi obj.toString().

    public class Main {
        public static void main(String[] args) {
            Shape[] shapes = { new Circle(2), new Square(3) };
            for (Shape s : shapes) {
                System.out.println(s);          // each calls its own toString
            }
        }
    }
    
    class Shape {
        public String toString() { return "a shape"; }
    }
    
    class Circle extends Shape {
        private int r;
        public Circle(int r) { this.r = r; }
        public String toString() { return "Circle r=" + r; }     // override
    }
    
    class Square extends Shape {
        private int side;
        public Square(int side) { this.side = side; }
        public String toString() { return "Square side=" + side; }   // override
    }
    

    Lỗi thường gặp

    • Một phương thức ghi đè phải khớp chính xác chữ ký; hãy thêm @Override để trình biên dịch bắt được sai sót.
    • super(...) phải là dòng đầu tiên của constructor subclass.
    • Một đối tượng subclass IS-A đối tượng superclass, nhưng không phải ngược lại.
  • 10 Recursion
    10.1

    Đệ quy

    Đệ quy (recursion) là một phương thức gọi chính nó. Mọi đệ quy đều cần một base case (khi nào thì dừng) và một cuộc gọi đệ quy tiến gần đến nó. Không có base case, nó sẽ không bao giờ dừng và bị crash với lỗi stack overflow.

    Call stack cho factorial(3): mỗi cuộc gọi chờ đợi, rồi trả về theo thứ tự ngược lại
    Call stack cho factorial(3): mỗi cuộc gọi chờ đợi, rồi trả về theo thứ tự ngược lại
    public class Main {
        public static void main(String[] args) {
            System.out.println(factorial(5));   // 120
        }
    
        public static int factorial(int n) {
            if (n <= 1) return 1;            // base case
            return n * factorial(n - 1);     // recursive call: n * (n-1)!
        }
    }
    

    Theo dõi nó: factorial(5) chờ đợi factorial(4), cái gì đó chờ đợi factorial(3)… xuống đến factorial(1) trả về 1. Sau đó các câu trả lời nhân ngược lên: 1 → 2 → 6 → 24 → 120.

    Đệ quy cũng hoạt động trên Strings — gọt bỏ một ký tự mỗi lần gọi:

    public class Main {
        public static void main(String[] args) {
            System.out.println(reverse("PYTHON"));   // NOHTYP
        }
    
        static String reverse(String s) {
            if (s.length() <= 1) return s;               // base case
            return reverse(s.substring(1)) + s.charAt(0);
        }
    }
    

    Merge sort là thuật toán sắp xếp đệ quy trong đề thi AP: chia mảng thành hai nửa, sắp xếp mỗi nửa đệ quy, sau đó gộp hai nửa đã sắp xếp lại. Nó chạy trong O(n log n) — nhanh hơn nhiều so với các thuật toán O(n²) trên mảng lớn.

    import java.util.Arrays;
    
    public class Main {
        public static void main(String[] args) {
            int[] a = {5, 2, 9, 1, 7, 3};
            mergeSort(a, 0, a.length - 1);
            System.out.println(Arrays.toString(a));   // [1, 2, 3, 5, 7, 9]
        }
    
        static void mergeSort(int[] a, int lo, int hi) {
            if (lo >= hi) return;                 // base case: one element
            int mid = (lo + hi) / 2;
            mergeSort(a, lo, mid);                // sort the left half
            mergeSort(a, mid + 1, hi);            // sort the right half
            merge(a, lo, mid, hi);                // merge the two halves
        }
    
        static void merge(int[] a, int lo, int mid, int hi) {
            int[] tmp = new int[hi - lo + 1];
            int i = lo, j = mid + 1, k = 0;
            while (i <= mid && j <= hi) {
                if (a[i] <= a[j]) tmp[k++] = a[i++];
                else              tmp[k++] = a[j++];
            }
            while (i <= mid) tmp[k++] = a[i++];
            while (j <= hi)  tmp[k++] = a[j++];
            for (k = 0; k < tmp.length; k++) a[lo + k] = tmp[k];
        }
    }
    

    Lỗi thường gặp

    • Quy hồi cần một trường hợp cơ sở, nếu không sẽ gây ra StackOverflowError.
    • Mỗi cuộc gọi đệ quy phải di chuyển GẦN HƠN đến base case.
    • Trace một ví dụ nhỏ bằng tay để kiểm tra xem đệ quy có trả về giá trị đúng không.
    • Trong merge sort, bước merge làm công việc thực sự; đệ quy chỉ chia mảng.
  • 11 Tìm kiếm & sắp xếp
    11.1

    Tìm kiếm tuyến tính & nhị phân

    Tìm kiếm tuyến tính kiểm tra từng phần tử — hoạt động trên mọi mảng. Tìm kiếm nhị phân nhanh hơn nhiều nhưng cần một mảng đã sắp xếp: nó xem xét phần tử ở giữa, sau đó loại bỏ một nửa mỗi bước. Cả hai đều trả về chỉ số, hoặc -1 nếu không tìm thấy.

    public class Main {
        public static void main(String[] args) {
            int[] a = {2, 5, 8, 12, 16, 23};      // sorted, so binary search works
            System.out.println(linear(a, 12));    // 3
            System.out.println(binary(a, 12));    // 3
            System.out.println(binary(a, 9));     // -1 (not found)
        }
    
        static int linear(int[] a, int target) {
            for (int i = 0; i < a.length; i++)
                if (a[i] == target) return i;
            return -1;
        }
    
        static int binary(int[] a, int target) {
            int lo = 0, hi = a.length - 1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (a[mid] == target) return mid;
                else if (a[mid] < target) lo = mid + 1;
                else hi = mid - 1;
            }
            return -1;
        }
    }
    
    Binary search chia đôi phạm vi mỗi bước, nên mảng đã sắp xếp được tìm kiếm trong O(log n)
    Binary search chia đôi phạm vi mỗi bước, nên mảng đã sắp xếp được tìm kiếm trong O(log n)
    11.2

    Sắp xếp chọn & sắp xếp chèn

    Sắp xếp chọn (selection sort) liên tục tìm giá trị nhỏ nhất còn lại và hoán đổi nó lên đầu. Sắp xếp chèn (insertion sort) lấy từng giá trị và trượt nó trở lại vị trí phù hợp trong số các giá trị đã được sắp xếp.

    import java.util.Arrays;
    
    public class Main {
        public static void main(String[] args) {
            int[] a = {5, 2, 9, 1, 7};
            for (int i = 0; i < a.length - 1; i++) {
                int min = i;
                for (int j = i + 1; j < a.length; j++)
                    if (a[j] < a[min]) min = j;
                int t = a[min]; a[min] = a[i]; a[i] = t;   // swap into place
            }
            System.out.println(Arrays.toString(a));   // [1, 2, 5, 7, 9]
        }
    }
    
    import java.util.Arrays;
    
    public class Main {
        public static void main(String[] args) {
            int[] a = {5, 2, 9, 1, 7};
            for (int i = 1; i < a.length; i++) {
                int key = a[i], j = i - 1;
                while (j >= 0 && a[j] > key) {    // shift bigger values right
                    a[j + 1] = a[j];
                    j--;
                }
                a[j + 1] = key;                  // drop key into the gap
            }
            System.out.println(Arrays.toString(a));   // [1, 2, 5, 7, 9]
        }
    }
    

    So sánh tốc độ:

    Thuật toán Thời gian
    linear search O(n)
    binary search O(log n), chỉ mảng đã sắp xếp
    selection / insertion sort O(n²)
    merge sort (đề mục 10) O(n log n)

    Lỗi thường gặp

    • Binary search chỉ hoạt động trên một mảng đã sắp xếp.
    • Linear search là O(n); binary search là O(log n) nhưng cần sắp xếp trước.
    • Selection và insertion sort là O(n²) — dễ học, nhưng chậm trên dữ liệu lớn.
  • 12 Tệp & FRQ
    12.1

    Tập tin văn bản với Scanner

    Một Scanner đọc văn bản từng dòng một. Đối với một tập tin thực tế, bạn viết new Scanner(new File("scores.txt")); ở đây chúng tôi bao quanh một String để ví dụ chạy ở bất cứ đâu. Sử dụng .split(" ") để tách một dòng thành các phần và Integer.parseInt(...) để phân tích một số từ văn bản.

    import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            // Real file:  Scanner in = new Scanner(new File("scores.txt"));
            String data = "Alice 80\nBob 95\nCara 72";
            Scanner in = new Scanner(data);
            int total = 0, count = 0;
            while (in.hasNextLine()) {
                String line = in.nextLine();
                String[] parts = line.split(" ");      // break the line on the space
                total += Integer.parseInt(parts[1]);
                count++;
            }
            System.out.println("average = " + (total / count));   // average = 82
        }
    }
    
    Scanner đọc dòng trong khi hasNextLine là true
    Scanner đọc dòng trong khi hasNextLine là true
    12.2

    Các loại câu hỏi FRQ của AP

    Đề thi AP CS A có bốn câu hỏi tự luận, mỗi câu có dạng cố định:

    • Q1 — Phương thức & điều khiển: viết các phương thức theo yêu cầu đã cho; vòng lặp, if, String/Math.
    • Q2 — Thiết kế lớp: viết một lớp đầy đủ (trường, khởi tạo, phương thức) từ mô tả.
    • Q3 — Mảng / ArrayList: xử lý mảng 1-D hoặc ArrayList (tìm kiếm, đếm, xây dựng danh sách mới).
    • Q4 — Mảng 2-D: duyệt qua lưới theo hàng và cột.

    Kỹ năng luôn giống nhau: đọc yêu cầu, viết phương thức đúng như mô tả, trả về kiểu dữ liệu chính xác.

    public class Main {
        public static void main(String[] args) {
            // Q1 style: implement a method to a spec, then it is tested.
            System.out.println(countEven(new int[]{4, 7, 10, 3, 6}));   // 3
        }
    
        /** Returns how many values in arr are even. */
        public static int countEven(int[] arr) {
            int count = 0;
            for (int x : arr)
                if (x % 2 == 0) count++;
            return count;
        }
    }
    

    Lỗi thường gặp

    • nextInt() giữ lại ký tự xuống dòng, nên nextLine() tiếp theo sẽ đọc một dòng trống — hãy đọc nó đi trước.
    • Kiểm tra hasNext() trước khi đọc, để tránh vượt quá cuối tập tin.
    • Trong FRQ, đọc kỹ phần khai báo phương thức: khớp chính xác kiểu trả về và tham số.

Đăng nhập hoặc tạo tài khoản

IGCSE, A-Level & AP