欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Keep2019届校招算法笔试题

程序员文章站 2022-07-13 14:17:31
...

1. 输入一个字符串和整数k,每3k个子串,将子串前面的k个字符反转,后面2*k个子串保持原样。如果剩余的子串长度不足3k,则如果长度小于k,此末尾子串全部反转,如果剩余的子串长度大于k且小于3k,则把前面的k个子串翻转,后面的末尾字符都保持原样。

代码如下:

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int main()
{
	string str;
	int k;
	cin >> str >> k;
	if (k <= 0) {
		cout << str << endl;
		return 0;
	}
	int n = str.size() / (3 * k);
	int t = str.size() - 3 * k*n;
	int i = 0, j = 0;
	for (; j < n; j++, i += 3 * k){
		reverse(str.begin() + i, str.begin() + i + k);
	}
	if (t<k&&t>0){
		reverse(str.begin() + i, str.end());
	}
	if (t >= k) {
		reverse(str.begin() + i,str.begin()+i+k);
	}
	cout << str << endl;
	return 0;
}

2.背包问题的变形,第一行输入容量Cap,和物体个数n,接下来n行表示n组物体体重和物体价值,求使得在此容量一定的条件下物体价值最大化的物品取法。1表示取物品,0表示不取物品。典型的动态规划问题,就是要加一个回溯函数。代码如下:

#include<iostream>
#include<algorithm>
using namespace std;

int fun(int** f, int i,int cap, int n, int* weight, int* profit)
{
	if (f[i][cap] > 0) {
		return f[i][cap];
	}
	if (i == n) {
		f[i][cap] = weight[n] <= cap ? profit[i] : 0;
		return f[i][cap];
	}
	if (weight[i] > cap) {
		f[i][cap] = fun(f, i + 1, cap, n, weight, profit);
	}
	else {
		f[i][cap] = max(fun(f, i + 1, cap, n, weight, profit), fun(f, i + 1, cap - weight[i], n, weight, profit) + profit[i]);
	}
	return f[i][cap];
}

void traceback(int** f, int* weight, int cap, int n, int* x)
{
	for (int i = 1; i <n; i++) {
		if (f[i][cap] == f[i + 1][cap]) {
			x[i] = 0;
		}
		else {
			x[i] = 1;
			cap -= weight[i];
		}
	}
	x[n]= weight[n] <= cap ? 1 : 0;
}
int main()
{
	int cap, n;
	cin >> cap>> n;
	int* profit = new int[n+1];
	int* weight = new int[n+1];
	for (int i =1; i <=n; i++) {
		cin >> weight[i] >> profit[i];
	}
	int** f = new int*[n+1];
	for (int i =0; i <=n; i++) {
		f[i] = new int[cap+1];
		for (int j = 0; j <= cap; j++) {
			f[i][j] = -1;
		}
	}
	int* x = new int[n + 1];
	//fun(f,cap,n,weight,profit);
	fun(f,1,cap,n,weight,profit);
	traceback(f,weight,cap,n,x);

	for (int i = 1; i <= n; i++) {
		cout << x[i] << endl;
	}

	delete [] profit;
	delete [] weight;
	for (int i = 0; i <=n; i++) {
		delete[] f[i];
	}
	delete [] f;
	return 0;
}

方法二,可以用迭代法写fun函数,代码如下

void fun(int** f, int cap, int n,int* weight,int* profit)
{
	int ymax = min(weight[n]-1, cap);
	for (int y = 0; y <=ymax; y++) {
		f[n][y] = 0;
	}
	for (int y =weight[n]; y <= cap; y++) {
		f[n][y] = profit[n];
	}
	for (int i = n-1; i>=1; i--) {
		ymax = min(weight[i]-1, cap);
		for (int y = 0; y <= ymax; y++) {
			f[i][y] = f[i + 1][y];
		}
		for (int y = weight[i]; y <= cap; y++) {
			f[i][y] = max(f[i + 1][y], f[i + 1][y - weight[i]] + profit[i]);
		}
	}
}

3.给定一个数字字符串,例如“1234”,输入一个整数k,例如4。求出所有可以被k整除的子串组合,此例输出12,124,24,4

(假设,子串的字符相对顺序是不能变化的,记不清题目了,,,,,如果是不管顺序,那就复杂了,先对字符串排序,然后调用bool next_permutation(iterator start,iterator end))产生此字符串的下一排列,即对所有可能的排列进行递归。)

#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

void dfs(string str,int b,string s,int k,set<int>& ret,vector<int>& used)
{
	if (!s.empty()&&stoi(s)%k == 0) {
		ret.insert(stoi(s));
	}
	for (int i = b; i < str.size(); i++) {
		if (used[i] == 0) {
			used[i] = 1;
			dfs(str, b + 1, s.append(1, str[b]), k, ret,used);
			s.pop_back();
			dfs(str, b + 1, s, k, ret,used);
			used[i] = 0;

		}
	}
}

int main()
{
	string str;
	int k;
	getline(cin, str);
	cin >> k;
	set<int> ret;
	vector<int> used(str.size(), 0);
	dfs(str,0,"",k,ret,used);
	for (int a : ret) {
		cout << a << endl;
	}
	system("pause");
	return 0;
}