CS61B 课程笔记（Project 1B Applying and Testing Data Structures version 1.0）

问题描述

在这个项目中，我们需要实现一个用于检查字符串是否为回文的工具。回文是正向和反向读都相同的字符串，比如 "racecar"。我们还将扩展这个工具，允许用户使用字符比较器来定义更灵活的回文条件，例如允许字符之间的差异。

任务 1: Deque 接口

目标：定义一个双端队列接口 Deque，用于支持在队列的两端插入和删除元素。

实现：

public interface Deque<Item> {
    void addFirst(Item item);
    void addLast(Item item);
    Item removeFirst();
    Item removeLast();
    boolean isEmpty();
    int size();
    Item get(int index);
}

任务 2: wordToDeque 方法

目标：将输入的字符串转换为一个字符双端队列。

实现：

import java.util.LinkedList;

public class Palindrome {
    public Deque<Character> wordToDeque(String word) {
        Deque<Character> deque = new ArrayDeque<>();
        for (char c : word.toCharArray()) {
            deque.addLast(c);
        }
        return deque;
    }
}

任务 3: isPalindrome 方法

目标：检查给定的字符串是否是回文。

实现：

public boolean isPalindrome(String word) {
    Deque<Character> deque = wordToDeque(word);
    while (deque.size() > 1) {
        if (deque.removeFirst() != deque.removeLast()) {
            return false;
        }
    }
    return true;
}

任务 4: 广义回文

OffByOne 类

目标：实现一个字符比较器，允许相差一个字符的回文检查。

实现：

public class OffByOne implements CharacterComparator {
    @Override
    public boolean equalChars(char x, char y) {
        return Math.abs(x - y) == 1;
    }
}

重载的 isPalindrome 方法

目标：支持使用自定义字符比较器的回文检查。

实现：

public boolean isPalindrome(String word, CharacterComparator cc) {
    if (cc == null) {
        return isPalindrome(word);
    }
    Deque<Character> deque = wordToDeque(word);
    while (deque.size() > 1) {
        char front = deque.removeFirst();
        char back = deque.removeLast();
        if (!cc.equalChars(front, back)) {
            return false;
        }
    }
    return true;
}

OffByN 类

目标：实现一个字符比较器，允许任意指定字符间隔的回文检查。

实现：

public class OffByN implements CharacterComparator {
    private int n;

    public OffByN(int n) {
        this.n = n;
    }

    @Override
    public boolean equalChars(char x, char y) {
        return Math.abs(x - y) == n;
    }
}

任务 5: 测试

目标：编写单元测试以验证实现的正确性。

实现：

import org.junit.Test;
import static org.junit.Assert.*;

public class TestPalindrome {
    @Test
    public void testIsPalindrome() {
        Palindrome palindrome = new Palindrome();
        assertTrue(palindrome.isPalindrome("racecar"));
        assertFalse(palindrome.isPalindrome("cat"));
    }

    @Test
    public void testIsPalindromeWithOffByOne() {
        Palindrome palindrome = new Palindrome();
        CharacterComparator cc = new OffByOne();
        assertTrue(palindrome.isPalindrome("flake", cc));
        assertFalse(palindrome.isPalindrome("hello", cc));
    }
}

类和导入

import org.junit.Test;
import static org.junit.Assert.*;

• import org.junit.Test;：导入 JUnit 测试框架的 Test 注解，用于标记测试方法。
• import static org.junit.Assert.*;：导入 JUnit 的断言方法，方便在测试中使用，例如 assertTrue 和 assertFalse。

测试类

public class TestPalindrome {

• 定义一个名为 TestPalindrome 的公共类，专门用于测试 Palindrome 类的功能。

测试方法 1：testIsPalindrome

@Test
public void testIsPalindrome() {
    Palindrome palindrome = new Palindrome();
    assertTrue(palindrome.isPalindrome("racecar"));
    assertFalse(palindrome.isPalindrome("cat"));
}

• @Test：标记该方法为测试方法，JUnit 会自动识别并执行它。
• Palindrome palindrome = new Palindrome();：创建一个 Palindrome 类的实例，以便调用其方法。
• assertTrue(palindrome.isPalindrome("racecar"));：调用 isPalindrome 方法，检查字符串 "racecar" 是否是回文。assertTrue 会检查该方法返回值是否为 true，如果不是，测试将失败。
• assertFalse(palindrome.isPalindrome("cat"));：检查字符串 "cat" 是否是回文。这里使用 assertFalse 检查返回值是否为 false。

测试方法 2：testIsPalindromeWithOffByOne

@Test
public void testIsPalindromeWithOffByOne() {
    Palindrome palindrome = new Palindrome();
    CharacterComparator cc = new OffByOne();
    assertTrue(palindrome.isPalindrome("flake", cc));
    assertFalse(palindrome.isPalindrome("hello", cc));
}

• @Test：同样标记该方法为测试方法。
• Palindrome palindrome = new Palindrome();：再次创建 Palindrome 类的实例。
• CharacterComparator cc = new OffByOne();：创建一个 OffByOne 类型的字符比较器实例，用于允许相差一个字符的回文检查。
• assertTrue(palindrome.isPalindrome("flake", cc));：调用 isPalindrome 方法，检查 "flake" 是否符合通过 cc 定义的回文条件。若返回值为 true，测试通过。
• assertFalse(palindrome.isPalindrome("hello", cc));：检查 "hello" 是否符合该回文条件，若返回值为 false，测试通过。