设计模式-模板方法模式

发表于 2022-03-02 | 分类于设计模式 |

字数统计: 205

模板方法模式

定义：定义一个操作的算法骨架，将一些操作延迟到子类实现。Template Method使得子类可以在不改变算法结构的基础上即可重新定义算法的某些特定步骤

其实该模式很简单，就是定义一个抽象类，然后定义一个抽象方法给子类去实现。

处理器

public abstract class Handler {
    public void operation(){
        System.out.println("做前期准备");
        System.out.println("准备就绪，开始处理");
        doHandler();
        System.out.println("处理完毕");
    }

    abstract void doHandler();
}

字符处理器

public class CharHandler extends Handler{
    @Override
    void doHandler() {
        System.out.println("将字符串转化");
    }
}

字符串处理器

public class StringHandler extends Handler{
    @Override
    void doHandler() {
        System.out.println("字符串转化");
    }
}

设计模式-策略模式

发表于 2022-03-02 | 分类于设计模式 |

字数统计: 797

策略模式

定义：定义了算法族，分别封装起来，让他们之间可以互相替换，此模式的变化独立于算法的使用者

有一个电商平台，当用户消费满1000元，根据vip等级可享受优惠

普通会员不打折
白银会员优惠50元
黄金会员打8折
白金会员优惠50元，再打七折

Version 1.0

会员类型枚举

public enum UserType {
    /**
     * ORDINARY_VIP: 普通会员
     * SILVER_VIP: 白银会员
     * GOLD_VIP： 黄金会员
     * PLATINUM_VIP：白金会员
     */
    ORDINARY_VIP(1),
    SILVER_VIP(2),
    GOLD_VIP(3),
    PLATINUM_VIP(4);
    private int code;
    UserType(int code) {
        this.code = code;
    }

    public int getCode() {
        return code;
    }
}

private static double getResult(long money, int type){
    double result = money;
    if(money >= 1000){
        if(type == UserType.SILVER_VIP.getCode()){
            result = money - 50;
        }else if(type == UserType.GOLD_VIP.getCode()){
            result = money * 0.8;
        }else if(type == UserType.PLATNUM_VIP.getCode()){
            result = (money - 50)*0.7;
        }
    }
    return result;
}

下面使用策略模式来优化

Version 1.2

策略接口

1
2
3

public interface Strategy {
    double compute(long money);
}

普通会员

public class OrdinaryStrategy implements Strategy{
    @Override
    public double compute(long money) {
        return money;
    }
}

黄金会员

public class GoldStrategy implements Strategy{
    @Override
    public double compute(long money) {
        return money*0.8;
    }
}

白金会员

public class PlatinumStrategy implements Strategy{
    @Override
    public double compute(long money) {
        return (money-50)*0.7;
    }
}

白银会员

public class SilverStrategy implements Strategy{
    @Override
    public double compute(long money) {
        return money-50;
    }
}

public static double getResult(long money,int type){
    double result = money;
    if(money<1000){
        return result;
    }
    if(type== UserType.ORDINARY_VIP.getCode()){
        result = new OrdinaryStrategy().compute(money);
    }else if(type == UserType.SILVER_VIP.getCode()){
        result = new SilverStrategy().compute(money);
    }else if(type == UserType.GOLD_VIP.getCode()){
        result = new GoldStrategy().compute(money);
    }else if(type==UserType.PLATINUM_VIP.getCode()){
        result = new PlatinumStrategy().compute(money);
    }
    return result;
}

Version 2.1

public class StrategyFactory {
    public static Map<Integer,Strategy> map;
    private StrategyFactory(){
        map = new HashMap<>();
        init();
    }
    private void init(){
        map.put(UserType.ORDINARY_VIP.getCode(), new OrdinaryStrategy());
        map.put(UserType.SILVER_VIP.getCode(), new SilverStrategy());
        map.put(UserType.GOLD_VIP.getCode(),new GoldStrategy());
        map.put(UserType.PLATINUM_VIP.getCode(),new PlatinumStrategy());
    }
}

public static double getResult(int userType, long money){
    if(money<1000){
        return money;
    }
    if(StrategyFactory.map.get(userType)==null){
        throw new IllegalArgumentException("参数错误，无此类型的用户");
    }
    return map.get(userType).compute(money);
}

