leetcode-aboutString

About string operations

The most classic must be this problem ： String addition

Ideas ： At first, I saw the requirements of the topic , You cannot convert the input string directly into numbers . Then I thought , Since I'm not allowed to use it , Then I'll write one myself .

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

So I wrote a string turn int Function of , I intend to convert two numbers into int Perform the add operation . Then we get the addend int.

At this point, you should int Turn into String, After thinking for a long time, I don't know how to turn , Then I read the answer , Discovery can ：

  StringBuffer stringBuffer=new StringBuffer();
     stringBuffer.append("");
     stringBuffer.append(addnum);

Build a stringBuffer,append（“”）, Then you can append（int）
You can output .

I thought it was perfect , But there is a problem , This is the case where overflow occurs ！！！

If two numbers are very big , For example, the following situation ：

Well, the two one. int The sum has actually exceeded int What can be expressed , So it will overflow , At this time int It is not the result of adding two real numbers , And we will int Transformed string Certainly not the real result .
So this plan is not feasible

In order not to overflow the results , We cannot turn it into int Add up , You have to use strings , Every bit adds up , such （ character string ） There is no overflow .

      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);
            // Direct will carry as sum/10  There is no need to judge whether it is greater than 10, Do you need to carry ,carry It can already be shown 
            carry=sum/10;
            tag1--;
            tag2--;
            
            //999+1  This is just right 000 Then enter a situation 
            if(tag1<0&&tag2<0&&carry==1){
    
                result.append(1);
            }
        }
        return result.reverse().toString();

This code is smelly and long , To simplify the ：

 
             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();

String multiplication

Link

Ideas ：

leetcode Big guy thinking ：

Code ：

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

         if (num1.equals("0") || num2.equals("0")) {
    
            return "0";
        }
        //Multiply Strings  Similarly, it cannot be directly transformed into int Multiply , Because the data is too large , The result will overflow 
        // So we still need to use the idea of string addition 
        // character string 123 *456  It's actually  6*123+50*123+400*123 （ The addition here uses the string addition we have written ）
        // and 6*123  This multiplication , It's not difficult. , It is also the idea of addition , Multiply sequentially , And then carry 
        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;
				//!!!!!
				// Here, too  ！  Multiplication also has overflow ！！！
                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();


    }
}

Also attached is the solution of the great God ：

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();
    }
}

 author ：breezean
 link ：https://leetcode.cn/problems/multiply-strings/solution/you-hua-ban-shu-shi-da-bai-994-by-breezean/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .