题目一 在字符串中找出连续最长的数字串
问题描述
给定一个字符串，输出字符串中最长的数字串，并把这个数字串的长度输出。
请在一个字符串中找出连续最长的数字串，并把这个串的长度返回；如果存在长度相同的连续数字串，返回最后一个连续数字串。
__注意__：数字串只需要是数字组成的就可以，并不要求顺序，比如数字串”1234”的长度就小于数字串”1359055”，如果没有数字，就返回空字符串 (“”) 而不是NULL。
输入描述
输出描述
1
2
| 输出最长的数字串，输出最长数字串中数字个数
中间以逗号 (,) 隔开
|
示例 1
输入
1
| abcd12345ed125ss123058789
|
输出
备注
- 如果存在长度相同的连续数字串，则输出最后一个连续数字串。
- 数字串只需要是数字组成的就可以，并不要求顺序，比如数字串”1234”的长度就小于数字串”1359055”。
- 如果没有数字，就返回空字符串 (“”) 而不是NULL。
解决方案
可以设定两对指针，每对指针包含字符串的起始位置和结束位置的后一个位置，第一对指针保存着最长的数字串，第二对指针保存当前找到的数字串，通过指针相减可以得到字符串长度，通过比对长度大小不断更新指针的位置。实现代码如下：
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
48
49
50
51
52
53
54
55
| #include <iostream>
#include <string>
using namespace std;
int main()
{
string str;
while (cin >> str) {
bool numeric;
int long_start, long_end, long_len;
int tmp_start, tmp_end;
long_start = long_end = -1;
long_len = 0;
tmp_start = tmp_end = 0;
numeric = false;
int i;
for (i=0; i<str.size(); i++) {
if (str[i] >= '0' && str[i] <= '9') {
if (numeric == false)
tmp_start = i;
numeric = true;
} else {
if (numeric == true) {
tmp_end = i;
if ((tmp_end - tmp_start) >= long_len) {
long_start = tmp_start;
long_end = tmp_end;
long_len = tmp_end - tmp_start;
}
}
numeric = false;
}
}
if (i == str.size() && numeric == true) {
tmp_end = i;
if ((tmp_end - tmp_start) >= long_len) {
long_start = tmp_start;
long_end = tmp_end;
long_len = tmp_end - tmp_start;
}
}
if (long_len > 0) {
for (i=long_start; i<long_end; i++)
cout << str[i];
cout << "," << long_len << endl;
} else {
cout << ",0" << endl;
}
}
return 0;
}
|
题目二 字节流解析
问题描述
根据数值占用BIT数，按顺序从输入字节流中解析出对应数值，解析顺序按输入数组astElement索引升序
1
2
| void Decode(unsigned int uiInputLen, unsigned char aInputByte[],
unsigned int uiElementNum, ELEMENT_STRU astElement[]);
|
其中
1
2
3
4
5
6
7
8
9
| unsigned int uiInputLen : 字节数组 (流) 长度
unsigned char aInputByte : 字节数组 (流)
unsigned int uiElementNum : 解析数值个数
ELEMENT_STRU astElement[] : 数值的结构数组指针，含义如下
Struct
{
unsigned int uiElementLength; //表示uiElementValue占用BIT数，范围1~32
unsigned int uiElementValue; //从字节流中按顺序解析的数值，用于输出
} ELEMENT_STRU;
|
输入描述
1
2
3
4
5
| 字节数组长度uiInputLen为3;
字节数组aInputByte[3]为{0x62, 0x80, 0x00}，对应二进制为 "0110 0010, 1000 0000, 0000 0000";
解析数值个数uiElementNum为2;
数值[0]的值占4个bit，即 astElement[0].uiElementLength = 4;
数值[1]的值占5个bit，即 astElement[1].uiElementLength = 5;
|
输出描述
1
2
| 数值[0]的值为6，二进制为 "0110"，即 astElement[0].uiElementValue = 6;
数值[1]的值为5，二进制为 "0010 1"，即 astElement[1].uiElementValue = 5;
|
示例 1
输入
输出
解决方案
这道题目主要是对数字进行进制转换，输入为一个十六进制字符串，然后需要转换成对应的二进制字符串，我的做法是将字符串转换成十进制整数 (使用stoi函数)，然后将这个十进制整数转化成二进制字符串，将转换后的二进制字符串保持到数组aInputByte，这里我不固定数组aInputByte大小，根据输入的参数uiInputLen动态设定数组大小，数据转换完毕后，调用Decode函数进行解析。
PS: 十六进制字符串转二进制字符串应该可以直接用映射关系来转换，因为每个十六进制字符对应的二进制是固定的。
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #include <iostream>
#include <string>
using namespace std;
struct ELEMENT_STRU {
unsigned int uiElementLength;
unsigned int uiElementValue;
};
void Decode(unsigned int uiInputLen, unsigned char aInputByte[],
unsigned int uiElementNum, ELEMENT_STRU astElement[])
{
unsigned int uiElementValue, uiElementLength, pow2;
int start, end;
start = 0;
for (int i=0; i<uiElementNum; i++) {
uiElementLength = astElement[i].uiElementLength;
uiElementValue = 0;
pow2 = 1;
end = start + uiElementLength;
for (int j=end-1; j>=start; j--) {
if (aInputByte[j] == '1')
uiElementValue = uiElementValue + pow2;
pow2 = 2 * pow2;
}
astElement[i].uiElementValue = uiElementValue;
start = end;
}
}
int main()
{
string str;
unsigned int uiInputLen, num, uiElementNum,flag;
unsigned int numberBytes;
int start, end;
unsigned char *aInputByte = NULL;
ELEMENT_STRU *astElement = NULL;
while (cin >> uiInputLen) {
aInputByte = (unsigned char *)malloc(sizeof(unsigned char) * 32 * uiInputLen);
start = 0;
end = 0;
for (int i=1; i<=uiInputLen; i++) {
cin >> str;
if (str.size() == 3) // 0xX
numberBytes = 4;
else if (str.size() == 4) // 0xXX
numberBytes = 8;
else if (str.size() == 5) // 0xXXX
numberBytes = 12;
else if (str.size() == 6) // 0xXXXX
numberBytes = 16;
end = start + numberBytes;
flag = 1;
num = stoi(str, 0, 16);
for (int j=end-1; j>=start; j--) {
if (flag & num)
aInputByte[j] = '1';
else
aInputByte[j] = '0';
flag = flag << 1;
}
start = end;
}
cin >> uiElementNum;
astElement = (ELEMENT_STRU*)malloc(sizeof(ELEMENT_STRU)*uiElementNum);
for (int i=0; i<uiElementNum; i++) {
cin >> num;
astElement[i].uiElementLength = num;
}
Decode(uiInputLen, aInputByte, uiElementNum, astElement);
for (int i=0; i<uiElementNum; i++)
cout << astElement[i].uiElementValue << endl;
free(aInputByte);
free(astElement);
}
return 0;
}
|
题目三 长整数相乘
问题描述
长整数相乘
输入描述
输出描述
示例 1
输入
输出
解决方案
LeetCode有类似大整数相乘题目 43. Multiply Strings，和本题区别在于，LeetCode那题假设两个整数都是非负的，这题的整数可以是负数，在LeetCode 43题解题基础上加个符号判断即可解出该题。