程序员的算法趣题：Q25 鞋带的时髦系法（Java版）

本文主要是介绍程序员的算法趣题：Q25 鞋带的时髦系法（Java版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目说明

即便系得很紧，鞋带有时候还是免不了会松掉。运动鞋的鞋带有很多时髦的系法。
下面看看这些系法里，鞋带是如何穿过一个又一个鞋带孔的。
如下图所示的这几种依次穿过 12 个鞋带孔的系法很有名
（这里不考虑鞋带穿过鞋带孔时是自外而内还是自内而外）。

这里指定鞋带最终打结固定的位置如上图中的前两种系法所示，
即固定在最上方（靠近脚腕）的鞋带孔上，并交错使用左右的鞋带孔。
求：鞋带交叉点最多时的交叉点个数。
譬如上图左侧的系法是 5 个，正中间的系法是 9 个。

思路

1.六个孔（左右各三个）时，有五条线
2.每条线都有左、右两个编号：{左孔编号,右孔编号}
3.五条线之间两两组合，罗列出所有可能性
4.判断是否有交叉点，统计个数并求出最大值

代码

private static int max = 0; // 统计最大值public static void main(String[] args) {// {左孔编号,右孔编号}// int[] L1 = {1,2};// int[] L2 = {3,1};// System.out.println(judge(L1, L2)); // 测试两条线段是否有交叉点int N = 6; // 左右各有6个孔// 两个集合分别保存左边、右边可选的孔（不包含起点和终点）List<Integer> left = new LinkedList<>();List<Integer> right = new LinkedList<>();// 已经要求最上边的左右两个孔是起点和终点，所以后续的组合只与左右各自剩下的5个孔有关，所以从1开始即可for (int i = 1; i < N; i++) {left.add(i);right.add(i);}List<String> lines = new LinkedList<>(); // 保存生成的每一条线段，格式如："左#右"// 以左上方的第一个孔为“起点”（因为是统计交叉点的最大值，从左、右开始都不影响）laceup(0, null, left, right, lines);System.out.println("max = " + max);
}

/*** 系鞋带：每次调用该方法，都会生成一条线段（从左或右中选一个孔，与当前的R或者L连成线段）* @param L     如果有值，则本次从左侧孔出发，在右侧选一个孔，连成线段* @param R     如果有值，则本次从右侧孔出发，在左侧选一个孔，连成线段* @param left  左侧剩余可用的孔* @param right 右侧剩余可用的孔*/
private static void laceup(Integer L, Integer R, List<Integer> left, List<Integer> right, List<String> lines) {// 入参检查if (L == null && R == null) return;if (left == null || right == null || lines == null) return;/**  已生成所有线段，开始两两判断，统计交叉点的个数*/// 最初以左上方的孔为起点if (L != null && right.size() == 0) {lines.add(L + "#" + 0); // 最后一条线段int cnt = countNode(lines);lines.remove(L + "#" + 0);max = max < cnt ? cnt : max;return;}// 最初以右上方的孔为起点if (R != null && left.size() == 0) {lines.add(0 + "#" + R); // 最后一条线段int cnt = countNode(lines);lines.remove(0 + "#" + R);max = max < cnt ? cnt : max;return;}/**  选择一个孔，连成线段*/if (L != null) {                                    // 如果L非空，说明上一次选择的是左边的孔，这次从右边选int index = left.indexOf(L);if (index >= 0)                                 // 首次进来时，起点不在集合中，index为-1，直接remove会报错left.remove(index);                         // L已经用了两次了（一进一出），起点和终点只能用一次，需要删除了for (int i = 0; i < right.size(); i++) {Integer r = right.get(i);                   // 右边选一个孔lines.add(L + "#" + r);                     // 生成一条线段// 这一次选择的是右边的孔laceup(null, r, left, right, lines);        // 继续生成后续的线段lines.remove(L + "#" + r);                  // 恢复}if (index >= 0)left.add(index, L);                         // 恢复} else {                                            // 如果R非空，说明上一次选择的是右边的孔，这次从左边选int index = right.indexOf(R);if (index >= 0)                                 // 首次进来时，起点不在集合中，index为-1，直接remove会报错right.remove(index);                        // R已经用了两次了（一进一出），需要删除了for (int i = 0; i < left.size(); i++) {Integer l = left.get(i);                    // 左边选一个孔lines.add(l + "#" + R);                     // 生成一条线段laceup(l, null, left, right, lines);        // 继续生成后续的线段lines.remove(l + "#" + R);                  // 恢复}if (index >= 0)right.add(index, R);                        // 恢复}}

/*** 统计线段中的交叉点数量* @param lines 线段集合* @return */
private static int countNode(List<String> lines) {int count = 0;  // 统计交叉点的数量for (int i = 0; i < lines.size(); i++) {String s1 = lines.get(i);                       // 取出一条线段String[] ss = s1.split("#");                    // 通过#切割成两部分int l1 = Integer.parseInt(ss[0]);               // String ==> intint r1 = Integer.parseInt(ss[1]);               // String ==> intint[] a = {l1, r1};                             // 将线段信息组装成数组形式for (int j = i + 1; j < lines.size(); j++) {    // 从i+1开始，可以避免“a和b,b和a”类型的重复比较String s2 = lines.get(j);String[] ss2 = s2.split("#");int l2 = Integer.parseInt(ss2[0]);int r2 = Integer.parseInt(ss2[1]);int[] b = {l2, r2};count += judge(a, b) ? 1 : 0;               // 成功，+1； 失败，不变。}}System.out.println(count + " ==> " + lines);        // 不关注鞋带的系法时，可以注释掉该输出语句，能节约80%左右的时间（N=6时，运行时间：2.5s ==> 0.5s）return count;
}

/*** 判断两条线段是否有交叉点* @param L1    {左孔编号,右孔编号}* @param L2    {左孔编号,右孔编号}* @return      是否有交叉点*/
private static boolean judge(int[] L1, int[] L2) {// 不合法if (L1 == null || L2 == null) return false;// 自己和自己比if (Arrays.equals(L1, L2)) return false;// 两条线段的左边相减、右边相减，只要相乘的结果为负数，就有交叉点。（如果不理解，推荐动手画图感受一下）return (L1[0] - L2[0]) * (L1[1] - L2[1]) < 0;
}