Largest Rectangle in Histogram

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.
histogram
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
histogram_area
The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

题目链接在这里

继续阅读:

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.

题目链接在这里

题目要求对链表进行复制,不过这个链表稍微有点特殊:在每一个节点中除了指向下一个节点的指针,还有一个指向链表中随机节点的指针,如下:

这个链表看起来大概是这个样子:

带有随机指针的链表

带有随机指针的链表

这个随机指针对链表的拷贝造成了不小的麻烦…

继续阅读:

Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目链接在这里

这是一道很有意思的题目,大意是说在一个整型数组中,所有的数字都出现了两次,只有一个数是例外,找出这个数。

乍一看感觉很简单啊,开个数组计数就好了~可惜题目还要求要在不使用额外空间的情况下找到解,这就有点蛋疼了…如果使用二分查找倒是不会用到额外空间,可是时间复杂度为O(nlogn),又不符合题目要求的线性复杂度…

该怎么办呢?该怎么办呢?

继续阅读: