1673. Find the Most Competitive Subsequence leetcode.com/problems/find-the-most-competitive-subsequence/ Medium 50333Add to ListShare Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k. An array's subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array. We define that a subsequence a is more..
leetcode.com/problems/kth-largest-element-in-an-array/ 이 문제는 굉장히 중요하다. 왜냐하면 퀵소트(퀵셀렉트)로 푸는 문제이기 때문이다. 215. Kth Largest Element in an Array Medium 4928318Add to ListShare Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. Example 1: Input: [3,2,1,5,6,4] and k = 2 Output: 5 Example 2: Input: [3,2,3,1,2,4,5,5,..
Google 1658. Minimum Operations to Reduce X to Zero Medium 4569Add to ListShare You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations. Return the minimum number of operations to reduce x to exactly 0 if it's possi..
881. Boats to Save People Medium 101944Add to ListShare The i-th person has weight people[i], and each boat can carry a maximum weight of limit. Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit. Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.) Example 1: Inp..
127. Word Ladder leetcode.com/problems/word-ladder/ Hard 43961374Add to ListShare Given two words beginWord and endWord, and a dictionary wordList, return the length of the shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transformed word must exist in the word list. Return 0 if there is no such transformation sequence. Example..
1539. Kth Missing Positive Number leetcode.com/problems/kth-missing-positive-number/ O(N)과 O(lgN)이 존재하므로 흥미롭다고 생각되는 문제 Easy 54918Add to ListShare Given an array arr of positive integers sorted in a strictly increasing order, and an integer k. Find the kth positive integer that is missing from this array. Example 1: Input: arr = [2,3,4,7,11], k = 5 Output: 9 Explanation: The missing positive inte..
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..
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/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 += ..
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/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..
leetcode.com/problems/smallest-range-ii/ 910. Smallest Range II Medium 431186Add to ListShare Given an array A of integers, for each integer A[i] we need to choose either x = -K or x = K, and add x to A[i] (only once). After this process, we have some array B. Return the smallest possible difference between the maximum value of B and the minimum value of B. Example 1: Input: A = [1], K = 0 Outpu..
leetcode.com/problems/decoded-string-at-index/ An encoded string S is given. To find and write the decoded string to a tape, the encoded string is read one character at a time and the following steps are taken: If the character read is a letter, that letter is written onto the tape. If the character read is a digit (say d), the entire current tape is repeatedly written d-1 more times in total. N..
64. Minimum Path Sum leetcode.com/problems/minimum-path-sum/ Summary We have to find the minimum sum of numbers over a path from the top left to the bottom right of the given matrix . Solution Approach 1: Brute Force The Brute Force approach involves recursion. For each element, we consider two paths, rightwards and downwards and find the minimum sum out of those two. It specifies whether we nee..
1. Two Sum leetcode.com/problems/two-sum/ class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: d = {} for i, n in enumerate(nums): m = target - n if m in d: return [d[m], i] else: d[n] = i class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ h = {} for i, num in enumerate(nums): n = target - num if n not in h: h..
leetcode.com/problems/squares-of-a-sorted-array/ 3번으로 해야함. Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. Example 1: Input: nums = [-4,-1,0,3,10] Output: [0,1,9,16,100] Explanation: After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100]. Example 2: Input: nums = [-7,-3,2..
leetcode.com/problems/plus-one-linked-list/ Given a non-negative integer represented as a linked list of digits, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list. Example 1: Input: head = [1,2,3] Output: [1,2,4] Example 2: Input: head = [0] Output: [1] Constraints: The number of nodes in the linked list is in the range [1, 100]. 0