Author Archives: Robert Lu

LeetCode:991. Broken Calculator

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

题意

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

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

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

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

题解

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

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

代码

/**
 * https://www.robberphex.com/broken-calculator/
Read the rest

LeetCode:1106. Parsing A Boolean Expression

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

题意

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

表达式可以是:

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

题解

直接递归解释表达式… Read the rest

LeetCode:103. Binary Tree Zigzag Level Order Traversal

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

题意

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

例如:

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

    3
   / \
  9  20
    /  \
   15   7

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

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

题解

对于第一层遍历,从左到右,添加到一个stack中;对于第二层遍… Read the rest

LeetCode 1103:Distribute Candies to People

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

题意

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

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

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

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

返回一个数组(长度为num_people… Read the rest

LeetCode题解:Path In Zigzag Labelled Binary Tree

本文为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:
Read the rest

yum仓库内部原理

本文是yum repository internals的翻译。

TL;DR

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

什么是yum仓库?

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

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

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

在详细了解yum仓库元数据之前,先让我… Read the rest

PHP Generator相关的设计失误

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

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

Return Type Declarations(返回类型声明)

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

<?php
declare(strict_types=1);

function inner(): \Iterator
Read the rest

Java中的SPI机制

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

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

SPI的实现

Java 1.6中,开发者只需要在META-INF/services下添加文件,即可切换、修改… Read the rest

Java的类/实例初始化过程

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

程序的输出见文章最后

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

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

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

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

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

于是… Read the rest

为什么HTTP Upgrade的时候,需要Connection: upgrade

很久之前,在看HTTP头部的时候,发现WebSocket等协议的Upgrade请求,需要同时带上Connection和Upgrade头部。但是,如果是仅仅Upgrade的话,Connection头部不就是多余的设计了么?

GET /chat HTTP/1.1
Host: example.com:8000
Upgrade: websocket
Connection: Upgrade
Sec-WebSocket-Key: dGhlIHNhbXBsZSBub25jZQ==
Sec-WebSocket-Version: 13

当时在… Read the rest