# 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;
// 其余各点都是正无穷
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;
}

# 01背包～四次元背包里都会装上什么呢~$≧▽≦)/ 啊w 01背包呐～给出一堆不可拆分的东西，它们有各自的重量和对你来说相应的价值，但是你的背包能装的最大重量是有限的，这个时候要如何选择装哪些东西使得背包里的东西有着最大的总价值呢～ Continue reading 01背包～四次元背包里都会装上什么呢~\(≧▽≦)/ # 由前序遍历和中序遍历重构二叉树w #include <iostream> #include <vector> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; TreeNode * rebin(vector<int> pre, vector<int> in) { // 首先看看有米有东西吧 // 一个元素都没有的话 // 这个二叉树就只有一个NULL节点 // 直接返回即可w if (pre.size() == 0) return nullptr; // 根据前序遍历的定义 根节点一定在前序遍历结果的第一个位置上 // 而中序遍历的话 根结点必然需要等到它的左子树都输出完才会出现 // 利用这一点我们分开左右子树 int root_value = pre; TreeNode * root = new TreeNode(root_value); // 找到根节点在中序遍历里的下标 // 以此分开左右子树 int root_index_of_in = 0; for (int i = 0; i < in.size(); i++) { if (in[i] == root_value) { root_index_of_in = i; break; } } // 分开左右子树 // 按原始的顺序分别保存左右子树的前序遍历和中序遍历 vector<int> left_pre, left_in, right_pre, right_in; // 先是左子树 for (int i = 0; i < root_index_of_in; i++) { // 这里需要+1 // 因为前序遍历的话 第一个元素是根节点 // 所以需要跳过当前（下标为0）的这个元素 left_pre.emplace_back(pre[i+1]); left_in.emplace_back(in[i]); } // 然后是右子树 for (int i = root_index_of_in + 1; i < in.size(); i++) { right_pre.emplace_back(pre[i]); right_in.emplace_back(in[i]); } // 既然左右子树的前序遍历和中序遍历都有了 // 和我们一开始拿到的初始条件很相似吧～ // 那么递归吧w root->left = rebin(left_pre, left_in); root->right = rebin(right_pre, right_in); return root; } // 三种遍历方式～/ typedef enum { PRE_ORDER, IN_ORDER, POST_ORDER, } TreeTraversal; void print_with_order(TreeNode * root, TreeTraversal order) { // 如果根节点是空的 // 那啥都不用说直接返回吧 if (root == nullptr) return; // 看看使用什么序来遍历 // 本质上仅仅只是输出当前root节点的位置不一样 if (order == PRE_ORDER) { cout << root->val << ' '; print_with_order(root->left, order); print_with_order(root->right, order); } else if (order == IN_ORDER) { print_with_order(root->left, order); cout << root->val << ' '; print_with_order(root->right, order); } else { print_with_order(root->left, order); print_with_order(root->right, order); cout << root->val << ' '; } } int main(int argc, const char * argv[]) { vector<int> pre = {1,2,4,7,3,5,6,8}; vector<int> in = {4,7,2,1,5,3,8,6}; TreeNode * head = rebin(pre, in); // 用构建好的树输出前序和中序遍历来验证～ cout << "pre: "; print_with_order(head, PRE_ORDER); cout << endl; cout << "in: "; print_with_order(head, IN_ORDER); cout << endl; } # There is only one problem to solve——汉诺塔问题 汉诺塔问题的描述如下，汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱子，在一根柱子上从上往下从小到大顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一回只能移动一个圆盘，只能移动在最顶端的圆盘。 那么这里我们也先来思考最简单的情况（变量当然是盘子的个数\(n$啦），那么最简单的就是$n=1$了（当然，$n=0$也可以算是一种情况，不过没必要分析了） # 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!"