文章目录
一. 概念定义
高精度其实就是当一个数无法用程序给定的数据类型表示时，我们通常用数组进行存储，模拟计算。
二. 专栏推荐
英雄哥的算法基础：《算法零基础100讲》(第27讲) 字符串算法(七) - 高精度
三. 课后习题
3.1 千位分隔数
分析：
这道题很好理解，就是从尾部开始，每隔三个数加一个 ’ . ’ 字符。
代码思路：
- 首先我们需要将整数n转化为数字字符串nums，并计算出它的长度len。
- 从尾部，即len - 1开始遍历，将每个字符拷贝入一个新的字符串ret，每遍历三个字符便插入一个点字符。
- 将ret反转。
代码如下：
void reserve(char* ret, int len){
int l = 0, r = len - 1;
while(l < r){
char tmp = *(ret + l);
*(ret + l) = *(ret + r);
*(ret + r) = tmp;
l++;r--;
}
}
char * thousandSeparator(int n){
char* nums = (char*)malloc(sizeof(char) * 32);
//转化为字符串
sprintf(nums, "%d", n);
//计算长度
int len = strlen(nums);
char* ret = (char*)malloc(sizeof(char) * 42);
int retSize = 0;
int k = 0;
//将nums从尾部开始拷贝入ret
for(int i = len - 1; i >= 0; i--){
//插入.字符
if(k % 3 == 0 && k != 0){
ret[retSize++] = '.';
}
ret[retSize++] = nums[i];
k++;
}
ret[retSize] = '\0';
//反转
reserve(ret, retSize);
return ret;
}
3.2 字符串转化后的各位数字之和
题目链接：
1945. 字符串转化后的各位数字之和
题目分析：
题目给定一个由小写字母组成的字符串，并且从’a’ = 1…‘z’ = 26，每个字符代表一个数字，题目要求将其转化为数字，然后将每一位上的数字相加，进行k次操作。
代码思路：
- 首先我们需将字符串s转化为单个的数字，并存放入一个数组中。
- 将数组内的所有值相加，得到总值sum。
- 因为我们可能要重复多次此操作，所以我们还需继续将sum进行拆分，并放入数组中，同时更新数组的长度。直到完成k次操作
代码如下：
void Mul(int* nums, int* numsSize, int sum){
int n = 0;
while(sum){
nums[n++] = sum % 10;
sum /= 10;
}
*numsSize = n;
}
int Sum(int* nums, int numsSize){
int sum = 0;
for(int i = 0; i < numsSize; i++){
sum += nums[i];
}
return sum;
}
int getLucky(char * s, int k){
int nums[201] = { 0 };
int len = strlen(s);
int numsSize = 0;
//字母转化为数字
for(int i = 0; i < len; i++){
int m = s[i] - 'a' + 1;
//应为有两位数存在，所以需将其拆分存入
while(m){
nums[numsSize++] = m % 10;
m /= 10;
}
}
int sum = 0;
while(k--){
//计算各位数相加之和
sum = Sum(nums, numsSize);
//如果k == 0，则无需再拆分，直接退出
if(k == 0)break;
//拆分
Mul(nums, &numsSize, sum);
}
return sum;
}
3.3 字符串中第二大的数字
题目链接：
1796. 字符串中第二大的数字
分析：
题目要求我们找出第二大的数字，所以我们需要用两个变量max1和max2分别存储前两个大的数，如果不存在第二个则返回-1。
代码思路：
- 定义两个变量max1，max2，并初始化为-1。
- 首先我们需要判断是否为数字。
- 然后比较大小，将最大的赋给max1，第二大的赋给max2。
代码如下：
bool isNum(char ch){
if(ch >= '0' && ch <= '9')return true;
return false;
}
int secondHighest(char * s){
int n = strlen(s);
int max1 = -1, max2 = -1;
for(int i = 0; i < n; i++){
//判断数字
if(isNum(s[i])){
int m = s[i] - '0';
//记录前两个最大值
if(max1 < m){
max2 = max1;
max1 = m;
}
else if(max2 < m && m < max1){
max2 = m;
}
}
}
return max2;
}
3.4 最小时间差
题目链接：
539. 最小时间差
分析：
这道题让我们计算最小的时间差，但他给定的是一个字符串表示时间，所以我们可以通过sscanf()函数进行转化，同时将小时转化为分钟，并记录起来，最后将其排序，找出相差最短的时间。
代码思路：
- 首先使用函数sscanf()将所有时间转化，记录在数组time中。
- 对数组进行排序(这里我们进行降序排序)。
- 遍历所有相邻的时间点，找出最短的时间差，其中我们要注意，时间是有周期的，[22:00，14:00，00:00]，在这样一组数据中，22小时和0相差的并不是22个小时，而是2个小时，所以我们需判断1440 - time[i] + time[i + 1]与time[i] - time[i + 1]这两个哪个更小。
代码如下：
int cmp(const int* a, const int* b){
return *b - *a;
}
int findMinDifference(char ** timePoints, int timePointsSize){
int* time = (int*)malloc(sizeof(int) * timePointsSize);
//转化字符，并记录，并转化时间单位
for(int i = 0; i < timePointsSize; i++){
int h, m;
sscanf(timePoints[i], "%d:%d", &h, &m);
time[i] = h * 60 + m;
}
//降序排序
qsort(time, timePointsSize, sizeof(int), cmp);
//for(int i = 0; i < timePointsSize; i++)printf("%d ", time[i]);
int min = 1440;//一天1440分钟
//找出最小时差
for(int i = 0; i < timePointsSize - 1; i++){
min = fmin(min, fmin(time[i] - time[i + 1], 1440 - time[i] + time[i + 1]));
}
//判断最大时间与最小时间因周期性导致，是否有更小时差
min = fmin(min, 1440 - time[0] + time[timePointsSize - 1]);
return min;
}
3.5 罗马数字转整数
题目链接：
13. 罗马数字转整数
分析：
这道题我们分别用罗马数字表示各个字符，其中我们要注意的是每当遇到5和1这两个数是，罗马数字否会进行一个较大的字符改变，例如：I , II , III , IV , V , VI。
代码思路：
- 首先我们需对特殊情况进行处理，例如I, V, X, L, C ,D, M。以及它们相邻的两个数。
- 遍历数组，并计算
代码如下：
int romanToInt(char * s){
int num = 0;
int len = strlen(s);
for(int i = 0; i < len; i++){
if(s[i] == 'I' && s[i + 1] && s[i + 1] == 'V'){
num += 4;
i++;
continue;
}
if(s[i] == 'I' && s[i + 1] && s[i + 1] == 'X'){
num += 9;
i++;
continue;
}
if(s[i] == 'C' && s[i + 1] && s[i + 1] == 'M'){
num += 900;
i++;
continue;
}
if(s[i] == 'X' && s[i + 1] && s[i + 1] == 'C'){
num += 90;
i++;
continue;
}
if(s[i] == 'C' && s[i + 1] && s[i + 1] == 'D'){
num += 400;
i++;
continue;
}
if(s[i] == 'X' && s[i + 1] && s[i + 1] == 'L'){
num += 40;
i++;
continue;
}
switch(s[i]){
case 'M':num += 1000;break;
case 'D':num += 500;break;
case 'C':num += 100;break;
case 'L':num += 50;break;
case 'X':num += 10;break;
case 'V':num += 5;break;
case 'I':num += 1;break;
default:break;
}
}
return num;
}
3.6 整数转罗马数字
题目链接：
12. 整数转罗马数字
题解分析链接：模拟方法
代码如下：
const int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5,
4, 1};
const char* symbols[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL",
"X", "IX", "V", "IV", "I"};
char * intToRoman(int num){
char* roman = (char*) malloc (sizeof(char) * 16);
roman[0] = '\0';
for(int i = 0; i < 13; i++){
//找出num大于的最大数
while(num >= values[i]){
//减去该数
num -= values[i];
//将values[i]对应的symbols[i]拷贝过去
strcpy(roman + strlen(roman), symbols[i]);
}
//当num == 0， 说明已经转化完毕
if(num == 0){
break;
}
}
return roman;
}
3.7 字符串压缩
题目链接：
面试题 01.06. 字符串压缩
分析：
题目所谓的压缩，实际上就是将连续重复的字母用数字表示，例如：aaaa压缩后就是a4，当然如果压缩后的长度不小于原来的字符串，则返回原串。
代码思路：
- 首先我们需要开辟一块strlen(S)长度的字符数组ret，定义一个char类型的变量ch，用于比较，定义一个cnt计算连续相同的字符。
- 当遇到不相同的字符时，将ch拷贝入ret中，并将cnt转化为字符串，也拷贝入ret中，然后更新ch和cnt
代码如下：
char* compressString(char* S){
char* ret = malloc(100001);
int retSize = 0;
int n = strlen(S);
//特殊情况
if(n == 0)return "";
int cnt = 0;
char ch = S[0];
char k[5];//
for(int i = 0; i < n; i++){
if(ch == S[i]){//比较是否相同
cnt++;
}
else{//如若不相同，将原先记录的数目存储进ret中
ret[retSize++] = ch;
sprintf(k, "%d", cnt);//转化cnt
strcpy(ret + retSize, k);//拷贝
retSize += strlen(k);
ch = S[i];//更新
cnt = 1;
}
if(i == n - 1){
ret[retSize++] = ch;
sprintf(k, "%d", cnt);
strcpy(ret + retSize, k);
retSize += strlen(k);
}
}
if(retSize >= n)return S;
ret[retSize] = '\0';
return ret;
}