Skip to content

Commit 7d1978a

Browse files
author
Мето Трајковски
committed
Trimmed whitespaces
1 parent f6719fa commit 7d1978a

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

45 files changed

+89
-90
lines changed

‎Backtracking/jumping_numbers.py‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,16 @@
11
'''
22
Jumping numbers
33
4-
A number is called as a Jumping Number if all adjacent digits in it differ by 1.
4+
A number is called as a Jumping Number if all adjacent digits in it differ by 1.
55
The difference between ‘9’ and ‘0’ is not considered as 1.
6-
All single digit numbers are considered as Jumping Numbers.
6+
All single digit numbers are considered as Jumping Numbers.
77
For example 7, 8987 and 4343456 are Jumping numbers but 796 and 89098 are not.
88
99
Input: 20
1010
Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12]
1111
1212
=========================================
13-
Make a tree (DFS way/backtracking), for each next digit take the last digit, go up and down
13+
Make a tree (DFS way/backtracking), for each next digit take the last digit, go up and down
1414
(example: 123, last digit is 3, so next digit should be 2 or 4).
1515
Time Complexity: O(9 * 2^(NumOfDigits(N) - 1))
1616
Space Complexity: O(1) , recursion stack will have depth 9 (but this can be considered as constant)

‎Backtracking/power_set.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
'''
22
The power set
33
4-
The power set of a set is the set of all its subsets.
4+
The power set of a set is the set of all its subsets.
55
Write a function that, given a set, generates its power set.
66
77
Input: {1, 2, 3}

‎Backtracking/queens_problem.py‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
11
'''
22
Queens Problem
33
4-
You have an N by N board. Write a function that, given N, returns the number of possible arrangements
5-
of the board where N queens can be placed on the board without threatening each other,
4+
You have an N by N board. Write a function that, given N, returns the number of possible arrangements
5+
of the board where N queens can be placed on the board without threatening each other,
66
i.e. no two queens share the same row, column, or diagonal.
77
88
=========================================

‎Backtracking/river_sizes.py‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -2,10 +2,10 @@
22
River Sizes
33
44
You are given a two-dimensional array (matrix) of potentially unequal height and width containing only 0s and 1s.
5-
Each 0 represents land, and each 1 represents part of a river. A river consists of any number of 1s that are
6-
either horizontally or vertically adjacent (but not diagonally adjacent).
7-
The number of adjacent 1s forming a river determine its size.
8-
Write a function that returns an array of the sizes of all rivers represented in the input matrix.
5+
Each 0 represents land, and each 1 represents part of a river. A river consists of any number of 1s that are
6+
either horizontally or vertically adjacent (but not diagonally adjacent).
7+
The number of adjacent 1s forming a river determine its size.
8+
Write a function that returns an array of the sizes of all rivers represented in the input matrix.
99
Note that these sizes do not need to be in any particular order.
1010
1111
Input:

‎Dynamic Programming/climbing_staircase.py‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
11
'''
2-
Climbing Staircase
2+
Climbing Staircase
33
4-
There exists a staircase with N steps, and you can climb up either X different steps at a time.
5-
Given N, write a function that returns the number of unique ways you can climb the staircase.
4+
There exists a staircase with N steps, and you can climb up either X different steps at a time.
5+
Given N, write a function that returns the number of unique ways you can climb the staircase.
66
The order of the steps matters.
77
88
Input: steps = [1, 2], height = 4

‎Dynamic Programming/coin_change.py‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,12 @@
11
'''
22
Coin Change
33
4-
You are given coins of different denominations and a total amount of money amount.
5-
Write a function to compute the fewest number of coins that you need to make up that amount.
4+
You are given coins of different denominations and a total amount of money amount.
5+
Write a function to compute the fewest number of coins that you need to make up that amount.
66
If that amount of money cannot be made up by any combination of the coins, return -1.
77
88
Input: coins = [1, 2, 5], amount = 11
9-
Output: 3
9+
Output: 3
1010
1111
Input: coins = [2], amount = 3
1212
Output: -1

‎Dynamic Programming/max_subarray_sum.py‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
'''
2-
Maximum subarray sum
2+
Maximum subarray sum
33
44
The subarray must be contiguous.
55
@@ -8,7 +8,7 @@
88
Output explanation: [4, -1, -2, 1, 5]
99
1010
=========================================
11-
Need only one iteration, in each step add the current element to the current sum.
11+
Need only one iteration, in each step add the current element to the current sum.
1212
When the sum is equal or less than 0, reset the sum to 0 and continue with adding. (we care only about the positive sums)
1313
After each addition, check if the current sum is greater than the max sum. (Called Kadane's algorithm)
1414
Time Complexity: O(N)

‎Dynamic Programming/min_cost_coloring.py‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,14 @@
11
'''
22
Min Cost Coloring
33
4-
A builder is looking to build a row of N houses that can be of K different colors.
4+
A builder is looking to build a row of N houses that can be of K different colors.
55
He has a goal of minimizing cost while ensuring that no two neighboring houses are of the same color.
6-
Given an N by K matrix where the nth row and kth column represents the cost to build the
6+
Given an N by K matrix where the nth row and kth column represents the cost to build the
77
nth house with kth color, return the minimum cost which achieves this goal.
88
99
=========================================
1010
Dynamic programming, for each house search for the cheapest combination of the previous houses.
11-
But don't search the whole array with combinations (colors), save only the smallest 2
11+
But don't search the whole array with combinations (colors), save only the smallest 2
1212
(in this case we're sure that the previous house doesn't have the same color).
1313
Time Complexity: O(N * K)
1414
Space Complexity: O(1)
@@ -28,7 +28,7 @@ def min_cost_coloring(dp):
2828
m = len(dp[0])
2929
if m < 2:
3030
return -1
31-
31+
3232
# save only the smallest 2 costs instead of searching the whole previous array
3333
prev_min = [(0, -1), (0, -1)]
3434

‎Dynamic Programming/number_of_decodings.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
All of the messages are decodable!
77
88
=========================================
9-
The easiest solution is Brute-Force (building a tree and making all combinations),
9+
The easiest solution is Brute-Force (building a tree and making all combinations),
1010
and in the worst case there will be Fibbionaci(N) combinations, so the worst Time Complexity will be O(Fib(N))
1111
1212
Dynamic programming solution.

‎Dynamic Programming/sum_non-adjecent.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
'''
22
Sum of non-adjacent numbers
33
4-
Given a list of integers, write a function that returns the largest sum of non-adjacent numbers.
4+
Given a list of integers, write a function that returns the largest sum of non-adjacent numbers.
55
Numbers can be 0 or negative.
66
77
Input: [2, 4, 6, 2, 5]

0 commit comments

Comments
 (0)