전체 글
-
[LeetCode] Subsets알고리즘 2019. 11. 18. 17:30
문제 Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. Example: Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] Approach 전형적인 Bactracking문제로 n개의 요소로 된 집합에서 0개짜리 부분집합 ~ n개짜리 부분집합을 DFS등을 써서 backtracking으로 찾아가면 된다. Discussion을 보니까 bit manipulation으로 푸는 방법도 있던데 이건 좀 신박 Code h..
-
[LeetCode] Minimum Window Substring알고리즘 2019. 11. 5. 22:18
문제 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC" Note: If there is no such window in S that covers all characters in T, return the empty string "". If there is such window, you are guaranteed that there will always be only one unique minimum window in S. Ap..
-
[LeetCode] Set Colors알고리즘 2019. 11. 5. 17:23
문제 Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library's sort function for this problem. Example: Input: [2,0,2,1,1,0] Output: [0..
-
[LeetCode] Set Matrix Zeroes알고리즘 2019. 11. 4. 18:39
문제 Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place. Example 1: Input: [ [1,1,1], [1,0,1], [1,1,1] ] Output: [ [1,0,1], [0,0,0], [1,0,1] ] Example 2: Input: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] Output: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ] Follow up: A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) s..
-
[LeetCode] Climbing Stairs알고리즘 2019. 11. 3. 23:04
문제 You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb t..
-
[LeetCode] Sqrt(x)알고리즘 2019. 11. 3. 21:15
문제 Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned. Example 1: Input: 4 Output: 2 Example 2: Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 ..
-
[LeetCode] Plus One알고리즘 2019. 11. 3. 20:18
문제 Given a non-empty array of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself. Example 1: Input: [1,2,3] Output: [1,2,4] Explanation: The array rep..
-
[LeetCode] Unique Paths알고리즘 2019. 11. 3. 03:43
문제 Share A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there? Above is a 7 x 3 grid. How many possible unique paths are there? Note: m and n..