ARTS-W04（1.10 - 1.16）

2021-03-15 本文已影响0人寒沁

Algorithm（一道算法题）

分割回文串
题目描述：
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。

示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]

先提几个问题：

如何快速地判断回文串？
左右指针的方式
覆盖所有可能，找到子请求，动态规划？
用深度遍历及其回溯的方式

例如 s = abbc作为示例，遍历s ，s.length = 4
i = 0 时
   将s拆分成 a, bbc 先判断a是否是回文串，是的话，将a存入双向栈 Deque<String> path 中,继续往下，将 bbc 当做s，递归调用。
   bbc拆分成 b、bc，将b存入path，bc递归，bc拆分成b、c，将b存入path，c递归，c就一个字符，将c存入path，遍历结束，第一个深度遍历完成，只要完成的，就将path放入到List<List<String>>中，我们得到了第一队符合要求的数据结构：[a,b,b,c]。
   回到最近的一次遍历，bc长度为2，上面处理好了 b、c，还需要继续处理 bc ，判断bc非回文串，结束遍历。
   再回到上一次遍历bbc，b、bc已处理，继续处理 bb，c ，判断bb是回文串，递归c，c也是，所以得到第二符合要求的数据结构：[a,bb,c]。到此为止，以a起头的拆分递归调用完成。
i = 1 时
  将s拆分成 ab, bc 先判断ab是否是回文串，是的话，继续往下，把bc当做整体s，递归调用。ab不是回文串，结束调用。
i = 2 时
  将s拆分成abb，c 同上。 abb不是回文串，调用结束。
i = 3 时
  将s拆分成abbc，"" 同上。 abbc不是回文串，调用结束。
所以abbc的最终结果为 [[a,b,b,c],[a,bb,c]]

