Today, I solved "Maximum Subarray." Description: Solution: As we can see, we don't have to include the first negative array. curSum is a cumulative sum of numbers. If curSum is negative, it means that subarray is not for maximum sum. I use max() to compare the curSum and maxSub.
Today, I solved coin chnage. Description: In this problem, we should find the fewest number of coins that make up that amount. Solution: This is the brute force solution. Let's say coin is [1, 3, 4, 5], and amount = 7. dp[0] is always "0" (because no need to coin to get to 0) dp[1] = 1 dp[2] = 2 dp[3] = 1 -> one 3coin dp[4] = 1 -> one 4coin dp[5] = 1 -> one 5coin dp[6] = 2 -> one 1coin + one 5co..
Today, I solved the climbing staris. Description: Solution: Let's say the example(n = 5). On the 4th stair, we have only 1 way to get 5th stair. On the 3rd stair, we have (1 + 1) ways to get 5th stair. On the 2nd stair, we have (2 + 1) ways to get 5th stair. In my code, we set (n-1)th stair as "one", and nth stair as "two." We shift those one and two until we get to 0(start point). (n-1) and (n)..
Today, I solved "Reverse Bits." Description: In this problem, we are gonna do reverse order of 32-bits number. Solution: "output" will store "0" or "1." If the bit number is 1, then the output store 1 in it. Otherwise, it stores 0. In output, we shift the bit left, and also we shift the bit right in n.
Today, I solved the Missing number. Description: In this question, we are asked to find missing number in nums. Solution: In this method, we are gonna subtract sum of nums from sum of every number of n. For example 2: The length of nums: 2 Range: [0, 2] sum([0, 1, 2]) - sum([0, 1] = 2 Space Complexity: O(1) Time Complexity: O(n)
Today, I solved Counting Bits. Description: In this problem, we are gonna return the array. The array length should ne "n+1", and the array show how many 1 bits each number has in their binary number. Solution: The length of dp array: [0] * (n + 1) offset = 1 (This tells where the numbers between 2 ^n-1, 2^n) we are gonna check the offset reach out 1, 2, 4, 8 ... each time in for loop. 0 -> 0000..
Today, I solved the Number of 1 Bits from Leetcode. Description: In this question, we are gonna work on changing the binary number to decimal numbers. There are two methods to solve this problem in Python: Solution1: The first solution, we are gonna divide the number to see the first bit is 1 or 0. For example, 17 is 10001. 10001 % 2 = 1 Now, keep moving to the right! 1000 % 2 = 0 100 % 2 = 0 10..
Today I soled the "Sum of Two Integers" Description: This question ask us how to get sum of the two integers without using sign "+" and "-." In example 2, a is 2 => 10 b is 3 => 11 a+b: 10 + 11 ----- 101 (which is 5) In binary number, 1 + 1 makes the carry "1" to the next slot. For carry "1", we are gonna use & a & b: 10 & 11 ----- 100(so move to left
Today, I solved the Merge K sorted Lists. Description: In this question, we are gonna merge several lists. And, the merged list should be sorted in order. Solution: This is the first part of solution. We will look into mergeLists() function later. If the gived lists are empty, we return None. While loop runs until the length of lists is over 1. We make the list for storing merged lists. Since we..
Today, I did the question: Linked List Cycle. Description: We should check whether cycle exist or not. head and pos is given. We can check the pos that which position is cycled back on the list. In example 1, 1st node is the returning node on the list. Then, how do we check the cycle on the list? The solution is similar to previous linked list question: We are gonna make the slow and fast pointe..
