乐趣区

关于算法:递归迭代和动态规划以九宫格键盘为例

本文记述笔者的算法学习心得,因为笔者不相熟算法,如有谬误请不吝指正。

九宫格键盘问题

给定一个从数字到字母的映射表:1 => [a, b, c], 2 => [d, e, f], 3=> [g, h, i], ……,实现一个函数 List<String> calculate(String input),若用户输出任意的数字串,要根据映射表转换每一个数字,返回所有可能的转换后果。例如,若输出“12”会失去 ad, ae, af, bd, be, bf, cd, ce, cf 这 9 个后果;若输出“123”会失去 27 个后果。

以上是此题的根底版,还有一个难度加强版:映射表的键还能够是数字组合,如 12 => [x], 23 => [y]。若输出“12”会有 10 个后果,还会有 x 这 1 个后果(总共 10 个后果);若输出“123”,岂但有之前的 27 个后果,还会有 xg, xh, xi, ay, by, cy 这 6 个后果(总共 33 个后果)。

根底版的解法

能够用递归法也能够用迭代法,两种办法是等价的。以下是算法思维和实现代码。

递归法

递归法的思维是继续把问题降解为子问题,直到子问题足够小。例如,calculate(“123”)等价于 calculate(“1”) * calculate(“23”),而 calculate(“23”)等价于 calculate(“2”) * calculate(“3”)。这里引入了一种非凡的汇合乘法,能把如 [a, b, c] 和[d, e, f]这样的两个汇合相乘失去 9 个后果(即输出“12”对应的后果),这种乘法能够用一个函数来实现。如此就清晰地表述了递归法的算法框架。

实现代码为

static List<String> calculate(String input) {if (input.isEmpty()) {return Collections.emptyList();
  }

  String key = String.valueOf(input.charAt(0));
  List<String> values = mappings.get(key);
  String substring = input.substring(1);

  if (substring.isEmpty()) {return values;} else {return product(values, calculate(substring));
  }
}

// 乘法
static List<String> product(List<String> lefts, List<String> rights) {List<String> results = new ArrayList<>();
  for (String left : lefts) {for (String right : rights) {results.add(left + right);
    }
  }
  return results;
}

迭代法

迭代法的思维是顺次解决输出的每一位,用已得后果集示意以后状态,记住和更新以后状态。例如,calculate(“123”)的处理过程是,第一步解决”1”,失去初始状态 [a, b, c],第二步解决”2”,让以后状态[a, b, c] 乘以“2”对应的[d, e, f],失去新状态[ad, ae, af, bd, be, bf, cd, ce, cf],第三步解决”3”,让以后状态乘以”3”对应的[g, h, i],失去新状态,此时输出值已全副解决实现。

实现代码为

static List<String> calculate(String input) {List<String> results = Collections.emptyList();

  for (int i = 0; i < input.length(); i++) {String key = String.valueOf(input.charAt(i));
    List<String> values = mappings.get(key);

    if (results.isEmpty()) {results = values;} else {results = product(results, values);
    }
  }

  return results;
}

static List<String> product(List<String> lefts, List<String> rights) {List<String> results = new ArrayList<>();
  for (String left : lefts) {for (String right : rights) {results.add(left + right);
    }
  }
  return results;
}

难度加强版的解法

根底版间接把每 1 位数字作为 key,用 mappings.get(key)获取映射值。而难度加强版面对不等长的 key,须要换一个形式,遍历 mappings 中的每一个 key,判断以后输出是否以这个 key 结尾,若是,就采纳这个 key 的映射值,同时从以后输出去掉这个 key,而后持续解决残余输出。
根底版的递归法略加修改就能失去难度加强版的解法。迭代法不能批改失去新解法,因为每一步可能产生多个步长不同的分支,这些分支所需解决的残余输出是不同的,不能枯燥迭代,用算法实践来说,因为这里的递归法不是尾递归,因而没有等价的迭代法版本。能够用栈或队列将递归计算转换为连续(continuation)来实现迭代计算,其实相当于模仿了递归,这个留给读者自行实现。
其实迭代法能够更高效地实现,然而要应用动静规划法。

递归法

实现代码为

static List<String> calculate(String input) {if (input.isEmpty()) {return Collections.emptyList();
  }

  List<String> results = new ArrayList<>();

  for (String key : mappings.keySet()) {if (input.startsWith(key)) {List<String> values = mappings.get(key);

      if (values == null) {throw new IllegalArgumentException("Unrecognized input");
      }

      String substring = input.substring(key.length());
      if (substring.isEmpty()) {results.addAll(values);
      } else {results.addAll(product(values, calculate(substring)));
      }
    }
  }

  return results;
}

// 乘法
static List<String> product(List<String> lefts, List<String> rights) {List<String> results = new ArrayList<>();
  for (String left : lefts) {for (String right : rights) {results.add(left + right);
    }
  }
  return results;
}

