学步园

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

这是Normal的一种情况，就是倒序表示的，即107表示成链表是 7-》0-》1，如果是顺序的话解法又不一样。

 #define ln ListNode
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
    ln* l3=NULL;
    ln* ans=NULL;
	int carry=0;
	while(l1&&l2)
	{
		int sum=l1->val+l2->val+carry;
		carry=sum/10;
		ln* tmp=new ln(sum%10);
		if ( !l3)
			ans=l3=tmp;
		else
		{
			l3->next=tmp;
			l3=tmp;
		}
		l1=l1->next;
		l2=l2->next;
	}
	ln* rest=l1?l1:l2;
	while(carry&&rest)
	{
		int sum=rest->val+carry;
		carry=sum/10;
		ln* tmp=new ln(sum%10);
		if(!l3)
			ans=l3=tmp;
		else
		{
			l3->next=tmp;
			l3=tmp;
		}
		rest=rest->next;
	}
	if ( carry )
	{
		ln* tmp=new ln(carry);
		if ( !l3 )
			ans=l3=tmp;
		else
			l3->next=tmp;
	}
	else
	{
		if (!l3)
			ans=l3=rest;
		else
			l3->next=rest;
	}
	return ans;
    }
};

Divide Two Integers：

Divide
two integers without using multiplication, division and mod operator.

思路嘛就是
求 A / B的时候，可以把A表示成  A = B* 2^k1+ B* 2^k2+  - -  这样，注意在count的时候，不能直接以 ( B << c ) <= A 来判断，因为可能会越界，当然后来用long long 了之后就没有这个问题了，long long也是为了解决当A或者B = INT_MIN的时候，取相反数会溢出。

class Solution {
public:
	int divide(int dividend, int divisor) {
		// Start typing your C/C++ solution below
		// DO NOT write int main() function

		//assert(divisor!=0);
		long long div=dividend,sor=divisor;
		bool isNeg=(div<0&&sor>0)||(div>0&&sor<0);
		div=div<0?-div:div;
		sor=sor<0?-sor:sor;
		int ans=0;
		while(div>=sor)
		{
			int c=count(div,sor);
			ans+=(1<<c);
			div-=sor<<c;
		}
		return isNeg?-ans:ans;
	}
	int count(long long n,long long d)
	{
		if ( d>n)
			return 0;
		int c=0;
		while( ( n>>1) >= (d<<c) )
			c++;
		return c;
	}
};

Multiply Strings：

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.

这个就是大数相乘啦，LeetCode里比较简单，没有要求负数。另外跟atoi一样，很多地方要添加错误检测的，比如输入不是一个合法的数字啦，之类的。在面试里要考虑到这些才能打动面试官啦。

我这里也没有写错误检测的，但是考虑正负数相乘了。

class Solution {
public:
	string multiply(string num1, string num2) {
		// Start typing your C/C++ solution below
		// DO NOT write int main() function

		bool isNeg1=num1[0]=='-';
		bool isNeg2=num2[0]=='-';
		bool isNeg=isNeg1!=isNeg2;

		int n1=(num1[0]=='-'||num1[0]=='+')?num1.size()-1:num1.size();
		int n2=(num2[0]=='-'||num2[0]=='+')?num2.size()-1:num2.size();
		int n =n1+n2;

		reverse(num1.begin(),num1.end());
		reverse(num2.begin(),num2.end());
		vector<int> ans(n,'0');
		for(int i=0;i<n1;i++)
		{
			for(int j=0;j<n2;j++)
			{
				ans[i+j]+=(num1[i]-'0')*(num2[j]-'0');
			}
		}
		int carry=0,i=0;
		for(i=0;i<n;i++)
		{
			int t=carry+ans[i]-'0';
			ans[i]=t%10+'0';
			carry=t/10;
		}
		
		while(!ans.empty()&&ans.back()=='0')
			ans.pop_back();
		if ( ans.empty())
			return "0";
		else
		{
			if ( isNeg)
				ans.push_back('-');
			reverse(ans.begin(),ans.end());
			return string(ans.begin(),ans.end());
		}
	}
};

Add Binary：

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

For example,

a = "11"

b = "1"

Return "100".

class Solution {
public:
    string addBinary(string a, string b) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int na=a.length();
	    int nb=b.length();
	    if ( na==0 || nb==0 )
	    {
		    if ( na==0 && nb==0 )
			    return "0";
		    else
			    return na==0?b:a;
	    }

	    int pa =na-1,pb=nb-1;
	    int carry=0;
	    string ret;
	    while(pa>=0&&pb>=0)
	    {
		    int sum= a[pa]-'0'+b[pb]-'0'+carry;
		    carry=sum/2;
		    ret.push_back((sum%2)+'0');
		    pa--;
		    pb--;
	    }
	    int pRest=pa>=0?pa:pb;
	    string& sRest=pa>=0?a:b;
	    while(pRest>=0)
	    {
		    int sum=sRest[pRest]-'0'+carry;
		    carry=sum/2;
		    ret.push_back((sum%2)+'0');
		    pRest--;
	    }
	    if (carry>0 )
	    {
		    ret.push_back('1');
	    }
	    reverse(ret.begin(),ret.end());
	    return ret;
    }
};

Plus
One：

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

class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        vector<int> ret(digits);
	    int n =ret.size();
	    if (n==0)
	    {
		    ret.push_back(1);
		    return ret;
	    }
	    int first=n-1;
	    while(first>=0&&ret[first]==9)
		    ret[first--]=0;
	    if ( first>=0 )
	    {
		    ret[first]++;
		    return ret;
	    }
	    else
	    {
		    reverse(ret.begin(),ret.end());
		    ret.push_back(1);
		    reverse(ret.begin(),ret.end());
		    return ret;
	    }
    }
};

Sqrt(x):

Implement int
sqrt(int x).

Compute and return the square root of x.

class Solution {
public:
    int sqrt(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        assert(x>=0);
	    if ( x==0 )
		    return 0;
	    int l=1,r=x;
	    while(l<=r)
	    {
		    int mid=l+((r-l)>>1);
		    int half= x/mid;
		    if ( half == mid )
			    return mid;
		    else if (mid < half )
			    l=mid+1;
		    else
			    r=mid-1;
	    }
	    return r;
    }
};