FRQ Cheatsheet

FRQ1

String常考思路

1. 替换某个subStr，其他内容不变

举例：bigStr = “I enjoy APCS”, 将第一次出现的enjoy替换为like，其他位置的内容不变，返回新的字符串。

String bigStr = "I enjog APCS";
String subStr = "enjoy";
String repl = "like";

int pos = bigStr.indexOf(subStr);
String result = bigStr.substring(0, pos)+repl+bigStr.substring(pos+subStr.length());

1. 判断一个长String是否包含subStr，或包含多少个subStr

可能要用到的方法：indexOf, substring

举例：WordMatch

• For循环思路：从长String的第一个字符开始，index每次移动一个位置，判断当前位置是否与subStr相同。

• While循环思路：从长String bigStr开始，判断bigStr是否包含subStr; 如果包含，bigStr从第一个subStr的下一个位置开始截取。

For Loop

public static int count(String bigStr, String subStr) {
    count = 0;
    for(int i=0; i<bigStr.length()-subStr.length(); i++) {
        if(bigStr.substring(i, i+subStr.length()).equals(subStr)) {
            count++;
        }
    }
    return count;
}

While Loop

public static int count(String bigStr, String subStr) {
    int count = 0;
    while(bisStr.indexOf(subStr) != -1) {
        int pos = bigStr.indexOf(subStr);
        bigStr = bigStr.substring(pos+1);
        count++;
    }
    return count;
}

注意：上题中subStr是可以重叠的。如果题目要求subStr不能重叠，那么使用while循环，并且index移动距离为subStr长度。

public static int count(String bigStr, String subStr) {
    int count = 0;
    while(bisStr.indexOf(subStr) != -1) {
        int pos = bigStr.indexOf(subStr);
        bigStr = bigStr.substring(pos+subStr.length());
        count++;
    }
    return count;
}

1D Array

1. 返回最大值

public int findBiggest(int[] arr)
{
    int max = arr[0]; // 或 int max = MIN_VALUE;
    for(int i=0; i < arr.length; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
        }
    }
    return max;
}

1. 返回最小值

public int findSmallest(int[] arr)
{
    int min = arr[0]; // 或 int min = MAX_VALUE;
    for(int i=0; i < arr.length; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
        }
    }
    return min;
}

1. 返回最大值的index

public int findBiggestIndex(int[] arr)
{
    int indexMax = 0;
    for(int i=0; i < arr.length; i++)
    {
        if (arr[i] > arr[indexMax])
        {
            indexMax = i;
        }
    }
    return indexMax;
}

1. 返回最小值的index

public int findSmallestIndex(int[] arr)
{
    int indexMin = 0;
    for(int i=0; i < arr.length; i++)
    {
        if (arr[i] <= arr[indexMin])
        {
            indexMin = i;
        }
    }
    return indexMin;
}

1. Reverse数组

public void reverseArray(int[] arr)
{
    for (int i = 0; i < arr.length/2; i++)
    {
        int temp = arr[i];
        arr[i] = arr[arr.length-1-i];
        arr[arr.length-1-i] = temp;
    }
}

循环只需要执行一半，否则数组会reverse两次，导致数组不变。

1. 判断数组为递增序列

思路：找反例！

public boolean isIncreasing(int[] arr)
{
    for (int i = 0; i < arr.length - 1; i++)
    {
        if (arr[i+1] < arr[i]) // 注意数组的索引是从0开始，此处判断当前元素与下一个元素，若大则返回false
        {
            return false;
        }
    }
    return true;
}

public boolean isDecreasing(int[] arr)
{
    for (int i = 0; i < arr.length - 1; i++)
    {
        if (arr[i+1] > arr[i])
        {
            return false;
        }
    }
    return true;
}

1. 判断是否有peak，即中间值同时大于前一个值和后一个值

public boolean havePeak(int[] arr)
{
    for (int i = 1; i < arr.length - 1; i++)
    {
        if (arr[i] > arr[i-1] && arr[i] > arr[i+1]) // 判断中间的元素是否比它的前一个和后一个都大
        {
            return true;
        }
    }
    return false;
}

1. 返回最长连续序列起始位置

Ex. [7, 10, 10, 15, 15, 15, 15, 3, 3, 3, 3, 3, 3]，最长连续序列是6个3，返回序列的起始位置，也就是7。

方法：起始位置 = 结束位置 - 连续长度 + 1

public static int findLongest(int[] nums) {
    int currentLen = 1; // 保存连续数的计数
    int maxLen = 0;   // 保存最长的连续数的长度
    int maxStart = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i-1]) {
            currentLen++; // 记录连续长度
            if(currentLen > maxLen) {
                maxLen = currentLen;
                maxStart = i - maxLen + 1;
            }
        }
        else {
            currentLen = 1; // 一旦数值断裂就重设连续数的计数为0
        }
    }
    return maxStart;
}

