京东神奇数,个人觉得比较好理解的方式。没有案例,求检查

#include <iostream>
#include <vector>
#include <string>

using namespace std;

string IntToStr(int i)
{
	char c[256];
	_itoa_s(i, c, 256, 10);
	return c;
}

bool isMagicNumber(int Num)
{
	int sum = 0;
	string digit = IntToStr(Num);
	for (string::const_iterator i = digit.begin(); i != digit.end(); i++)
	{
		sum += (*i);
	}
	if (sum % 2 != 0) //神奇数各个位数之和必为偶数
	{
		return false;
	}
	else
	{
		int record = 0;
                //位数相继做和差运算。
		for (string::const_iterator j = digit.begin(); j != digit.end(); j++)
		{
			if (record > 0)
				record -= (*j);
			else
				record += (*j);
		}
		if (record == 0)
			return true;
		else
			return false;        
	}
}

int main()
{
	int l, r;
	cin >> l >> r;
	int countNum = 0;
	for (int i = l; i <= r; i++)
	{
		if (isMagicNumber(i))
			countNum++;
	}
	cout << countNum << endl;
	system("pause");
	return 0;
}    

#华为#
全部评论
只提供简单思路,但是严重超时,要优化。
点赞 回复 分享
发布于 2017-09-09 13:34
75433可以通过么?
点赞 回复 分享
发布于 2017-09-12 16:04
#include<iostream> using namespace std; int isMagic(int n) { int num[20] = { 0 }; int temp = 0, sum = 0, dp[20][20] = { 0 }; while (n) { num[temp] = n % 10; sum = sum + n % 10; n /= 10; temp++; } if (sum % 2 != 0) { return 0; } int length = temp; for (int i = 1; i <= length; i++) { for (int j = 0; j <= sum / 2; j++) { dp[i][j] = dp[i - 1][j]; if (j >= num[i]) { int t = dp[i][j - num[i]] + num[i]; if (t > dp[i][j]) dp[i][j] = t; } if (j == sum / 2) { if (dp[i][j] == sum / 2) { return 1; } } } } return 0; } int main() { long long start, end; int result = 0; cin >> start >> end; for (long long i = start; i <= end; i++) { if (isMagic(i)) { result++; } } cout << result << endl; system("pause"); return 0; }
点赞 回复 分享
发布于 2017-09-12 16:14

相关推荐

点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务