从面向if-else编程升级为面向状态编程,减少代码复杂度

举报
breakDawn 发表于 2021/09/28 23:15:11 2021/09/28
【摘要】 下面的场景引用自力扣原题65:https://leetcode-cn.com/problems/valid-number/submissions/§ 需求有一个非常经典的数字校验场景, 需求如下:有效数字(按顺序)可以分成以下几个部分:一个 小数 或者 整数(可选)一个 ‘e’ 或 ‘E’ ,后面跟着一个 整数小数(按顺序)可以分成以下几个部分:(可选)一个符号字符(’+’ 或 ‘-’)下述...

下面的场景引用自力扣原题65:
https://leetcode-cn.com/problems/valid-number/submissions/

§ 需求

有一个非常经典的数字校验场景, 需求如下:

有效数字(按顺序)可以分成以下几个部分:
一个 小数 或者 整数

(可选)一个 ‘e’ 或 ‘E’ ,后面跟着一个 整数
小数(按顺序)可以分成以下几个部分:

(可选)一个符号字符(’+’ 或 ‘-’)
下述格式之一:
至少一位数字,后面跟着一个点 ‘.’
至少一位数字,后面跟着一个点 ‘.’ ,后面再跟着至少一位数字
一个点 ‘.’ ,后面跟着至少一位数字
整数(按顺序)可以分成以下几个部分:

(可选)一个符号字符(’+’ 或 ‘-’)
至少一位数字
部分有效数字列举如下:

[“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, >>“53.5e93”, “-123.456e789”]
部分无效数字列举如下:

[“abc”, “1a”, “1e”, “e3”, “99e2.5”, “–6”, “-+3”, “95a54e53”]
给你一个字符串 s ,如果 s 是一个 有效数字 ,请返回 true

复杂度高的硬写代码

这时候如果直接硬写,大概率写出容易复杂度巨高的代码,还容易遗漏而出错。
例子如下:

	class Solution {
	    public boolean isNumber(String s) {
	        int sign = 1;
	        int pointSign = 1;
	        int eSign = 1;
	        int numSign = -1;
	        int i = 0;
	        int n = s.length();
	        while(i<n){
	            if(s.charAt(i)>='0'&&s.charAt(i)<='9'){
	                numSign = 1;
	                sign = -1;
	            }else if(s.charAt(i)=='+'||s.charAt(i)=='-'){
	                if(sign>0){
	                    sign = -sign;
	                }else{
	                    return false;
	                }
	                if(i>0&&s.charAt(i-1)=='.'){
	                    return false;
	                }
	            }else if(s.charAt(i)=='.'){
	                //numSign = -1;
	            
	                if(pointSign>0){
	                    pointSign = -pointSign;
	                }else{
	                    return false;
	                }
	                if(i>0&&(s.charAt(i-1)=='e'||s.charAt(i-1)=='E')){
	                    return false;
	                }
	            }else if(s.charAt(i)=='e'||s.charAt(i)=='E'){
	                if(eSign<0||numSign<0){
	                    return false;
	                }
	                eSign = -1;
	                sign = 1;
	                numSign = -1;
	                pointSign = -1;
	            }else{
	                return false;
	            }
	            i++;
	        }
	        return numSign>0;
	    }
	}

这段代码的复杂度为 21, 放在科目一考试直接不及格了,而且非常容易出错,改着改着把自己改晕了,或者改漏了。

§ 状态机优化

图片引用自Leetcode官方题解,链接见:
https://leetcode-cn.com/problems/valid-number/solution/you-xiao-shu-zi-by-leetcode-solution-298l/

可以看到校验的过程可以组成一个状态, 当遇到特定字符时,进入特定的状态去判断,并且该状态后面只能接入有限的状态。

因此我们可以定义N个状态,每个状态定义X个状态变化条件和变化状态。
在java中用多个map即可进行维护这种关系。

