leetcode.com/explore/learn/card/binary-search/ left + (right - left) // 2 class Solution: def search(self, nums: List[int], target: int) -> int: n = len(nums) l = 0 r = n-1 while l ythat means2yx That means one could rewrite the recursion above as \textrm{mySqrt}(x) = \textrm{mySqrt}(x >> 2) >2) int: l = 0 r = len(nums) - 1 n = len(nums) def find_rotate_index(left, right): if nums[left] < nums[..
leetcode.com/contest/weekly-contest-222 222 9692 4096 1594 664 247 42.26% 16.45% 6.85% 2.55% 12.58% My 2021 is ruined :( TLE for both q2 and q3 1710. Maximum Units on a Truck leetcode.com/problems/maximum-units-on-a-truck/ class Solution: def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int: boxTypes.sort(key=lambda x: -x[1]) max_units = 0 for n, units in boxTypes: max_units ..
Math Most of the math questions asked in interviews do not require math knowledge beyond middle school level. We recommend: Count Primes Power of Three. 412. Fizz Buzz leetcode.com/problems/fizz-buzz/ 피즈버즈 하나 가지고도 이런 다양한 토론을 할수 있군.. Solution You must have played FizzBuzz as kids. FizzBuzz charm never gets old. And so here we are looking at how you can take on one step at a time and impress your ..
leetcode.com/contest/weekly-contest-210 1614. Maximum Nesting Depth of the Parentheses leetcode.com/problems/maximum-nesting-depth-of-the-parentheses/ def maxDepth(self, s): res = cur = 0 for c in s: if c == '(': cur += 1 res = max(res, cur) if c == ')': cur -= 1 return res 괄호문제는 보통 스택이 필요할것 같지만, 잘 생각해보면 필요없다. 그리고 아래의 조건 때문에, 짝이 안맞는것을 디텍팅할 필요도 없다. 문제를 잘 읽자. For example, "", "()()", and "()(()())..
1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/ Given two binary trees original and cloned and given a reference to a node target in the original tree. The cloned tree is a copy of the original tree. Return a reference to the same node in the cloned tree. Note that you are not allow..
leetcode.com/contest/weekly-contest-211 1624. Largest Substring Between Two Equal Characters leetcode.com/problems/largest-substring-between-two-equal-characters/ 문제를 잘읽자, 없으면 -1을 반환하라고 되있으니. class Solution: def maxLengthBetweenEqualCharacters(self, s: str) -> int: dic = {} max_len = -1 for i in range(len(s)): if s[i] in dic: max_len = max(max_len, i - dic[s[i]] - 1) else: dic[s[i]] = i return m..
leetcode.com/contest/weekly-contest-212 leetcode.com/problems/slowest-key/ class Solution: def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str: #Time complexity = O(n) #Space complexity = O(1) maxletter = keysPressed[0] maxvalue = releaseTimes[0] for i in range(1, len(releaseTimes)): value = releaseTimes[i] - releaseTimes[i-1] if value > maxvalue: maxvalue = value maxletter = ..
leetcode.com/contest/weekly-contest-221/ 1704. Determine if String Halves Are Alike leetcode.com/problems/determine-if-string-halves-are-alike/ You are given a string s of even length. 라고 했는데 복잡하게 홀수 처리 하고 있었네. 문제를 잘읽자. class Solution: def halvesAreAlike(self, s: str) -> bool: vowels = set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']) i = 0 j = len(s)-1 cnt_i = cnt_j = 0 while i < j: if s[..
198. House Robber leetcode.com/problems/house-robber/ 구글기출 213. House Robber II leetcode.com/problems/house-robber-ii/ 337. House Robber III leetcode.com/problems/house-robber-iii/ 656. Coin Path leetcode.com/problems/coin-path/ 구글기출 740. Delete and Earn leetcode.com/problems/delete-and-earn/
leetcode.com/contest/weekly-contest-220 class Solution: def reformatNumber(self, number: str) -> str: ans = "" chunk = "" for n in number: if n.isdigit(): chunk += n if len(chunk) % 3 == 0: if len(ans) != 0: ans += '-' ans += chunk chunk = "" if len(chunk) == 1: chunk = ans[-1] + chunk ans = ans[:-1] if len(chunk) > 0: if len(ans) != 0: ans += '-' ans += chunk return ans 1695. Maximum Erasure Va..
leetcode.com/problems/check-array-formation-through-concatenation/ 공간이 중요할때는 바이너리서치 시간이 중요할때는 해쉬맵 사용 You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i]. Return true ..
leetcode.com/problems/palindrome-permutation/. class Solution: def canPermutePalindrome(self, s: str) -> bool: val = 0 for letter in s: val = val ^ 1 bool: map = {} for c in s: map[c] = map.get(c, 0) + 1 odd = 0 for (char, count) in map.items(): if count % 2 == 1: odd += 1 return odd bool: count = collections.Counter(s) oddcount = 0 for ele,value in count.items(): if value % 2 != 0: oddcount += ..
Design These problems may require you to implement a given interface of a class, and may involve using one or more data structures. These are great exercises to improve your data structure skills. We recommend: Shuffle an Array Min Stack. 384. Shuffle an Array leetcode.com/problems/shuffle-an-array/ hint The solution expects that we always use the original array to shuffle() else some of the tes..
289. Game of Life leetcode.com/problems/game-of-life/ 시간 복잡도는 MN일수 밖에없고 공간복잡도는 단순하게 하면 MN이나 생각해보면 O(1)에도 구현할 수 있다. 어프로치2 According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970." 콘웨이의 게임이라고도 알려져 있는 문제. The board is made up of an m x n grid of cells, where each cell has an initial state..
페이스북 폰스크린 기출문제, 이 문제는 easy이기 때문에, 관련문제 medium까지 함께 풀이. 859. Buddy Strings leetcode.com/problems/buddy-strings/ Given two strings A and B of lowercase letters, return true if you can swap two letters in A so the result is equal to B, otherwise, return false. Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at A[i] and A[j]. For exa..
leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/ Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters. Example 1: Input: s = "eceba", k = 2 Output: 3 Explanation: The substring is "ece" with length 3. Example 2: Input: s = "aa", k = 1 Output: 2 Explanation: The substring is "aa" with length 2. Co..
1457. Pseudo-Palindromic Paths in a Binary Tree leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/ Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome. Return the number of pseudo-palindromic paths going from the root node to leaf nodes. Ex..
이 문제들은 내가 목표로 하는 회사에서 내는 스타일은 아닌것 같다. 811. Subdomain Visit Count leetcode.com/problems/subdomain-visit-count/ class Solution: def subdomainVisits(self, cpdomains: List[str]) -> List[str]: ans = collections.Counter() for domain in cpdomains: count, domain = domain.split() count = int(count) frags = domain.split('.') for i in range(len(frags)): ans[".".join(frags[i:])] += count return ["{} {}".for..
leetcode.com/problems/reach-a-number/ You are standing at position 0 on an infinite number line. There is a goal at position target. On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps. Return the minimum number of steps required to reach the destination. Example 1: Input: target = 3 Output: 2 Explanation: On the first move we step from 0 to 1...
leetcode.com/problems/decode-ways/ A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. The answer is guaranteed to fit in a 32-bit integer. Example 1: Input: s = "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) o..
점프게임 시리즈 공부하기 leetcode.com/problemset/all/?search=jump%20game 6개나 있네. 2,4 가 구글 기출문제이다. 55. Jump Game leetcode.com/problems/jump-game/ 미디움 그냥 도달하기만 하면 되는거라서, 그리디로 짜면 된다. 내 코드 class Solution: def canJump(self, nums: List[int]) -> bool: reachable = 0 for i in range(len(nums)): if i = len(nums)-1: return True return True if reachable >= len(nums)-1 else False 일주일전에는 이렇게 짰다는게 웃기다 ㅋㅋ class Solution: d..
leetcode.com/contest/biweekly-contest-42. leetcode.com/problems/number-of-students-unable-to-eat-lunch/ 문제에 기술된 그대로의 코드 class Solution: def countStudents(self, students: List[int], sandwiches: List[int]) -> int: n = len(students) ans = n start = 0 for sandwich in sandwiches: found = False print(start, start+n) for i in range(start, start+n): idx = i % n start = (idx+1)%n if students[idx] == sand..
leetcode.com/problems/swap-nodes-in-pairs/ 24. Swap Nodes in Pairs Medium 3022194Add to ListShare Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes. Only nodes itself may be changed. Example 1: Input: head = [1,2,3,4] Output: [2,1,4,3] Example 2: Input: head = [] Output: [] Example 3: Input: head = [1] Output: [1] Constraint..
leetcode.com/problems/find-nearest-right-node-in-binary-tree/ Given the root of a binary tree and a node u in the tree, return the nearest node on the same level that is to the right of u, or return null if u is the rightmost node in its level. Example 1: Input: root = [1,2,3,null,4,5,6], u = 4 Output: 5 Explanation: The nearest node on the same level to the right of node 4 is node 5. Example 2:..
leetcode.com/problems/balanced-binary-tree/ Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the left and right subtrees of every node differ in height by no more than 1. Example 1: Input: root = [3,9,20,null,null,15,7] Output: true Example 2: Input: root = [1,2,2,3,3,null,null,4,4] Output: false Exampl..
Math 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. Happy Number Factorial Trailing Zeroes Excel Sheet Column Number Pow(x, n) Sqrt(x) Divide Two Integers Fraction to Recurring Decimal 202. Happy Number leetcode.com/problems/happy-number/ 4가지 방식이 있는데 하나는 logN / lo..