Easy

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

return its minimum depth = 2.

Easy

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

1
2
3
4
5
6
7

      1
     / \
    2   2
   / \
  3   3
 / \
4   4

Return false.

虽然简单，但仍然不能小看的一道题。判断一棵树是否是平衡二叉树，平衡二叉树定义如下：

它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

教材：W3school, MDN web doc

1. HTML hyper text markup language 超文本标记语言，是用来描述网页的一套语言。不是编程语言而是标记语言。标记语言是一套标记标签 markup tag。

2. markup tag 标记标签：

   成对出现，比如<b> 和 </b>（没想到typora除了自动识别Markdown，也会识别HTML，可以使用< > 效果 <p> </p>），<b>是开始标签，</b>是结束标签

3. HTML 文档 = HTML 标签 + 纯文本 = 网页

4. <p>This is a paragraph.</p>

   <h1>This is a heading.</h1>

   <a href="http://......">This is a link.</a> 在href 属性中指定地址

   <img src="aaa.jpg" width="104" height="142" /> 图像的名称和尺寸是以属性的形式提供的。注意，这是一个空元素void element, 即使是空元素，也需要加结尾/>

5. HTML 元素

   HTML元素是从开始标签到结束标签里所有的代码。某些元素有空内容。大多数元素可以拥有属性。元素之间可以嵌套。

   虽然对大小写不敏感，但推荐使用小写标签，然后每一个元素都要关闭，哪怕是空元素 <br /> <img src="aaa.jpg" width="104" height="142" />

6. HTML 属性

   属性可以为元素提供更多的信息。总是以名称=值（name=“value”）形式出现。总是在开始标签里规定。

   多个属性之间空格间隔，属性名称后紧跟=，属性值一定要使用“”包围（不然浏览器会误解）

   虽然对大小写不敏感，但推荐使用小写。始终为属性加引号，单双引号都可以，但里面出现双引号，外面就要使用单引号。

   布尔属性：属性值与属性名称相等，如disabled

   例子， 全局属性参考手册

7. 当显示页面时，浏览器会移除源代码中多余的空格和空行。所有连续的空格或空行都会被算作一个空格。需要注意的是，HTML 代码中的所有连续的空行（换行）也被显示为一个空格

   如果想保留这些换行和空格，可以使用

   1 2 3 4 5 6 7

   8. 超级链接: 基本格式 ```html <a href="url">Link text</a>

​ target：在新窗口打开网页

1

<a href="http://www.w3school.com.cn/" target="_blank">Visit W3School!</a>

​ name：命名锚，读者看不见，但可以用它实现界面跳转。使用 id 属性来替代 name 属性，命名锚同样有效。

1

<a name="label">锚（显示在页面上的文本）</a>

然后，我们在同一个文档中创建指向该锚的链接：

1

<a href="#label">有用的提示</a>

您也可以在其他页面中创建指向该锚的链接：

1

<a href="http://www.w3school.com.cn/html/html_links.asp#tips">有用的提示</a>

9. 当同一个 HTML 元素被不止一个样式定义时，会使用哪个样式呢？

   一般而言，所有的样式会根据下面的规则层叠于一个新的虚拟样式表中，其中数字 4 拥有最高的优先权。

   1. 浏览器缺省设置
   2. 外部样式表
   3. 内部样式表（位于 标签内部）
   4. 内联样式（在 HTML 元素内部）

   因此，内联样式（在 HTML 元素内部）拥有最高的优先权，这意味着它将优先于以下的样式声明： 标签中的样式声明，外部样式表中的样式声明，或者浏览器中的样式声明（缺省值）。

10. 块级元素(block-level)和内联元素(inline)

    Block-level element: will appear on a new line eg.

    Inline element: are contained within block-level elements and surround only small parts of the document’s content

1
2
3

<em>first</em><em>second</em><em>third</em> inline element

<p>fourth</p><p>fifth</p><p>sixth</p>  block element

11. 元数据 元素

元数据就是描述数据的数据

1

<meta charset="utf-8"> 字符集

utf-8包含了任何人类语言的大部分字符，没有出现在字符集里的字符会显示乱码。

1
2
3
4

<meta name="author" content="Chris Mills">
<meta name="description" content="The MDN Learning Area aims to provide
complete beginners to the Web with all they need to know to get
started with developing web sites and applications.">

指定包含关于页面内容的关键字的页面内容的描述是很有用的，因为它可能或让你的页面在搜索引擎的相关的搜索出现得更多，SEO搜索引擎优化。description就是出现在搜索网页结果下面的一段描述。

许多meta元素不再使用了，比如key — 提供关键词给搜索引擎，根据不同的搜索词，查找到相关的网站 — 已经被搜索引擎忽略了， 因为作弊者填充了大量关键词到keyword， 错误地引导搜索结果。

其他类型元数据：

1
2
3
4
5

<meta property="og:image" content="https://developer.cdn.mozilla.net/static/img/opengraph-logo.dc4e08e2f6af.png">
<meta property="og:description" content="The Mozilla Developer Network (MDN) provides
information about Open Web technologies including HTML, CSS, and APIs for both Web sites
and HTML5 Apps. It also documents Mozilla products, like Firefox OS.">
<meta property="og:title" content="Mozilla Developer Network">

在facebook（不仅仅，linkedin也支持）上链接网页时，所展示的图片，描述和标题

12. 在HTML里应用CSS和JavaScript

    HTML：网站内容

    CSS：网站样式

    JavaScript：网站的互动

    1. link元素经常位于文档的头部。这个link元素有2个属性，rel=”stylesheet”表明这是文档的样式表，而 href包含了样式表文件的路径
    2. Script 元素放在文档末尾，这样可以确保在加载脚本之前浏览器已经解析了HTML内容（如果脚本加载某个不存在的元素，浏览器会报错）

1
2
3

<link rel="stylesheet" href="my-css-file.css">

<script src="my-js-file.js"></script>

Medium

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

1
2
3
4
5

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

1
2
3
4
5
6
7

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

Hard

424078FavoriteShare

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Hard

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

1
2

Input: [2,1,5,6,2,3]
Output: 10

Easy

Suppose we have a class:

1
2
3
4
5

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().

Example 1:

1
2
3

Input: [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

Example 2:

1
2
3

Input: [1,3,2]
Output: "firstsecondthird"
Explanation: The input [1,3,2] means thread A calls first(), thread B calls third(), and thread C calls second(). "firstsecondthird" is the correct output.

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) – Push element x onto stack.
• pop() – Removes the element on top of the stack.
• top() – Get the top element.
• getMin() – Retrieve the minimum element in the stack.

Example:

1
2
3
4
5
6
7
8

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Medium

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

1
2

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

1
2

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

\146. LRU Cache

Medium

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?