Phân Tách Chuỗi Hồi Văn

Sử dụng hai hàm: một để kiểm tra chuỗi có phải là hồi văn hay không, và một để thực hiện thuật toán quay lui.

class Solution:
    def kiemTraHoiVan(self, chuoi):
        return chuoi == chuoi[::-1]

    def quyLui(self, chuoi, viTriBatDau, duongDiHienTai, ketQua):
        if viTriBatDau >= len(chuoi):
            ketQua.append(duongDiHienTai.copy())
            return

        for i in range(viTriBatDau, len(chuoi)):
            if self.kiemTraHoiVan(chuoi[viTriBatDau:i + 1]):
                duongDiHienTai.append(chuoi[viTriBatDau:i + 1])
                self.quyLui(chuoi, i + 1, duongDiHienTai, ketQua)
                duongDiHienTai.pop()

    def phanTach(self, chuoi: str) -> List[List[str]]:
        ketQuaCuoiCung = []
        self.quyLui(chuoi, 0, [], ketQuaCuoiCung)
        return ketQuaCuoiCung

Tìm Vị Trí Chèn

Sử dụng thuật toán tìm kiếm nhị phân với khoảng đóng.

class Solution:
    def timViTriChen(self, danhSachSo: List[int], giaTriMucTieu: int) -> int:
        trai, phai = 0, len(danhSachSo) - 1
        while trai <= phai:
            giua = (trai + phai) // 2
            if danhSachSo[giua] < giaTriMucTieu:
                trai = giua + 1
            else:
                phai = giua - 1
        return trai

Tìm Kiếm Trong Ma Trận Hai Chiều

Phương Pháp Một:

Áp dụng thuật toán tìm kiếm nhị phân cho từng hàng của ma trận.

class Solution:
    def timTrongMaTran(self, maTran: List[List[int]], giaTriMucTieu: int) -> bool:
        for hang in maTran:
            trai, phai = 0, len(hang) - 1
            while trai <= phai:
                giua = (trai + phai) // 2
                if hang[giua] < giaTriMucTieu:
                    trai = giua + 1
                elif hang[giua] > giaTriMucTieu:
                    phai = giua - 1
                else:
                    return True
        return False

Phương Pháp Hai:

Xem ma trận hai chiều như một danh sách đã sắp xếp và áp dụng thuật toán tìm kiếm nhị phân.

class Solution:
    def timTrongMaTran(self, maTran: List[List[int]], giaTriMucTieu: int) -> bool:
        soHang, soCot = len(maTran), len(maTran[0])
        trai, phai = 0, soHang * soCot - 1
        while trai <= phai:
            giua = (trai + phai) // 2
            giaTriGiua = maTran[giua // soCot][giua % soCot]
            if giaTriGiua == giaTriMucTieu:
                return True
            if giaTriGiua < giaTriMucTieu:
                trai = giua + 1
            else:
                phai = giua - 1
        return False

Tìm Khoảng Của Giá Trị Trong Mảng Đã Sắp Xếp

Sử dụng thuật toán tìm kiếm nhị phân để xác định vị trí bắt đầu và kết thúc của giá trị mục tiêu.

class Solution:
    def gioiHanDuoi(self, danhSachSo, giaTriMucTieu):
        trai, phai = 0, len(danhSachSo) - 1
        while trai <= phai:
            giua = (trai + phai) // 2
            if danhSachSo[giua] < giaTriMucTieu:
                trai = giua + 1
            else:
                phai = giua - 1
        return trai

    def timKhoang(self, danhSachSo: List[int], giaTriMucTieu: int) -> List[int]:
        batDau = self.gioiHanDuoi(danhSachSo, giaTriMucTieu)
        if batDau == len(danhSachSo) or danhSachSo[batDau] != giaTriMucTieu:
            return [-1, -1]
        ketThuc = self.gioiHanDuoi(danhSachSo, giaTriMucTieu + 1) - 1
        return [batDau, ketThuc]