代码示例如下

    public List<List<String>> partition(String s) {
        int len = s.length();
        List<List<String>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // Stack 这个类 Java 的文档里推荐写成 Deque<Integer> stack = new     
        ArrayDeque<Integer>();
        // 注意：只使用 stack 相关的接口
        Deque<String> stack = new ArrayDeque<>();
        backtracking(s, 0, len, stack, res);
        return res;
    }

    /**
     * @param s
     * @param start 起始字符的索引
     * @param len   字符串 s 的长度，可以设置为全局变量
     * @param path  记录从根结点到叶子结点的路径
     * @param res   记录所有的结果
     */
    private void backtracking(String s, int start, int len, Deque<String> path, List<List<String>> res) {
        if (start == len) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < len; i++) {

            // 因为截取字符串是消耗性能的，因此，采用传子串索引的方式判断一个子串是否是回文子串
            // 不是的话，剪枝
            if (!checkPalindrome(s, start, i)) {
                continue;
            }

            path.addLast(s.substring(start, i + 1));
            System.out.println("i:" + i +" ,path Add:" + s.substring(start, i+1));
            backtracking(s, i + 1, len, path, res);
            System.out.println("path lastValue is:"+path.getLast());
            path.removeLast();
        }
    }

    /**
     * 这一步的时间复杂度是 O(N)，因此，可以采用动态规划先把回文子串的结果记录在一个表格里
     *
     * @param str
     * @param left  子串的左边界，可以取到
     * @param right 子串的右边界，可以取到
     * @return
     */
    private boolean checkPalindrome(String str, int left, int right) {
        // 严格小于即可
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

Review（阅读并点评一篇英语技术文章）

Getting started with Kubernetes

摘抄
Kubernetes Basic Architecture

control plane [ this controls the cluster ]
kube-apiserver [ This is basically the interface of the k8s cluster ]
kube-scheduler [ looks at the resources needed for the pod checks the health of the cluster and schedules the pod into most appropriate node ]
kube-controller-manager [ this is the controller of the controller plane ]
etcd [ Contains information about configurations and state of the cluster ]
nodes [ Nodes have something called pods which are made up of containers ]
pod [ Pod is the small component in the k8s cluster ]
Container Runtime Engine [ To run the pods each node need a container runtime engine. exp: docker ]

这篇文章，从大体的原理上介绍了什么k8s，以及k8s的基础构成，最后还讲述了其中一款k8s软件（Microk8s）的安装过程。
花了很长一段时间来看这篇文章，比较长，看的比较吃力，但看英文的技术文章，从技术原理的理解会比看中文文章更容易些。

Tips（学习一个技术技巧）

sentinel对接dubbo与web http 全局配置
官网
 主流框架适配链接

接入web http全局配置
引入的maven包

<dependency>
    <groupId>com.alibaba.csp</groupId>
    <artifactId>sentinel-web-servlet</artifactId>
    <version>x.y.z</version>
</dependency>

通过Filter启动Sentinel支持
spring boot 项目

    @Bean
    public FilterRegistrationBean sentinelFilterRegistration() {
        FilterRegistrationBean<Filter> registration = new FilterRegistrationBean<>();
        registration.setFilter(new CommonFilter());
        registration.addUrlPatterns("/*");
        registration.setName("sentinelFilter");
        registration.setOrder(1);
        return registration;
    }

普通的web.xml系统

<filter>
    <filter-name>SentinelCommonFilter</filter-name>
    <filter-class>com.alibaba.csp.sentinel.adapter.servlet.CommonFilter</filter-class>
</filter>

<filter-mapping>
    <filter-name>SentinelCommonFilter</filter-name>
    <url-pattern>/*</url-pattern>
</filter-mapping>

流控统一格式处理

public class SentinelUrlBlockHandler implements UrlBlockHandler {


    @Override
    public void blocked(HttpServletRequest request, HttpServletResponse response, BlockException ex) throws IOException {
        SoulMsgData errorMsg = null;
        if(ex instanceof FlowException){
            //限流异常
            errorMsg =  SoulMsgData.error(SentinelExceptionCodeEnum.DEGRADE_CODE);

        }else if(ex instanceof DegradeException){
            //降级异常
            errorMsg =  SoulMsgData.error(SentinelExceptionCodeEnum.FLOW_CODE);

        }else if(ex instanceof SystemBlockException){
            //sentinel系统异常
            errorMsg =  SoulMsgData.error(SentinelExceptionCodeEnum.SYSTEMBLOCK_CODE);

        }else {
            //未知异常
            errorMsg = SoulMsgData.error(SentinelExceptionCodeEnum.SYSTEM_ERROR_CODE);
        }

        response.setCharacterEncoding("UTF-8");
        response.setContentType("application/json;charset=utf-8");
        response.setHeader("Content-Type","application/json;charset=utf-8");
        response.getWriter().write(JSON.toJSONString(errorMsg));
    }
}

接入dubbo 全局配置

引入的maven坐标

<!-- Apache Dubbo 2.7.x 版本 -->
<dependency>
    <groupId>com.alibaba.csp</groupId>
    <artifactId>sentinel-apache-dubbo-adapter</artifactId>
    <version>x.y.z</version>
</dependency>

<!-- Dubbo 2.6.x -->
<dependency>
    <groupId>com.alibaba.csp</groupId>
    <artifactId>sentinel-dubbo-adapter</artifactId>
    <version>x.y.z</version>
</dependency>

全局限流异常处理

public class ProviderSentinelFallbackHandler implements DubboFallback {
    @Override
    public Result handle(Invoker<?> invoker, Invocation invocation, BlockException ex) {
        MsgData errorMsg = null;

        if(ex instanceof FlowException){
            //限流异常
            errorMsg =  MsgData.error(SentinelExceptionCodeEnum.DEGRADE_CODE);

        }else if(ex instanceof DegradeException){
            //降级异常
            errorMsg =  MsgData.error(SentinelExceptionCodeEnum.FLOW_CODE);

        }else if(ex instanceof SystemBlockException){
            //sentinel系统异常
            errorMsg =  MsgData.error(SentinelExceptionCodeEnum.SYSTEMBLOCK_CODE);

        }else {
            //未知异常
            errorMsg = MsgData.error(SentinelExceptionCodeEnum.SYSTEM_ERROR_CODE);
        }

        AsyncRpcResult asyncRpcResult = new AsyncRpcResult(invocation);
        asyncRpcResult.setValue(errorMsg);

        log.error("handle the Sentinel BlockException , exception info is [Rule is {}] [RuleLimitApp is {}]  " , ex.getRule() , ex.getRuleLimitApp());
        return asyncRpcResult;
    }
}

Share（分享一篇有观点有思考的技术文章）

责任链的项目使用
责任链定义

Avoid coupling the sender of a request to its receiver by giving more than one object a chance to handle the request. Chain the receiving objects and pass the request along the chain until an object handles it
直译如下：通过让多个对象有机会处理请求， $\color{red}{避免请求发送者与接收者耦合}$ ，将这些对象连成一条链路，并沿着这条链路传递请求，直到有对象处理它为止。

通用类图

责任链通用类图.png

运用场景与优缺点核心理解

优点
$\color{red}{将请求与处理解耦}$
请求者不用知道是谁处理的，屏蔽了请求处理的全过程，只需要把请求抛给责任链第一处理者，最终会返回一个结果，作为请求者不用知道到底需要谁来处理。
缺点

性能从链头遍历到链尾，链很长的时候，性能堪忧。 $\color{red}{设置链条的最大数量}$
调试不方便

简单demo
套用《设计模式之禅》中的示例
需求：古代女子想出去逛街，要得到家中同意才可出去。未嫁，父亲审批，父过世，兄长审批，出嫁，丈夫审批，丈夫过世，儿子审批。
第一版需求，假设只有这四种情况，实际情况应该比这要复杂。
不用设计模式，可以这么写

最简单的方式，不做任何设计，代码都写在一坨，没有抽象。

class Woman{

    private String state;

    public Woman(String state){
        this.state = state;
    }

    public String getState() {
        return state;
    }

    public void setState(String state) {
        this.state = state;
    }

    public void watchLantern(){
        System.out.println("看花灯");
    }

}

  public static void doSomething(Woman woman){
        if("1".equals(woman.getState())){
            //未嫁,父亲在
            System.out.println("父亲审批了");
            woman.watchLantern();
        }else if("2".equals(woman.getState())){
            //未嫁,父亲去世
            System.out.println("兄长审批了");
            woman.watchLantern();
        }else if("3".equals(woman.getState())){
            //已嫁,丈夫在
            System.out.println("丈夫审批了");
            woman.watchLantern();
        }else if("4".equals(woman.getState())){
            //已嫁,丈夫不在
            System.out.println("儿子审批了");
            woman.watchLantern();
        }else{
            System.out.println("没人管了,自己决定吧");
            woman.watchLantern();
        }
    }

对参与对象与行为进行抽象。

如果要对女性进行扩展，就要修改现有代码逻辑块了。
处理人没有抽象出来，模糊不清楚，单一原则和开闭原则都不符合
改造之后的第二版如下

public interface IWoman {

    /**
     * 获取妇女状态
     * @return
     */
    Integer getWomanStatus();

    /**
     * 做一些重要的事情
     */
    String doSomeImportant();
}

