CONY的世界

8. String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

 這題有點微妙，因為testcase 有那種 -+2 => 0, +413 => 0，網路上有人說這題根本shitty

不過我還是寫了一版我覺得對的版本（雖然碰上像是上面那種testcase是錯的....）但是就先看一下相對應會用到的function囉

主要是order可以換算出字元符號在unicode裡的address（反之是unichr，可以從位置反推字元符號）

詳細table在這裡 http://www.ssec.wisc.edu/~tomw/java/unicode.html#x0000

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        if not str: 
            return 0
        value, signed = 0, 1
        for s in str:
            if ord(s) == ord("-"):
                signed = -1
            if ord(s) in range(ord("0"),ord("9")):
                value = value*10+ int(s)
        value *= signed
        return value

 別人的方法，先用正規表示法（regular expression)找出可能用到值的string，在transform

def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        str = str.strip()
        str = re.findall('^[+\-]?\d+', str)

        try:
            res = int(''.join(str))
            MAX = 2147483647
            MIN = -2147483648
            if res > MAX:
                return MAX
            if res < MIN: 
                return MIN
            return res
        except: 
            return 0

 29. Divide Two Integers

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

If it is overflow, return MAX_INT.

======================================================================

在這邊看到一個post再討論 == 和 is 的差別，先講結論：  不要用 is ，因為太容易出錯 

== is for value equality. Use it when you would like to know if two objects have the same value.

is is for reference equality. Use it when you would like to know if two references refer to the same object.

到這邊看似很清楚，但是有特例......

Python caches integer objects in the range -5..256 as singleton instances for performance reasons. Here's an example demonstrating this:

 >>>for i inrange(250,260): a = i;print"%i: %s"%(i, a isint(str(i)));

... 
250: True
251: True
252: True
253: True
254: True
255: True
256: True
257: False
258: False
259: False

 ======================================================================

Success:

做題的時候有想到說要用倍數除數來加速除法，但是想不到要怎麼做，沒想到官解就是這樣做，所以蓋住自己寫一遍

不做倍數的話，就會像是我fail的例子time exceed

這邊注意的點有三個

1. positive 的判斷方式

2. 用兩個while loop，一個判斷是否繼續做除法，另外一個負責double 除數，一但除數太大就重新再來  （下面有例子）

3.就是判斷INT_MAX和INT_MIN 可結合 max() 和 min()

然後這邊也有用到之前判斷signed後將dividend和diivisor 絕對值再來處理

2.的例子：

for example, if we want to calc (17/2)

ret = 0;

17-2 ,ret+=1; left=15

15-4 ,ret+=2; left=11

11-8 ,ret+=4; left=3

3-2 ,ret+=1; left=1

ret=8;

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        positive = (dividend < 0) == (divisor < 0)
        dividend, divisor = abs(dividend), abs(divisor)
        res = 0
        while dividend >= divisor:
            temp, i = divisor, 1
            while dividend >= temp:
                dividend -= temp
                res+=i
                temp<<=1
                i<<=1
        if not positive:
            res = -res;
        return min(2**31-1, max(res,-2**31))

Fail:

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        signed, mod = 1, 0
        if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):
            signed = -1
        dividend, divisor = abs(dividend), abs(divisor)
        if divisor == 1:
            mod, dividend = dividend, 0
        while 1:
            tmp = dividend - divisor
            if tmp >= 0:
                dividend = tmp
            else:
                break
            mod +=1
        mod *= signed
        if mod < -2**31:    #-2147483648 <----0x80000000
            mod = -2**31
        elif mod > 2**31-1:   #2147483647 <----0x7FFFFFFF
            mod = 2**31-1
        return mod