leetcode-aboutString

关于字符串运算

最经典的肯定为这道题：字符串相加

思路：一开始看到题目要求，不能把输入的字符串直接转化为数字。然后就想，既然不让我用，那我就自己写一个。

    public int  stringToInt(String num1) {
        int  total=0;
        int length=num1.length();
        for(int i=0;i<length;i++){
            total+=(num1.charAt(i)-'0')*Math.pow(10,length-i-1);
        }
        return total;
    }
1
2
3
4
5
6
7
8

于是就写了一个string转int的函数，打算把两个数转化为int执行相加操作。然后得到加数的int。

此时要把int转化为String，想了好久不知道该怎么转，后来看了答案，发现可以：

  StringBuffer stringBuffer=new StringBuffer();
     stringBuffer.append("");
     stringBuffer.append(addnum);
1
2
3

建立一个stringBuffer，append（“”），然后可以append（int）
就可以输出了。

原本以为已经天衣无缝了，但是却出现了一个问题，就是这种情况会发生溢出！！！

如果两个数很大很大，比如下面这种情况：

那么两个int相加实际上已经超出了int所能表示的范围了，所以就会溢出，此时的int并不是真实两个数相加的结果，而我们将int转化的string肯定也不是真实的结果。
所以这种方案是不可行的

为了结果不溢出，我们不能将其转化为int相加，而得利用字符串，每一位每一位相加，这样（字符串）没有溢出的情况。

      StringBuffer result=new StringBuffer();
        result.append("");
        int tag1=num1.length()-1;
        int tag2=num2.length()-1;
        int tagResult1=0;
        int tagResult2=0;
        int sum=0;
        int carry=0;
        while(tag1>=0||tag2>=0){
            if(tag1<0){
                tagResult1='0';
            }else{
                tagResult1=num1.charAt(tag1);
            }
            if(tag2<0){
                tagResult2='0';
            }else{
                tagResult2=num2.charAt(tag2);
            }
            sum=tagResult1-'0'+tagResult2-'0'+carry;
            result.append(sum%10);
            //直接将carry看成sum/10 就不用去判断是否大于10，需不需要进位，carry已经可以表明了
            carry=sum/10;
            tag1--;
            tag2--;
            
            //999+1 这种刚好000然后进一位的情况
            if(tag1<0&&tag2<0&&carry==1){
                result.append(1);
            }
        }
        return result.reverse().toString();
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

这代码写出来又臭又长，简化一下：

 
             int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        ans.reverse();
        return ans.toString();
1
2
3
4
5
6
7
8
9
10
11
12
13
14

字符串相乘

Link

思路：

leetcode大佬思路：

代码：

class Solution {
    public String multiply(String num1, String num2) {

         if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        //Multiply Strings 同样不能直接转化为int相乘，因为数据太大的话，结果会溢出
        //所以仍然要用字符串相加的思路
        //字符串123 *456 实际上就是 6*123+50*123+400*123 （这里的加法就用我们已经写出来的字符串加法）
        //而6*123 这种乘法，也不难，也是加法的思路，依次乘，然后进位
        String res=new String();
        for(int i = num1.length() - 1 ; i >= 0; i--){
            int mul = (num1.charAt(i) - '0');
            StringBuffer str=new StringBuffer();
            int sum = 0,add = 0;
            for(int j = num2.length() - 1;j >= 0; j--){
                sum=mul*(num2.charAt(j)-'0')+add;
                str.append(sum%10);
                add=sum/10;
				//!!!!!
				//这里也要注意 ！ 相乘也会有溢出的情况！！！
                if(j == 0 && add != 0){
                str.append(add % 10);
                }
            }
            str.reverse();
            for(int k=i;k < num1.length() - 1; k++){
                str.append(0);
            }
            res=addStrings(res,str.toString());
        }
return res;
    }
    public  String addStrings(String num1, String num2) {

             int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        ans.reverse();
        return ans.toString();


    }
}
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

另附上大神的解法：

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int[] res = new int[num1.length() + num2.length()];
        for (int i = num1.length() - 1; i >= 0; i--) {
            int n1 = num1.charAt(i) - '0';
            for (int j = num2.length() - 1; j >= 0; j--) {
                int n2 = num2.charAt(j) - '0';
                int sum = (res[i + j + 1] + n1 * n2);
                res[i + j + 1] = sum % 10;
                res[i + j] += sum / 10;
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            if (i == 0 && res[i] == 0) continue;
            result.append(res[i]);
        }
        return result.toString();
    }
}

作者：breezean
链接：https://leetcode.cn/problems/multiply-strings/solution/you-hua-ban-shu-shi-da-bai-994-by-breezean/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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