1. 返回target的最长连续长度

public static int getLongestRun(int target, int[] values) {
    int currentLen = 0;
    int maxLen = 0;
    for (int i = 0; i < values.length; i++) {
        if (values[i] == target) {
            currentLen++; // 如果values[i]是target就增加连续的计数
            if (currentLen > maxLen) {
                maxLen = currentLen; // 如果连续计数大于目前的最大长度就更新最大长度
            }
        } else {
            currentLen = 0; // 如果value[i]不是target，连续计数为0
        }
    }
    return maxLen;
}

ArrayList:

包含两个class，一个为常规classA，另一个classB包含ArrayList类型instance variable，ArrayList包含的元素类型是classA的Object。

Ex1. WordPair是常规class，WordPairList包含WordPair类型的ArrayList<allPairs>.

public class WordPair {
    public WordPair(String first, String second)
    public String getFirst()
    public String getSecond()
}

public class WordPairList {
    private ArrayList<WordPair> allPairs
    public WordPairList(String[] words)
    public int numMatches;
}

a. 完成classB的constructor，即完成ArrayList的初始化

方法：

• private ArrayList<WordPair> allPairs已经声明过，在constructor里不要重复声明

• 初始化allPairs，即add相应的WordPair object到allPairs，生成wordPair object的方法即为调用WordPair class的构造方法

• 所以要弄清楚WordPair的object是由哪些变量组成，仔细阅读WordPair的构造方法

本题可以看出构造WordPair需要两个String类型变量，根据题目，理解出这两个String变量对应题目中数组的哪些元素。

FRQ-1

public WordPairList(String[] words) {
    allPairs = new ArrayList<WordPair>();
    for(int i=0; i<words.length-1; i++) {
        for(int j=i+1; j<words.length; j++) {
            allPairs.add(new WordPair(words[i], words[j]));
        }
    }
}

b. Write the WordPairList method numMatches. This method returns the number of WordPair objects in allPairs for which the two strings match.

public int numMatches()
{
    int count = 0;
    for (WordPair pair: allPairs)
    {
        if (pair.getFirst().equals(pair.getSecond())){
            count++;
        }
    }
return count;
}

b. （高频考点）因为ArrayList中的每个元素都是classA的object，所以ArrayList的每个元素都可以调用classA中的method（通常是getter method)，获取classA object中的实例变量，并与参数进行比较。

根据比较结果，对ArrayList进行相应的add，remove，返回极值等操作。

模版：

• Add/Remove某些元素

for(int i=0; i<listName.size(); i++) {
    if(listName.get(i).getMethod() == /.equals(var)) {
        listName.add(new classA(para1, para2, ...));
    }
}

Remove元素要倒序遍历，否则会跳过元素！

for(int i=listName.size()-1; i>=0; i--) {
    if(listName.get(i).getMethod() == /.equals(var)) {
        listName.remove(i);
    }
}

• 返回极值

int minIndex = 0;
type minValue = listName.get(0).getMethod();
for(int i=0; i<listName.size(); i++) {
    if(listName.get(i).getMethod() < minValue) {
        minIndex = i;
    }
}
return listName.get(minIndex).getMethod();

Ex2：

public class StudentAnswerSheet {
    private ArrayList<String> answers;
    
    public double getScore(ArrayList<String> key)
    
    public String getName()
}

public class TestResults {
    private ArrayList<StudentAnswerSheet> sheets;
    
    public String highestScoringStudent(ArrayList<String> key)
}

a) Write the StudentAnswerSheet method getScore. The parameter passed to method getScore is an ArrayList of strings representing the correct answer key for the test being scored. The method computes and returns a double that represents the score for the student's test answers when compared with the answer key. One point is awarded for each correct answer and . of a point is deducted for each incorrect answer. Omitted answers (indicated by"?") do not change the student's score.

思路：循环answer里所有元素，与key的对应元素进行比较

public double getScore(ArrayList<String> key)
{
    double score = 0.0;
    for (int i = 0; i < answers.size(); i++) {
        if (answers.get(i).equals(key.get(i))) {
            score += 1.0;
        } else if (!answers.get(i).equals("?")) {
            score -= 0.25;
        }
    }
    return score;
}

b) Consider the following class that represents the test results of a group of students that took a multiple-choice test.

public String highestScoringStudent(ArrayList<String> key)
{
    StudentAnswerSheet highest = sheets.get(0);
    for (StudentAnswerSheet sheet : sheets) {
        if (sheet.getScore(key) > highest.getScore(key)) {
            highest = sheet;
        }
    }
    return highest.getName();
}

