1. 2018微软预科生计划最后一道

1.1 问题描述

小明在实习，每天可以选择一个eazy的工作，或者一个hard的工作。但是当且仅当前一天没有工作时，才能在当天选择hard 的工作。不同的工作对应的salary不同。 给出在实习的天数和这些天里所有工作对应的salary组合。求出小明能拿到的最大salary

输入： numOfDays，整数             salaryList，N*2的二维数组 输出： maxSalary，整数

实例： numOfDays： 4             salaryList： [[1,5],[2,3],[2,9],[1,3]]             输出： 5+0+9+1=15

1.2 问题解决

//求解最大利益
int max_salary(int **List, int len) {
	int result_1 = 0, result_2 = 0, result = 0;
	if (len <= 0)
		return result;

	result_1 = max_salary(List, len - 1) + *(*(List + len - 1) + 0);
	result_2 = max_salary(List, len - 2) + 0 + *(*(List + len - 1) + 1);

	if (result_1 >= result_2) {
		result = result_1;
	}
	else {
		result = result_2;
	}
}

int main() {
#define MAXNUMLENGTH 5
#define MAXLENGTH 100
	char input_num[MAXNUMLENGTH] = { 0 };
	char input[MAXLENGTH] = { 0 };
	int in_count = 0;
	int count = 0;
	int num_len = 0;
	int len = 0;

	int num_of_days = 0;

	//输入第一行
	char c = getchar();
	while (c != '\n') {
		input_num[count] = c;
		c = getchar();
		count++;
	}
	num_len = count;
	count = 0;

	for (int i = num_len - 1; i >= 0; i--) {
		num_of_days += (int)((input_num[i] - '0')*pow(10, in_count));
		in_count++;
	}
	in_count = 0;

	//输入第二行
	c = getchar();
	while (c != '\n') {
		input[count] = c;
		c = getchar();
		count++;
	}
	len = count;
	count = 0;
	
	//申请内存
	int **salary_list = (int **)(malloc(sizeof(int*) * num_of_days));
	memset(salary_list, 0, sizeof(int*) * num_of_days);
	for (int i = 0; i < num_of_days; i++) {
		*(salary_list + i) = (int*)(malloc(sizeof(int) * 2));
		memset(*(salary_list + i), 0, sizeof(int) * 2);
	}

	int first_num = 0, second_num = 0;
	for (int i = num_of_days - 1; i >= 0; i--) {
		count += 2;
		second_num = 0;
		while (input[len - count - 1] != ',') {
			second_num += (int)((input[len - count - 1] - '0')*pow(10, in_count));
			in_count++;
			count++;
		}
		in_count = 0;
		count++;

		*(*(salary_list + i) + 1) = second_num;
		
		first_num = 0;
		while (input[len - count - 1] != '[') {
			first_num += (int)((input[len - count - 1] - '0')*pow(10, in_count));
			in_count++;
			count++;
		}
		in_count = 0;
		count++;

		*(*(salary_list + i) + 0) = first_num;
	}

	//for (int i = 0; i < num_of_days; i++) {
	//	for (int j = 0; j < 2; j++) {
	//		cout << *(*(salary_list + i) + j) << endl;
	//	}
	//}

	//int salary_list[4][2] = { {1, 5},{2, 3},{2, 9},{1, 3} };

	cout << max_salary(salary_list, num_of_days) << endl;

	//释放内存
	for (int i = 0; i < num_of_days; i++) {
		free(*(salary_list + i));
		*(salary_list + i) = NULL;
	}
	free(salary_list);
	salary_list = NULL;
	
	return 0;
}

2. 2018京东在牛客网上最后一道题

2.1 问题描述

删掉某一字符串的几个字符后，该字符串为回文串，问总共几种情况 比如 ABA—>A/B/ABA—>3

2.2 问题解决

int count_seq(string str, int low, int high) {

	int result = 0;

	if (high - low == 0) {
		return 1;
	}

	if (high - low == 1) {
		if (str[high] == str[low])
			return 3;
		else
			return 2;
	}

	if (str[low] == str[high]) {
		result = count_seq(str, low + 1, high) + count_seq(str, low, high - 1) + 1;
	}
	else {
		result = count_seq(str, low + 1, high) + count_seq(str, low, high - 1) - count_seq(str, low + 1, high - 1);
	}

	return result;
}

int main() {
	string str = "ABA";
	cout << count_seq(str, 0, str.length() - 1) << endl;
}