这里的工厂还可以通过这种方式来实现

Version 2.2

策略接口

public interface Strategy {
    double compute(long money);
    int getType();
}

黄金会员

public class GoldStrategy implements Strategy {
    @Override
    public double compute(long money) {
        return money*0.8;
    }

    @Override
    public int getType() {
        return UserType.GOLD_VIP.getCode();
    }

}

普通会员

public class OrdinaryStrategy implements Strategy {
    @Override
    public double compute(long money) {
        return money;
    }

    @Override
    public int getType() {
        return UserType.ORDINARY_VIP.getCode();
    }
}

白金会员

public class PlatinumStrategy implements Strategy {
    @Override
    public double compute(long money) {
        return (money-50)*0.7;
    }

    @Override
    public int getType() {
        return UserType.PLATINUM_VIP.getCode();
    }
}

白银会员

public class SilverStrategy implements Strategy {
    @Override
    public double compute(long money) {
        return money-50;
    }

    @Override
    public int getType() {
        return UserType.SILVER_VIP.getCode();
    }
}

策略工厂

public class StrategyFactory {
    private static Map<Integer, Strategy> map;

    public StrategyFactory() {
        map=new HashMap<>();
        init();
    }
    private void init() {
        List<Strategy> strategies=new ArrayList<>();
        strategies.add(new GoldStrategy());
        strategies.add(new OrdinaryStrategy());
        strategies.add(new PlatinumStrategy());
        strategies.add(new SilverStrategy());
        map=strategies.stream().collect(Collectors.toMap(Strategy::getType,strategy -> strategy));
    }
}

public static double getResult(int userType, long money){
    if(money<1000){
        return money;
    }
    if(StrategyFactory.map.get(userType)==null){
        throw new IllegalArgumentException("参数错误，无此类型的用户");
    }
    return map.get(userType).compute(money);
}

算法-二分查找的多种写法

发表于 2022-03-02 | 分类于算法，技巧篇 |

字数统计: 2.2k

二分查找

二分查找作为数组的基操，肯定是要牢牢掌握的，其思想十分简单，但是对于细节的处理，就可以看出你对二分算法的理解深刻与否。

如果没有真正的理解细节处的内涵，二分查找算法的编写就是玄学编写，这里加不加等号呢？这里是+1还是不变呢？最后该返回啥呢？

接下来我们就来看看这些细节该如何处理

下面使用三个二分查找使用的场景做出分析：寻找一个数、寻找左侧边界、寻找右侧边界

二分查找的骨架

public int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = ..;// nums.length-1还是nums.length
    int mid;
    while(left..right){// <=还是<
        mid = (left + right) >> 1;// (right - left) / 2 + left(left + right) >> 1还是 (right + left) / 2
        if(nums[mid] == target){
            .. = ..; // right还是left  mid-1还是mid
        }else if(target < nums[mid]){
            right = ..; // mid-1还是mid
        }else {
            left = ..; // mid+1 
        }
    }
    return ..;// left或者要做什么处理
}

或许你经常看见一些代码不会将等于的情况单独列出来，但是我觉得对于二分查找的分析，将等于的情况单独分离出来，会更有利于理解

等到彻底理解后，随便怎么写都不会少搜索区间的时候，那就随便合并语句了

上述骨架中..出现的地方就是我们需要去琢磨的细节之处了，乍一看，全是细节，所以叫魔鬼细节探究

先解决最好解决的一个细节

很多人都在LeetCode官网中看到有时候官网对于中间值的取值

有时候会使用(right - left) / 2 + left

有时候会使用(left + right) >> 1

有时候看见别人写的代码中又是(right + left) / 2，肯定会很迷糊，这三者的计算到底有什么不同之处呢？

(right - left) / 2 + left这种写法是为了防止(left+right)因为数据过大导致溢出，导致mid计算错误，

(left + right) >> 1这是位运算，处理效率会高一点

(right + left) / 2这就是正常写法，一般也不会出错

接下来按照二分查找的常见使用场景来逐个做出分析

查找一个数

场景1：查找一个数，存在返回索引，不存在返回-1

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1;
    int mid;
    // [left,right]
    while(left <= right) {
        mid = left + (right - left) / 2;
        if(nums[mid] == target){
            return mid; 
        }
        else if (nums[mid] < target){
            left = mid + 1; 
        }
        else if (nums[mid] > target){
            right = mid - 1; 
        }
    }
    return -1;
}

