Algorithm

题目描述

给定一个只包括 ‘(',')','{','}','[',']’ 的字符串,判断字符串是否有效。leetcode-20

Example

输入: “()” -> 输出: true 输入: “()[]{}” -> 输出:true

题目解答

此种题目可以使用栈来进行处理,主要有几个核心点

  1. 入参数为奇数则一定不匹配
  2. 对于左括号,直接进行push操作
  3. 对于右括号,对栈进行pop操作与右括号进行匹配
  4. 最后栈为空则说明所有都匹配成功
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public class BracketMatching {
    public boolean isValid (String s) {

        if (null == s || s.length() % 2 != 0) return false;

        Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');

        for (char c : s.toCharArray()) {
            if (!map.containsKey(c)) {
                stack.push(c);
            } else if (stack.empty() || map.get(c) != stack.pop()) {
                return false;
            }
        }
        return stack.empty();
    }

Review

code-smells-mutation本文是Idea作者代码味道系列的第四篇。讲述了作者对一个近百行的方法进行重构的过程,主要是因为可变变量的坏味道。

由于变化的值引发的重构难题

  1. 由于mf是可变的,在方法中有好几个地方对其进行值的修改,这样对后续逻辑的推理产生阻碍
  2. 抽取代码到更小的代码块时提示错误,因为还有一个可变的boolean值
  3. 修改输入参数,使调用者感到迷惑

重构步骤

停止修改正在遍历的数组

对pathElements这个参数使用一个新的变量(databasePathElements)来进行处理。这样可以把对pathElements的修改改成对databasePathElements的修改,还可以使用Java8的Collectors.joining()方法来对路径进行拼接,不用自己循环了。其实这个修改主要是降低了方法的复杂性。

移除hasTranslations标志

处理这个是因为在尝试重构时,方法中存在多个可变变量,导致不能进行重构操作。作者直接删除了hasTranslations标志,即所有的操作都会执行setLength和append方法。

抽取方法

由于移除了标识且使用新变量来存储path值,现在可以进行方法的抽取了,把mf的作用范围提取出来,限制在一个更小的方法中。

引入新的类型

这个是针对修改输入参数情况的重构,作者在这里引入了新的类型来封装先前的值,这样可以解决返回多个值的问题,其实开发中的Pair和Triple这种类型就是为了返回多个值来服务的。

修改返回值,而不是修改参数

引入新类型可以在新类型中增加数据库的path值了,这样可以停止StringBuilder的变化了。

总结

  1. 重构效果,代码从93->74行
  2. 如果代码从一个集合中又读又修改,则要考虑使用一个的新集合进行变量的修改跟踪。这样对于多线程的读也有好处
  3. 如果很难分辨一个特定值来自哪个分支,则可以考虑使用可读的名称来存储,而不是重用一个变量,或者将修改控制在一个小的可控的方法范围中,方便理解。在IDE中可以使用增加final的方法来让IDE进行错误显示来辅助判断
  4. 要想修改输入参数,考虑向返回对象中新增加一个值,使其包含所有需要的数据。如果这样不行则可以引入一个新对象来进行包装
  5. 计数器或者boolean值可能不是跟踪方法中状态的最好方式,删除它们或者移动它们可能会带来更好的可读性

注意事项

  1. 重构的代码是否对性能有要求,如果有则要对比重构前后性能差异
  2. 完整的单元测试非常重要

Tip

在Emacs中多使用C-u这个前缀有时会收到意想不到的效果,比如C-u 1 org-capture daily-plan可以弹出要记录的daily-plan日期组件进行选择,如果没有C-u前缀则只是处理当前时间日志的daily-plan.

Share

今天分享的是Idea-pro-tips这篇文章,这里面介绍了一些Idea的高级技巧,包含常用的设置,搜索,分析,开发调试的高级功能。那个Dependency Structure Matrix可以分析出当前类被使用的详细信息,可以更好的处理组件中的依赖情况。还有就是调试中Drop frame,这个在调试时非常有用,可以对执行步骤进行后退后再调试(即回到过去)。