字符串的陷阱-记对字符串大小比较的错误理解


本文记录了笔者在做题过程中被字符串坑的(其实就是自己菜,顺便水一篇博客)的一次小经历,希望能够帮助像我一样的小白加深对字符串某个方面的理解。

万恶之源

小明决定申请一个新的QQ号码,系统随机生成了若干个号码供他选择。小明的选号原则是:

  1. 选择所有号码中各位数字之和最大的号码。
  2. 如果有多个号码各位数字之和相同则选择数值最大的号码。
    请你写一个程序帮助小明选择一个QQ号码。

输入说明    
输入数据由两行构成,第一行为一个整数n表示有n个待选号码(0<n<100),第二行有n个正整数,表示各个待选的号码,每个号码长度不超过9位数。每个号码之间用空格分隔,且每个号码都不相同。

输出说明    
输出根据小明的选号原则选出的号码。

输入样例    
5
10000 11111 22222 333 1234

输出样例    
2222

问题描述:

首先这是我的思路是用pair来存储一个号码的各位数字之和以及这个号码它本身,然后用sort对它进行一个排序,取最后一个元素即可。各位可以想想这样做会有什么问题。(提示,题目的第二个要求是数值最大的号码)

这是我写的比较函数(sort本身也是这样比较的)

bool cmp(pair<int, string>a, pair<int, string>b) {
if (a.first != b.first)
return a.first < b.first;
else
return a.second < b.second;
}

原因分析:

看出问题了吗?

如果能一眼看出来,说明你对字典序的概念和string的比较已经了如指掌啦。

在else里,我们比较string使用了小于号,这类似于c语言中的strcmp函数,它的比较方法是从第一个字母开始,依次向后比较每个字符(ascii),一旦出现不一样的就返回一个值(具体可以参考baidu)。

比如98455987和676692496,98455987的字典序更大,但其实数值上它更小。

于是,在string里大于号小于号不一定能反映真实的数值的比较(其实这我之前就知道,但就是没留意到=-=)

解决方案:

留意到了“不一定”吗,其实字典序在某些条件下也可以反映数值大小。

那就是两个字符串长度相同的时候。

因此长度是一个关键的量,这里的号码有长有短,因而不能比较字符串的大小,于是我们就可以想到对于不同长度的字符串,首先比较的应该是他们的长度。长度长,位数多,数值自然更大。

于是我们可以这样改写比较函数

bool cmp(pair<int, string>a, pair<int, string>b) {
if (a.first != b.first)
return a.first < b.first;
else if (a.second.length() != b.second.length())
return a.second.length() < b.second.length();
else
return a.second < b.second;
}

总结

string中的大于小于比较的是字典序,只有在两个字符串(纯数字)长度相同时才能反映真实的数值大小,否则一定要考虑长度。

另附代码

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

bool cmp(pair<int, string>a, pair<int, string>b) {
	if (a.first != b.first)
		return a.first < b.first;
	else if (a.second.length() != b.second.length())
		return a.second.length() < b.second.length();
	else
		return a.second < b.second;
}

int main() {
	pair<int, string> s[1000];
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> s[i].second;
		int sum = 0, ans = 0;
		for (int j = 0; j < s[i].second.length(); j++) {
			sum += (s[i].second[j] - '0');
		}
		s[i].first = sum;
	}
	sort(s, s + n, cmp);
//	for (int i = 0; i < n; i++)
//		cout << s[i].second << endl;
	cout << s[n - 1].second;
	return 0;
}
//对拍用
#include <iostream>
#include <ctime>
using namespace std;

//返回L 到 R之间的整数
int gr(int L, int R) {
	return rand() * rand() % (R - L + 1) + L;
}

int main() {
	//初始化随机种子
	srand(time(0));
	int a, b;
	//生成一组随机数据
	a = gr(1, 100);
	cout << a << endl;
	for (int i = 0; i < a; i++)
		cout << gr(1, 1000000000) << " ";
	return 0;
}

​
上一篇:基本算法之贪心算法


下一篇:【背包动态规划】P1048 [NOIP2005 普及组] 采药