文章目录

• 一. 概念定义
• 二. 专栏推荐
• 三. 课后习题
• • 3.1 千位分隔数
  • 3.2 字符串转化后的各位数字之和
  • 3.3 字符串中第二大的数字
  • 3.4 最小时间差
  • 3.5 罗马数字转整数
  • 3.6 整数转罗马数字
  • 3.7 字符串压缩

一. 概念定义

  高精度其实就是当一个数无法用程序给定的数据类型表示时，我们通常用数组进行存储，模拟计算。

二. 专栏推荐

英雄哥的算法基础：《算法零基础100讲》(第27讲) 字符串算法(七) - 高精度

三. 课后习题

3.1 千位分隔数

1556. 千位分隔数

分析：
  这道题很好理解，就是从尾部开始，每隔三个数加一个 ’ . ’ 字符。

代码思路：

1. 首先我们需要将整数n转化为数字字符串nums，并计算出它的长度len。
2. 从尾部，即len - 1开始遍历，将每个字符拷贝入一个新的字符串ret，每遍历三个字符便插入一个点字符。
3. 将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次操作。

代码思路：

1. 首先我们需将字符串s转化为单个的数字，并存放入一个数组中。
2. 将数组内的所有值相加，得到总值sum。
3. 因为我们可能要重复多次此操作，所以我们还需继续将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。

代码思路：

1. 定义两个变量max1，max2，并初始化为-1。
2. 首先我们需要判断是否为数字。
3. 然后比较大小，将最大的赋给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()函数进行转化，同时将小时转化为分钟，并记录起来，最后将其排序，找出相差最短的时间。

代码思路：

1. 首先使用函数sscanf()将所有时间转化，记录在数组time中。
2. 对数组进行排序(这里我们进行降序排序)。
3. 遍历所有相邻的时间点，找出最短的时间差，其中我们要注意，时间是有周期的，[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。

代码思路：

1. 首先我们需对特殊情况进行处理，例如I, V, X, L, C ,D, M。以及它们相邻的两个数。
2. 遍历数组，并计算

代码如下：

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，当然如果压缩后的长度不小于原来的字符串，则返回原串。

代码思路：

1. 首先我们需要开辟一块strlen(S)长度的字符数组ret，定义一个char类型的变量ch，用于比较，定义一个cnt计算连续相同的字符。
2. 当遇到不相同的字符时，将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;
    
}