分类目录归档：coding

面试题整理

各家的面试基本上都告一段落了，整理下自己觉得有意思的题目吧。

1. 一个大小为n的数组，元素有正有负，求将所有负数放在正数前面的稳定的算法。

解：考虑归并排序的思路，每次将两个子段合并整理成一长段的过程，即为[负][正][负][正]，转换成[负][正]的形式。时间复杂度是O(NlgN)的。

2. 有n个囚犯排成一列，每个人头上有帽子，帽子是黑色或者白色。每个人只能看到自己前面的人的帽子，看不到自己和自己后面人的帽子。从后往前，每个人需要报出自己帽子的颜色，如果错了就被处决，否则就被释放。前面的人能听到后面的人报的是黑还是白。求一个确定的策略，使得尽可能多的囚犯被释放。

解：最优解只牺牲最后面的一个人。把黑帽子视作0，把白帽子视作1，每个人求他前面所有人帽子颜色值的异或值。最后面的人报出异或值后，从倒数第二个人开始，每个人都能根据他后面人的帽子颜色来计算出自己头上帽子是什么颜色。

3. 有100个囚徒，每人在不同的房间。另有一个大厅，大厅里有一盏灯，初始是关的。每天会有一个囚徒被从房间叫出到大厅，并能开、关灯。也即每个囚徒能知道的信息包括：1. 当前是第几天；2. 如果被叫到大厅了，灯是开着的还是关着的。每个囚犯到大厅时，都可以选择告诉警官“所有人都至少来过大厅一次了”，如果确实如此，那么所有囚徒都会被释放，不过只有一次机会尝试。问一个确定的方案，使得这些囚徒能够重获自由。并且需要分析该方案完成的期望天数。

解：考虑选第一天出到大厅的囚徒为master，只有master有权力关灯，其他囚徒会且仅会开一次灯，那么当master关了99次灯之后，就知道所有人都至少出来过一次了。期望天数是1 + 100/99 + 100/1 + 100/98 + 100/1 + … + 100/1 + 100/1。

4. 有一个线段，线段上有两点A、B，有两个机器人分别在这两个点上。初始A、B点位置不确定，线段无限长。你需要为这两个机器人写一段相同的程序，使得他们可以相遇。指令集是给定的，包括4种指令：
1. move left 向左移动（耗时1）
2. move right 向右移动（耗时1）
3. if at A点或B点
4. goto 某行

解：考虑使两个机器人同时向右走，一开始都是慢走，其中一个机器人一定会遇到另一个机器人出发的起点（A或B），那么将其转换成快走模式，追赶慢走的机器人。
1: move right
2: move left
3: move right
4: if at A点或B点
5: goto 7:
6: goto 1:
7: move right
8: goto 7:

5. 求一个完全二叉树的结点总数。

解：完全二叉树有这样的性质：对于树上任意的一个结点，其左子树或右子树中至少有一个是满二叉树。可以通过探测最左和最右结点的深度来判断这棵树是不是满二叉树，时间复杂度是O(lgN)的。因此，依次从最高层向下，每层判断是否满二叉树后最多只沿其中一个子树继续向下，这里时间复杂度是O(lgN)+O(lg(N/2))+…+O(lg(N/N)) = O((lgN)^2)的。

6. 有100层楼，以及这样一种鸡蛋：该鸡蛋从某层以上的楼层往下丢会摔碎，而从该层以下往下丢则是怎么摔都不会碎。给你两个鸡蛋，要求通过最少的尝试次数试出这个鸡蛋从哪层开始会碎。扩展：有N层楼和M个鸡蛋的情况。

解：第一个鸡蛋用来大致试探，第二个鸡蛋需要逐层试探。第一个鸡蛋试探的楼层间隔即是第二个鸡蛋最多要尝试的上限。那么第一个鸡蛋划分出的间隔应该是逐渐递减的，这样才能使总尝试次数最小。例如，第一个鸡蛋分别从x、x+(x-1)、x+(x-1)+(x-2)、…开始往下丢，第二鸡蛋分别需要尝试x-1、x-2、x-3…次，那么最坏情况下总是需要x次尝试就能试出楼层数了。这里需要使得x(x+1)/2 >= 100-1，解得x>=14。这里是100-1是因为，如果刚好x(x+1)/2==99还没碎，那么肯定是第100层楼才会碎的，也就不用额外去试了。
扩展的情况下，考虑3个鸡蛋，若设最多尝试次数为x，那么第一个鸡蛋划分出的区间之间的间隔应该是使得两个鸡蛋的总尝试次数递减的，也即需要满足sum{x(x-1)/2} >= M-2。4个鸡蛋的情况就是sum{sum{x(x-1)/2}} >= M-3，依此类推。

