Ciel's blog

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

1
2
3
4
5
6
7
8

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

解题

My first commit

没有降低min的复杂度, 遍历一次时间复杂度为O(N)

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

class MinStack:
    stack = []

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []


    def push(self, x: int) -> None:
        self.stack.append(x)


    def pop(self) -> None:
        top_item = self.stack[-1]
        self.stack = self.stack[:-1]
        return top_item


    def top(self) -> int:
        top = self.stack[-1]
        return top


    def min(self) -> int:
        # stack_items = self.stack
        minimun = self.stack[0]
        for cnt in range(len(self.stack)-1):
            if self.stack[cnt+1] <= minimun:
                minimun = self.stack[cnt+1]
        return minimun

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

Takeaway from others

面试题30. 包含 min 函数的栈（辅助栈，清晰图解）

• 利用辅助栈来降低复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class MinStack:
    def __init__(self):
        self.A, self.B = [], []

    def push(self, x: int) -> None:
        self.A.append(x)
        if not self.B or self.B[-1] >= x:
            self.B.append(x)

    def pop(self) -> None:
        if self.A.pop() == self.B[-1]:
            self.B.pop()

    def top(self) -> int:
        return self.A[-1]

    def min(self) -> int:
        return self.B[-1]

总结

1. python 中 slice:

   Understanding slice notation

   1	a[start:stop:step]

   is equivalent to:

   1	a[slice(start, stop, step)]

2. 常犯错误: 循环中不能改变循环变量!

Source

难点：口音

Transcript

On August 12, 2020, two groups of girls went out to protest in Minsk, the capital city of Belarus. They put on white clothes and went barefoot out into the street. In the morning, some went to Komarovskiy Market in the center of town. Later that day, the other group gathered with flowers at the eternal flame under the victory monument. They stood together holding hands, and they started to sing the Belarusian lullaby, waiting for the police cars to arrive. They knew the police would pick them up just like that: barefoot with flowers in their hands, that they would take them to the police station, beat them up and try to humiliate them. And yet they did it anyway.

This year, something changed in Belarus, a country of more than nine million people that has been ruled by an authoritarian leader since 1994. These young women were protesting the latest rigged election result, which had taken [place] just a few days earlier. Their small expressions of protest very quickly expanded into massive, peaceful, women-led demonstrations all across the country.

Within just a few days, a few hundred thousand people took to the streets and demonstrations have continued ever since, the likes of which Belarus has never seen before. All this despite the fact that the president proclaimed himself reelected and that more than 10,000 people have been detained, hundreds tortured and at least six killed.

Many people wonder why the people of Belarus are speaking up now. What makes them keep taking to the streets despite unprecedented police violence, despite state lawlessness? The answer I hear the most is that people have become fearless, and it’s something we have become together.

Because fear is the province of one. It feeds on isolation. It doesn’t discriminate: men, women, children, elderly – all of us can feel fear, but only as long as we are on our own. Fearlessness takes two. It only works if and when we show up for each other. Show up so that your neighbor, your colleague, your friend has courage. And they will do the same for you.

A lot has been made of my own role in the presidential election of August 2020. How I stepped in to run for my husband, Sergei, when he was jailed and it became clear that the authorities would deny him his chance to run himself; how I rightfully won the election and became the elected leader of a democratic Belarus, but the official results only gave me 10 percent of the vote and I was forced into exile with my children; how I still fight for those who voted for me and whose voice the regime wants to steal; how “fearless” I am.

But there were many moments when I was frightened, and I wanted to step down. I was threatened and forced to believe that I’m alone in this fight. And yet the more cities I visited, the more people showed up for the rallies, the less fear I had. And then in the days before the election in Minsk, 60,000 people came to show their support for me, and I was no longer afraid.

I never wanted to do any of this. I was never overly political, and I never planned to run for office. I wanted to be a mom and a wife. But by fate and the will of my people, I was elevated to this position. And I accept this with a sense of duty and pride. I will not give up. And I will show up for people, because they show up for me. Our courage is born from unity. Our solidarity is our strength.

I also now understand that being fearless is a commitment. It is a decision you make every single day. It is a responsibility you take – responsibility for one another. In this regard, I’m no different from my fellow Belarusians. Their support is tangible. Their solidarity grows in progression. When there are two of you, you are daring. When you’re 100, you are brave. When there are thousands of you, you are fearless. And once you are tens of thousands, you become invincible.

