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，这个在调试时非常有用，可以对执行步骤进行后退后再调试（即回到过去）。