O(n)找无序数组第k大的元素

发表回复

最近一直在面试，不时会被问到找无序数组中第k大元素的题。基本做法，看到过都是基于快排的partition思想的，时间复杂度虽然说平均O(n)，但是极端情况下会退化成O(n^2)。这个方法写起来不但很麻烦，复杂度方面也一直让我纠结，实在是一百万个不喜欢。

于是开始自己考虑别的解法。

传统的partition中最不好的地方是无法确定中位元的位置，也即难以将数组分成尽可能均等的两份。那么可不可以从别的角度来作划分呢？仔细思考后发现可以从bit方面作文章的。

假设数组存储的全部都是int类型的正整数（如果是long long或者有负数的情况也是类似的），从最高位开始，将所有该位为0的数放到数组的左面，将所有为1的数放到数组的右面，这显然是一个O(n)的划分过程。划分结果可以得到一个中间位置，其左面的数全部小于右边。到这里思路应该很清楚了：依次对更低的每一位重复该操作，就可以逐步逼近第k大的数。由于int正数最多只有31位，那么总的时间复杂度便是O(31n)的。虽然上界情况常数很大，但由于实际上不可能每次都扫遍整个数组的，所以实际的时间会比较接近O(n)。该算法还有很多其他好处，例如空间是O(1)的，也不存在退化的问题。

下面是实现代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n, m, a[10000000];

void init() {
	for(int i=0; i<n; i++) scanf("%d", a+i);
}

int partition(int a[], int n, int m, int b) {
	if(n==1) return a[0];
	int i, j;
	for(i=0, j=n-1; i<j; ) {
		while(i<j && !(a[i]&b)) i++;
		while(i<j && (a[j]&b)) j--;
		if(i<j) swap(a[i], a[j]);
	}
	if(a[i]&b) i--;
	if(n-1-i>=m) {
		return partition(a+i+1, n-1-i, m, b>>1);
	} else {
		return partition(a, i+1, m-(n-1-i), b>>1);
	}
}

void solve() {
	printf("%d\n", partition(a, n, m, 1<<30));
}

