笔试算法题一共是有4道，第一道是手搓模拟实现一个ArrayList，第二道是判断字符串是否回文，第三道是用代码实现1到2种设计模式。

目录

一.模拟实现ArrayList

二.判断字符串是否回文

▐ 解法一

▐ 解法二

▐ 解法三

三.代码实现设计模式

---

一.模拟实现ArrayList

首先，要实现一个ArrayList就必须得知道ArrayList有哪些方法，他相较于别的数据结构有什么特性。

顺序表是一种线性数据结构，是数据元素按照线性顺序存储的数据结构，通常使用数组实现。顺序表中的元素以一定的顺序排列，每个元素都可以通过下标来进行访问。顺序表支持随机访问，可以快速地访问任意一个元素，但插入或删除元素时需要移动其余元素，效率较低。

这是ArrayList的API文档：ArrayList - Java17中文文档

我们可以基于数组实现ArrayList

    public int[] arr;//使用数组来实现ArrayList
    public int usedSize;//
    public static final int DEFAULT_SIZE = 10;

有了基础的数据结构以后，我们就可以通过其中的 usedSize 和 arr 灵活的去操作顺序表。

对于ArrayList我们至少要实现以下的一些功能

public interface Ilist {
    // 新增元素,默认在数组最后新增
    public void add(int data);
    // 在 pos 位置新增元素
    public void add(int pos, int data);
    // 判定是否包含某个元素
    public boolean contains(int toFind);
    // 查找某个元素对应的位置
    public int indexOf(int toFind);
    // 获取 pos 位置的元素
    public int get(int pos);
    // 给 pos 位置的元素设为 value
    public void set(int pos, int value);
    //删除第一次出现的关键字key
    public void remove(int toRemove);
    // 获取顺序表长度
    public int size();
    // 清空顺序表
    public void clear();
}

对应上述的接口，可以按照如下实现 

import java.util.Arrays;

public class MyArrayList implements Ilist {
    public int[] arr;
    public int usedSize;
    public static final int DEFAULT_SIZE = 5;
    
    public MyArrayList() {
        arr = new int[DEFAULT_SIZE];
    }
    
    public void display() {
        for (int x : arr) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
    
    // 新增元素,默认在数组最后新增
    public void add(int data) {
        //判断满了之后要扩容
        if (arr.length == usedSize) {
            arr = Arrays.copyOf(arr, DEFAULT_SIZE * 2);
        }
        arr[usedSize] = data;
        usedSize++;
    }
    
    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        cheakPos(pos);
        //判断满了之后要扩容
        if (arr.length == usedSize) {
            arr = Arrays.copyOf(arr, DEFAULT_SIZE * 2);
        }
        //移动元素留出空位
        for (int i = usedSize - 1; i >= pos; i--) {
            arr[i + 1] = arr[i];
        }
        arr[pos] = arr[pos - 1];
        //给pos位置元素赋值
        arr[pos - 1] = data;
        usedSize++;
    }
    
    // 判定是否包含某个元素
    public boolean contains(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if (arr[i] == toFind)
                return true;
        }
        return false;
    }
    
    // 查找某个元素对应的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if (arr[i] == toFind)
                return i + 1;
        }
        return -1;
    }
    
    // 获取 pos 位置的元素
    public int get(int pos) {
        //检查输入位置是否合法
        cheakPos(pos);
        //检查顺序表是否为空
        cheakEmpty();
        return arr[pos];
    }
    
    // 给 pos 位置的元素设为 value
    public void set(int pos, int value) {
        //检查输入位置是否合法
        cheakPos(pos);
        //检查顺序表是否为空
        cheakEmpty();
        arr[pos-1] = value;
    }
    
    //删除第一次出现的关键字key
    public void remove(int toRemove) {
        //检查顺序表是否为空
        cheakEmpty();
        int delPos = indexOf(toRemove);
        for (int i = delPos; i < usedSize; i++) {
            arr[i-1] = arr[i];
        }
        arr[usedSize-1] = arr[usedSize];
        usedSize--;
    }
    
    // 获取顺序表长度
    public int size() {
        //检查顺序表是否为空
        cheakEmpty();
        return usedSize;
    }
    
    // 清空顺序表
    public void clear() {
        usedSize = 0;
    }
    
    private void cheakPos(int pos) {
        if (pos < 0 || pos > usedSize)
            throw new ExceptionOfPos("pos位置不能为：" + pos);
    }
    
    private void cheakEmpty() {
        if (usedSize == 0)
            throw new ExceptionOfEmpty("当前顺序表为空，无法操作");
    }
}

最后俩个自定义异常用来处理 pos 位置非法和顺序表为空。 

---

二.判断字符串是否回文

这道题目在leetcode上也是有资源的，这里将链接给出：LCR 018. 验证回文串 - 力扣（LeetCode）

给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。本题中，将空字符串定义为有效的 回文串 。

示例 1:

输入: s = "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

示例 2:

输入: s = "race a car"
输出: false
解释："raceacar" 不是回文串

▐ 解法一

可以采用双指针法，设置俩个指针分别指向字符串的首个和末尾元素，然后利用他们挨个遍历比较。

