景驰笔试

发表于 | 分类于 |

周六笔试的，就三道编程题，蚊子拖延症。。。。一直拖到现在才写出来。

同时朋友今天告诉我，笔试通过了。。。。准备一下面试

其实三道题都是经典题，就是输入很恶心，因为它输入里面数字用逗号分开且逗号跟数字有任意空白字符。

第一题：装最多水问题

思路：采用两边逼近法，显而易见，当逐渐逼近的时候，容器的长在变短，那么要使得面积增大的话，宽必须要变大，所以我们保留长的那条线段，使得短线段向另一方逐渐逼近。

代码：

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
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
int main() {
	int num[100000], ind = 0;
	string in;
	while (cin >> in) {
		int sum = 0, flag = 0;
		for (int i = 0; i < in.size(); ++i) {
			if (in[i] > '9'||in[i] < '0') {
				if (flag)
					num[ind++] = sum, sum = 0, flag = 0;
			}
			else {
				flag = 1;
				sum = sum * 10 + in[i] - '0';
			}
		}
		if (flag)
			num[ind++] = sum;
	}
	int l = 0, r = ind - 1, maxn = 0, now = 0;
	while (l != r) {
		now = min(num[l], num[r])*(r - l);
		maxn = max(now, maxn);
		if (num[l] > num[r])
			r--;
		else
			l++;
	}
	cout << maxn << endl;
	return 0;
}

第二题：给定一个代表硬币不同面值的数组，和一个硬币的总数额，求用硬币凑出该总数额的最小硬币个数。如果无法凑出该面额，返回-1。

思路：用动态规划的方法，也就是完全背包，硬币总额从0开始，一步一步地往上加，直到amount。每一步记录得到该金额的最小硬币数。

代码：

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
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
int cmp(int x, int y) { return x > y; }
int num[100000], ind = 0, Size[11000000];
int main() {
	string in;
	while (cin >> in) {
		int sum = 0, flag = 0;
		for (int i = 0; i < in.size(); ++i) {
			if (in[i] > '9'||in[i] < '0') {
				if (flag)
					num[ind++] = sum, sum = 0, flag = 0;
			}
			else {
				flag = 1;
				sum = sum * 10 + in[i] - '0';
			}
		}
		if (flag)
			num[ind++] = sum;
	}
	int m = num[--ind];
	for (int i = 0; i <= m + 1; i++)
		Size[i] = m + 1;
	Size[0] = 0;
	sort(num, num + ind, cmp);
	for (int i = 0; i < ind; ++i)
		for (int j = num[i]; j <= m; j++)
			Size[j] = min(Size[j], Size[j - num[i]] + 1);
	cout << (Size[m] == m + 1 ? -1 : Size[m]) << endl;
	return 0;
}

第三题：leetcode 原题，最小跳跃II

思路：贪心，每次我们只要在某个步数所能涵盖的最大范围内设置它当前的步数，只有超过这个最大范围的时候才对这个步数加一。求下一个步数的时候则求在当前步数的范围内能涵盖的最大值。在具体的实现中，我们需要记录在每一步中它所能涵盖的最大值，每次到遍历到这个值的时候，我们的步数加一。另外，我们在每次的遍历中都要计算当前位置所能涵盖的最大范围以作为下一个步数所能涵盖的范围。

代码：

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
#include<algorithm>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
using namespace std;
int num[10000011], ind = 0;
int main()
{
    char in;
    int sum = 0, flag = 0;
    while ((in = getchar()) != EOF)
    {
        if (in > '9' || in < '0')
        {
            if (flag)
            {
                num[ind++] = sum, sum = 0, flag = 0;
            }
            else
            {
                flag = 1;
                sum = sum * 10 + in - '0';
            }
        }
    }

    if (flag)
        num[ind++] = sum;
    int maxcover = 0;
    int step = 0;
    int lastcover = 0;
    for(int i = 0; i <= maxcover && i < ind; i++)
    {
        if(i > lastcover)
        {
            step++;
            lastcover = maxcover;
        }
        if(num[i] + i > maxcover)
        {
            maxcover = num[i] + i;
        }
    }
    cout<< step <<endl;
    return 0;
}