本文为LeetCode 25. Reverse Nodes in k-Group的题解。

题意

给定一个链表，k个一组反转链表。

k 是一个正数，且小于链表长度。如果按照k个一组，最后剩下的不组k，则不反转剩下的元素。

例子:

对于链表: 1->2->3->4->5

若 k = 2, 应返回: 2->1->4->3->5

若 k = 3, 应返回: 3->2->1->4->5

注意:

• 只允许O(1)的空间复杂度。
• 不可以改变节点的值。

此文为LeetCode 991. Broken Calculator的题解。

题意

有一台坏掉的计算器，能够显示一个数字，我们可以对这个数字做两个操作：

• 乘二: 将显示的数字乘以2, 或者;
• 减一: 将显示的数字减1.

初始时，计算器显示数字 X.

返回要得到数字Y需要的最小操作次数。

题解

如果X>Y，则只能执行减一操作。否则，如果Y是奇数，则上一步操作一定是X减一；如果Y是偶数，则上一步操作只能是X乘二。

只需要通过上述规则，由Y反推X即可。

代码

本文是LeetCode 1106. Parsing A Boolean Expression的题解。

题意

给定一个String类型的布尔表达式expression，返回一个求值的结果。

表达式可以是：

• "t", 表示为 True;
• "f", 表示为 False;
• "!(expr)", 将内部的 expr 结果取反;
• "&(expr1,expr2,...)", 将内部的expr1, expr2, ...求与;
• "|(expr1,expr2,...)", 将内部的expr1, expr2, ...求或。

题解

直接递归解释表达式就好，每层负责解释上述的一个规则就可以。

这儿有一个优化点：实现表达式惰性求值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/**
 * https://www.robberphex.com/parsing-a-boolean-expression/
 * Runtime: 1 ms, faster than 100.00% of Java online submissions for Parsing A Boolean Expression.
 * Memory Usage: 38 MB, less than 100.00% of Java online submissions for Parsing A Boolean Expression.
 */
class Solution {
    class Result {
        /**
         * 表达式结果
         */
        boolean res;
        /**
         * 下次解析的起始位置
         */
        int end;

        Result(boolean res, int end) {
            this.res = res;
            this.end = end;
        }
    }

    private Result parseBoolExpr(String expression, int start) {
        if (expression.charAt(start) == 'f') {
            return new Result(false, start + 1);
        } else if (expression.charAt(start) == 't') {
            return new Result(true, start + 1);
        } else if (expression.charAt(start) == '!') {
            Result result = parseBoolExpr(expression, start + 2);
            result.res = !result.res;
            result.end++;
            return result;
        } else if (expression.charAt(start) == '&') {
            Result finalResult = new Result(true, 0), result;
            start++;
            do {
                result = parseBoolExpr(expression, start + 1);
                if (!result.res) {
                    // 在这儿可以实现惰性求值
                    finalResult.res = false;
                }
                start = result.end;
                // 如果是逗号，继续解析
            } while (expression.charAt(result.end) == ',');
            finalResult.end = result.end + 1;
            return finalResult;
        } else if (expression.charAt(start) == '|') {
            Result finalResult = new Result(false, 0), result;
            start++;
            do {
                result = parseBoolExpr(expression, start + 1);
                if (result.res) {
                    // 在这儿可以实现惰性求值
                    finalResult.res = true;
                }
                start = result.end;
            } while (expression.charAt(result.end) == ',');
            finalResult.end = result.end + 1;
            return finalResult;
        } else {
            throw new RuntimeException();
        }
    }

    public boolean parseBoolExpr(String expression) {
        return parseBoolExpr(expression, 0).res;
    }

    public static void main(String[] args) {
        boolean res = new Solution().parseBoolExpr("!(&(&(!(&(f)),&(t),|(f,f,t)),&(t),&(t,t,f)))");
        System.out.println(res);
        // 输出 true
    }
}

本文为LeetCode：103. Binary Tree Zigzag Level Order Traversal的题解。

题意

一颗给定的二叉树，返回节点值的之子形的便利结果。即，从左到右，然后下一级别是从右到左，如此交替。

例如：

给定二叉树：[3,9,20,null,null,15,7]：

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

程序将会返回之字形遍历顺序：

1
2
3
4
5

[
  [3],
  [20,9],
  [15,7]
]

题解

对于第一层遍历，从左到右，添加到一个stack中；对于第二层遍历，pop出来的顺序是从右到左，所以要额外考虑先添加right子节点、再添加left子节点到stack中。

本文为LeetCode 1103：Distribute Candies to People的题解。

题意

我们用下面的方法给num_people个人分发一些糖果：

我们给第一个人1块糖，给第二个人2块糖，以此类推，直到我们给最后一个人n块糖。

然后，我们回到开始，给第一个人n + 1块糖，给第二个人n + 2块糖，以此类推，直到我们给最后一个人2 * n块糖。

这个过程不断重复（当重新走到队首的时候，我们每次比上次多给n个糖果），直到糖果分配结束。最后一个人将收到我们所有剩余的糖果。

返回一个数组（长度为num_people），该数组表示最终每个人得到的糖果数量。

题解

首先我们考虑能完整的分发几轮。

由于分发数量总体上就是从1到n*num_people的等差序列，n符合如下不等式：

本文为LeetCode 1104. Path In Zigzag Labelled Binary Tree 的题解。

题目描述

一棵无穷的二叉树，每个节点都编号（label）了：对于奇数层（第1、3、5等层），从左向右编号。对于偶数层，从右向左编号。但是每层的编号还是最小2^(level-1),最大2^level-1。

如图：

给你一个编号（label），输出从顶层到该节点经过的节点编号。

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

本文是yum repository internals的翻译。

