LeetCode day1

5 minutes read
LeetCode
#LeetCode
views 910 words

1. Two Sum

Topic: Array, Hash Table

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Approach 1

Brute Force:

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i in range(len(nums)):
        for j in range(len(nums)):
            if nums[i] + nums[j] == target:
                return [i,j]
  • Time complexity : $O(n^2)$
  • Space complexity : $O(1)$

Approach 2

def twoSum(self, nums: List[int], target: int) -> List[int]:
    temp = {}
    for i,num in enumerate(nums):
        remain = target - num
        if remain in temp:
            return [temp[remain],i]
        temp[num] = i
    return []
  • Time complexity : $O(n)$
  • Space complexity : $O(n)$

7. Reverse Integer

Topic: Math

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note: Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: $[−2^{31}, 2^{31} − 1]$. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Approach1

将int转成str, 然后反转后再转回int

def reverse(self, x: int) -> int:
    if x > 0:  # handle positive numbers  
        a =  int(str(x)[::-1])  
    if x <=0:  # handle negative numbers  
        a = -1 * int(str(x*-1)[::-1])  
    # handle 32 bit overflow  
    print(a)
    mina = -2**31  
    maxa = 2**31 - 1  
    if a not in range(mina, maxa):  
        return 0  
    else:  
        return a

Approach2

def reverse(self, x):
    result = 0

    if x < 0:
        symbol = -1
        x = -x
    else:
        symbol = 1

    while x:
        result = result * 10 + x % 10
        x //= 10

    return 0 if result > pow(2, 31) else result * symbol
  • Time complexity : $O(log(n))$
  • Space complexity : $O(1)$

13. Roman to Integer

Topic: Math, String

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Approach1

    def romanToInt(self, s: str) -> int:
        translations = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000
        }
        number = 0
        s = s.replace("IV", "IIII").replace("IX", "VIIII")
        s = s.replace("XL", "XXXX").replace("XC", "LXXXX")
        s = s.replace("CD", "CCCC").replace("CM", "DCCCC")
        for char in s:
            number += translations[char]
        return number

Apprpoach2

First sum up all single roman numerals, then if we find currValue > prevValue, we subtract 2 * prevValue, e.g. CM, first we get 1100, then we subtract 200, the result is 900.

def romanToInt(self, s):
    value, prevValue, result = {'M': 1000, 'D': 500, 'C': 100, 'L': 50, 'X': 10, 'V': 5, 'I': 1}, None, 0
    for ch in s:
        currValue = value[ch]
        result += currValue
        if prevValue and currValue > prevValue: result -= 2 * prevValue
        prevValue = currValue
    return result

Approach3

def romanToInt(self, s: str) -> int:
    temp={'I':1,'V':5,'X':10,'L':50, 'C':100, 'D':500, 'M':1000, 'IV':4,'IX':9,'XL':40,'XC':90,'CD':400, 'CM':900}
    res = 0
    for i in range(len(s)-1):
        if temp[s[i]] >= temp[s[i+1]]:
            res += temp[s[i]]
        else:
            res -= temp[s[i]]
        
    res += temp[s[len(s)-1]]
    return res

14. Longest Common Prefix

Topic: String

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Approach1

def longestCommonPrefix(self, strs: List[str]) -> str:
    if not strs: return ""
    if len(strs) == 1: return strs[0]
    
    strs.sort()
    p = ""
    for x, y in zip(strs[0], strs[-1]):
        if x == y: 
            p+=x
        else: 
            break
    return p

Approach2

strs = ["flower","flow","flight"]
l = list(zip(*strs))
>>> l = [('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]


def longestCommonPrefix(self, strs: List[str]) -> str:
    l = list(zip(*strs))
    prefix = ""
    for i in l:
        if len(set(i))==1:
            prefix += i[0]
        else:
            break
    return prefix