Ex3.

1D Array/ArrayList elements to 2D Array

方法：遍历2D Array，循环里更新1D Array的index

FRQ-2

public SeatingChart(ArrayList<Student> studentList, int rows, int cols)
{
    seats = new Student[rows][cols];

    int sIndex = 0;

    for(int c = 0; c < seats[0].length; c++)
    {
        for(int r = 0; r < seats.length; r++)
        {
            if(sIndex < studentList.size())
            {
                seats[r][c] = studentList.get(sIndex);
                sIndex++;
            }
        }
    }
}

public int removeAbsentStudents(int allowedAbsences)
{
    int removed = 0;
    for(int r = 0; r < seats.length; r++)
    {
        for(int c = 0; c < seats[0].length; c++)
        {
            if(seats[r][c] != null && seats[r][c].getAbsenceCount() > allowedAbsences)
            {
                seats[r][c] = null;
                removed++;
            }
        }
    }

    return removed;
}

Ex4. FRQ4

public void addReview(ProductReview prodReview)
{
    reviewList.add(prodReview);
    String prodName = prodReview.getName();
    boolean found = false;

    for(int i=0; i<productList.size(); i++) {
       if(productList.get(i).equals(prodName)) found = true;
    }
    if(!found) prodList.add(prodName);
	
}

public int getNumGoodReviews(String prodName) {
    int result = 0;
    for (ProductReview pr: reviewList) {
        if(prodName.equals(pr.getName())) {
            String review = pr.gerReview();
            if(review.indexOf("best") >=0) result++;
        }
    }
    return result;
}

2D Array

Ex1. Put all elements of a single row/column to 1D Array

public static int[] rowToArray(int[][] 2d, row){
    int[] result = new int[2d[0].length];
    result = 2d[row];
    return result;
}

public static int[] colToArray(int[][] 2d, col){
    int[] result = new int[2d.length];
    for(int i=0; i<2d.length; i++) {
        result[i] = 2d[i][col];
    }
    return result;
}

Ex2. A square is labeled with a positive number if and only if:

• the square is white and

• the square does not have a white square immediately above it, or it does not have a white square immediately to its left, or both.

The squares identified by these criteria are labeled with consecutive numbers in row-major order, starting at 1.

要注意边界问题！

• 行号最大值是arr2D.length-1

• 列号最大值是array[0].length-1

• row[0]没有upper元素

• col[0]没有left元素

• row[arr.length-1]没有down元素

• col[arr[0].length-1]没有right元素

(a) Write the Crossword method toBeLabeled. The method returns true if the square indexed by row r, column c in a crossword puzzle grid should be labeled with a positive number according to the crossword labeling rule; otherwise it returns false. The parameter blackSquares indicates which squares in the crossword puzzle grid are black.

public boolean toBeLabeled(int r, int c) {
    // Check if the square is black.
    if (blackSquares[r][c]) {
        return false;
    }
    // Check if it's the first row or column.
    if (r == 0 || c == 0) {
        return true;
    }
    // Check if there's no white square immediately above or to the left.
    if (blackSquares[r-1][c]) || blackSquares[r][c-1]) {
        return true;
    }
    return false;
}

Ex3.

FRQ-3

注意边界！

public double computeTemp(int row, int col) {

    if ((row == 0 || row == temp.length - 1) || (col == 0 || col == temp.length - 1)) {
        return temp[row][col];
    }
    else {
        return (temp[row - 1][col - 1] + temp[row][col - 1] + temp[row + 1][col] + temp[row][col + 1]) / 4.0;
    }
}

public boolean updateAllTemps(double tolerance) {
    double[][] newTemp;
    boolean isTolerence = true;

    for (int row = 0; row < temp.length; row++) {
        for (int col = 0; col < temp[row].length; col++) {
            newTemp[row][col] = computeTemp(row, col); //elements unchanged
            if (Math.abs(temp[row][col] - newTemp[row][col]) > tolerance) {
                isTolerence = false;
            }
        }
    }
   temp = newTemp;
   return isTolerence;
}

Ex4.

Traverse all elements of 2D Arrays

Given a String 2D Arrays , return a new 2D Array, which contains the length of each corresponding element. The size of the new array should be the same as the given array.

public int[][] lenOfStrings(String[][] 2d) {
    int[][] result = new int[2d.length][2d[0].length];
    
    for(int i=0; i<2d.length; i++) {
        for(int j=0; j<2d[0].length; j++) {
            result[i][j] = 2d[i][j].length();
        }
    }
    
    return result;
}