TL;DR

这篇博客将会检查各种yum仓库中的索引文件，从而深入了解yum仓库的细节。我们将介绍每个索引文件的含义，并研究用户如何检查这些元数据。

什么是yum仓库？

Yum仓库就是一些RPM包的集合，加上一些yum命令能够读取的元数据。有一个yum仓库能够让你安装、删除、升级软件包或者软件组。

yum仓库对于存储、管理、交付软件非常重要。

使用createrepo命令创建一个yum仓库

在详细了解yum仓库元数据之前，先让我们看看如何用开源命令行工具createrepo架设一个yum仓库。

使用命令行工具createrepo，你能创建一个yum仓库。你能在CentOS或Red Hat系统中使用如下命令安装这个工具：

1

$ sudo yum install createrepo

PHP的Generator，也就是 yield/yield from 语法，使得函数调用可以“暂停”执行，并保留上下文，并在后续可以恢复执行。

但是，在PHP后续的设计中，很多地方都没有考虑到Generator：

Return Type Declarations（返回类型声明）

RFC见https://wiki.php.net/rfc/return_types。简而言之，可以给函数声明返回类型。先来看一段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

<?php
declare(strict_types=1);

function inner(): Iterator
{
    yield __FUNCTION__;
    return 1;
}

function gen(): Generator
{
    yield __FUNCTION__;
    return yield from inner();
}

try {
    $gen = gen();
    foreach ($gen as $yielded) {
        echo "yield: ".$yielded . PHP_EOL;
    }
    echo "return: " . $gen->getReturn() . PHP_EOL;
} catch (Exception $e) {
    echo PHP_EOL;
    echo $e->getTraceAsString();
    echo PHP_EOL;
}

gen/inner函数是一个generator，yield的的类型是string，return的类型是int。但为了让PHP不报错，gen/inner函数的返回类型只能声明为Iterator或Generator——这完全破坏了返回类型声明的初衷：

对于普通函数，返回类型声明用来表示返回类型；对于generator，返回类型声明用来表示这是一个迭代器/Generator。（听着很不一致的样子）

好，没关系，无伤大雅。没法通过返回类型声明来推倒类型而已，我们通过PhpDoc来总可以了吧？

通过PhpDoc来标记返回类型

但是这个怎么写呢？对于刚刚的inner函数（yield的的类型是string，return的类型是int），最自然的写法是这样：

SPI 全称为 (Service Provider Interface) ，是Java 1.6之后内置的一种服务提供发现机制。SPI可以通过配置来替换服务（或者说interface）的实现；比如java.sql.Driver接口，可以很轻松的从MySQL切换到MongoDB实现。

问题的核心在于，如何根据interface查找对应的实现。

SPI的实现

Java 1.6中，开发者只需要在META-INF/services下添加文件，即可切换、修改对应interface的实现。文件名为实现的接口，文件内容为N个实现的类名，按行分隔。比如：

1
2
3

$ cat src/main/resources/META-INF/services/com.robberphex.Plugin 
com.robberphex.impl.PluginImpl1
com.robberphex.impl.PluginImpl2

使用起来，主要就是ServiceLoader类：

1
2
3
4

ServiceLoader<Plugin> loader = ServiceLoader.load(Plugin.class);
for (Plugin plugin : loader) {
    System.out.println(plugin.getClass().getCanonicalName());
}

要注意的是，ServiceLoader#load方法是CallerSensitive的，即load的时候用的是调用者的类加载器。

Java 9

Java 9之后，由于模块化的引入，所以SPI机制也做了扩展：除了原有的通过META-INF/services来注册服务外，还可以通过module中的provides…with语句来注册服务：

昨天看到群里面有人分享了一道题目，我答错了，于是趁机了解了下Java的类/对象初始化过程：

程序的输出见文章最后。

程序A主要考察的是类实例初始化。简单验证了下，类实例初始化过程如下：

• 父类实例初始化
• 构造块/变量初始化（按照文本顺序执行）
• 构造函数

程序B考察的则是类初始化。类初始化的过程如下：

• 父类初始化
• static变量初始化/static块（按照文本顺序执行）

但是我们必须做到面向接口编程，而不是面向实现编程（Program to an ‘interface’, not an ‘implementation’）。

于是就得看看Java Language Specification是如何规定的。其中类初始化过程如下：

1. 每个类都有一个初始化锁LC，进程获取LC（如果没有获取到，就一直等待）
2. 如果C正在被其他线程初始化，释放LC并等待C初始化完成
3. 如果C正在被本线程初始化，即_递归初始化_，释放LC
4. 如果C已经被初始化了，释放LC
5. 如果C处于erroneous状态，释放LC并抛出异常NoClassDefFoundError
6. 否则，将C标记为正在被本线程初始化，释放LC；然后，初始化那些final且为基础类型的类成员变量
7. 初始化C的父类SC和各个接口SI_n（按照implements子句中的顺序来） ；如果SC或SIn初始化过程中抛出异常，则获取LC，将C标记为erroneous，并通知所有线程，然后释放LC，然后再抛出同样的异常。
8. 从classloader处获取assertion是否被打开
9. 接下来，按照文本顺序执行类变量初始化和静态代码块，或接口的字段初始化，把它们当作是一个个单独的代码块。
10. 如果执行正常，获取LC，标记C为已初始化，并通知所有线程，然后释放LC
11. 否则，如果抛出了异常E。若E不是Error，则以E为参数创建新的异常ExceptionInInitializerError作为E。如果因为OutOfMemoryError导致无法创建ExceptionInInitializerError，则将OutOfMemoryError作为E。
12. 获取LC，将C标记为erroneous，通知所有等待的线程，释放LC，并抛出异常E。