循环条件是left <= right而不是left < right？

这里我们要说一下什么时候应该退出循环，就是当我所有的元素都搜索完成之后（即搜索区间里面没有元素的时候），或者是找到了目标值的时候可以直接终止，返回结果。

当right赋值为nums.length - 1，则搜索区间为[left,right]，所有元素搜索完成的条件应该是left==right+1，即搜索区间为[right+1,right]，符合要求。如果循环退出条件改为 left<right，则退出循环的时候，搜索区间为[left,right]，会缺少搜索第left个元素，不符合要求

如果**right赋值为nums.length**，则搜索区间为[left,right)，所有元素搜索完成的条件应该是left==right，即搜索区间为[left,right)

当nums[mid] > target的时候，为什么是right = mid - 1; 而不是right = mid; ？

还是回到搜索区间的问题上，当我发现当前这个元素与target不等而是大于target，那么我只需要搜索左边区间，即将[left,right]分割为左边区间[left,mid-1]和右边区间[mid+1,right]，所以下一步应该将mid-1赋值给right

此算法的用途

这种方法只可以在找到目标值的情况下返回索引，但是当nums为[1,2,2,2,4]的时候，返回的值是2，没错，但是这样可能就无法满足我们的需求了，只能在数组是严格递增的情况下使用。

如果场景变为：查找一个数，如果找到则返回索引位置，如果找不到，则返回目标值插入数组的位置

这个时候其实只要最后返回left即可

返回左边界

int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int mid;
    // [left,right]
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    if (left >= nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}

为什么最后返回的时候要做出判断？

当目标元素比所有的值都小的时候，在最后一次循环的时候，right = mid - 1，left此时为0，但是无法确定该元素是否为目标元素，所以需要做出判断，

当目标元素比所有的值都大的时候，在最后一次循环的时候，left= mid + 1，left此时为数组长度，这时候则说明，该元素在此数组中不存在，也要做出判断

为什么找到的一定是左边界？

因为这一段代码

1
2
3

if(nums[mid] == target){
    right= mid - 1;
}

当数组元素等于目标元素的时候，不着急返回，而是缩小查找范围。因为需要查找左边界，所以需要向左边收缩区间

这里面while的循环条件可以改为left < right吗？

当然可以，只要理解了搜索区间，只要能够保证所有的元素都被查找了，怎么写都可以。

int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    int mid;
    while (left < right) {
        mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    // 如果target毕nums所有的值都小，则right会变成-1,left就是0
    // 如果target比nums所有的值都大，则left会变成nums.length，right就是nums.length-1
    if (left == nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}

当目标元素比所有的值都大的时候，在最后一次循环的时候，left= mid + 1，left此时为数组长度，这时候则说明，该元素在此数组中不存在，需要单独做出判断

当目标元素比所有的值都小的时候，在最后一次循环的时候，right = mid ，left此时为0，但是无法确定该元素是否为目标元素，所以需要做出判断，

返回右边界

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1;
    int mid;
    while(left <= right) {
        mid = left + (right - left) / 2;
        if(nums[mid] == target){
            left = mid + 1;
        }
        else if (nums[mid] < target){
            left = mid + 1; 
        }
        else if (nums[mid] > target){
            right = mid - 1; 
        }
    }
    // 如果target比nums中所有元素都大，left在nums.length,right在nums.length-1
    // target比nums所有元素都小，left在0，right是-1
    if (left == 0 || nums[left - 1] != target) {
        return -1;
    }
    return left - 1;
}

为什么最后返回的时候要做出判断？

当目标元素比所有的值都小的时候，在最后一次循环的时候，right = mid - 1，left此时为0，但是无法确定该元素是否为目标元素，所以需要做出判断，

为什么找到的一定是右边界？

因为这一段代码

1
2
3

if(nums[mid] == target){
    left = mid + 1;
}

当数组元素等于目标元素的时候，不着急返回，而是缩小查找范围。因为需要查找右边界，所以需要向右边收缩区间

如何修改循环条件为left < right？