int main() {
	while(~scanf("%d%d", &n, &m)) {
		init();
		solve();
	}
	return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n, m, a[10000000];

void init() {

for(int i=0; i<n; i++) scanf("%d", a+i);

}

int partition(int a[], int n, int m, int b) {

if(n==1) return a[0];

int i, j;

for(i=0, j=n-1; i<j; ) {

while(i<j && !(a[i]&b)) i++;

while(i<j && (a[j]&b)) j--;

if(i<j) swap(a[i], a[j]);

}

if(a[i]&b) i--;

if(n-1-i>=m) {

return partition(a+i+1, n-1-i, m, b>>1);

} else {

return partition(a, i+1, m-(n-1-i), b>>1);

}

void solve() {

printf("%d\n", partition(a, n, m, 1<<30));

}

int main() {

while(~scanf("%d%d", &n, &m)) {

init();

solve();

}

return 0;

}

不知道有没错呢，细心的人帮我看看好了。 =)

附送测试数据：

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

20 1

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

20 5

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

20 10

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

20 15

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

20 20

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

从此妈妈再也不用担心我不会解第k大元素啦！！！

ps：吐槽一下，竟然还有人写了这么长的文章来分析时间复杂度…能全部看完的人请一定来教育教育我。

[LeetCode Largest Rectangle in Histogram]

发表回复

Largest Rectangle in Histogram

题意：给出一个长度n的数组，每个值为非负数，描述一个宽为1的立柱的高h[i]，求立柱围成区域中最大的矩形区域面积。

分析：
对于每个立柱i，求出满足h[j]到h[i-1]都不小于h[i]的最左值j，记i-j+1为lc[i]，类似地求出rc[i]，那么位置i对应的最大可行面积即为h[i]*(lc[i]+rc[i]+1)。

以求lc[i]为例，需要一个单调栈，单调栈中由底到顶依次记录扫描到i之前的上升序列d[l]及其位置di[l]，扫描到i时，初始化lc[i]=1，对于所有高度d[l]大于等于h[i]的栈顶元素，依次出栈，并将其lc[di[l]]加到lc[i]中，最后将h[i]和i入栈。

时间复杂度方面，计算lc和rc时，每个元素刚好入栈、出战各一次，因此根据平摊分析，时间复杂度是O(n)的。

int d[100000], di[100000], lc[100000], rc[100000], n, ans;

class Solution {
public:
    int largestRectangleArea(vector<int> &h) {
        n=h.size(); ans=0;
        int i, l;
        for(i=0, l=0; i<n; i++)
        {
            for(lc[i]=1; l&&h[i]<=d[l-1]; l--)
                lc[i]+=lc[di[l-1]];
            d[l]=h[i];
            di[l++]=i;
        }
        for(i=n-1, l=0; i>-1; i--)
        {
            for(rc[i]=1; l&&h[i]<=d[l-1]; l--)
                rc[i]+=rc[di[l-1]];
            d[l]=h[i];
            di[l++]=i;
        }
        for(i=0; i<n; i++)
            ans=max(ans, h[i]*(lc[i]+rc[i]-1));
        return ans;
    }
};

int d[100000], di[100000], lc[100000], rc[100000], n, ans;

class Solution {

public:

int largestRectangleArea(vector<int> &h) {

n=h.size(); ans=0;

int i, l;

for(i=0, l=0; i<n; i++)

{

for(lc[i]=1; l&&h[i]<=d[l-1]; l--)

lc[i]+=lc[di[l-1]];

d[l]=h[i];

di[l++]=i;

}

for(i=n-1, l=0; i>-1; i--)

{

for(rc[i]=1; l&&h[i]<=d[l-1]; l--)

rc[i]+=rc[di[l-1]];

d[l]=h[i];

di[l++]=i;

}

for(i=0; i<n; i++)

ans=max(ans, h[i]*(lc[i]+rc[i]-1));

return ans;

}

};

ps：最早是半年前被问到了这题。现在回头看看，写得真是惨不忍睹。现在做LeetCode又遇到这题，分析题意方面，要比之前稍好一些了吧……

[LeetCode Unique Binary Search Trees II]

1条回复

Unique Binary Search Trees II

题意：输入是n，要求枚举出包含1…n这n个整数的所有二叉搜索树（BST）。

分析：显然这题n不可能很大，考察的是如何枚举每种可能的状态。首先考虑了所有全排列的插入构建BST，发现这样得到的BST有重复。然后发现，若设n的全部BST为T(n)，当根是i时，其左子树的所有可能情况为T(i-1)，右子树的所有可能情况为T(n-i)。这样就可以按n由小到大地递推构造出各个BST了。

int vvpl=0;
vector<vector<TreeNode *>> vvp;
vector<TreeNode *> vp;
vector<TreeNode *>::iterator it1, end1, it2, end2;

TreeNode *mk(TreeNode *p, int d)
{
    if(!p)
        return 0;
    TreeNode *q=new TreeNode(p->val+d);
    q->left=mk(p->left, d);
    q->right=mk(p->right, d);
    return q;
}

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        int i, j, k, l;
        TreeNode *p;
        if(vvpl<=n)
        {
            if(vvpl==0)
            {
                vvp.push_back(vp);
                vvp[0].push_back(0);
                vvpl=1;
            }
            for(; vvpl<=n; vvpl++)
            {
                vvp.push_back(vp);
                for(i=1; i<=vvpl; i++)
                {
                    for(it1=vvp[i-1].begin(), end1=vvp[i-1].end(); it1!=end1; it1++)
                    {
                        for(it2=vvp[vvpl-i].begin(), end2=vvp[vvpl-i].end(); it2!=end2; it2++)
                        {
                            p=new TreeNode(i);
                            p->left=mk(*it1, 0);
                            p->right=mk(*it2, i);
                            vvp[vvpl].push_back(p);
                        }
                    }
                }
            }
        }
        return vvp[n];
    }
};

int vvpl=0;

vector<vector<TreeNode *>> vvp;

vector<TreeNode *> vp;

vector<TreeNode *>::iterator it1, end1, it2, end2;

TreeNode *mk(TreeNode *p, int d)

{

if(!p)

return 0;

TreeNode *q=new TreeNode(p->val+d);

q->left=mk(p->left, d);

q->right=mk(p->right, d);

return q;

}

