2019-06-15

Algorithm(6) two numbers sum and multiply(By solution)

主要是leetcode中两个数相乘和相加的几个问题，这种类型的题目应该属于必须熟练掌握的，注意其中的一些细节。

two number add and mutiply

Add two numbers

Add Two Numbers Total Accepted: 86504 Total Submissions: 427184 My Submissions Question Solution
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

解答：思路上应该没有什么难度，应该算是考察基本功的一类题目。主要是有诸多细节问题需要考虑，反反复复调整了好多次才搞定，涉及指针的时候，比如分配新的节点什么的，套路的东西需要特别熟悉，需要细致。

需要注意一下的几个点：

声明struct的时候添加构造函数：ListNode(int x) : val(x), next(NULL) {} 最好在声明的时候就通过构造函数给next指针赋好值，要不然在后面还得不断地手动添加，就像自己下面代码中写的这样，很容易出现漏掉的情况。因为Next是否为NULL是判断链表是否结束的标志，所以就显得很重要了。
注意进位，要单独拿出来考虑（9 9）（1）像这种用例，在共同部分相加完之后，剩余的部分再相加，还会出现进位，要考虑得周全。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
	int carry=0;
	//headnode;
	ListNode *T=(ListNode*)malloc(sizeof(ListNode));
	ListNode *t=T;
	while(true){
		t->val=l1->val+l2->val+carry;
		if (t->val>=10){
		t->val=t->val-10;
		carry=1;
		}else{
            carry=0;
		}
    if(l1->next!=NULL&&l2->next!=NULL){
    ListNode *Node_next=(ListNode*)malloc(sizeof(ListNode));
    Node_next->next=NULL;
	t->next=Node_next;
	t=t->next;
	l1=l1->next;
	l2=l2->next;
	}else{
		break;
	}
	}
		l1=l1->next;
		l2=l2->next;
		// l1 or l2 have the redundant elements
		while (l1!=NULL){
			ListNode *Node_next=(ListNode*)malloc(sizeof(ListNode));
			Node_next->next=NULL;
			Node_next->val=l1->val+carry;
			carry=0;
			if (Node_next->val>=10){
                 Node_next->val=Node_next->val-10;
					carry=1;
			}
            
		t->next=Node_next;
		l1=l1->next;
		t=t->next;
	}
		while(l2!=NULL){
			ListNode *Node_next=(ListNode*)malloc(sizeof(ListNode));
			Node_next->next=NULL;
			Node_next->val=l2->val+carry;
			carry=0;
			if (Node_next->val>=10){
                 Node_next->val=Node_next->val-10;
					carry=1;
			}
		t->next=Node_next;
		l2=l2->next;
		t=t->next;
	}
		if (carry!=0){
			ListNode *Node_next=(ListNode*)malloc(sizeof(ListNode));
			Node_next->next=NULL;
			Node_next->val=1;
			carry=0;
			t->next=Node_next;
			t=t->next;
		}
   			t->next=NULL;
			return T;
    }
};

从两数相加的角度类似的题

mutiply string

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

开始的时候读题读错了，注意这个是两个数相乘，不是相加（相加的话那也太简单了的说。。。）最简单的思路就是遍历乘数中的每个元素，让其与被乘数相乘，之后和原来的数错位相加，注意处理进位等等相关细节。之后还是弄了好久，这个应该算是面试题目中常考的那种了，必须不用思考直接写出来这样才行。主要需要注意的都是一些细节的地方，一些常用的库函数要记清楚。这些细节的地方就是决定成败的关键所在了：

这个和链表的那种不一样，并不是每次都先申请空间，而是要先申请好sum所占用的总的空间，初始值全为0，string sum(len1 + len2+1 , ‘0’) 要不然会有段错误，注意空间是 len1+len2+1 因为可能还会存在着进位的情况。
在相乘相加的时候要注意 str1中的第i个数字和 str2中的第j个数字相乘之后的结果，要累加在之前的第 i+j 个结果上面。由于存入的都是char类型的，每次计算出int之后，把对应应该存入的数字，以及进位都处理好再往str中填入，只需要转化一次就好了，之前是一股脑都加入到str中，最后在从str中拿出来转化为int再处理进位，导致了各种混乱，是思路不清晰的表现。还要注意在每次把进位加上之后要及时清零。
先把数字都取逆之后在按照乘法规则，每次相乘相加，最后再把结果取逆，(相当于是逆向思维转化成了正向思维)需要注意的是要把开头的几个0去掉，需要使用substr函数。

