Palindrome Number – Python 3 (Week 11 – 02)

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        
        ans = 0
        tmp = x
        
        while tmp != 0:
            ans = ans * 10 + tmp % 10
            tmp = tmp // 10
            
        return x == ans
        

Time O(n). Space O(1).

Sqrt(x) II – Python 3 (Week 11 – 01)

  class Solution:
    """
    @param x: a double
    @return: the square root of x
    """
    def sqrt(self, x):
        # write your code here
        if x < 1:
            start, end = x, 1
        else:
            start, end = 1, x
            
        
        while end - start > 1e-10:
            mid = start + (end  - start) / 2
            if mid * mid < x:
                start = mid
            else:
                end = mid
                
        return start
        
      

Time O(logn). Space O(1).

String to Integer (atoi) – Python 3 (Week 10 – 19)

 class Solution:
    def myAtoi(self, str: str) -> int:
        str = str.strip()
        
        if len(str) == 0:
            return 0
        elif str[0] != '-' and str[0] != '+' and not str[0].isdigit():
            return 0       
        ans = 0
        
        start, end = 0, 0
        isNegative = False
        if str[0] == '+':
            start += 1
            end += 1
        elif str[0] == '-':
            isNegative = True
            start += 1
            end += 1
            
        
        if start >= len(str) or not str[start].isdigit():
            return 0
        
        while end < len(str) and str[end].isdigit():
            end += 1
        
        ans = int(str[start:end])
        
        if isNegative:
            ans = -ans
        
        if ans < -2**31:
            ans = -2**31
        elif ans > 2**31 - 1:
            ans = 2**31 - 1
        
        return ans
            

Sparse Matrix Multiplication – Python 3 (Week 10 – 18)

class Solution:
    """
    @param A: a sparse matrix
    @param B: a sparse matrix
    @return: the result of A * B
    """
    def multiply(self, A, B):
        # write your code here
        
        n = len(A)
        m = len(B[0])
        t = len(A[0])
        
        AB = [[0]  * m for i in range(n)]
     
        BB = []
        
        for k in range(t):
            BB.append([])
            for j in range(m):
                if B[k][j] != 0:
                    BB[k].append(j)
        
        for i in range(n):
            for k in range(t):
                if A[i][k] == 0:
                    continue
                for j in BB[k]:
                    AB[i][j] += A[i][k] * B[k][j]

 
        return AB

Time O(n^3). Space O(n^2)

Find the Celebrity – Python 3 (Week 10 – 17)

"""
The knows API is already defined for you.
@param a, person a
@param b, person b
@return a boolean, whether a knows b
you can call Celebrity.knows(a, b)
"""


class Solution:
    # @param {int} n a party with n people
    # @return {int} the celebrity's label or -1
    def findCelebrity(self, n):
        # Write your code here
        
        ans = 0
        
        for i in range(n):
            if Celebrity.knows(ans, i):
                ans = i
            
            
        i = 0
        for i in range(n):
            if ans != i and Celebrity.knows(ans, i):
                return -1
            if ans != i and not Celebrity.knows(i, ans):
                return -1
            
            
        return ans

Time O(n). Space O(n).

Integer to Roman – Python 3 (Week 10 – 15)

class Solution:
    def intToRoman(self, num: int) -> str:
        
        M = ["", "M", "MM", "MMM"];
        C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
        X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
        I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
        return M[num//1000] + C[(num%1000)//100] + X[(num%100)//10] + I[num%10];

Valid Number – Python 3 (Week 10 – 14)

class Solution:
    def isNumber(self, s: str) -> bool:
        if len(s) == 0:
            return False
        
        s = s.strip() + " "
        i = 0;
        
        if s[i] == '+' or s[i] == '-':
            i += 1
        
        nDigit, nPoint = 0, 0
        while s[i].isdigit() or s[i] == '.':
            if s[i].isdigit():
                nDigit += 1
            elif s[i] == '.':
                nPoint += 1
            i += 1
        if nDigit <= 0 or nPoint > 1:
            return False
            
        if s[i] == 'e':
            i += 1
            if s[i] == '+' or s[i] == '-':
                i += 1
            if i == len(s) - 1:
                return False;
            while i < len(s) - 1:
                if not s[i].isdigit():
                    return False
                i += 1
         
        return i == len(s) - 1       
            
        
        
        
        
        

Valid Number – Java

   public class Solution {
    /**
     * @param s: the string that represents a number
     * @return: whether the string is a valid number
     */
    public boolean isNumber(String s) {
        // write your code here
        if (s == null) {
            return false;
        }
        int i = 0;
        s = s.trim() + ' '; //delete UnsupportedOperationException
        char[] sc = s.toCharArray();
        int len = s.length() - 1;
        
        if (sc[i] == '+' || sc[i] == '-'){
            i++;
        }
        int nDigit = 0, nPoint = 0;
        while  (Character.isDigit(sc[i]) || sc[i] == '.') {
            if (Character.isDigit(sc[i])) {
                nDigit++;
            }
            if (sc[i] == '.') {
                nPoint++;
            }
            i++;
        }
        if (nDigit <= 0 || nPoint > 1) {
            return false;
        }
        if (sc[i] == 'e') {
            i++;
            if (sc[i] == '+'|| sc[i] == '-') {
                i++;
            }
            if (i == len) {
                return false;
            }
            for (; i < len; i++) {
                if (!Character.isDigit(sc[i])){
                    return false;
                }
            }
        }
        return i == len;
    }
}

Time O(n). Space O(1).

Create your website at WordPress.com
Get started