Skip to content

Commit f6719fa

Browse files
author
Мето Трајковски
committed
Fixed tab spaces
1 parent a348932 commit f6719fa

Some content is hidden

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

52 files changed

+276
-276
lines changed

‎Backtracking/jumping_numbers.py‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -27,13 +27,13 @@ def jumping_numbers(x):
2727
# take all 9 possible starting combinations
2828
for i in range(1, 10):
2929
jumping_num(i, x, result)
30-
30+
3131
return result
3232

3333
def jumping_num(num, x, result):
3434
if num > x:
3535
return
36-
36+
3737
result.append(num)
3838

3939
last_digit = num % 10
@@ -42,11 +42,11 @@ def jumping_num(num, x, result):
4242
# decrease the last digit by one
4343
if last_digit != 0:
4444
jumping_num(next_num + last_digit - 1, x, result)
45-
45+
4646
# increase the last digit by one
4747
if last_digit != 9:
4848
jumping_num(next_num + last_digit + 1, x, result)
49-
49+
5050

5151
###########
5252
# Testing #

‎Backtracking/power_set.py‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -10,8 +10,8 @@
1010
1111
=========================================
1212
Simple recursive combinations algorithm.
13-
Time Complexity: O(Sum(C(I, N))) , sum of all combinations between 0 and N = C(0, N) + C(1, N) + ... + C(N, N)
14-
Space Complexity: O(Sum(C(I, N))) , this is for the result array, if we print the number then the space complexity will be O(1)
13+
Time Complexity: O(Sum(C(I, N))) , sum of all combinations between 0 and N = C(0, N) + C(1, N) + ... + C(N, N)
14+
Space Complexity: O(Sum(C(I, N))) , this is for the result array, if we print the number then the space complexity will be O(1)
1515
'''
1616

1717

@@ -27,10 +27,10 @@ def power_set(arr):
2727
def combinations(arr, taken, pos):
2828
result = []
2929
result.append([arr[i] for i in taken]) # create the current combination
30-
30+
3131
if len(arr) == pos:
3232
return result
33-
33+
3434
n = len(arr)
3535
# start from the last position (don't need duplicates)
3636
for i in range(pos, n):

‎Backtracking/queens_problem.py‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7,8 +7,8 @@
77
88
=========================================
99
Backtracking solution.
10-
Time Complexity: O(N!) (but I think it's much faster!)
11-
Space Complexity: O(N)
10+
Time Complexity: O(N!) (but I think it's much faster!)
11+
Space Complexity: O(N)
1212
* There are much faster solutions, like O(N^2)
1313
'''
1414

@@ -29,7 +29,7 @@ def backtracking(columns, order):
2929

3030
if len(order) == n:
3131
return 1
32-
32+
3333
total = 0
3434

3535
for i in range(n):

‎Backtracking/river_sizes.py‎

Lines changed: 48 additions & 48 deletions
Original file line numberDiff line numberDiff line change
@@ -21,8 +21,8 @@
2121
=========================================
2222
This problem can be solved using DFS or BFS.
2323
If 1 is found, find all horizontal or vertical neighbours (1s), and mark them as 0.
24-
Time Complexity: O(N*M)
25-
Space Complexity: O(R) , R = num of rivers
24+
Time Complexity: O(N*M)
25+
Space Complexity: O(R) , R = num of rivers
2626
'''
2727

2828

@@ -31,53 +31,53 @@
3131
############
3232

3333
def river_sizes(matrix):
34-
n = len(matrix)
35-
m = len(matrix[0])
36-
37-
results = []
38-
39-
for i in range(n):
40-
for j in range(m):
41-
if matrix[i][j] != 0:
42-
# find the river size
43-
size = dfs((i, j), matrix)
44-
45-
# save the river size
46-
results.append(size)
47-
48-
return results
49-
34+
n = len(matrix)
35+
m = len(matrix[0])
36+
37+
results = []
38+
39+
for i in range(n):
40+
for j in range(m):
41+
if matrix[i][j] != 0:
42+
# find the river size
43+
size = dfs((i, j), matrix)
44+
45+
# save the river size
46+
results.append(size)
47+
48+
return results
49+
5050
def dfs(coord, matrix):
51-
(i, j) = coord
52-
53-
if i < 0 or j < 0:
54-
# invalid position
55-
return 0
56-
57-
n = len(matrix)
58-
m = len(matrix[0])
59-
60-
if i == n or j == m:
61-
# invalid position
62-
return 0
63-
64-
if matrix[i][j] == 0:
65-
# not a river
66-
return 0
67-
68-
# update the matrix, the matrix is passed by reference
69-
matrix[i][j] = 0
70-
# this position is part of river
71-
size = 1
72-
73-
# directions: down, left, up, right
74-
dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
75-
76-
# check all 4 directions
77-
for d in dirs:
78-
size += dfs((i + d[0], j + d[1]), matrix)
79-
80-
return size
51+
(i, j) = coord
52+
53+
if i < 0 or j < 0:
54+
# invalid position
55+
return 0
56+
57+
n = len(matrix)
58+
m = len(matrix[0])
59+
60+
if i == n or j == m:
61+
# invalid position
62+
return 0
63+
64+
if matrix[i][j] == 0:
65+
# not a river
66+
return 0
67+
68+
# update the matrix, the matrix is passed by reference
69+
matrix[i][j] = 0
70+
# this position is part of river
71+
size = 1
72+
73+
# directions: down, left, up, right
74+
dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
75+
76+
# check all 4 directions
77+
for d in dirs:
78+
size += dfs((i + d[0], j + d[1]), matrix)
79+
80+
return size
8181

8282

8383
###########

‎Dynamic Programming/coin_change.py‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@ def coin_change_1(coins, amount):
3434
max_value = amount + 1 # use this instead of math.inf
3535
dp = [max_value for i in range(max_value)]
3636
dp[0] = 0
37-
37+
3838
for i in range(1, max_value):
3939
for c in coins:
4040
if c <= i:
@@ -60,7 +60,7 @@ def coin_change_2(coins, amount):
6060
max_coin = min(max_value, max(coins) + 1)
6161
dp = [max_value for i in range(max_coin)]
6262
dp[0] = 0
63-
63+
6464
for i in range(1, max_value):
6565
i_mod = i % max_coin
6666
dp[i_mod] = max_value # reset current position

‎Dynamic Programming/max_subarray_sum.py‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -11,8 +11,8 @@
1111
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)
14-
Time Complexity: O(N)
15-
Space Complexity: O(1)
14+
Time Complexity: O(N)
15+
Space Complexity: O(1)
1616
'''
1717