class Solution {
public:
    	string multiply(string num1, string num2) {
		int i,j;
		int current;
		int next;
		int carry=0;
		reverse(num1.begin(),num1.end());
		reverse(num2.begin(),num2.end());
		int len1=num1.size();
		int len2=num2.size();
       string sum(len1 + len2+1 , '0');
		int tempsum;
		if (num1=="0" || num2=="0"){
			sum="0";
			return sum;
		}
		for(i=0;i<len2;i++){
            current=char(num2[i])-'0';
			for(j=0;j<len1;j++){
				next=current*(char(num1[j])-'0');
        		carry=0;
				tempsum=sum[i+j]-'0'+next;
				if(tempsum>=10){
				carry=tempsum/10;
				sum[i+j]='0'+tempsum%10;
				sum[i+j+1]=sum[i+j+1]+carry;
				carry=0;
				}else{
                   sum[i+j]='0'+tempsum;
				}
		}
	}
			if (carry!=0){
			next='0'+carry;
			sum=sum+char(next);
			}
        	reverse(sum.begin(),sum.end());
			i=0;
			while(i < sum.size() && char(sum[i]) == '0'){
                   i++;
		}
		return sum.substr(i);
    }
};

add binary

Given two binary strings, return their sum (also a binary string).

For example,
a = “11”
b = “1”
Return “100”

有了前面两个题目的基础，这个就比较容易了，就是按位相加就可以了啊，为了方便计算显示，可以按照上一个题目的套路，先取逆，再相加，再取逆，只不过由于是二进制的问题，这里不用取0了，只要记录下来实际的长度就好了，注意最后carry!=0 那里处理的时候，也要让i++这样就可以用i的值表示实际的长度了,注意substr的使用，第二个参数是截取的长度。

class Solution {
	public:
		string addBinary(string a, string b) {
		int i;
		int temp;
		int carry=0;
		reverse(a.begin(),a.end());
		reverse(b.begin(),b.end());
		int len1=a.size();
		int len2=b.size();
		int len=len1<len2?len1:len2;
		//assign the space
		string sum(len1 + len2+1 , '0');
			for(i=0;i<len;i++){
				temp=a[i]-'0'+b[i]-'0'+carry;
				carry=0;
				if(temp>=2){
				carry=temp/2;
				temp=temp%2;
				}
				sum[i]=temp+'0';
			}
		while(i<len1){
			temp=a[i]-'0'+carry;
			carry=0;
			if(temp>=2){
				carry=temp/2;
				temp=temp%2;
				}
			sum[i]=temp+'0';
			i++;
		}
		while(i<len2){
			temp=b[i]-'0'+carry;
			carry=0;
			if(temp>=2){
			carry=temp/2;
			temp=temp%2;
		}
		sum[i]=temp+'0';
		i++;
		}
		if(carry!=0){
		sum[i]=carry+'0';
		carry=0;
		i++;
		}
		string substr=sum.substr(0,i);
		reverse(substr.begin(),substr.end());
		return substr;
		}
};

Plus one

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

基本上同之前的一样了，先取逆，再相加，algorithm的reverse 方法还是挺好用的，string和vector只要通过begin以及end返回对应的迭代器就好。注意这次由于是vector如果最后一位进位导致序列增长的话，要单独push到vector中来。

class Solution {
public:
    vector plusOne(vector& digits) {
    int carry=0;
    int i=0;
    reverse(digits.begin(),digits.end());
    digits[i]=digits[i]+1;
    if (digits[i]>=10){
        digits[i]=digits[i]-10;
        carry=1;
    }
    i++;
    while(i=10){
        digits[i]=digits[i]-10;
        carry=1;
    }
    i++;
    if(carry==0){
        break;
    }
    }
    if (carry==1){
        digits.push_back(1);
        carry=0;
    }
    reverse(digits.begin(),digits.end());
    return digits;
    }
};

AverageMind

Algorithm(6) two numbers sum and multiply(By solution)

two number add and mutiply

Add two numbers

从两数相加的角度类似的题

mutiply string

add binary

Plus one

推荐文章

two number add and mutiply

Add two numbers

从两数相加的角度 类似的题

mutiply string

add binary

Plus one

推荐文章

从两数相加的角度类似的题