可以写出如下的代码, 虽然代码量看起来更高了,但是可维护性和复杂度变强不少。

	class Solution {
	    public enum CharType {
	        NUMBER,
	        OP,
	        POINT,
	        E;
	 
	        public static CharType toCharType(Character c) {
	            if (Character.isDigit(c)) {
	                return NUMBER;
	            } else if (c == '+' || c == '-') {
	                return OP;
	            } else if (c == '.') {
	                return POINT;
	            } else if (c =='e' || c == 'E') {
	                return E;
	            } else {
	                return null;
	            }
	        }
	    }
	 
	 
	    public enum State {
	        INIT(false),
	        OP1(false),
	        // 在.前面的数字
	        BEFORE_POINT_NUMBER(true),
	        // 前面没数字的点
	        NO_BEFORE_NUMBER_POINT(false),
	        // 前面有数字的点
	        BEFORE_NUMBER_POINT(true),
	        // 点后面的数字
	        AFTER_POINT_NUMBER(true),
	        // e/E
	        OPE(false),
	        // E后面的符号
	        OP2(false),
	        // e后面的数字
	        AFTER_E_NUMBER(true);
	 
	        // 是否可在这个状态结束
	        private boolean canEnd;
	 
	        State(boolean canEnd) {
	            this.canEnd = canEnd;
	        }
	 
	        public boolean isCanEnd() {
	            return canEnd;
	        }
	    }
	 
	    public Map<State, Map<CharType, State>> transferMap = new HashMap<>() {{
	        Map<CharType, State> map = new HashMap<>() {{
	            put(CharType.OP, State.OP1);
	            put(CharType.NUMBER, State.BEFORE_POINT_NUMBER);
	            put(CharType.POINT, State.NO_BEFORE_NUMBER_POINT);
	        }};
	        put(State.INIT, map);
	 
	        map = new HashMap<>() {{
	            put(CharType.POINT, State.NO_BEFORE_NUMBER_POINT);
	            put(CharType.NUMBER, State.BEFORE_POINT_NUMBER);
	        }};
	        put(State.OP1, map);
	 
	        map = new HashMap<>() {{
	            put(CharType.POINT, State.BEFORE_NUMBER_POINT);
	            put(CharType.NUMBER, State.BEFORE_POINT_NUMBER);
	            put(CharType.E, State.OPE);
	        }};
	        put(State.BEFORE_POINT_NUMBER, map);
	 
	        map = new HashMap<>() {{
	            put(CharType.NUMBER, State.AFTER_POINT_NUMBER);
	        }};
	        put(State.NO_BEFORE_NUMBER_POINT, map);
	 
	        map = new HashMap<>() {{
	            put(CharType.NUMBER, State.AFTER_POINT_NUMBER);
	            put(CharType.E, State.OPE);
	        }};
	        put(State.BEFORE_NUMBER_POINT, map);
	 
	        map = new HashMap<>() {{
	            put(CharType.E, State.OPE);
	            put(CharType.NUMBER, State.AFTER_POINT_NUMBER);
	        }};
	        put(State.AFTER_POINT_NUMBER, map);
	 
	 
	        map = new HashMap<>() {{
	            put(CharType.OP, State.OP2);
	            put(CharType.NUMBER, State.AFTER_E_NUMBER);
	        }};
	        put(State.OPE, map);
	 
	 
	        map = new HashMap<>() {{
	            put(CharType.NUMBER, State.AFTER_E_NUMBER);
	        }};
	        put(State.OP2, map);
	 
	        map = new HashMap<>() {{
	            put(CharType.NUMBER, State.AFTER_E_NUMBER);
	        }};
	        put(State.AFTER_E_NUMBER, map);
	    }};
	 
	 
	    public boolean isNumber(String s) {
	        State state = State.INIT;
	        for (char c : s.toCharArray()) {
	            Map<CharType, State> transMap = transferMap.get(state);
	            CharType charType = CharType.toCharType(c);
	            if (charType == null) {
	                return false;
	            }
	            if (!transMap.containsKey(charType)) {
	                return false;
	            }
	            // 状态变更
	            state = transMap.get(charType);
	        }
	        return state.canEnd;
	    }
	}

可以看到复杂度也只有8,不会复杂度超标。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。