Post published over one year ago
Assuming all the compile should be involved in
int32 type, which means every returned answer should be limited in [-2^31, 2^31-1]
There’s only two basic calculations : Addition and Subtraction , and three basic bool judgments : ‘More than’ , ‘Less than’ and ‘Equal’, which composed all algorithm next.
I personally regard the symbol and the value as two divided attributes in a single integer. Thus, to use if(int<0) to check whether the integer is negative is quite useful, we can quickly multiply -1 to it , and use another variable to save its symbol. It’s useful when the problem do not care symbol, for example, Problem 7: Reverse Integer.
We can simply isolate the symbol, do reverse operation in whatever way you like , and reduce symbol:
class Solution: def reverse(self, x: int) -> int: if x<0:#check negativity x=-x flag=-1 else: flag=1 s = str(x) s=s[::-1] res = int(s)*flag #convert to string and reverse if res < -2**31 or res>2**31-1: #check overflow return 0 else: return res
However, everything above can be represented as 3 lines with totally same thought of solution:
s = cmp(x, 0)#check negativity r = int(`s*x`[::-1])#convert to string and reverse return s*r * (r < 2**31)#check overflow #By StefanPochmann
Some times we need to get each number of a integer, for example (int)1234, we hope we can get 1, 2,3,4 each time, or 4,3,2,1 each time. Next I use Problem 2 : Add Two Numbers as an example.
You are given two non-empty linked lists representing two non-negative integers. 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.You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
First we talk about having the sum 807, How do we get each number of this sum and put it in each node of final linked list?
We can use such scheme: 123% 10 = 3, 123-3 % 100 = 20 , 123 -20 -3 %1000 = 100 . And 3 /1 =3 , 20/10 = 2 , 100/100 = 1. This law can be used in every integer.
Next, How we assemble a integer by getting single digit each time? The answer is quite easy: 3x1=3, 2x10=20,1x100=100. 3+20+100 = 123.
Thus the solution is clear:
class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: N=0 N1=0 N2=0 while(l1!=None):#get each digit of l1 N1=N1+l1.val*pow(10,N) l1=l1.next N=N+1 N=0 while(l2!=None):#get each digit of l2 N2=N2+l2.val*pow(10,N) l2=l2.next N=N+1 Sum=N1+N2 #get plused result length=len(str(Sum))#check number of digits to create nodes nodes= i=1 while(i<=length): node=ListNode(int((Sum % pow(10,i))/pow(10,i-1)))#get each digit number of result nodes.append(node) i=i+1 for i in range(0,length-1): nodes[i].next=nodes[i+1] return nodes
However, we can plus each list’s unit’s digit , ten’s digit together at the same time , and put every result in single variable. Moreover, use same loop to put each digit in result linked list , and use
divmod to get each number.
def addTwoNumbers(self, l1, l2): carry = 0 res = n = ListNode(0) while l1 or l2 or carry:#while carry :check number of digits to create nodes if l1: carry += l1.val#get each digit of l1 and plus l1 = l1.next if l2: carry += l2.val;#get each digit of l2 and plus l2 = l2.next carry, val = divmod(carry, 10)#get each digit number of result n.next = n = ListNode(val) return res.next
Another approach to get each digit is to use
while(n>0): print(n%10) n/=10
Given two integers
divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing
The integer division should truncate toward zero.
Input: dividend = 10, divisor = 3 Output: 3
At first we all can think of setting a counter, and make subtraction each time like :
counter = 0 WHILE dividend > 0 dividend -= divisor counter++ return counter
However, this would be O(n) , which is too slow. We can try to set the ‘divisor’ as large as possible by multiply 2 until it can’t be larger, and then make the subtraction. This will be O(logn):
div = divisor //save the divisor res=0 WHILE dividend > 0 counter = 1 WHILE div < dividend div<<=1 //<<= is faster than div = div*2 counter<<=1 dividend -= div res += counter return res
In Python with overflow control:
res=0 if ((dividend<0) is (divisor<0)) == False: flag=-1 else: flag=1 if dividend==0: return 0 if dividend==-2147483648 and divisor==-1: return 2**31-1 dividend=abs(dividend) divisor=abs(divisor) while dividend-divisor>=0: temp=divisor counter=1 while dividend>=temp*2: temp=temp*2 counter=counter*2 dividend=dividend-temp res+=counter res=res*flag if res<-2**31 or res>2**31-1: return 2**31-1 else: return res
Clear vision by lee215:
sig = (a < 0) == (b < 0) a, b, res = abs(a), abs(b), 0 while a >= b: x = 0 while a >= b << (x + 1): x += 1 res += 1 << x a -= b << x return min(res if sig else -res, 2147483647)