零、写在前面
今天是打卡的第26天，今天稍微调整了点作息好很多了，大家就算要熬夜一定要两点前睡呀，保持六个小时充足睡眠。老规矩，知识点在：
《算法零基础100讲》(第27讲) 字符串算法(七) - 高精度
https://blog.csdn.net/WhereIsHeroFrom/article/details/121347597
一、主要知识点
1.高精度加法
加数逆序
模拟加法
处理进位
处理前导0
结果逆序
char * addStrings(char * a, char * b){ char *c; int lena = strlen(a); int lenb = strlen(b); int i, cap, now; int av, bv; int maxlen = max(lena, lenb); inverse(a); // 1. inverse(b); // 1. c = (char *)malloc( sizeof(char) * (maxlen + 2) ); cap = 0; for(i = 0; i < maxlen; ++i) { av = (i < lena) ? (a[i]-'0') : 0; // 超出范围设置为0 bv = (i < lenb) ? (b[i]-'0') : 0; // 超出范围设置为0 now = (av + bv + cap); // 计算结果 cap = now / 10; // 计算进位 c[i] = (now % 10) + '0'; // 写入结果 } if(cap) { c[i] = '1'; // 进位 最多是1 maxlen ++; } c[maxlen] = '\0'; inverse(c); // 反转 return c; }
2.高精度乘法
乘数逆序
模拟乘法
处理进位
处理前导0
结果逆序
char * multiply(char * a, char * b){ int i, j, num; int lena = strlen(a); int lenb = strlen(b); int len = lena + lenb; int *cnum = (int *)malloc( sizeof(int) * (len+5) ); char *c = (char *)malloc( sizeof(char) * (len+5) ); memset( cnum, 0, sizeof(int) * (len+5) ); inverse(a); // 反转 inverse(b); // 反转 for(i = 0; i < lena; ++i) { for(j = 0; j < lenb; ++j) { // (3) cnum[i+j] += (a[i] - '0') * (b[j] - '0'); } } for(i = 0; i < len; ++i) { // 处理进位 cnum[i+1] += cnum[i] / 10; cnum[i] %= 10; } ++len; while(len > 1 && !cnum[len-1]) { // 处理前面的0 --len; } for(i = 0; i < len; ++i) { // 写入字符串 c[i] = cnum[i] + '0'; } c[len] = '\0'; inverse(c); // 反转 return c; }
3.分治思想
当一个问题过于复杂的时候，先化成多个小问题，然后各个击破。
我就先提出来个概念，等下最后一题的时候我们用用-.-
二、课后习题
1556. 千位分隔数
1556. 千位分隔数
https://leetcode-cn.com/problems/thousand-separator/
题目描述
给你一个整数 n，请你每隔三位添加点（即 "." 符号）作为千位分隔符，并将结果以字符串格式返回。
思路
利用栈的先入后出的特性进行输入数字的反转就好了。加入分隔符。
char * thousandSeparator(int n){ int zhan[13],zhansize = 0,ansSize = 0;//创建栈 先入后出 while(n){ zhan[zhansize++] = n % 10; //栈赋值 n /= 10; } if(!zhansize) zhan[zhansize++] = 0; char *ans = malloc(sizeof(char) * (zhansize + zhansize / 3 + 1));//返回字符串空间 int j = zhansize; for(int i = 0;i <zhansize;i++){ //写入字符串信息 if(i&&!(j%3)) ans[ansSize++] = '.';//够三位就加一个分隔符 ans[ansSize++] = zhan[--j]+ '0' ;//出栈元素 } ans[ansSize] = 0; return ans; }
1945. 字符串转化后的各位数字之和
1945. 字符串转化后的各位数字之和
https://leetcode-cn.com/problems/sum-of-digits-of-string-after-convert/
题目描述
给你一个由小写字母组成的字符串 s ，以及一个整数 k 。
首先，用字母在字母表中的位置替换该字母，将 s 转化 为一个整数（也就是，'a' 用 1 替换，'b' 用 2 替换，... 'z' 用 26 替换）。接着，将整数 转换 为其 各位数字之和 。共重复 转换 操作 k 次 。
例如，如果 s = "zbax" 且 k = 2 ，那么执行下述步骤后得到的结果是整数 8 ：
转化："zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124
转换 #1：262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17
思路
由于k>=1，那么至少要做一次加和，那我们第一次读入的时候就把这个做了，也方便我们之后进行运算。之后就是按要求进行位和计算就好了。
int getLucky(char * s, int k){ int ans = 0,i = 0; k--; while(s[i]){ //计算位和 int temp = 0; temp = s[i] - 'a' +1; if(temp/10) temp = temp /10+temp %10; //计算位和 最多两位？ ans += temp; i++; } while(k--){ //迭代计算位和 int temp = ans; ans = 0; while(temp){ ans += temp %10; temp /= 10; } } return ans; }
1796. 字符串中第二大的数字
1796. 字符串中第二大的数字
https://leetcode-cn.com/problems/second-largest-digit-in-a-string/
题目描述
给你一个混合字符串 s ，请你返回 s 中 第二大 的数字，如果不存在第二大的数字，请你返回 -1 。
思路
初始化两个变量，一个是第一大的数字，一个第二大的，初始化为-1.(为啥是-1？题目说的)
根据扫描到的元素进行变量的改变 最后返回就好了。
int secondHighest(char * s){ int max = -1,max1 = -1; //两个最大值和次大值 for(int i = 0;s[i];i++) if(s[i]>='0'&&s[i]<='9'){ //扫描到数字 int temp = s[i] - '0'; if(temp>max){max1 = max;max = temp;}//比最大值大 更新最大值和次大值 else if(temp < max && temp > max1) max1 = temp;//比次大值大但是小于最大值，只更新次大值 } return max1; }
539. 最小时间差
539. 最小时间差
https://leetcode-cn.com/problems/minimum-time-difference/
题目描述
给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
思路
先将所有时间转换为分钟的表示，然后做排序，最小值只可能出现在排序后的前后两个元素，或者最前和最后的位置。
int cmp(int *a,int*b){//升序排列 return *a > *b; } int findMinDifference(char ** timePoints, int timePointsSize){ int hash[timePointsSize],hashSize = 0; for(int i = 0;i<timePointsSize;i++) //转化为分钟 hash[hashSize++] = (((timePoints[i][0] -'0') * 10) + timePoints[i][1] - '0') * 60 + (timePoints[i][3] - '0')*10 + timePoints[i][4]; qsort(hash,hashSize,sizeof(int),cmp);//排序 int min = 24*60+hash[0] - hash[hashSize - 1];//最小值赋值为最小和最大值的差 垮了一天 for(int i = 1;i < hashSize;i++) if(min>hash[i]-hash[i-1]) min = hash[i] - hash[i-1]; return min; }
3. 罗马数字转整数
3. 罗马数字转整数
https://leetcode-cn.com/problems/roman-to-integer/
题目描述
常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。
思路
顺序读入，如果读到V、X、L、C、D、M扫描前面的元素是不是对应的可以放置左边的元素，进行统计和就好了。
int romanToInt(char * s){ int ans = 0; for(int i = 0;s[i];i++){ if(s[i] == 'I') ans += 1; else if(s[i] == 'X') if(i&&s[i-1]=='I') ans += 8;//上次统计的时候多加了1 此时就少加 else ans += 10; else if(s[i] == 'V') if(i&&s[i - 1] =='I') ans += 3; else ans += 5; else if(s[i] == 'L') if(i&&s[i - 1] =='X') ans += 30; else ans+= 50; else if(s[i] == 'C') if(i&&s[i - 1] == 'X') ans += 80; else ans += 100; else if(s[i] == 'D') if(i&&s[i-1] == 'C') ans+=300; else ans+= 500; else if(s[i] == 'M') if(i&&s[i-1] == 'C') ans += 800; else ans+= 1000; } return ans; }
12. 整数转罗马数字
12. 整数转罗马数字
https://leetcode-cn.com/problems/integer-to-roman/
题目描述
给你一个整数，将其转为罗马数字。
思路
根据不同元素代表的值进行写入就好了？把左边放元素的看作一个整体就完事了 ，这题不难的。就是情况太多 很烦
char * intToRoman(int num){ char *ans = malloc(sizeof(char)*1000); int anssize = 0; while(num/1000){ num -=1000; ans[anssize++]='M'; } while(num/900){ num-=900; ans[anssize++] = 'C';ans[anssize++] = 'M'; } while(num/500){ num -= 500; ans[anssize++] = 'D'; } while(num /400){ num -= 400; ans[anssize++] = 'C';ans[anssize++] = 'D'; } while(num/100){ num -= 100; ans[anssize++] ='C'; } while(num/90){ num-=90; ans[anssize++] = 'X';ans[anssize++] = 'C'; } while(num/50){ num-=50; ans[anssize++] = 'L'; } while(num/40){ num-=40; ans[anssize++] = 'X';ans[anssize++] = 'L'; } while(num/10){ num -= 10; ans[anssize++] = 'X'; } while(num/9){ num-=9; ans[anssize++] = 'I';ans[anssize++] = 'X'; } while(num/5){ num-=5; ans[anssize++] ='V'; } while(num/4){ num-=4; ans[anssize++] = 'I';ans[anssize++] = 'V'; } while(num){ num --; ans[anssize++] = 'I'; } ans[anssize++] = 0; return ans; }
面试题 01.06. 字符串压缩
面试题 01.06. 字符串压缩
https://leetcode-cn.com/problems/compress-string-lcci/
题目描述
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
思路
先按照要求进行压缩，然后判断返回值就好了。
char* compressString(char* S){ int Szie = 0,anssize = 0;//字符串长度和返回长度 char *ans = malloc(sizeof(char)*60000); //返回空间 while(S[Szie]){ //按字符进行判断 int temp = 0,zhan[5],zhansize = 0; while(S[temp+Szie] == S[Szie]) temp++; //计算元素个数 ans[anssize++] = S[Szie]; int temp2 = temp; //保留元素个数 while(temp){ //利用栈转化为字符串 zhan[zhansize++] = temp % 10; temp /= 10; } while(zhansize) ans[anssize++] = zhan[--zhansize]+'0';//转化为字符 Szie = temp2 + Szie; //跳过重复元素 } ans[anssize] = 0; if(anssize>=Szie) return S;//判断长度 return ans; }
