LeetCode 23. Merge k Sorted Lists

LeetCode 23. Merge k Sorted Lists

题意

合并k个链表,每个链表内部都是排好序的(从小到大),但是k个链表之间是无序的。

思路

首先,最简单的办法就是链表之间选择排序,取第一个链表的第一个节点插到结果中。然后如果链表还有节点,放回到数组中。如此往复,直到没有节点剩余。

时间复杂度O(k*n),空间复杂度O(1)。

// from https://www.robberphex.com/merge-k-sorted-lists/
// Runtime: 420 ms Memory Usage: 38.6 MB
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0)
return null;
ListNode head = null;
int hi = -1;
// 选出一个head
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null && (head == null || lists[i].val < head.val)) {
head = lists[i];
hi = i;
}
}

    if (head == null)
        return head;
    lists\[hi\] = lists\[hi\].next;
    ListNode prev = head;

    while (true) {
        ListNode cur = null;
        int ci = 0;
        // 选出最小的node
        for (int i = 0; i < lists.length; i++) {
            if (lists\[i\] != null && (cur == null || lists\[i\].val < cur.val)) {
                cur = lists\[i\];
                ci = i;
            }
        }
        if (cur == null)
            break;
        // 插入到链表中
        lists\[ci\] = lists\[ci\].next;
        prev.next = cur;
        cur.next = null;
        prev = cur;
    }

    return head;
}

}

显然,多次对k个链表排序是很浪费的,这时候就想到了堆,只需要将k个链表构成一个堆即可。时间复杂度O(N*log(k)),空间复杂度O(1):

阅读更多

Codeforces Round #575 B. Odd Sum Segments

题目:https://codeforces.com/contest/1196/problem/B

将长度为n的数组a划分成k个非空组,确保所有的组内之和都为奇数。

本来以为是要输出所有的可行解,所以想了一个O(n^k)的解法,结果超时。后来发现只需要输出一组解即可。

首先计算数组中奇数个数,如果奇数个数等于k,则每组一个奇数,满足需求。

如果奇数个数比k大奇数个,则这些奇数一定会导致一个组的和变成偶数,不满足。如果奇数个数比k大偶数个,则满足要求。

然后就是如何构造序列的问题了。

首先,对于前k-1个序列,每个序列仅包含一个奇数,最后剩下的一个组包含剩下的数字,很容易可以想到,最后一个组一定包含了奇数个奇数。

另外,java.util.Scanner有性能问题,还是使用自己实现的FastReader

代码如下:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

阅读更多

特工355(Agent 355)

特工355(1780年后去世)是美国革命期间女性间谍的代名,是库尔珀组(Culper Ring)的一部分。 特工355是美国的第一批间谍之一,真实身份未知。355这个数字是库尔珀组中的加密系统用来表示“女士”的数字。

生平

在库尔珀组的公文中,唯一直接提及特工355的是亚伯拉罕·伍德赫尔乔治·华盛顿将军的信。伍德赫尔形容她是“对这封信有帮助的人”。

特工355的真实身份仍然未知,但有关她的一些事实似乎很清楚。作为间谍,她在美国独立战争期间与美国爱国者(或称美国辉格党,革命党)合作。她本会被伍德赫尔招募进间谍组。355这个代码表明她可能具有“某种程度的社会突出性”。她可能生活在纽约市,并且在某些时候与约翰·安德烈少校贝内迪克特·阿诺德有过接触。 一个可能是特工355的人是伍德赫尔的邻居安娜·斯特朗(Anna Strong)。另一个说法是,特工355可能是罗伯特汤森事实上的妻子。有传说表明汤森爱上了特工355。约翰·伯克和安德里亚·梅耶尔通过间接证据证明她可能与约翰·安德烈少校和本杰明·塔尔马奇关系密切,从而保护伍德赫尔不被指控为间谍,这为355参与间谍活动提出了不同的理由。特工355的其他可能候选人包括Sarah Horton Townsend和Elizabeth Burgin。

