# Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

• -10000 <= Node.val <= 10000
• Node.random is null or pointing to a node in the linked list.
• Number of Nodes will not exceed 1000.
Continue reading Copy List with Random Pointer

# Integer to Roman

Roman numerals are represented by seven different symbols: IVXLCD and M.

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

# Maximum Rectangular Area in Histogram

The description of the maximum rectangular area in histogram problem is fairly simple. Given an array of the height of continuous bars with equal width, and the goal is to find the maximum rectangular area inside them. For example, the following figure shows the maximum rectangular area in pink of height array [1, 2, 3, 4, 5], which is 9.

Let's breakdown the problem. To form such a rectangular area, the following constraint must be satisfied.

All bars inside the area is at least as high as the rectangular.

Which suggests that no matter how we choose the rectangular, all involved bars must be continuous and the best height we could reach is limited to the lowest one.

As shown above, the maximum height of the rectangular area is limited to the lowest involved bar. (The height of the lowest one is mark in pink).

Continue reading Maximum Rectangular Area in Histogram

# Dijkstra's Shortest Path First algorithm

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

/*
输入
6
9
0 1 2
0 2 3
1 2 2
1 3 4
2 3 1
2 4 3
3 4 2
3 5 7
4 5 4
*/
int main(int argc, const char * argv[]) {
// 一共有多少个顶点
int n;
cin >> n;

// 初始化这个“图”
int64_t * graph = new int64_t[n * n];
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
graph[row * n + col] = INT64_MAX;
}
}

// 一共有多少组边
int p;
cin >> p;
for (int i = 0; i < p; i++) {
// 依次输入每一条边
int start, end, distance;
cin >> start >> end >> distance;
// 假设我们是无向图
// 无向图具有对称性～
graph[start * n + end] = distance;
graph[end * n + start] = distance;
}

// 保存定点是否被访问过
vector<bool> visited;
visited.resize(n);

// 保存源点到各点的最短距离
vector<int64_t> distance;
distance.resize(n);
// 起始点到自己的距离是0～
distance[0] = 0;
// 其余各点都是正无穷
for (int i = 1; i < n; i++) {
distance[i] = INT64_MAX;
}

// 保存路径的数组
vector<int> path;
path.resize(n);

// 从源点开始吧/
int current = 0;
while (true) {
// 标记当前节点已经访问
visited[current] = true;
// 找出当前点可以一步访问到的所有的点
for (int i = 0; i < n; i++) {
if (visited[i] == false && // i 没有被访问过
graph[current * n + i] != INT64_MAX // 并且current可以走到i这个顶点
) {
// 从 0 ->...-> current -> i
int64_t access_i_via_current = distance[current] + graph[current * n + i];
// 从 0 ->...-> i
int64_t access_i_via_other_path = distance[i];

// 如果经过当前的点
// 可以使得到 i 的距离变短的话
if (access_i_via_current < access_i_via_other_path) {
// 那么更新路径～下面这个赋值的意思是
// 下标 i 这个点
// 应该从 current 来更近
path[i] = current;
// 更新距离
distance[i] = access_i_via_current;
}
}
}

int64_t new_minimum = INT64_MAX;
for (int i = 0; i < n; i++) {
// 从还没有访问过的点中
if (visited[i] == false) {
// 找出有着最小距离的点扩展
if (distance[i] < new_minimum) {
current = i;
new_minimum = distance[i];
}
}
}

// 如果所有的点都访问过了
// 那么这个 new_minimum 就还是初始值 +INF
if (new_minimum == INT64_MAX) {
// 此时就说明可以结束了
break;
}
}

cout << "minimum distance 0->" << n-1 << " is " << distance[n - 1] << '\n';

// 保存最短路的路径
stack<int> minimum_path;
// 从最后一个点往回看
current = n - 1;
minimum_path.push(current);
while (minimum_path.top() != 0) {
// 从某个点到 current 是最近的
// 把那个点放进去～
minimum_path.push(path[current]);
// 再来准备看是哪个点 到 那个点最近
current = path[current];
}

// 按顺序输出整条路径
while (!minimum_path.empty()) {
cout << minimum_path.top() << ", ";
minimum_path.pop();
}
cout << endl;
}

# There is only one problem to solve——$2^k\times 2^k$棋盘覆盖问题

$2^k\times 2^k$棋盘覆盖问题描述如下，给出$k$的值，得到一块$2^k\times 2^k$大小的棋盘，棋盘上有一格是特殊方格。随后给出如下4种L型的骨牌，要求使用这四种L型的骨牌覆盖给定棋盘上的，除特殊方格以外的所有格子，并且任何两个L型骨牌不得重叠覆盖。

# Google Code Jam 2016 Round 1B Problem A in J language

You just made a new friend at an international puzzle conference, and you asked for a way to keep in touch. You found the following note slipped under your hotel room door the next day:

"Salutations, new friend! I have replaced every digit of my phone number with its spelled-out uppercase English representation ("ZERO", "ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX", "SEVEN", "EIGHT", "NINE" for the digits 0 through 9, in that order), and then reordered all of those letters in some way to produce a string S. It's up to you to use S to figure out how many digits are in my phone number and what those digits are, but I will tell you that my phone number consists of those digits in nondecreasing order. Give me a call... if you can!"