class Solution {

public:

vector<TreeNode *> generateTrees(int n) {

int i, j, k, l;

TreeNode *p;

if(vvpl<=n)

{

if(vvpl==0)

{

vvp.push_back(vp);

vvp[0].push_back(0);

vvpl=1;

}

for(; vvpl<=n; vvpl++)

{

vvp.push_back(vp);

for(i=1; i<=vvpl; i++)

{

for(it1=vvp[i-1].begin(), end1=vvp[i-1].end(); it1!=end1; it1++)

{

for(it2=vvp[vvpl-i].begin(), end2=vvp[vvpl-i].end(); it2!=end2; it2++)

{

p=new TreeNode(i);

p->left=mk(*it1, 0);

p->right=mk(*it2, i);

vvp[vvpl].push_back(p);

}

return vvp[n];

}

};

ps：LeetCode上面很多这种要求构造出所有可行解的题目，这是之前做的ACM中几乎没有的。虽然题型相对陌生，但解起来也很好玩~

[LeetCode Word Ladder II]

3条回复

Word Ladder II

题意：给出一个初始字符串S和目标字符串T，以及可行的中间字符串集合dict，转换字符串时仅允许一次改变一个字符，要求从S变为T的所有最短可行序列。

分析：首先，需要枚举每个字符串可行的改变方式，并用BFS建图：建立结点编号对可达字符串的映射关系，并记录每个结点的深度。建图结束后，用深搜的方式枚举出所有可行的字符串，剪枝方案只简单记录了无效结点。最后跑出的时间是1096 ms。

vector<vector<string> > vvs;
vector<string> vs;
map<string, int> Msi;
map<int, string> Mis;
int hd[100000], el, si, ti, sl, d[100000];
char b[100000];

struct E
{
    int v, p;
}e[100000];

void adde(int u, int v)
{
    e[el].v=v; e[el].p=hd[u]; hd[u]=el++;
}

void bfs(string s, string t, unordered_set<string> &dict)
{
    int i, j, k, l, u, v;
    queue<string> Q;
    d[si]=0;
    Msi[s]=si++;
    Mis[0]=s;
    Q.push(s);
    while(!Q.empty())
    {
        s=Q.front(); Q.pop();
        u=Msi[s];
        for(i=0; i<sl; i++)
        {
            k=s[i];
            for(j='a'; j<='z'; j++)
            {
                if(j==k)
                    continue;
                s[i]=j;
                if(dict.find(s)==dict.end())
                    continue;
                if(Msi.find(s)!=Msi.end())
                {
                    v=Msi[s];
                    if(d[v]==d[u]+1)
                        adde(u, v);
                    continue;
                }
                v=Msi[s]=si++;
                d[v]=d[u]+1;
                Mis[v]=s;
                Q.push(s);
                adde(u, v);
            }
            s[i]=k;
        }
    }
}

int dfs(int u, int vsl)
{
    if(b[u]||vsl>d[ti])
        return b[u]=1;
    int l, v;
    if(vs.size()<=vsl)
        vs.push_back(Mis[u]);
    else
        vs[vsl]=Mis[u];
    if(u==ti)
    {
        vvs.push_back(vs);
        return 0;
    }
    b[u]=1;
    for(l=hd[u]; l!=-1; l=e[l].p)
    {
        v=e[l].v;
        if(!dfs(v, vsl+1))
            b[u]=0;
    }
    return b[u];
}

class Solution {
public:
    vector<vector<string>> findLadders(string s, string t, unordered_set<string> &dict) {
        dict.insert(t);
        vvs.clear();
        vs.clear();
        Msi.clear();
        Mis.clear();
        memset(hd, -1, sizeof hd);
        memset(b, 0, sizeof b);
        si=el=0;
        sl=s.length();
        bfs(s, t, dict);
        if(Msi.find(t)==Msi.end())
            return vvs;
        ti=Msi[t];
        dfs(0, 0);
        return vvs;
    }
};

100

101

vector<vector<string> > vvs;

vector<string> vs;

map<string, int> Msi;

map<int, string> Mis;

int hd[100000], el, si, ti, sl, d[100000];

char b[100000];

struct E

{

int v, p;

}e[100000];

void adde(int u, int v)

{

e[el].v=v; e[el].p=hd[u]; hd[u]=el++;

}

void bfs(string s, string t, unordered_set<string> &dict)

{

int i, j, k, l, u, v;

queue<string> Q;

d[si]=0;

Msi[s]=si++;

Mis[0]=s;

Q.push(s);

while(!Q.empty())

{

s=Q.front(); Q.pop();

u=Msi[s];

for(i=0; i<sl; i++)

{

k=s[i];

for(j='a'; j<='z'; j++)

{

if(j==k)

continue;

s[i]=j;

if(dict.find(s)==dict.end())

continue;

if(Msi.find(s)!=Msi.end())

{

v=Msi[s];

if(d[v]==d[u]+1)

adde(u, v);

continue;

}

v=Msi[s]=si++;

d[v]=d[u]+1;

Mis[v]=s;

Q.push(s);

adde(u, v);

}

s[i]=k;

}

int dfs(int u, int vsl)

{

if(b[u]||vsl>d[ti])

return b[u]=1;

int l, v;

if(vs.size()<=vsl)

vs.push_back(Mis[u]);

else

vs[vsl]=Mis[u];

if(u==ti)

{

vvs.push_back(vs);

return 0;

}

b[u]=1;

for(l=hd[u]; l!=-1; l=e[l].p)

{

v=e[l].v;

if(!dfs(v, vsl+1))

b[u]=0;

}

return b[u];

}

class Solution {

public:

vector<vector<string>> findLadders(string s, string t, unordered_set<string> &dict) {

dict.insert(t);

vvs.clear();

vs.clear();

Msi.clear();

Mis.clear();

memset(hd, -1, sizeof hd);

memset(b, 0, sizeof b);

si=el=0;

sl=s.length();

bfs(s, t, dict);

if(Msi.find(t)==Msi.end())

return vvs;

ti=Msi[t];

dfs(0, 0);

return vvs;

}

};

ps：不得不说LeetCode做题好刺激，每题都不给数据范围，并且debug非常困难，基本就是各种靠猜。这题整整交了48次才过，实在是太多的血与泪。

Pythoning…

发表回复

读了a byte of python后，顺手把a byte of vim也读了。唔，就是用起来还不是很顺手……

刚做的codeforces r195d2c，C一下就过了。。。python就一直TLE。看了下status，竟然没有用python3做的，python2的倒是有几个。明明只是N=10^5，O(N*lgN)的复杂度，却要各种找优化……看来python还真是非高手不能用：用C就是怎样烂的代码只要复杂度没错基本都能过，用python就非得尽量优化不可啊。。。

贴个code纪念一下吧：

n = int(input())
a = list(map(int, input().split()))

mxa = max(a)
v = 1 << 30
while v > mxa:
    v >>= 1

while True:
    d = -1
    for i in range(n):
        if a[i] & v:
            d &= a[i]
    if d % v == 0:
        break
    v >>= 1

b = [i for i in a if i & v]
print(len(b))
print(' '.join(map(str, b)))

n = int(input())

a = list(map(int, input().split()))

mxa = max(a)

v = 1 << 30

while v > mxa:

v >>= 1

while True:

d = -1

for i in range(n):

if a[i] & v:

d &= a[i]

if d % v == 0:

break

v >>= 1

b = [i for i in a if i & v]

print(len(b))

print(' '.join(map(str, b)))

这是C的，对比一下就清楚了，python是最后才构建b[]的，每次赋值太慢了：

int n,a[100000],k,b[100000];

int main()
{
	int i,d,v;
	while(~scanf("%d",&n))
	{
		k=0;
		for(i=0;i<n;i++) scanf("%d",a+i);
		for(v=1<<30;1;v>>=1)
		{
			k=0;
			d=-1;
			for(i=0;i<n;i++)
			{
				if(a[i]&v)
				{
					d&=a[i];
					b[k++]=a[i];
				}
			}
			if(d%v==0) break;
		}
		printf("%d\n",k);
		for(i=0;i<k-1;i++) printf("%d ",b[i]);
		printf("%d\n",b[k-1]);
	}
	return 0;
}

int n,a[100000],k,b[100000];

int main()

{

int i,d,v;

while(~scanf("%d",&n))

{

k=0;

for(i=0;i<n;i++) scanf("%d",a+i);

for(v=1<<30;1;v>>=1)

{

k=0;

d=-1;

for(i=0;i<n;i++)

{

if(a[i]&v)

{

d&=a[i];

b[k++]=a[i];

}

if(d%v==0) break;

}

printf("%d\n",k);

for(i=0;i<k-1;i++) printf("%d ",b[i]);

printf("%d\n",b[k-1]);

}

return 0;

}