偶尔也有一些说法,说根本没有特工355,355仅仅代指一名知道有用信息的女人,并没有与特工组正式关联。代码355仅仅表示“一个女人”,而不是一个女性特工。

探员355被认为是揭露阿诺德和逮捕少校约翰·安德烈的主要角色,后者在纽约塔潘被绞死。她可能是一个著名的保皇派(或称托利党)家庭的成员,这个家庭背景使她很容易接近英国指挥官。

1780年,本尼迪克特·阿诺德(Benedict Arnold)前往保皇派那里,这时特工355被逮捕。她被囚禁在泽西号军舰上,这是一艘监狱船,在那里她可能生下了一个名叫小罗伯特·汤森的男孩。她后来死在监狱船上。然而,亚历山大·罗斯不同意这种说法,他说“女性没有被关在监狱船上”,“没有任何出生的记录”。这强化了355号特工可能是安娜·斯特朗的观点,因为她的丈夫塞拉·斯特朗被囚禁在泽西岛,她应该可以给丈夫带食物。她出现在船上使人们传言特工355被囚禁在那里。

在流行文化中

特工355已经成为通俗小说的一部分。她是《Y:世上最后一个男人》中一个主要角色。她也是现代间谍355的灵感来源,并收录在《刺客信条3》的游戏内历史事实数据库中,她的信息对于帮助主角发现要捕获的英国阴谋至关重要。

在电视剧《逆转奇兵》(Turn: Washington’s Spies)中,特工355是一位名叫阿比盖尔(Abigail)的前奴隶,安娜·斯特朗曾是她的主人。英国军队在安娜·斯特朗入狱后没收了他的财产。虽然名义上阿比盖尔是自由的,但她被迫为约翰·安德烈工作。阿比盖尔把她在安德烈家中无意中听到消息藏在给儿子的礼物中,这个儿子被迫留下交给安娜照顾。剧中,特工355由伊达拉·维克托扮演。

阅读更多

Is the Perfect the Enemy of the Good?

Voltaire once said, “perfect is the enemy of the good.” And as a perfectionist in recovery, I can say without hesitation, the boy was he right!

Having high standards motivates us to work hard and to excel in life.

However, the desire to be perfect only handicaps us. It stops us from doing what we’d really like to do. And if it doesn’t, it deprives us of the pleasure of enjoying what we pursue.

Here’s what happens when we reach for perfection:

We become Haunted by Failure

Under the false illusion that our path in life should be a straight line, we become terrified of curves and detours. Nothing sounds more catastrophic than the idea of making a mistake. So we become scared to death of taking risks. Of going beyond the unknown to try something new.

We don’t see failure as an opportunity to learn and to grow. But only as the most intimidating threat to be feared. So we do everything in our power to avoid it at all costs. Even if it means we stop living.

We Fail to Enjoy Success

If we see failure as our enemy then success would be our foremost ally, right? Well no. Even if we succeed, our expectations are such that any success is perceived as trivial. When we accomplish a goal we underestimate it. And fail to savor it.

There’s always something that could have been done better. A mistake that could have been avoided. A detail that shouldn’t have been missed. In the end, there’s always something that we failed to do, even if we succeeded. Because we failed to be perfect.

阅读更多

yum仓库内部原理

本文是yum repository internals的翻译。

TL;DR

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

什么是yum仓库?

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

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

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

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

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

$ sudo yum install createrepo

阅读更多

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
{
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。(听着很不一致的样子)

阅读更多

为何一次请求会有两次HttpServlet:service调用?

今天看了下阿里出的 Arthas使用文档中有问到:

为什么只访问了http://localhost:8080/a.txt,但Arthas的trace命令打印出了两个请求树?

然后我去自己试了下,发现还真的是这个情况,trace日志如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
`---ts=2019-02-24 18:05:20;thread_name=http-nio-8080-exec-1;id=15;is_daemon=true;priority=5;TCCL=org.springframewo[email protected]6601a0f8
`---[22.125552ms] javax.servlet.http.HttpServlet:service()
`---[22.048005ms] javax.servlet.http.HttpServlet:service()
`---[21.977486ms] org.springframework.web.servlet.FrameworkServlet:service()
+---[0.015829ms] javax.servlet.http.HttpServletRequest:getMethod()
+---[0.023379ms] org.springframework.http.HttpMethod:resolve()
`---[21.847595ms] org.springframework.web.servlet.HttpServletBean:service()
`---……

`---ts=2019-02-24 18:05:20;thread_name=http-nio-8080-exec-1;id=15;is_daemon=true;priority=5;TCCL=org.springframewo[email protected]6601a0f8
`---[108.691709ms] javax.servlet.http.HttpServlet:service()
`---[108.658563ms] javax.servlet.http.HttpServlet:service()
`---[108.612929ms] org.springframework.web.servlet.FrameworkServlet:service()
+---[0.024764ms] javax.servlet.http.HttpServletRequest:getMethod()
+---[0.004569ms] org.springframework.http.HttpMethod:resolve()
`---[108.540682ms] org.springframework.web.servlet.HttpServletBean:service()
`---……

然后,过去翻了一下代码才发现,是org.apache.catalina.core.StandardHostValve#invoke方法的逻辑:

//正常的处理请求(这是第一个HttpServlet:service调用)
context.getPipeline().getFirst().invoke(request, response);
// 如果response是失败的,那么再处理ErrorPage的逻辑
if (response.isErrorReportRequired()) {
if (t != null) {
throwable(request, response, t);
} else {
status(request, response);
}
}

在status方法中,获取ErrorPage,然后给request设置javax.servlet.error.*的属性,然后再forward到HttpServlet:service。这儿就会出现第二个HttpServlet:service请求。

那么问题来了,这个行为是规范里面有约定吗?

翻了翻 Java Servlet Specification,第10.9.2小节有说:

To allow developers to customize the appearance of content returned to a Web client when a servlet generates an error, the deployment descriptor defines a list of error page descriptions. The syntax allows the configuration of resources to be returned by the container either when a servlet or filter calls sendError on the response for specific status codes, or if the servlet generates an exception or error that propagates to the container.

If the sendError method is called on the response, the container consults the list of error page declarations for the Web application that use the status-code syntax and attempts a match. If there is a match, the container returns the resource as indicated by the location entry.

The Web application may have declared error pages using the exception-typeelement. In this case the container matches the exception type by comparing the exception thrown with the list of error-page definitions that use the exception-typeelement. A match results in the container returning the resource indicated in the location entry. The closest match in the class hierarchy wins.

阅读更多

怪屋女孩:灵魂博物馆

刚刚读完了 Library of Souls - The Third Novel of Miss Peregrine’s Peculiar Children

我读这本书其实是为了学英语,但作为一本冒险小说,设定还是很有新意的,尤其是那些照片,还有男主的女朋友!

不过,这种故事是典型的英雄之旅(Hero’s journey)的模版。读到最后,回忆主角经历的种种,恍若隔世,还是蛮温馨的。


接下来是我的笔记,见笑了。

She wished me luck and kissed me on the lips. Then I looked at Sharon, who tilted his head at me as if to say, I hope you’re not expecting a kiss from me, too, and I just laughed and walked toward the fighters.

这个梗在漫威电影里面也有用到

Just because I’m a capitalist doesn’t mean I’m a black-hearted bastard.

我是一个资本家,但这并不意味着我是一个黑心的混蛋

“Gold coins!” said Emma, fairly spitting with disgust. “What about the well-being of your fellow peculiars? What about loyalty?”
Sharon chuckled. “If I cared about things like that, I’d have been dead long ago.”

Sharon说的很有道理,居然无法反驳

He was a hoarder, like his brother, of strange and ghastly things—only where Bentham was organized to a tee, Caul badly needed a maid.

badly needed,哈哈

“In the tales that are told about us after our victory, I should like to be known as Addison the Intrepid.”
“And so you shall,” said Emma.
“Make that Extremely Intrepid,” Addison said. “And handsome.”
“Done,” I said.

这两个应该算是英式幽默吧,Addison Intrepid and Handsome!

阅读更多

Billionaire

The topic is billionaire, namely, If you had a billion dollars, what would you do. How about browsers billionaires firstly? No, it isn’t interesting. What can we do with those non-existent one billion dollars? Hey, I am a man, the cosmetics, the luxuries, will not be on the top of the list. The simplest thing is buying an island, for fun? I can’t find the reason. Seriously, The spacecraft can be the first. There are space stations built by NASA(acronymized by National Aeronautics and Space Administration) and CNSA(acronymized by China National Space Administration). But I prefer crewed spacecraft because I could be a crew. The second can be supporting research institute. How about research on immortality? It sounds like perpetual motion, does it? Namely, it’s medical research, that we can prolong the lifespan until eternity. When a  scientist states that something is impossible, he is very probably wrong. And the cosmology research is what I want to sponsor if the money is enough. Earth is the cradle of humanity, but one cannot live in a cradle forever. But, one billion dollars isn’t enough, neither for research or spacecraft. The budget is certainly limited, right? Here is some billionaire we mentioned: Rockefeller, an American oil industry business magnate, had 400 billion dollars. But Rockefeller has died, so let’s move on. Zuckerberg, Facebook co-founder, also a philanthropist, has 56 billion dollars. Larry Ellison, Oracle co-founder, has 59 billion dollars. Larry Page, Google co-founder, has 53 billion dollars. Bill Gates, Microsoft co-founder, has 95 billion dollars. Jeff Bezos, Amazon co-founder, has 137 billion dollars. OK, as a former developer, I’m over-focused on IT sphere. Liliane Bettencourt, the founder of L’Oréal that I never heard it, had 44 billion dollars. Kjeld Kirk Kristiansen, the former CEO of The LEGO Group, has 5 billion dollars. Sheldon Adelson, the founder of Las Vegas Sands, has 43 billion dollars. And, maybe the most famous one, Donald Trump has 3 billion dollars. How about Chinese? Jack Ma, the founder of Alibaba, has 34.7 billion dollars. Pony Ma, the founder of Tencent, has 42.7 billion dollars. Robin Li, the founder of Baidu, has 18.8 billion dollars. Wang Jianlin that is famous for her son has 28.1 billion dollars. And, Richard Liu, the founder of JD, that is infamous for the sexual assault, has 12.7 billion dollars.

阅读更多

The woman on the bus was molested

On 25th, Sep, domestic violence happened at a bus at Beiliu City, Guangxi Provence. According to the video, a woman moved to bus’s roar exit gate, trying to get off at the next station. The man pulled the woman off the rear of the bus while the woman tried holding on the handles. The man threw the girl to the last row of seat and sat beside her. The woman was screaming throughout the video. At first, the video is thought to have happened at Zhongshan City, Guangdong Provence. After investing, police at Zhongshang declared that it didn’t happen in Zhongshan. Later, a reporter contacted the police in Beiliu City, Guangxi Provence, which confirmed the violence happen at Beiliu City, Guangxi Provence. Sadly, the police’s response in the video shows the lack of legal knowledge:

“The man and the woman are factual marriage, which means they haven’t registered, hadn’t a marriage certificate. They have one child. The woman is too young to register for marriage. And the police has told the man not to use violence.”

According to Chinese laws, the statement from police doesn’t make sense. Factual marriage was deprecated since 1994, and it should be considered illegal cohabitation. The police should know it well. By all means, neither the marriage or the child doesn’t make the domestic violence legal. So, Why didn’t the police protect the woman? We should notice that no one stood up to protect the woman at the bus. But the most important things is the police just tried to muddle through, not protect the woman.

阅读更多