int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length;
    int mid;
    while (left < right) {
        mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    // 当target比数组中所有元素都小的时候，right和left都走到了0的位置
    // 这时候这说明，数组中不存在target元素，直接返回0
    if (left == 0) {
        return -1;
    }
    // 当target比数组所有元素都大的时候，right和left都走到了数组长度的位置，
    // 如果数组最后一个元素不是这说明数组中没有target元素
    if (nums[left - 1] != target) {
        return -1;
    }
    return left - 1;
}

【34-Medium】在排序数组中查找元素的第一个和最后一个位置

发表于 2022-03-01 | 分类于算法，刷题篇 |

字数统计: 300

在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

1 2	输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

示例 2：

1 2	输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]

示例 3：

1 2	输入：nums = [], target = 0 输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

Related Topics

数组
二分查找

二分查找

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = binarySearch(nums, target);
        if (first == -1) {
            return new int[]{-1, -1};
        }
        return new int[]{first, binarySearch(nums, target + 1) - 1};
    }

    private int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) >> 1;
            if (nums[mid] == target) {
                right = mid - 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

设计模式-装饰者模式

发表于 2022-03-01 | 分类于设计模式 |

字数统计: 261

装饰者模式

定义：在不改变原有对象的基础上，将功能附加到对象上

这个其实大家在平时写代码的时候就已经用过了，只是不知道这是一个模式

下面看一个案例

有一个组件的接口，然后我有一个具体的实现类，现在我需要在这个具体实现类的基础上进行功能拓展

组件接口

1
2
3

public interface Component {
    void operation();
}

具体接口实现

public class ConcreteComponent implements Component{
    @Override
    public void operation() {
        System.out.println("实现组件功能");
    }
}

拓展功能抽象类

public abstract class EnhanceComponent implements Component{
    protected Component component;

    public EnhanceComponent(Component component) {
        this.component = component;
    }

}

具体增强类

public class ConcreteEnhanceComponent extends EnhanceComponent{
    public ConcreteEnhanceComponent(Component component) {
        super(component);
    }
    @Override
    public void operation() {
        component.operation();
        System.out.println("拓展功能一");
    }
}

优点：

不改变原有代码的情况下，对原来的类进行增强
使用不同的组合可以实现不同的人效果
符合开闭原则

设计模式-适配器模式

发表于 2022-03-01 | 分类于设计模式 |

字数统计: 385

适配器模式

定义：将一个类的接口转换为用户希望的另一个接口。这使得原本由于接口不兼容而不能一起工作的那些类就可以一起工作了

接下来我们来模拟USB转接网线口，从而使电脑上网的案例

网线接口

1
2
3

public interface NetWorkThread {
    void connectNetWork();
}

华为的网线

public class HuaWeiNetWorkThread implements NetWorkThread{
    @Override
    public void connectNetWork() {
        System.out.println("华为网线连接网络，可以上网了");
    }
}

自制的网线

public class CustomerNetWorkThread implements NetWorkThread{
    @Override
    public void connectNetWork() {
        System.out.println("自制网线，可以上网了");
    }
}

适配器（网线口变为USB口）

1
2
3

public interface Adapter {
    void netWorkToUSB();
}

华为的适配器（转接口）

public class HuaWeiAdapter implements Adapter{
    private NetWorkThread netWorkThread;

    public void setNetWorkThread(NetWorkThread netWorkThread) {
        this.netWorkThread = netWorkThread;
    }

    @Override
    public void netWorkToUSB() {
        if(netWorkThread==null){
            System.out.println("适配器没有网线插入！");
            return;
        }
        System.out.println("华为适配器适配了网线");
        netWorkThread.connectNetWork();
    }
}

电脑

public class Computer {
    private Adapter adapter;

    public void setAdapter(Adapter adapter) {
        this.adapter = adapter;
    }

    public void connectToNetWork(){
        if(adapter!=null){
            adapter.netWorkToUSB();
        }else {
            System.out.println("没有插网线！");
        }
    }
}

客户端

public class Client {
    public static void main(String[] args) {
        Computer computer = new Computer();
        computer.connectToNetWork();
        System.out.println("===================");
        HuaWeiAdapter huaWeiAdapter = new HuaWeiAdapter();
        computer.setAdapter(huaWeiAdapter);
        computer.connectToNetWork();
        System.out.println("===================");
        huaWeiAdapter.setNetWorkThread(new HuaWeiNetWorkThread());
        computer.connectToNetWork();
    }
}

控制台输出

没有插网线！
===================
适配器没有网线插入！
===================
华为适配器适配了网线
华为网线连接网络，可以上网了

【5-Medium】最长回文数

发表于 2022-02-28 | 分类于算法，刷题篇 |

字数统计: 1.5k

最长回文数

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

1
2
3

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1 2	输入：s = "cbbd" 输出："bb"

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

Related Topics

字符串
动态规划

法一：暴力枚举

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() < 2){
            return s;
        }
        char[] chars = s.toCharArray();
        int begin = 0;
        int end = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            for (int j = i+1 ; j < s.length(); j++) {
                if((j - i + 1) > (end - begin + 1) && isValid(chars,i,j)){
                    begin = i;
                    end = j;
                }
            }
        }
        return s.substring(begin, end+1);
    }

    private boolean isValid(char[] chars, int left, int right) {
        while(left < right){
            if(chars[left] != chars[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

法二：中心扩散

将每”一位”作为中心向两边扩撒，

每次扩散分两种情况，

第一种情况是以当前那一位为中心向两边扩散

第二种情况是以当前那一位和下一位为中心向两边扩散

取这两种情况的最值max

如果max比maxLen大的话，计算得出begin‘

最后直接返回截取的字符串

这是我的解法

class Solution {
    public String longestPalindrome(String s){
        if (s.length() < 2) {
            return s;
        }
        int begin = 0;
        int maxLen = 1;
        for (int i = 0; i < s.length(); i++) {
            int max = Math.max(expand(s,i,i),expand(s,i,i+1));
            if(max > maxLen){
                maxLen = max;
                begin = i - (max - 1)/2;
            }
        }
        return s.substring(begin, maxLen+begin);
    }

    public int expand(String s, int left, int right) {
        while(left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return right - left - 1;
    }
}

这是官方的解法


class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
}

法三：动态规划

对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。

例如对于字符串 “ababa’”，如果我们已经知道 “bab” 是回文串这层关系，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是a

使用dp[][]二位数组来存储这层关系

即使用dp[i][j]来表示s字符串的i到j是否是回文数

如果当前要判断的范围是dp[left][right]，字符串长度为x

第一步先看首尾是否一致，

如果不一致，则dp[left][right]直接为false，

如果一致，则进入下一步判断

如果当前判断的字符串长度小于3

为什么是3呢？

如果长度为1，则本身就是字符串，形成自回文

如果长度为2，则首尾一致的情况下，可以直接判断为回文

如果长度为3，则首尾一致的情况下，也可以直接判断回文

这三组数据是后面做判断的支撑

则直接将dp[left][right]赋值为true

反之将dp[left+1][right-1]（即去掉首尾的时候是否为回文数）的回文结构赋值给dp[i][j]

这些结束后，当dp[left][right]是true时，

则将当前循环长度和存储的maxLen进行比较，

如果当前循环长度较大，则将其赋值给maxLen，将left赋值给begin

反之，直接进行下一次循环

官方代码：

public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

下面是我理解思路后写的

对于变量的命名更贴近其本身的含义

可能会更好理解一点

public String longestPalindrome1(String s) {
    int len = s.length();
    if(len < 2){
        return s;
    }
    int begin = 0;
    int maxLen = 1;
    char[] chars = s.toCharArray();
    boolean[][] dp = new boolean[len][len];
    // dp[i][j]即表示s[i..j]是否为回文数
    // 对角线即为每个字符本身那就可以直接初始化为true
    // 也可以不初始化这个，但是为了语义完整，最好还是加上
    for (int i = 0; i < len; i++) {
        dp[i][i] = true;
    }
    //x表示长度，从长度为2开始，因为长度为1的情况可以直接判断
    for (int x = 2 ; x <= len; x++) {
        //循环次数为总长度减当前循环的长度再加一
        for (int left = 0; left < len - x + 1; left++) {
            //x=right-left+1
            int right = x + left - 1;
            if(chars[left] != chars[right]){
                dp[left][right] = false;
            }else {
                if(x < 4){
                    dp[left][right] = true;
                }else {
                    dp[left][right] = dp[left+1][right-1];
                }
            }
            if(dp[left][right] && x > maxLen){
                begin = left;
                maxLen = x;
            }
        }
    }
    return s.substring(begin, maxLen+begin);
}

关于权限修饰符protected

发表于 2022-02-28 | 分类于琐碎的知识 |

字数统计: 1.2k

权限修饰符

我们先回顾一下java中的权限修饰符

权限修饰符	同类	同包	子类	其他包
public	√	√	√	√
protected	√	√	√	×
default	√	√	×	×
private	√	×	×	×

对于public和private大家都很了解了，但是对于protected，大家可能对它的概念可能就一句话：被protected修饰的成员对于本包和其子类可见。

该权限修饰符的关键是

基类的protected成员属性是包内可见的，并且对所有子类可见
若子类与基类不在同一包下，则在子类中，子类实例可以访问从基类继承来的protected方法，而不能访问基类实例的protected方法

遇到protected

首先思考这个protected来自何方

接着看其和这个地方是不是同包

最后看其是否有父子类关系

可以通过以下几个Test来掌握protected的用法

注意：观察包限定名

模型

package com.lizhi.protect.p1;

public class Feather1 {
    protected void f(){}

    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone();
    }
}

package com.lizhi.protect.p1;

public class Son1 extends Feather1{
}

package com.lizhi.protect.p11;

import com.lizhi.protect.p1.Feather1;

public class Son11 extends Feather1 {
}

测试

package com.lizhi.protect.p1;

import com.lizhi.protect.p11.Son11;

public class Test {
    public static void main(String[] args) throws CloneNotSupportedException {
        Feather1 feather1 = new Feather1();
        Son1 son1 = new Son1();
        Son11 son2 = new Son11();
        son1.f();//编译通过，因为该测试类与Feather1处于同一包下
        son1.clone();//编译通过，因为该测试类与Feather1处于同一包下
        son2.f();//编译通过，因为该测试类与Feather1处于同一包下
        son2.clone();//编译通过，因为该测试类与Feather1处于同一包下
        feather1.f();//编译通过，因为该测试类与Feather1处于同一包下
        feather1.clone();//编译通过，因为该测试类与Feather1处于同一包下
    }
}

测试

package com.lizhi.protect.p11;

import com.lizhi.protect.p1.Feather1;
import com.lizhi.protect.p1.Son1;
import com.lizhi.protect.p11.Son11;

public class Test {
    public static void main(String[] args) throws CloneNotSupportedException {
        Feather1 feather1 = new Feather1();
        Son1 son1 = new Son1();
        Son11 son2 = new Son11();
        son1.f();//编译不通过，因为该测试类与Feather1处于不同一包下，该类也不是Feather1的子类
        son1.clone();//编译不通过，因为该测试类与Feather1处于不同一包下，该类也不是Feather1的子类
        son2.f();//编译不通过，因为该测试类与Feather1处于不同一包下，该类也不是Feather1的子类
        son2.clone();//编译不通过，因为该测试类与Feather1处于不同一包下，该类也不是Feather1的子类
        feather1.f();//编译不通过，因为该测试类与Feather1处于不同一包下，该类也不是Feather1的子类
        feather1.clone();//编译不通过，因为该测试类与Feather1处于不同一包下，该类也不是Feather1的子类
    }
}

测试

package com.lizhi.protect.p11;

import com.lizhi.protect.p1.Feather1;
import com.lizhi.protect.p1.Son1;

public class Son11 extends Feather1 {
    public static void main(String[] args) throws CloneNotSupportedException {
        Feather1 feather1 = new Feather1();
        Son1 son1 = new Son1();
        Son11 son2 = new Son11();
        son2.f();//编译通过，因为该测试类所在的地方是Feather1的子类
        son2.clone();//编译通过，因为该测试类所在的地方是Feather1的子类
        feather1.f();//编译不通过，因为该测试类与Feather1处于不同一包下
        feather1.clone();//编译不通过，因为该测试类与Feather1处于不同一包下
        son1.f();//编译不通过，因为该测试类与Feather1处于不同一包下
        son1.clone();//编译不通过，因为该测试类与Feather1处于不同一包下
    }
}

测试

package com.lizhi.protect.p1;

import com.lizhi.protect.p11.Son11;

public class Feather1 {
    protected void f(){}

    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone();
    }
    public static void main(String[] args) throws CloneNotSupportedException {
        Feather1 feather1 = new Feather1();
        Son1 son1 = new Son1();
        Son11 son2 = new Son11();
        son2.f();//编译通过，因为该测试类是Son1和Son11的父类
        son2.clone();//编译通过，因为该测试类是Son1和Son11的父类
        feather1.f();//编译通过，因为该测试类是Son1和Son11的父类
        feather1.clone();//编译通过，因为该测试类是Son1和Son11的父类
        son1.f();//编译通过，因为该测试类是Son1和Son11的父类
        son1.clone();//编译通过，因为该测试类是Son1和Son11的父类
    }
}

测试

package com.lizhi.protect.p4;

import com.lizhi.protect.p44.Test4;

public class MyObject4 extends Test4{
    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone();
    }
}

package com.lizhi.protect.p44;

import com.lizhi.protect.p4.MyObject4;

public class Test4 {
    public static void main(String[] args) throws CloneNotSupportedException {
        MyObject4 myObject4 = new MyObject4();
        myObject4.clone();//编译不通过
    }
}

说明：myobject4的clone直接来自MyObject4类本身

其范围是MyObjcet4的子类与其同包的类

Test4都不满足

所以编译不通过

测试

package com.lizhi.protect.p4;

import com.lizhi.protect.p44.Test4;

public class MyObject4 extends Test4{
    
}

package com.lizhi.protect.p44;

import com.lizhi.protect.p4.MyObject4;

public class Test4 {
    public static void main(String[] args) throws CloneNotSupportedException {
        MyObject4 myObject4 = new MyObject4();
        myObject4.clone();//编译通过
    }
}

说明：myobject4的clone直接来源于Test4

范围是Test4子类及其同包的类

满足与其同包

编译通过

设计模式-门面模式

发表于 2022-02-28 | 分类于设计模式 |

字数统计: 176

门面模式

定义：为子系统中的一组接口提供一个一致的高层接口，使得这一子系统更加容易使用

实现

子系统1

public class System1 {
    public void operateA(){
        System.out.println("子系统1的A操作");
    }
}

子系统2

public class System2 {
    public void operateB(){
        System.out.println("子系统2的B操作");
    }
}

子系统3

public class System3 {
    public void operateC(){
        System.out.println("子系统3的C操作");
    }
}

系统门面

public class SystemFacade {
    private System1 system1 = new System1();
    private System2 system2 = new System2();
    private System3 system3 = new System3();

    public void operateABC(){
        system1.operateA();
        system2.operateB();
        system3.operateC();
    }
}

客户端调用

public class Client {
    public static void main(String[] args) {
        new SystemFacade().operateABC();
    }
}

设计模式-享元模式

发表于 2022-02-26 | 分类于设计模式 |

字数统计: 259

享元模式

定义：运用共享技术有效地支持大量细粒度的对象

优点：如果系统有大量类似的对象，可以节省大量的内存和CPU资源

实现

场景：假如我要开发一款游戏，然后游戏里面的地图有很多树木

这个时候，我们不可能创建几万个树的对象

Tree

@Data
@AllArgsConstructor
@ToString
public class Tree {
    private final String name;
}

TreeNode

@Data
@AllArgsConstructor
public class TreeNode {
    private final Tree tree;
    private int x;
    private int y;
}

TreeFactory

public class TreeFactory {
    private static ConcurrentHashMap<String, Tree> map = new ConcurrentHashMap<>();
    public static Tree getTree(String name){
        if(map.containsKey(name)){
            return map.get(name);
        }
        return null;
    }

    public static void addTree(String name){
        map.put(name,new Tree(name));
    }
}

主函数

public static void main(String[] args) {
    TreeFactory.addTree("梧桐树");
    TreeFactory.addTree("香樟树");
    TreeFactory.addTree("银杏树");
    TreeFactory.addTree("面包树");
    TreeNode treeNode1 = new TreeNode(TreeFactory.getTree("梧桐树"),1,1);
    TreeNode treeNode2 = new TreeNode(TreeFactory.getTree("梧桐树"),1,2);
    TreeNode treeNode3 = new TreeNode(TreeFactory.getTree("梧桐树"),1,3);
}