递归法的性能优化

来找找优化点。递归过程有很多反复的计算,能够用 memoization 技术搞一个缓存来提速,据测试能提速一倍,缓存的数据结构能够用哈希表或数组来实现。哈希表以 calculate()的 input 参数作为键,以 calculate()的后果作为值;数组以 input.length()作为索引值,以 calculate()的后果作为元素值。若输出规模为 n,缓存的空间复杂度为 O(n)。这个就交给读者自行实现吧。

results.addAll(product(values, calculate(substring)));这行是能够优化的,product()返回一个新建的 list,这个 list 又被复制到 results 里,存在一些内存调配和复制的开销。如果 product()能间接输入到 results 而不是返回一个 list,就不必新建和复制一个 list。据测试能提速 10% 左右。
代码批改为

// 调用处这么改
product(values, calculate(substring), results);

// 定义处这么改
static List<String> product(List<String> lefts, List<String> rights, List<String> results) {for (String left : lefts) {for (String right : rights) {results.add(left + right);
    }
  }
}

String substring = input.substring(key.length());这行如同也能够优化,substring()返回一个新建的子字符串,存在一些内存调配和复制的开销。其实,在旧版 JVM 上有一个优化,substring()是像 subList()一样的视图对象,间接援用原始字符串而不是创立正本,但新版 JVM 为了避免内存透露而勾销了这一优化(大型原始字符串已不再应用,但仍被子字符串援用而无奈开释空间)。咱们能够手动实现一个 StringView 类来做同样的优化,但 substring()的调用次数不多,因而对理论性能没有什么晋升。这个技术还是比拟有意思的,StringView 的实现在文尾的附录提供。

动静规划法

动静规划法能达到和 memoization 差不多甚至更快的速度,因为它也防止了反复的计算,而且空间复杂度只有 O(1)。
《算法概论》和《算法设计》这两本算法教材都讲到,动静布局不可能用递归来实现。动静布局的思维是从初始状态登程,一步步产生新状态,每一个新状态是从之前的一个或多个状态失去的,实现起来像一个状态机,因而不可能用递归来表白。对于这道题,能够继续扫描输出串,每一步向前扫一位,用以后已扫过的字符序列来示意以后状态,若以后状态以某个 key 结尾,则把此 key 的映射值乘到它所对应的“上一步”的后果集上,把新的后果集保留到缓存。这个“上一步”是哪一步呢?不是简略地回退一位,而是把方才扫到的 key 从以后状态去掉,就能回退到上一步的状态(相当于回退了 key.length 位),因为每一步都把后果集保留到缓存了,因而只有查问缓存就能失去上一步的后果集。缓存以回退位数为键,因为回退位数最多也不可能超过最长的 key 的 length,因而缓存是一个大小不超过这个数的滑动窗口,新的值进来就把最旧的值挤掉,只需常数级空间。

实现代码为

static List<String> calculate(String input) {
  String state = "";
  List<String> results = new ArrayList<>();
  Cache cache = new Cache();

  for (int i = 0; i < input.length(); i++) {state += input.charAt(i);
    List<String> newResults = new ArrayList<>();

    for (String key : mappings.keySet()) {if (state.endsWith(key)) {List<String> prevResult = cache.get(key.length());
        List<String> values = mappings.get(key);
        if (prevResult == null) {newResults.addAll(values);
        } else {newResults.addAll(product(prevResult, values));
        }
      }
    }

    results = newResults;
    cache.put(results);
  }

  return results;
}

static List<String> product(List<String> lefts, List<String> rights) {List<String> results = new ArrayList<>();
  for (String left : lefts) {for (String right : rights) {results.add(left + right);
    }
  }
  return results;
}

// Sliding window
private static class Cache {private int maxLength = mappings.keySet().stream().map(String::length).max(Integer::compareTo).get();
  private LinkedList<List<String>> queue = new LinkedList<>();

  List<String> get(int lookBackLength) {if (queue.size() < lookBackLength) {return null;}
    return queue.get(lookBackLength - 1);
  }

  void put(List<String> solutions) {if (queue.size() == maxLength) {queue.removeLast();
    }
    queue.offerFirst(solutions);
  }
}

附录

StringView 的实现代码

class StringView {
  private final String string;
  private final int offset;

  StringView(String string, int offset) {if (offset > string.length()) {throw new IllegalArgumentException("offset should be within string length");
    }
    this.string = string;
    this.offset = offset;
  }

  StringView subview(int additionalOffset) {return new StringView(string, offset + additionalOffset);
  }

  boolean isEmpty() {return offset == string.length();
  }

  boolean startsWith(String key) {int keyLength = key.length();
    if (string.length() < offset + keyLength) {return false;}

    for (int i = 0; i < keyLength; i++) {if (key.charAt(i) != string.charAt(i + offset)) {return false;}
    }

    return true;
  }
}
退出移动版