Number

進制轉換

10進位 integer to string %10 /10

Given integer n

int[] digits
int len
while(len > 0){
    digits[len--] = n%10;
    n/=10;
}

13. Roman to Integer

Given a roman numeral, convert it to an integer.

The answer is guaranteed to be within the range from 1 to 3999.

• 7 characters

• Add number from left to right

• Test if left char is smaller than cur char

def romanToInt(self, s: str) -> int:
    dic = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
    num = dic[s[0]]
    
    for i in range(1, len(s)):
        num += dic[s[i]]
        if dic[s[i]] > dic[s[i-1]]:
            num -= dic[s[i-1]]*2

    return num

12 Integer to Roman

Given an integer, convert it to a roman numeral.

The number is guaranteed to be within the range from 1 to 3999.

• 13 strings

• 倍數數字 = 該roman number 重複數

def intToRoman(self, num: int) -> str:
    intList = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    romanList = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    
    ans = ''
    
    for i in range(13):
        while num >= intList[i]:
            ans += romanList[i]
            num -= intList[i]
            
    return ans

8. String to Integer(atoi)

• Leetcode 8

• Use long store

• The number could be bigger than Long

def myAtoi(self, str: str) -> int:
    str = str.strip(' ')
    
    num = 0
    isNeg = False
    
    for c in str:
        if not c.isdigit(): 
            if c == '-': isNeg = True
            continue
        
        if not isNeg:
            if (num > (2**31)//10) or (num == 2**31//10 and int(c) > 7): return 2**31-1
        if isNeg:
            if (num > (2**31)//10) or (num == 2**31//10 and int(c) > 8): return -2**31
        num = num*10 + int(c)
        
    return num if not isNeg else -num 

50. Pow(x, n)

def myPow(self, x: float, n: int) -> float:
    if n == 0: return 1
    isExpPositive = True
    if n < 0: 
        n = -n
        isExpPositive = False
        
    num = 1
        
    while n :
        if n%2:
            num *= x 
        x *= x
        n = int(n/2)

    return num if isExpPositive else 1/num

69. Sqrt

def mySqrt(self, x: int) -> int:
    if x < 2:
        return x
    
    start, end = 2, x//2 - 1
    
    while start < end:
        mid = (start + end)//2
        if mid**2 > x:
            end = mid 
        elif mid**2 < x:
            start = mid + 1
        else:
            return mid
    
    return start - 1

273 Integer to English Word

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

def numberToWords(self, num: int) -> str:
    LESS_THAN_20 = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve','Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']
    TEN = ['', 'Ten', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']
    THOUSAND = ['Billion', 'Million', 'Thousand', '']
    INDEX = [1000000000, 1000000, 1000, 1]
    
    def helper(num):
        if num < 20: 
            return LESS_THAN_20[num]
        elif num < 100: 
            # 注意要判斷helper回傳是否為空
            n = helper(num%10)
            return TEN[num//10] + ' ' + n if n else TEN[num//10]
        else:
            n = helper(num%100)
            return LESS_THAN_20[num//100] + ' Hundred ' + n \
                if n else LESS_THAN_20[num//100] + ' Hundred'
        
    if num == 0: return 'Zero'
    result = ''
    
    for i in range(len(INDEX)):
        if num//INDEX[i] == 0: continue
        result += helper(num//INDEX[i]) + ' ' + THOUSAND[i] + ' '
        num %= INDEX[i]
        
    return result.strip()