public interface IHandler {
    String doWomanRequest(IWoman woman);
}

public class OWomanImpl implements IWoman {
    private int owStatus = 0;
    private String questStr = "";

    public OWomanImpl(int owStatus, String questStr) {
        this.owStatus = owStatus;
        this.questStr = questStr;
    }

    public OWomanImpl() {
    }

    @Override
    public Integer getWomanStatus() {
        return this.owStatus;
    }

    @Override
    public String doSomeImportant() {
        return this.questStr;
    }
}

public class Father implements IHandler {
    @Override
    public String doWomanRequest(IWoman woman) {
        String result = "同意女儿的要求";
        System.out.println(woman.doSomeImportant());
        System.out.println(result);
        return result;
    }
}

public class Husband implements IHandler {
    @Override
    public String doWomanRequest(IWoman woman) {
        String result = "同意娘子的要求";
        System.out.println(woman.doSomeImportant());
        System.out.println(result);
        return result;
    }
}

public class Son implements IHandler {
    @Override
    public String doWomanRequest(IWoman woman) {
        String result = "同意母亲的要求";
        System.out.println(woman.doSomeImportant());
        System.out.println(result);
        return result;
    }
}

public class MySelft implements IHandler {
    @Override
    public String doWomanRequest(IWoman woman) {
        String result = "真爽,终于没人管我了";
        System.out.println(woman.doSomeImportant());
        System.out.println(result);
        return result;
    }
}

