目录
- 一、字符串相加
- 二、最长公共前缀
- 三、最长回文子串
- 四、二进制求和
- 五、字符串相乘
一、字符串相加
题目:
思路:
- 字符串中的每一位的字符转换为数字后要相加,相加的必须是同一位的,即个位加个位,十位加十位。所以要倒着来实现。这里end1和end2直接就是最后一个字符的下标了
- 两个数相加要考虑进位,用一个变量next来表示进位,进位是给下一位相加时用的,比如个位加个位有进位(0就算了),就给十位加十位用,所以next变量不能写在循环里面
- 循环条件和字符转换数字。while循环是end1和end2大于等于0,满足一个即可在循环里面。这里我们要结合具体的代码,如果是&&,不是||,那么肯定有一个越界(字符串个数相同另说),这时又要写while循环去处理剩余那个还没越界的有点麻烦且冗余,所以都在一个循环里面处理。问题来了,假如end1越界了,end2没有,根据前面的循环条件还是能进入循环的,但是取字符转化为数字不就可能越界了吗?所以这里有一个平衡的方法,先表示当前位的数字val1和val2等于0,记住,此时它们是0,后面不管有没有参与都不影响。然后重点是:接下来用if语句判断end1是否越界,end2也要判断,没有越界val1 才等于 当前位字符转换为数字,val2同理。到后面用时,不管是val1和val2都有值,还是一个有一个没有,都不影响后面的操作,因为没有值的那个是0
- 变量sum,同位的两个数相加(val1+val2),同时还要加上上一次的进位next,第一次进来next是0,到下一次加时,next可能有进位,就按照sum=val1+val2+next的操作就行了。sum得到前面变量相加的结果后,要给下一次的相加准备进位的数,next = sum/10(其实next要么为0要么为1,后面再看),然后sum %= 10,保证当前的位是个位的那个数(sum是12,取的是2,1给next进位了),返回值字符串ret += sum 转换字符
- next的处理。end1和end2都结束了,进位变量next可能没有处理干净,这里说的处理干净指的是next可能是1,如果是1,说明有进位,但是下一位没有元素了怎么办,根据竖加法图,要进行的操作是给下一位补1,那么next有没有可能是其他数字呢?(0就算了,说明整个过程已经处理干净,没有多余的数)不会有其他的数字,只能等于0或者1,因为ret最大的结果是19,同位相加9+9加上上一次的进位next=1,得到19,所以next那么为1那么为0,0就不处理了,1就进入该判断,然后补1
- 逆置,返回字符串
代码:
class Solution {
public:string addStrings(string num1, string num2) {string ret;int next = 0;// 进位int end1 = num1.size()-1, end2 = num2.size()-1;while(end1 >= 0 || end2 >= 0){int val1 = 0;int val2 = 0;if(end1 >= 0) val1 = num1[end1--]-'0';if(end2 >= 0) val2 = num2[end2--]-'0';int sum = val1 + val2 + next;next = sum / 10;sum %= 10;ret += sum + '0';}if(next == 1){ret += "1";}reverse(ret.begin(), ret.end());return ret;}
};
二、最长公共前缀
题目:
思路:
- set去重,数量大于1说明有不同,跳出结束
- 数组中每个字符串的同一个位置的字符都要遍历一遍,有一个为空跳出循环结束
代码:
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {if(strs.size() == 0) return "";string ret;int n = strs.size();for(int i=0; ; i++){string tmp;int flag = 0;for(int j=0; j<n; j++){char k = strs[j][i];if(!k) {flag = 1;break;}tmp += k;}if(flag == 1) break;set<char> se(tmp.begin(), tmp.end()); if(se.size() > 1) break;auto it = se.begin();ret += (*it);}return ret;}
};
三、最长回文子串
题目:
思路:中心扩展法
相同就+=2,不相同就跳出循环。返回两个函数,得到返回值的较大值
代码:
class Solution {
public:// 奇数 string func1(const string& str, int pos){int p1 = pos-1, p2 = pos+1, len = 1;while(p1 >= 0 && p2 < str.size()){if(str[p1] == str[p2]) len += 2;else break;p1--;p2++;}string ret = str.substr(p1+1, len);return ret;}// 偶数string func2(const string& str, int pos){int p1 = pos, p2 = pos+1, len = 0;while(p1 >= 0 && p2 < str.size()){if(str[p1] == str[p2]) len += 2;else break;p1--;p2++;}string ret = str.substr(p1+1, len);return ret;}string longestPalindrome(string s) {string ret;for(int i=0; i<s.size(); i++){string s1 = func1(s, i);string s2 = func2(s, i);string tmp = s1.size()>s2.size() ? s1 : s2;if(tmp.size() > ret.size()) ret = tmp;}return ret;}
};
四、二进制求和
题目:
思路:模拟二进制相加的过程(注意考虑进位)
代码:
class Solution {
public:string addBinary(string a, string b) {int end1 = a.size()-1, end2 = b.size()-1;int next = 0;string ret;while(end1 >= 0 || end2 >= 0){int val1 = 0, val2 = 0;if(end1 >= 0) val1 = a[end1--]-'0';if(end2 >= 0) val2 = b[end2--]-'0';int sum = val1+val2+next;if(sum > 2){ret += "1";next = 1;}else if(sum == 2){ret += "0";next = 1;}else if(sum == 1) {ret += "1";next = 0;}else {ret += "0";next = 0;}}if(next == 1) ret += "1";reverse(ret.begin(), ret.end());return ret;}
};
五、字符串相乘
题目:
思路:
- 两个字符串转化为数字后相乘,先定义一个返回值字符串ret,给它开的大小是两个字符串的长度之和,并且每个位置初始化为字符0;为什么要开空间大小?因为要给每个位置初始化为字符0,这是重点之一,后面要用到这些字符0。为什么开的空间大小是两个字符串的长度之和?直接上栗子,两位数X两位数,数字分别是是11和22时,得到的结果是242,长度是3;数字分别是是99X99时,得到的结果是9801,长度是4;也就是说,两位数乘以两位数,结果的最大的长度是两个字符串的和,即使是长度为3的,前面先占一个字符0,后面再讨论怎么处理。
- 用两层for循环。为什么是两层for循环?因为与加法不同,乘法:一个的数某位遍历乘完另一个数的每一位后,它的下一位还要进行同样的操作,所以要用两层for。for循环也是倒着实现的,即从最后一位数字开始累乘起来
- 变量sum,当前位取模操作、进位操作。sum是当前两个数的某位相乘的结果,但确定就是这样吗?不是的,还要加上进位。但是注意注意,这里的进位与加法那里不同,加法那里是用一个变量来表示进位的值的,而乘法这里是根据字符串数组的位置的元素来表示进位的多少。sum的公式代码:int sum = (s[i]-‘0’) * (t[j]-‘0’) + (ret[i+j+1]-‘0’); 这里的 ret[i+j+1]-'0’的值就是进位的数字。为什么是方括号里面的下标表示是i+j+1?因为刚开始时,i等于n-1,表示在第一个字符串的最后一个位置,j等于m-1,表示在第二个字符串的最后一个位置,前面说过,ret的长度是两个字符串的长度之和,那么ret的最后一个位置是n+m-1,i+j=n+m-2,所以i+j+1就得到ret的最后一个位置(刚开始时),随着j–和i–,位置就会发生变化,取的位置的值也就不一样了。当前位是要取模的,因为只能填sum的个位数字,取模公式:ret[i+j+1] = sum%10 + ‘0’; ret[i+j+1]就是当前要填的位置。进位操作:重!! 进位公式:ret[i+j] += sum/10; 当前位是i+j+1,进位到下一位是i+j,随着j–和i–是一样的(倒着)。有没有发现与取模不同,进位是+=,取模是赋值,因为取模最终就是要模后的结果,而进位的+=代表前面已经有元素,还要加上它才行,具体看下图的分析过程(ret的某个位置的类型是字符类型,数字+字符0=该数字字符;+=的话,字符0的用处来了(其一)因为前面初始化时已经给字符0了,假如之前的操作或者说是刚开始,那么i+j的位置是字符0,字符0加上除等后的数字得到该数字字符,如果已经是数字字符的话,加上除等后的数字,得到的是数字字符的数字加上该数字的和———【字符0+数字=数字字符】+数字 = 数字字符)。【还有字符0的用处(其二),在sum的公式里刚开始i+j+1就是字符0,所以减去字符0得到数字0,如果前面没有初始化为字符0的话,可能会是乱码】
- 图——进位理解——模拟下整个过程!
最后用循环的方式截取字符串返回。字符0用处(其三),字符串ret可能被占满,也可能前面的位置有字符0没有被覆盖,但不管是哪种情况,用for遍历,只要遇到不是字符0的元素,说明在这个位置及其后面的位置都是要返回的字符串(前面的字符0是多余,要的就是后面不是字符0开头的)只要遇到不是字符0,就截取后面全部的字符串,然后返回;即使只有一个也返回;如果连一个都没有,说明都是字符0,返回字符串0。(中间有字符0呢?中间有就有呗,2乘5=10,要返回10,难道后面的0不要了?)
代码:
class Solution {
public:string multiply(string num1, string num2) {int n = num1.size();int m = num2.size();string ret(n+m, '0');for(int i = n-1; i>=0; i--){for(int j=m-1; j>=0; j--){int sum = (num1[i]-'0') * (num2[j]-'0') + (ret[i+j+1]-'0');ret[i+j+1] = sum % 10 + '0';ret[i+j] += sum / 10; }}for(int i=0; i<m+n; i++){if(ret[i] != '0'){return ret.substr(i);}}return "0";}
};