1818

‎Dynamic Programming/min_cost_coloring.py‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@
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)
15-
'''
15+
'''
1616

1717
############
1818
# Solution #
@@ -41,14 +41,14 @@ def min_cost_coloring(dp):
4141
dp[i][j] += prev_min[0][0]
4242
else:
4343
dp[i][j] += prev_min[1][0]
44-
44+
4545
# save the current result if smaller than the current 2
4646
if curr_min[0][0] > dp[i][j]:
4747
curr_min[1] = curr_min[0]
4848
curr_min[0] = (dp[i][j], j)
4949
elif curr_min[1][0] > dp[i][j]:
5050
curr_min[1] = (dp[i][j], j)
51-
51+
5252
prev_min = curr_min
5353

5454
# return the min cost of the last house

‎Dynamic Programming/number_of_decodings.py‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -10,8 +10,8 @@
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.
13-
Time Complexity: O(N)
14-
Space Complexity: O(N)
13+
Time Complexity: O(N)
14+
Space Complexity: O(N)
1515
'''
1616

1717

@@ -22,24 +22,24 @@
2222
def num_decodings(code):
2323
n = len(code)
2424
dp = [0 for i in range(n)]
25-
25+
2626
if n == 0:
2727
return 0
2828
dp[0] = 1
2929
if n == 1:
3030
return dp[0]
3131
dp[1] = (code[1] != '0') + is_valid(code[0:2])
32-
32+
3333
for i in range(2, n):
3434
if code[i] != '0':
35-
# looking for how many combinations are there till now if this is a single digit
35+
# looking for how many combinations are there till now if this is a single digit
3636
dp[i] += dp[i-1]
3737
if is_valid(code[i-1 : i+1]):
38-
# looking for how many combinations are there till now if this is a number of 2 digits
38+
# looking for how many combinations are there till now if this is a number of 2 digits
3939
dp[i] += dp[i-2]
40-
40+
4141
return dp[n-1]
42-
42+
4343
def is_valid(code):
4444
k = int(code)
4545
return (k < 27) and (k > 9)

‎Dynamic Programming/sum_non-adjecent.py‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -14,8 +14,8 @@
1414
1515
=========================================
1616
Dynamic programming solution, but don't need the whole DP array, only the last 3 sums (DPs) are needed.
17-
Time Complexity: O(N)
18-
Space Complexity: O(1)
17+
Time Complexity: O(N)
18+
Space Complexity: O(1)
1919
'''
2020

2121

@@ -27,17 +27,17 @@ def sum_non_adjacent(arr):
2727
n = len(arr)
2828
# from the dp matrix you only need the last 3 sums
2929
sums = [0, 0, 0]
30-
30+
3131
# TODO: refactor these if-elses, those are to skip using of DP matrix
3232
if n == 0:
3333
return 0
3434

3535
# if negative or zero, the sum will be 0
3636
sums[0] = max(arr[0], 0)
37-
37+
3838
if n == 1:
3939
return sums[0]
40-
40+
4141
sums[1] = arr[1]
4242
# if the second number is negative or zero, then jump it
4343
if sums[1] <= 0:
@@ -56,17 +56,17 @@ def sum_non_adjacent(arr):
5656
# THE SOLUTION
5757
for i in range(3, n):
5858
temp = 0
59-
59+
6060
if arr[i] > 0:
6161
# take this number, because it's positive and the sum will be bigger
6262
temp = max(sums[0], sums[1]) + arr[i]
6363
else:
6464
# don't take this number, because the sum will be same or smaller
6565
temp = max(sums)
66-
66+
6767
# remove the first sum
6868
sums = sums[1:] + [temp]
69-
69+
7070
# return the max sum
7171
return max(sums)
7272

‎Dynamic Programming/transform_number_ascending_digits.py‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -11,8 +11,8 @@
1111
1212
=========================================
1313
Dynamic programming solution.
14-
Time Complexity: O(N) , O(N * 10 * 10) = O(100 N) = O(N)
15-
Space Complexity: O(1) , O(10 * 10) = O(100) = O(1)
14+
Time Complexity: O(N) , O(N * 10 * 10) = O(100 N) = O(N)
15+
Space Complexity: O(1) , O(10 * 10) = O(100) = O(1)
1616
'''
1717

1818

@@ -33,7 +33,7 @@ def operations(number):
3333
# find the min value for the previous digit and add it to the current value
3434
curr_dp[j] += min(prev_dp[0 : j + 1])
3535
prev_dp = curr_dp
36-
36+
3737
# min value from the last digit
3838
min_dist = min(prev_dp)
3939

0 commit comments

Comments
 (0)