public void ancientWomenRequest(List<IWoman> women){
        if(CollectionUtils.isEmpty(women)){
            return;
        }

        women.forEach((woman)->{
            if(1 == woman.getWomanStatus()){
                new Father().doWomanRequest(woman);
            }else if(2 == woman.getWomanStatus()){
                new Husband().doWomanRequest(woman);
            }else if(3 == woman.getWomanStatus()){
                new Son().doWomanRequest(woman);
            }else if(4 == woman.getWomanStatus()){
                new MySelft().doWomanRequest(woman);
            }
        });
    }

    public static void main(String[] args) {
        //随机女性
        List<IWoman> womens = new ArrayList<>(12);
        for(int i = 0; i<10; i++){
            int random = new Random().nextInt(4) + 1;
            System.out.println("random value is " + random);
            womens.add(new OWomanImpl(random,"看花灯"));
        }

        new Client().ancientWomenRequest(womens);
    }

这样写逻辑和分工就清晰了很多，由于有一定的接口抽象，扩展起来更方便了，主逻辑代码用抽象的方式实现，有更多的通用性。后面需求有扩展更多类别的女性，只要新增实现即可。但问题是，如果要扩展处理类，不仅要添加实现，还要继续写if_else，影响到了核心逻辑代码，违反开闭原则。主要的问题如下

扩展要不断地写if else ，代码臃肿，且耦合严重，Ihandler的实现添加，要继续修改client类
具体逻辑处理，不应该在client中，应该在具体的处理类中
请求处理类，只能做单一的处理，异常情况处理不了

这时候就需要用到 $\color{red}{责任链}$ ，以下是第三个版本

//定义问题处理者为抽象方法，实现功能：处理请求，请求处理不了，交给下一个请求，这样就屏蔽了变化的请求与处理之间的关系，我只要关心第一个请求者与处理者之间的关系即可
public enum LevelRequestEnum {
    FATHER(1,"父亲处理女儿请求"),
    HUSBAND(2,"丈夫处理妻子请求"),
    SAN(3,"儿子处理母亲请求"),
    SELF(4,"自己处理自己请求"),

    ;
    private int level;
    private String desc;


    LevelRequestEnum(int level, String desc) {
        this.level = level;
        this.desc = desc;
    }

    public int getLevel() {
        return level;
    }

    public String getDesc() {
        return desc;
    }
}

public abstract class AbstractHandler {
    private int doLevel;

    private IWoman iWoman;

    private AbstractHandler nextHandler;

    public AbstractHandler(int doLevel){
        this.doLevel = doLevel;
    }

    public void doHandler(IWoman iWoman){
        //自己的处理级别
        if(doLevel == iWoman.getWomanStatus()){
            this.responseResult(iWoman);
        }else{
            //不是自己
            if(nextHandler != null){
                nextHandler.doHandler(iWoman);
            }else{
                System.out.println("处理结束,不被允许");
            }
        }
    }

    abstract String responseResult(IWoman iWoman);

    public void setNextHandler(AbstractHandler handler){
        this.nextHandler = handler;
    }
}

public class FatherHandler extends AbstractHandler{
    public FatherHandler(int doLevel) {
        super(LevelRequestEnum.FATHER.getLevel());
    }

    @Override
    String responseResult(IWoman iWoman) {
        System.out.println("request is : " + iWoman.doSomeImportant());
        System.out.println("父亲的答复是：同意");
        return null;
    }
}
public class SonHandler extends AbstractHandler{
    public SonHandler(int doLevel) {
        super(LevelRequestEnum.SAN.getLevel());
    }

    @Override
    String responseResult(IWoman iWoman) {
        System.out.println("request is : " + iWoman.doSomeImportant());
        System.out.println("儿子的答复是：同意");
        return null;
    }
}

public class HusbandHandler extends AbstractHandler{
    public HusbandHandler(int doLevel) {
        super(LevelRequestEnum.HUSBAND.getLevel());
    }

    @Override
    String responseResult(IWoman iWoman) {
        System.out.println("request is : " + iWoman.doSomeImportant());
        System.out.println("丈夫的答复是：同意");
        return null;
    }
}

public class SelfHandler extends AbstractHandler {
    public SelfHandler(int doLevel) {
        super(LevelRequestEnum.SELF.getLevel());
    }

    @Override
    String responseResult(IWoman iWoman) {
        System.out.println("request is : " + iWoman.doSomeImportant());
        System.out.println("自己的答复是：同意");
        return null;
    }
}

工作中的某个场景
游戏登录的方式（另起一篇文章吧）

ARTS-W04（1.10 - 1.16）

Algorithm（一道算法题）

Review（阅读并点评一篇英语技术文章）

Tips（学习一个技术技巧）

Share（分享一篇有观点有思考的技术文章）

猜你喜欢

热点阅读