Thank you.

Background

2020 Belarusian presidential election

Notes

• Belarus

  白俄罗斯, Minsk is the capital city of Belarus

• authoritarian

  adj. 权力主义的,专制的; n. 权力主义者,专制者,独裁者

• rigged

  adj. 作弊的，以不正当手段操纵的

  But his rival Martin Fayulu claims the vote was rigged.
  但他的竞争对手马丁·法尤卢（Martin Fayulu）称投票存在舞弊行为。

  The rigged polls appeared before the Trump presidential bid began.
  该事件发生在特朗普开始竞选总统之前。

• the likes of which

  诸如此类的事

  Shapes and colors the likes of which I’ve never seen.
  哇噻 都是我从没见过的色彩和图案。

  Companies are moving back, creating job growth the likes of which our country has not seen in a very long time.
  企业正在搬回，创造就业增长，这是美国很久未曾见过的。

• take to

  开始，从事，喜欢，形成…的习惯，容易学会

  This week, they took to the streets.

  本周, 他们终于走上街头。

• province

  the proper sphere or extent of your activities

  If you say that a subject or activity is a particular person’s province, you mean that this person has a special interest in it, a special knowledge of it, or a special responsibility for it. (学识或活动的) 领域; (兴趣或职责的) 范围
  Tattooing is not just the province of sailors.
  纹身不只是水手们才感兴趣的事。

  “it was his province to take care of himself”

• exile

  vt. 流放, 放逐, 使流亡; n. 流放, 放逐, 流亡

• regime

  n. 政权，政体；社会制度；管理体制

  政权（英语：Regime）在政府、政治和外交领域是指国家的政体的统治体制，或者特定的行政管理当局；在社会学范畴是指社会的制度，或社会的秩序。

  It is an attempt by the American government to change the regime or the regime change.

  这是美国政府在企图改变南苏丹的政权。

• solidarity

  n. 团结

• progression

  n. 前进；连续

  But all this quick progression has come at a cost.
  但所有这些快速发展都是有代价的。

  You know much about the progression of A.L.S.?
  知道肌萎缩性脊髓侧索硬化症吗？

  Let’s go on now to talk about chord progression.
  接下来我们谈一下和弦进行。

• daring

  adj. 勇敢的, 无畏的

• invincible

  adj. 不可战胜的;不能征服的

Source

难点：词汇，语速

Structure

Transcript

Growing up in Missouri, they would kind of take us out into the woods, and they would give you a map, and they would give you a compass, and you had to find your way home. And without the compass, you can’t even read the map. That’s what I’m here to tell you. The compass is the key.

A compass is most simply a piece of metal that has been magnetized, so that it will turn towards the Earth’s magnetic pole. The one that we all think of is the pocket compass. It looks like a watch, right? You can hold it in your hand and watch the little needle bounce around until you find north.

Magnetism is still a pretty mysterious force to physicists, but what we do know for sure is that a compass works because the Earth is this giant magnet. And when you use a compass, you are in touch with the very center of our planet, where this kind of roiling ball of molten iron is spinning around and creating a magnetic field. Just like a magnet you can play with on your tabletop, it has a north pole and a south pole, and we use compasses to find our way north because of that fact.

The earliest known compass comes from about 200 BC in China. They figured out that some of the metal coming out of the ground was naturally magnetic, and so they fashioned this magnetized metal into this kind of ladle-looking thing, put it on a brass plate and then it would point north. It seems to have been primarily used to improve feng shui, so they could figure out what was the best way for energy to flow through their living spaces.

Sailors were probably the early adopters of the more portable versions of it, because no matter where the sun was, no matter what the condition of the stars were, they would always be able to find north.

Now, much later, the Europeans are the ones who innovate and come up with the compass rose. It essentially laid out what north, south, east and west looked like, and it also enabled you to kind of create new directions, like northwest, southeast, what have you. And for the first time, they knew where they were going. That’s kind of a big deal.

But also, I think it was part of this general reinvigoration of European science. You might know it as the Renaissance. Lots of new tools were invented, from the telescope to the microscope.

Maps got better because of compasses, right? Because then you start to understand which direction is which, you get a lot more detail, and that just kind of changes the human relationship to the world. The compass with a map is like a superpower. Everything that we think of as world history would not have taken place without the compass: the age of exploration, Magellan circumnavigating the globe, even the fact that we know it is a globe.

The compass ends up getting embedded in all these other tools, because it is such a functional object. So you might have it embedded in your multi-tool, you might have it embedded in your phone. The compass is everywhere, because it’s literally how we find our way across the face of the Earth. So you can go off and explore, and find out what is over that next hill or that next horizon, but you can also reliably find your way home.

Notes

• Missouri

  /mɪˈzʊri/ n. 密苏里（美国州名）

  

  Missouri (see pronunciations) is a state located in the Midwestern United States. It is the 21st most extensive, and the 18th most populous of the fifty states. The state comprises 114 counties and the independent city of St. Louis.

• magnetize

  magnetize vt. 吸引；使磁化; vi. 磁化；受磁;
  magnetizing n. [物] 磁化; v. [物] 磁化（magnetize的ing形式）;
  magnetized adj. 已磁化的; v. 使……磁化，使……有磁性（magnetize 的过去式和过去分词）;

  magnetic adj. 有磁性的, 有吸引力的

  magnetism n. 磁性, 磁学; 个人吸引力, 个人魅力

  magnet n. 磁铁；磁石；磁体

• pocket compass /‘kʌmpəs/

  袖珍指南针

• bounce

  n. 弹力；活力；跳
  vt. 弹跳；使弹起
  vi. 弹起，反跳；弹跳；弹回 bounce around

• physicist

  /‘fɪzɪsɪst/ n. 物理学家

• roil

  vt. 搅混(液体); 使烦恼,使不安；使生气

  It’s a giant collection of clouds roiling around, lightning going on…
  它吸纳了周围紊乱的云，雷电轰鸣..

  It falls as snow. It roils in oceans. It floats gently through forests as mist.
  它像雪一样落下。它在海洋中激荡。它像薄雾般在森林中缓缓飘过。

  The immigration issue is roiling the European Union as well, and, today, Hungary intensified its crackdown.
  移民问题同样也在困扰欧盟，今天匈牙利加强了对移民的打击力度。

• molten

  adj. 熔化的；炽热的；铸造的
  v. 换毛；脱毛（molt的过去分词）

  Molten tin can get hotter than molten salt, but it cannot flow through metal pipes.
  相比熔融盐，熔融锡会产生更多的热能, 但这种材质不能在金属管道中流动。

  “Molten” is now usually used of hard materials liquified by very high heat, like lava, glass, and lead. Most other substances are “melted,” though some people like to refer to “molten cheese” and a popular dessert is called “molten chocolate cake,” perhaps to emphasize its gooey, lava-like character.

• tabletop

  n. 桌面

• fashion

  【熟词僻义】vt. 做成…的形状；使用；改变；塑造 v. make out of components (often in an improvising manner)
  “She fashioned a tent out of a sheet and a few sticks”

• ladle

  vt. 不分对象予以赠送；以杓舀取；n. 杓子；长柄杓

  

  The sour cream on the surface is carefully ladled out.
  表皮的酸奶油先被小心的舀出来。

  You take a big ladle of that masala sauce. Yep.
  你只要舀一勺香料酱。是的。

• brass plate

  铜板

• compass rose

  罗盘玫瑰

  A compass rose, sometimes called a windrose, or Rose of the Winds, is a figure on a compass, map, nautical chart, or monument used to display the orientation of the cardinal directions: North, East, South, and West—and their intermediate points. It is also the term for the graduated markings found on the traditional magnetic compass. Today, the idea of a compass rose is found on, or featured in, almost all navigation systems, including nautical charts, non-directional beacons (NDB), VHF omnidirectional range (VOR) systems, global-positioning systems (GPS), and similar equipment.

  

• what have you

  等等；诸如此类

• reinvigoration

  n. 重新振作

  But it’s Russia and the Russian artists who we have to thank for this reinvigoration.

  但我们必须感谢俄罗斯和俄罗斯艺术家，是他们带来了这场复兴。

  -> invigoration n. 鼓舞

  -> invigorate vt. 使生气勃勃;使精力充沛;使健壮; adj. 生气勃勃的;精力充沛的;健壮的

• The Age of Exploration

  大航海时期

• Magellan circumnavigating the globe

  麦哲伦环球航行

• horizon

  n. 地平线；眼界；范围；视野