面试题整理1

Posted on Edited on In

在看《程序员面试金典》，里面150题有一些不错的，提交地址，记录整理一下：

5.3最接近的数

有一个正整数，请找出其二进制表示中1的个数相同、且大小最接近的那两个数。(一个略大，一个略小)

略大的数，考虑把数字最末端的那个0变成1，之后把剩下的1都堆到最左边，当然这需要过滤0（从左到右），再找1，再找0，把这个0变为1。

略小的数，考虑把数字最末端的那个1变成0，之后把剩下的1都堆到最右边，先过滤1，再找0，再找1，把这个1变为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class CloseNumber
{
public:
	int find_min(int x)
	{
		int res = x;
		int p = 0;
		int cnt1 = 0, cnt0 = 0;
		while ((1 << p)&res)
		{
			res ^= (1 << p);
			p++;
			cnt1++;
		}
		cnt0++;
		p++;
		while (((1 << p)&res) == 0)
		{
			p++;
			cnt0++;
		}
		cnt1++;
		res ^= (1 << p);
		res ^= ((1 << cnt1) - 1) << (cnt0 - 1);
		return res;
	}
	int find_max(int x)
	{
		int res = x;
		int p = 0;
		int cnt1 = 0, cnt0 = 0;
		while (((1 << p)&res)==0)
		{
			p++;
			cnt0++;
		}
		res ^= (1 << p);
		p++;
		while (((1 << p)&res))
		{
			res ^= (1 << p);
			p++;
			cnt1++;
		}
		res ^= (1 << p);
		cnt0++;
		res ^= ((1 << cnt1) - 1);
		return res;
	}
	vector<int> getCloseNumber(int x)
	{
		vector<int>ans;
		ans.push_back(find_min(x));
		ans.push_back(find_max(x));
		return ans;
	}
}wc;

5.7像素设定

有一个单色屏幕储存在一维数组中，其中数组的每个元素代表连续的8位的像素的值，请实现一个函数，将第x到第y个像素涂上颜色(像素标号从零开始)，并尝试尽量使用最快的办法。

给定表示屏幕的数组screen(数组中的每个元素代表连续的8个像素，且从左至右的像素分别对应元素的二进制的从低到高位)，以及int x,int y，意义如题意所述，保证输入数据合法。请返回涂色后的新的屏幕数组。

写起来陷阱还是挺多，挺麻烦的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Render 
{
public:
	vector<int> renderPixel(vector<int> screen, int x, int y)
	{
		int rx = x / 8, cx = x % 8;
		int ry = y / 8, cy = y % 8;

		if (rx < ry)
		{
			for (int k = rx + 1; k < ry; k++)
			{
				screen[k] = 0xff;
			}
			int num = 8 - cx;
			screen[rx] |= (((1 << (num)) - 1) << cx);
			screen[ry] |= ((1 << (cy + 1)) - 1);
		}
		else
		{
			screen[rx] |= 0xff & ~((1 << cx) - 1)&((1 << (cy + 1)) - 1);
		}
		return screen;
	}
};

9.3魔术索引(1)

在数组A[0..n-1]中，有所谓的魔术索引，满足条件A[i]=i。给定一个升序数组，元素值各不相同，编写一个方法，判断在数组A中是否存在魔术索引。请思考一种复杂度优于o(n)的方法。

给定一个int数组A和int n代表数组大小，请返回一个bool，代表是否存在魔术索引。

如果元素各不相同，通过A[mid]与mid之间的比较，可以直接二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n)
    {
        int sz = A.size();
        int le = 0, ri = sz - 1;
        while (le < ri)
        {
            int mid = (le + ri) >> 1;
            if (A[mid] == mid)
            {
                return true;
            }
            else if (A[mid] > mid)
            {
                ri = mid - 1;
            }
            else
            {
                le = mid + 1;
            }
        }
        return A[le]==le;
    }
};

魔术索引(2)

在数组A[0..n-1]中，有所谓的魔术索引，满足条件A[i]=i。给定一个不下降序列，元素值可能相同，编写一个方法，判断在数组A中是否存在魔术索引。请思考一种复杂度优于o(n)的方法。

给定一个int数组A和int n代表数组大小，请返回一个bool，代表是否存在魔术索引。

元素如果可能重复的话，那么二分就不能判定了，每次递归搜索左半部分和右半部分，可以跳过一些元素。具体情况看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class MagicIndex {
public:
	bool findMagicIndex(vector<int> A, int n)
	{
		return find(A, 0, n, n);
	}
	bool find(vector<int>&A, int st, int en, int n)
	{
		if (st > en || st<0 || en>n)return false;
		int mid = (st + en) >> 1;
		if (A[mid] == mid)return true;
		int le = min(mid - 1, A[mid]);
		int ri = max(mid + 1, A[mid]);

		return find(A, st, le, n) || find(A, ri, en, n);
	}
}wc;

9.10推箱子

有一堆箱子，每个箱子宽为wi，长为di，高为hi，现在需要将箱子都堆起来，而且为了使堆起来的箱子不到，上面的箱子的宽度和长度必须小于下面的箱子。请实现一个方法，求出能堆出的最高的高度，这里的高度即堆起来的所有箱子的高度之和。

给定三个int数组w,l,h，分别表示每个箱子宽、长和高，同时给定箱子的数目n。请返回能堆成的最高的高度。保证n小于等于500。

和最长递增数列一个动态规划的思路，前面来一个冒泡排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Box 
{
public:
	int getHeight(vector<int> w, vector<int> l, vector<int> h, int n)
	{
		for (int i = 0; i < w.size(); i++)
		{
			for (int j = 0; j < w.size() - i - 1; j++)
			{
				if (w[j] > w[j + 1])
				{
					swap(w[j], w[j + 1]);
					swap(l[j], l[j + 1]);
					swap(h[j], h[j + 1]);
				}
			}
		}
		for (int i = 0; i < w.size(); i++)
		{
			cout << w[i] << " " << l[i] << " " << h[i] << endl;
		}
		vector<int>res(w.size(), 0);
		for (int i = w.size()-1; i >= 0 ; i--)
		{
			int ans = 0;
			for (int j = w.size()-1; j > i; j--)
			{
				if (w[i] < w[j] && l[i] < l[j])
				{
					ans = max(ans, res[j]);
				}
			}
			res[i] = ans + h[i];
		}
		int ans = 0;
		for (auto it : res)
		{
			ans = max(ans, it);
		}
		return ans;
	}
};