首先将原有的字符串去除大写，通过 toLowerCase 将原字符串全部转化为小写，并且通过 replaceAll 利用正则表达式将所有的非字母非数字的元素全部删除掉，然后就得到了一个不包含其他字符的字符串。

在得到这么一个字符串后，为了方便我们遍历其中的每个元素，我们可以将这个字符串转化为字符数组，然后定义一个左右双指针来遍历整个数组，如果在其中某一个步骤首尾元素不相同，我们就直接返回 false 。正常情况则继续遍历下一轮，最后得出结论。

class Solution {
    public boolean isPalindrome(String s) {
        s= s.toLowerCase().replaceAll("[^a-z0-9]", "");
        char[] charArray = s.toCharArray();
        int first = 0;
        int last = charArray.length - 1;
        while (first <= last) {
            if (charArray[first] != charArray[last]) {
                return false;
            }
            first++;
            last--;
        }
        return true;
    }
}

▐ 解法二

我们可以采取直接对比原字符串和该字符串的镜像字符串，如果他们相同，则说明他们是回文串。

要实现这样的对比，首先第一步要做的还是对字符串的过滤，需要将其中的特殊字符和大小写过滤掉，为了方便操作，我们使用 StringBuffer 来进行字符串的拼接操作，我们对字符串的每一个字符都进行判断，只有该字符是字母和数字的时候才将其放入 StringBuffer 进行拼接。

最后对于得到的完整字符串，我们再调用 reverse 方法对齐进行镜像的反转，然后将俩个字符串对比得出结论。

class Solution {
    public boolean isPalindrome(String s) {
        // 创建一个StringBuffer对象来存储处理后的字符
        StringBuffer buffer = new StringBuffer();
        // 遍历输入字符串
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 仅当字符是字母或数字时才将其加入 buffer
            if (Character.isLetterOrDigit(c)) {
                buffer.append(Character.toLowerCase(c));
            }
        }
        // 创建一个新的StringBuffer对象，它是buffer的反转
        StringBuffer rebuffer = new StringBuffer(buffer).reverse();
        // 检查rebuffer和buffer是否相等
        return buffer.toString().equals(rebuffer.toString());
    }
}

▐ 解法三

同样是使用双指针法，但不同的是我们这一次直接对原字符串进行操作，这样就可以避免浪费额外的空间去存储中间步骤。

对于双指针的基本概念这里就不再赘述，在判断的时候需要对于每一步的字符进行额外的判断，每一个步骤都要保证左指针小于右指针，并且俩个指针指向的元素必须是字母和数字。

在对俩个字符比较的时候需要调用 toLowerCase 屏蔽大小写差异。

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            //保证左指针的指向始终为需要判断的字母和数字
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            //保证右指针的指向始终为需要判断的字母和数字
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            if (left < right) {
                //如果左指针和右指针指向的字母不同，则直接返回false
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }//左右指针指向的元素相同，则进行下一次判断
                left++;
                right--;
            }
        }
        return true;
    }
}

---

三.代码实现设计模式

单例模式：确保一个类只有一个实例，并提供一个全局访问点。

public class Singleton {
    private static Singleton instance;
    
    private Singleton() {}

    public static synchronized Singleton getInstance() {
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
}

工厂模式：定义一个创建对象的接口，但让子类决定实例化哪一个类。工厂方法让类的实例化推迟到子类。

public interface Product {
    void use();
}

public class ConcreteProductA implements Product {
    public void use() {
        System.out.println("Using Product A");
    }
}

public class ConcreteProductB implements Product {
    public void use() {
        System.out.println("Using Product B");
    }
}

public abstract class Factory {
    public abstract Product createProduct();
}

public class ConcreteFactoryA extends Factory {
    public Product createProduct() {
        return new ConcreteProductA();
    }
}

public class ConcreteFactoryB extends Factory {
    public Product createProduct() {
        return new ConcreteProductB();
    }
}

观察者模式：定义对象间的一对多依赖，当一个对象改变状态时，所有依赖的对象都会收到通知并自动更新。

import java.util.ArrayList;
import java.util.List;

public interface Observer {
    void update(String message);
}

public class ConcreteObserver implements Observer {
    private String name;

    public ConcreteObserver(String name) {
        this.name = name;
    }

    public void update(String message) {
        System.out.println(name + " received: " + message);
    }
}

public interface Subject {
    void attach(Observer observer);
    void detach(Observer observer);
    void notifyObservers();
}

public class ConcreteSubject implements Subject {
    private List<Observer> observers = new ArrayList<>();
    private String message;

    public void attach(Observer observer) {
        observers.add(observer);
    }

    public void detach(Observer observer) {
        observers.remove(observer);
    }

    public void notifyObservers() {
        for (Observer observer : observers) {
            observer.update(message);
        }
    }

    public void setMessage(String message) {
        this.message = message;
        notifyObservers();
    }
}

---

---

---

 本次的分享就到此为止了，希望我的分享能给您带来帮助，创作不易也欢迎大家三连支持，你们的点赞就是博主更新最大的动力！如有不同意见，欢迎评论区积极讨论交流，让我们一起学习进步！有相关问题也可以私信博主，评论区和私信都会认真查看的，我们下次再见