Here are some other questions that do not fit in other categories.
We recommend: Majority Element, Find the Celebrity and Task Scheduler.
[1] 371. Sum of Two Integers
Given two integers a and b, return the sum of the two integers without using the operators + and -.
My Answer 1: Accepted (Runtime: 32 ms - 50.76% / Memory Usage: 14.1 MB - 78.43%)
class Solution:
def getSum(self, a: int, b: int) -> int:
if b == 0:
return a
elif a == 0:
return b
elif b > 0xffffffff:
return a&0xffffffff
result = a^b
carry = (a&b) << 1
return self.getSum(result, carry)비트연산자가 생각나서 찾아보니까 재귀로 풀 수 있음
XOR 해주고 & 와 shift 로 carry 찾기
elif b > 0xffffffff: return a&0xffffffff 이거 안해주면 안된다...
overflow condition 이라네요 (-1, 1 일 경우)
[2] 150. Evaluate Reverse Polish Notation
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Note:
- Division between two integers should truncate toward zero.
- The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.
My Answer 1: Accepted (Runtime: 72 ms - 36.91% / Memory Usage: 14.5 MB - 72.34%)
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
operator = ["+", "-", "*", "/"]
stack = []
i = 0
for i in range(len(tokens)):
if tokens[i] in operator:
b = stack.pop()
a = stack.pop()
if tokens[i] == "+":
stack.append(a + b)
elif tokens[i] == "-":
stack.append(a - b)
elif tokens[i] == "*":
stack.append(a * b)
elif tokens[i] == "/":
stack.append(int(a / b))
else:
stack.append(int(tokens[i]))
return stack[0]stack 에 숫자들을 쭉 넣어가면서 연산자를 만나면 pop 두번 해서 a, b 잡고 계산하기
최종적으로 stack 에 남은 값이 답이 된다 => stack[0]
[3] 169. Majority Element
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
디스 이즈 이지~
My Answer 1: Accepted (Runtime: 164 ms - 76.43% / Memory Usage: 15.6 MB - 10.45%)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
counter = collections.Counter(nums)
for letter in counter:
if counter[letter] > len(nums) // 2:
return letterCounter 함수로 등장 횟수 세서 [n/2] 를 넘으면 바로 return
[4] 277. Find the Celebrity
Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.
Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).
You are given a helper function bool knows(a, b)which tells you whether A knows B. Implement a function int findCelebrity(n). There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.
My Answer 1: Wrong Answer (55 / 177 test cases passed.)
# The knows API is already defined for you.
# return a bool, whether a knows b
# def knows(a: int, b: int) -> bool:
class Solution:
def findCelebrity(self, n: int) -> int:
member = [0] * n
for i in range(n):
for j in range(n):
if i != j and knows(i, j):
member[j] += 1
maxmem = 0
result = 0
if min(member) == max(member):
return -1
for i in range(len(member)):
if member[i] > maxmem:
maxmem = member[i]
result = i
return resultn 이 무슨 값인지 몰라서... graph 의 size 라고 생각하고 풀었읍니다.
n 만큼의 member 배열을 만들어서 j 를 알아보는 사람의 수만큼 +1 해줌
모두 같게 알아보면 celebrity 가 없으니까 return -1
알아보는 사람이 가장 많은 멤버 maxmem 을 찾아서 그때의 인덱스 값을 return
Solution 1: Accepted (Runtime: 2132 ms / Memory Usage: 14.5 MB)
# The knows API is already defined for you.
# return a bool, whether a knows b
# def knows(a: int, b: int) -> bool:
class Solution:
def findCelebrity(self, n: int) -> int:
member = [True] * n
for i in range(n):
for j in range(n):
if i != j and member[i]:
if knows(i, j) or not knows(j, i):
member[i] = False
break
else:
member[j] = False
if member[i]:
return i
return -1member 를 boolean 형태의 리스트로 만들기
셀럽이 되려면 남은 나를 알아도, 나는 아무도 몰라야 한다!! 라네요
member 값이 True 일 때만
if knows(i, j) or not knows(j, i): => 나(i) 는 남(j) 을 알고 있는데 남은 나를 모를 경우
나는 셀럽이 아니니까 나 = False => member[i] = False
반대의 경우는 남이 나를 알고 있는 거니까 남은 셀럽이 될 수 X 남 = False => member[j] = False
그래서 두번째 for 문을 돌고도 member[i] 가 True 면 모두가 i 를 아는 거니까 return i
[5] 621. Task Scheduler
Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.
However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.
Return the least number of units of times that the CPU will take to finish all the given tasks.
My Answer 1: Accepted (Runtime: 552 ms - 28.94% / Memory Usage: 15 MB - 24.50%)
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
if n == 0:
return len(tasks)
counter = collections.Counter(tasks)
counter = list(counter.values())
maxlen = max(counter)
last = 0
for i in range(len(counter)):
if counter[i] == maxlen:
last += 1
return max(len(tasks), (maxlen-1) * (n+1) + last)(젤 많이 나온 문자의 개수-1) * (n+1) + (마지막 묶음 => interval 상관X) 라는 규칙이 보였다.
counter 를 구해주고 value 값만 (등장 횟수) 다시 리스트로 저장해줌
maxlen 과 같은 값이 여러개면 마지막 묶음에 들어가는 애들이니까 얘네도 count 해서 last 에 저장
원래는 return (maxlen-1) * (n+1) + last 였는데
최솟값으로 len(tasks) 을 가져야 한다고 해서
return max(len(tasks), (maxlen-1) * (n+1) + last) 로 바꿔줬더니 통과 !!
은근 생각할게 많은 others...☆
