Most of the math questions asked in interviews do not require math knowledge beyond middle school level.
We recommend: Excel Sheet Column Number, Pow(x, n) and Divide Two Integers.
[1] 202. Happy Number
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
- Starting with any positive integer, replace the number by the sum of the squares of its digits.
- Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
- Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
이지 선배님..
My Answer 1: Accepted (Runtime: 28 ms - 95.92% / Memory Usage: 14.2 MB - 51.52%)
class Solution:
def isHappy(self, n: int) -> bool:
if n == 1:
return 1
happy = 0
while n:
happy += pow(n%10, 2)
n = n//10
if happy == 2 or happy == 4:
return False
else:
return self.isHappy(happy)이중 for 문이를 쓰려다가.. 넘 무거울거 같아서 재귀로 했읍니다.
happy 에 자리수마다 제곱해서 더해주고 다음 재귀의 n 값으로 넘겨주기
전에는 if sum == 2 or sum == 4 or sum == 6 or sum == 8: 으로 했던 기억이 나네요~
이 친구 전에 unhappy 친구였던 거 같은데... 좀 달라졌네요^^
[2] 172. Factorial Trailing Zeroes
Given an integer n, return the number of trailing zeroes in n!.
Follow up: Could you write a solution that works in logarithmic time complexity?
이지 선배님2..
My Answer 1: Accepted (Runtime: 8868 ms - 6.09% / Memory Usage: 14.2 MB - 52.04%)
class Solution:
def trailingZeroes(self, n: int) -> int:
if n == 0:
return 0
fac = 1
# 1 ~ n
for i in range(1, n+1):
fac *= i
count = 0
while fac:
if fac%10 == 0:
count += 1
else:
break
fac = fac//10
return count팩토리얼 값 fac 구하고 10 으로 나누면서 0 의 갯수 세는 식으로 했는데 런타임 6%..^^
My Answer 2: Accepted (Runtime: 20 ms - 99.86% / Memory Usage: 14.3 MB - 23.02%)
class Solution:
def trailingZeroes(self, n: int) -> int:
if n < 5:
return 0
count = 0
while n:
count += n // 5
n = n // 5
return count그래서 루션이 슬쩍 보니까
n 에 포함된 5 의 개수에 따라서 0 의 개수가 결정되는 그 문제였군요 => 5 로 나눈 몫들을 저장
ex) 5! => 1개 / 10! => 2개 / 25! => 6개 (25 숫자는 5 가 2 개)
전에도 소름돋게 똑같은 순서로 풀었다는 점~
[3] 171. Excel Sheet Column Number
Given a column title as appear in an Excel sheet, return its corresponding column number.
이지 선배님3..
My Answer 1: Accepted (Runtime: 20 ms - 99.54% / Memory Usage: 14.2 MB - 74.98%)
class Solution:
def titleToNumber(self, s: str) -> int:
result = 0
for i in range(len(s)):
result += (ord(s[i]) - 64) * pow(26, len(s)-i-1)
return result해당 문자의 아스키코드 값 ord(s[i]) - 64 에 자릿수 pow(26, len(s)-i-1) 곱하기
1 자리 => 26^0 , 2 자리 => 26^1 , 3 자리 => 26^2
맨 앞자리부터 보기 때문에 len(s)-i-1
[4] 50. Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (i.e. xn).
Solution 1: Accepted (Runtime: 32 ms - 63.45% / Memory Usage: 14.2 MB - 82.16%)
class Solution:
def myPow(self, x: float, n: int) -> float:
if n < 0:
x = 1/x
n = -n
power = 1
cur = x
while n > 0:
if n%2 :
power = power * cur
cur = cur * cur
n = n//2
return power첨엔 반복문으로 계속 곱하기 하려 했는데 0.00001 2147483647 처럼 2^31-1 언저리 케이스면 난리남
x**n 으로 해도 되는거 아닌지..^^
아무튼 빠르게 하려면 n 을 2 로 나눠가면서 풀면 된다
음수는 1/x, -n 으로 바꿔주기
요런 식으로 풀기
[5] 69. Sqrt(x)
Given a non-negative integer x, compute and return the square root of x.
Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.
이지 선배님4..
My Answer 1: Accepted (Runtime: 20 ms - 99.75% / Memory Usage: 14 MB - 98.21%)
class Solution:
def mySqrt(self, x: int) -> int:
return int(x ** 0.5)이것도 답이라고 해줘요...
Solution 1: Accepted (Runtime: 40 ms - 47.15% / Memory Usage: 14.2 MB - 43.27%)
class Solution:
def mySqrt(self, x: int) -> int:
## RC ##
## APPROACH : Binary Search ##
# 1. Any number greater than 1, will have sqrt(n) less than n/2
# 2. We can check i*i < n till n/2.
# 3. Can be optimized with binary search, listing all nums till n/2 and check i*i < n
if(x < 4): return 1 if (x!=0) else 0
low = 2
high = x//2
while(low <= high):
mid = low + (high - low)//2
if( mid**2 < x):
low = mid + 1
elif( mid**2 > x):
high = mid - 1
else:
return mid
return high이걸 원한 거 같다 Binary Search 이용하기
1 보다 큰 숫자들의 제곱근은 모두 n/2 보다 작은 값을 갖기 때문에 high = x//2
따라서 2 ~ x//2 사이에 존재하는 sqrt(x) 찾기
mid 의 제곱이 x 보다 작으면 low 움직이기, 크면 high 움직이기
mid 의 제곱이 x 가 되면 return mid
신기하네요
[6] 29. Divide Two Integers
Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.
Note:
Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, assume that your function returns 231 − 1 when the division result overflows.
My Answer 1: Accepted (Runtime: 24 ms - 97.98% / Memory Usage: 14.3 MB - 58.58%)
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
if dividend == 0 or divisor == 0:
return 0
# special case
if dividend == -2**31 and divisor == -1:
return 2**31-1
# + + or - - => 양수니까 그냥 나눠서 return
if (dividend > 0 and divisor > 0) or (dividend < 0 and divisor < 0):
return dividend//divisor
# + - or - + => divisor 에 -1 곱해서 계산하고 -1 승으로 뒤집어주기
if dividend < 0 or divisor < 0:
return (dividend//(divisor*-1))*-1둘 다 0 일 경우, 둘 다 양수/음수일 경우, 둘 중 하나만 음수일 경우 나눠서 계산
[7] 166. Fraction to Recurring Decimal
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
If multiple answers are possible, return any of them.
It is guaranteed that the length of the answer string is less than 104 for all the given inputs.
My Answer 1: Accepted (Runtime: 32 ms - 66.28% / Memory Usage: 14.3 MB - 70.34%)
class Solution:
def fractionToDecimal(self, numerator: int, denominator: int) -> str:
# 나눠 떨어지면 그냥 몫 return
if numerator % denominator == 0:
return str(numerator // denominator)
# 둘 중에 하나만 음수일 경우, 절댓값 처리
if numerator < 0 and denominator > 0 or numerator > 0 and denominator < 0:
numerator = abs(numerator)
denominator = abs(denominator)
result = ["-" + str(numerator // denominator) + "."]
# 둘 다 음수거나 양수면, 그냥 몫에 소수점 붙이기
else:
result = [str(numerator // denominator) + "."]
remainder = numerator % denominator
use = {} # 나머지가 또 등장했는지 => 순환하는지 확인하기 위해
idx = len(result) # result 에서 소수점 다음 자리를 나타냄
while remainder:
# 한 번 만났던 나머지 == 순환
# => result[use[remainder]] 자리에 여는 괄호 삽입 & 마지막에 닫는 괄호 삽입
if remainder in use:
result.insert(use[remainder], "(")
result.append(")")
break
# result 에서의 위치값 idx
use[remainder] = idx
# 계산
remainder *= 10
result.append(str(remainder // denominator))
remainder = remainder % denominator
idx += 1
# list 를 string 으로
return ''.join(result)나눠 떨어질 때, 양수/음수 예외 처리 해주고
나머지값 remainder 로 소수점 구하기
remainder 마다 use 딕셔너리에 인덱스 값을 넣어줘서 혹시 순환할 경우 괄호가 들어갈 자리를 알려줌
if remainder in use: => 순환한다는 뜻
수학적 지식이 있으면 빠르게 풀 수 있겠네요~
