From 7cf9e8b5feb9459ba7cbebc9201d597cf31f6e03 Mon Sep 17 00:00:00 2001 From: diego Date: Mon, 18 Oct 2021 12:34:25 -0400 Subject: [PATCH 1/4] some algorithms --- .../50algorithms/boats_to_save_people.py | 31 ++++++++++++++++ algorithms/50algorithms/longest_substring.py | 24 ++++++++++++ algorithms/50algorithms/max_water_contain.py | 22 +++++++++++ algorithms/50algorithms/mountain_array.py | 37 +++++++++++++++++++ 4 files changed, 114 insertions(+) create mode 100644 algorithms/50algorithms/boats_to_save_people.py create mode 100644 algorithms/50algorithms/longest_substring.py create mode 100644 algorithms/50algorithms/max_water_contain.py create mode 100644 algorithms/50algorithms/mountain_array.py diff --git a/algorithms/50algorithms/boats_to_save_people.py b/algorithms/50algorithms/boats_to_save_people.py new file mode 100644 index 0000000..df4d47b --- /dev/null +++ b/algorithms/50algorithms/boats_to_save_people.py @@ -0,0 +1,31 @@ +"""Boats to save people.""" +from typing import List + + +def num_of_boats(people: List[int], limit: int) -> int: + """Find number of boats needed.""" + left = 0 + right = len(people) - 1 + boats_number = 0 + + # sort people from heviest to lightest + people.sort() + + while(left <= right): + if(left == right): + boats_number += 1 + break + + # move left pointer, next lightest + if(people[left]+people[right] <= limit): + left += 1 + + # move right pointer, next heviest + right -= 1 + boats_number += 1 + + return boats_number + + +res = num_of_boats([2, 1, 3, 4], 4) +print(f"number of boats: {res}") diff --git a/algorithms/50algorithms/longest_substring.py b/algorithms/50algorithms/longest_substring.py new file mode 100644 index 0000000..255f838 --- /dev/null +++ b/algorithms/50algorithms/longest_substring.py @@ -0,0 +1,24 @@ +"""What is the longest substring.""" + + +def longest_string(string: str) -> int: + """Find size of longest substring.""" + map: dict = dict() + left = 0 + right = 0 + ans = 0 + size = len(string) + + while(left < size and right < size): + el = string[right] + if(el in map): + left = max(left, map[el] + 1) + map[el] = right + ans = max(ans, right - left + 1) + right += 1 + + return ans + + +ans = longest_string("fivestarreview") +print(f"longest string: {ans}") diff --git a/algorithms/50algorithms/max_water_contain.py b/algorithms/50algorithms/max_water_contain.py new file mode 100644 index 0000000..7ed276f --- /dev/null +++ b/algorithms/50algorithms/max_water_contain.py @@ -0,0 +1,22 @@ +"""Max water that can be contained.""" + + +def max_water_contain(heights: list[int]) -> int: + """Find max water that can be contained.""" + maxarea = 0 + left = 0 + right = len(heights) - 1 + + while(left < right): + newMaxarea = min(heights[left], heights[right])*(right-left) + maxarea = max(maxarea, newMaxarea) + if(heights[left] < heights[right]): + left += 1 + else: + right -= 1 + + return maxarea + + +res = max_water_contain([2, 1, 1, 2]) +print(f"maxArea: {res}") diff --git a/algorithms/50algorithms/mountain_array.py b/algorithms/50algorithms/mountain_array.py new file mode 100644 index 0000000..9e1f9a0 --- /dev/null +++ b/algorithms/50algorithms/mountain_array.py @@ -0,0 +1,37 @@ +"""check if array is a mountain array.""" + + +def mountain_array(array: list[int]) -> bool: + """ + Check if is array is a mountain array. + + It incresses then decresses. + """ + if(len(array) < 3): + return False + + i = 1 + # array is incressing + while(i < len(array) and array[i] > array[i-1]): + i += 1 + + if(i == 1): + return False + + if(i == 1 or i == len(array)): + return False + + # array is decressing + while(i < len(array) and array[i] < array[i-1]): + i += 1 + + return i == len(array) + + +res = mountain_array([1, 1, 2, 3, 1]) + +print(f"mountain array: {res}") + +res = mountain_array([0, 1, 2, 3, 1]) + +print(f"mountain array: {res}") From 527f1975f6da8c5f75f2e3d2d7464a9b7f91e93f Mon Sep 17 00:00:00 2001 From: diego Date: Mon, 18 Oct 2021 14:57:10 -0400 Subject: [PATCH 2/4] more problems --- .../50algorithms/find_first_and_last.py | 56 +++++++++++++++++++ .../50algorithms/find_first_bad_version.py | 26 +++++++++ 2 files changed, 82 insertions(+) create mode 100644 algorithms/50algorithms/find_first_and_last.py create mode 100644 algorithms/50algorithms/find_first_bad_version.py diff --git a/algorithms/50algorithms/find_first_and_last.py b/algorithms/50algorithms/find_first_and_last.py new file mode 100644 index 0000000..1a6d9e1 --- /dev/null +++ b/algorithms/50algorithms/find_first_and_last.py @@ -0,0 +1,56 @@ +"""Find first and last position of elemente in sorted array.""" + +# import ipdb + + +def find_first_and_last(nums: list[int], target: int) -> list[int]: + """Find first and last index of target.""" + left = get_left_position(nums, target) + right = get_right_position(nums, target) + + return [left, right] + + +def get_left_position(nums: list[int], target: int) -> int: + """Get left position of target.""" + left = 0 + right = len(nums) - 1 + + while(left <= right): + mid = (left+right)//2 + if(nums[mid] == target): + if(mid-1 >= 0 and nums[mid-1] != target or mid == 0): + return mid + right = mid - 1 + elif(nums[mid] > target): + right = mid - 1 + else: + left = mid + 1 + + return -1 + + +def get_right_position(nums: list[int], target: int) -> int: + """Get right position of target.""" + left = 0 + right = len(nums) - 1 + + while(left <= right): + mid = (left+right)//2 + if(nums[mid] == target): + if(mid + 1 < len(nums) + and nums[mid+1] != target + or mid == len(nums)-1): + return mid + left = mid+1 + elif(nums[mid] > target): + right = mid - 1 + else: + left = mid + 1 + + return -1 + + +# ipdb.set_trace() +res = find_first_and_last([1, 2, 2, 3, 4, 4, 4, 4], 4) +print(f"first and last: {res}") diff --git a/algorithms/50algorithms/find_first_bad_version.py b/algorithms/50algorithms/find_first_bad_version.py new file mode 100644 index 0000000..2607003 --- /dev/null +++ b/algorithms/50algorithms/find_first_bad_version.py @@ -0,0 +1,26 @@ +"""Find first bad version.""" + + +def is_bad_version(version): + """Return if badVersion.""" + badVersion = 3 + return version >= badVersion + + +def find_first_bad_version(n: int) -> int: + """Find first bad version.""" + left = 1 + right = n + + while(left < right): + mid = (right + left)//2 + if(not is_bad_version(mid)): + left = mid + 1 + else: + right = mid + + return left + + +answer = find_first_bad_version(10) +print(f"answer: {answer}") From 021b6201621e266890f45b5b0fd0848fa769a4cc Mon Sep 17 00:00:00 2001 From: diego Date: Mon, 18 Oct 2021 18:05:29 -0400 Subject: [PATCH 3/4] math --- algorithms/50algorithms/math/binary_math.py | 26 +++++++++++++++++++ algorithms/50algorithms/math/find_primes.py | 22 ++++++++++++++++ .../math/find_the_single_number.py | 12 +++++++++ .../50algorithms/math/missing_number.py | 13 ++++++++++ 4 files changed, 73 insertions(+) create mode 100644 algorithms/50algorithms/math/binary_math.py create mode 100644 algorithms/50algorithms/math/find_primes.py create mode 100644 algorithms/50algorithms/math/find_the_single_number.py create mode 100644 algorithms/50algorithms/math/missing_number.py diff --git a/algorithms/50algorithms/math/binary_math.py b/algorithms/50algorithms/math/binary_math.py new file mode 100644 index 0000000..29871a6 --- /dev/null +++ b/algorithms/50algorithms/math/binary_math.py @@ -0,0 +1,26 @@ +"""Add binarry numbers.""" + + +def add_binary_numbers(a: str, b: str) -> str: + """Add binary numbers.""" + result = [] + carry = 0 + i, j = len(a)-1, len(b)-1 + while i >= 0 or j >= 0 or carry: + total = carry + + if i >= 0: + total += int(a[i]) + i -= 1 + if j >= 0: + total += int(a[j]) + j -= 1 + + result.append(str(total % 2)) + carry = total // 2 + + return ''.join(reversed(result)) + + +res = add_binary_numbers("110", "010") +print(f"binarry: {res}") diff --git a/algorithms/50algorithms/math/find_primes.py b/algorithms/50algorithms/math/find_primes.py new file mode 100644 index 0000000..6b2c8c8 --- /dev/null +++ b/algorithms/50algorithms/math/find_primes.py @@ -0,0 +1,22 @@ +"""Find the primes.""" +import math + + +def find_primes(num: int): + """Find the primes.""" + if(num < 2): + return 0 + isPrime = [True] * num + isPrime[0] = False + isPrime[1] = False + + for i in range(2, int(math.ceil(math.sqrt(num)))): + if(isPrime[i]): + for mult_of_i in range(i*i, num, i): + isPrime[mult_of_i] = False + + return sum(isPrime) + + +answer = find_primes(12) +print(f"answer: {answer}") diff --git a/algorithms/50algorithms/math/find_the_single_number.py b/algorithms/50algorithms/math/find_the_single_number.py new file mode 100644 index 0000000..f392eed --- /dev/null +++ b/algorithms/50algorithms/math/find_the_single_number.py @@ -0,0 +1,12 @@ +"""Find the number that was not repeated.""" + + +def find_number(nums: list[int]) -> int: + """Find the number that was not repeated.""" + numberSet = set(nums) + res = 2*sum(numberSet) - sum(nums) + return res + + +res = find_number([2, 2, 1]) +print(f"missing number: {res}") diff --git a/algorithms/50algorithms/math/missing_number.py b/algorithms/50algorithms/math/missing_number.py new file mode 100644 index 0000000..7b6012b --- /dev/null +++ b/algorithms/50algorithms/math/missing_number.py @@ -0,0 +1,13 @@ +"""Find the missing number.""" + + +def missing_number(nums: list[int]) -> int: + """Find missing number.""" + currentSum: int = sum(nums) + n = len(nums) + intendedSum = n*(n+1)/2 + return int(intendedSum - currentSum) + + +answer = missing_number([0, 3, 1, 2, 5]) +print(f"answer: {answer}") From 8c2333a4ecff46c77404694be84d83f3b3a9d5f9 Mon Sep 17 00:00:00 2001 From: diego Date: Tue, 19 Oct 2021 18:34:55 -0400 Subject: [PATCH 4/4] cool algorithms --- .../{ => arrays_strings}/big_o.py | 0 .../{ => arrays_strings}/binarry_search.py | 0 .../boats_to_save_people.py | 0 .../find_first_and_last.py | 0 .../find_first_bad_version.py | 0 .../{ => arrays_strings}/longest_substring.py | 0 .../{ => arrays_strings}/max_water_contain.py | 0 .../{ => arrays_strings}/mountain_array.py | 0 .../{ => arrays_strings}/move_zeros.py | 0 .../{ => arrays_strings}/sliding_window.py | 0 .../50algorithms/backtracking/subsets.py | 39 +++++++++++++++++++ 11 files changed, 39 insertions(+) rename algorithms/50algorithms/{ => arrays_strings}/big_o.py (100%) rename algorithms/50algorithms/{ => arrays_strings}/binarry_search.py (100%) rename algorithms/50algorithms/{ => arrays_strings}/boats_to_save_people.py (100%) rename algorithms/50algorithms/{ => arrays_strings}/find_first_and_last.py (100%) rename algorithms/50algorithms/{ => arrays_strings}/find_first_bad_version.py (100%) rename algorithms/50algorithms/{ => arrays_strings}/longest_substring.py (100%) rename algorithms/50algorithms/{ => arrays_strings}/max_water_contain.py (100%) rename algorithms/50algorithms/{ => arrays_strings}/mountain_array.py (100%) rename algorithms/50algorithms/{ => arrays_strings}/move_zeros.py (100%) rename algorithms/50algorithms/{ => arrays_strings}/sliding_window.py (100%) create mode 100644 algorithms/50algorithms/backtracking/subsets.py diff --git a/algorithms/50algorithms/big_o.py b/algorithms/50algorithms/arrays_strings/big_o.py similarity index 100% rename from algorithms/50algorithms/big_o.py rename to algorithms/50algorithms/arrays_strings/big_o.py diff --git a/algorithms/50algorithms/binarry_search.py b/algorithms/50algorithms/arrays_strings/binarry_search.py similarity index 100% rename from algorithms/50algorithms/binarry_search.py rename to algorithms/50algorithms/arrays_strings/binarry_search.py diff --git a/algorithms/50algorithms/boats_to_save_people.py b/algorithms/50algorithms/arrays_strings/boats_to_save_people.py similarity index 100% rename from algorithms/50algorithms/boats_to_save_people.py rename to algorithms/50algorithms/arrays_strings/boats_to_save_people.py diff --git a/algorithms/50algorithms/find_first_and_last.py b/algorithms/50algorithms/arrays_strings/find_first_and_last.py similarity index 100% rename from algorithms/50algorithms/find_first_and_last.py rename to algorithms/50algorithms/arrays_strings/find_first_and_last.py diff --git a/algorithms/50algorithms/find_first_bad_version.py b/algorithms/50algorithms/arrays_strings/find_first_bad_version.py similarity index 100% rename from algorithms/50algorithms/find_first_bad_version.py rename to algorithms/50algorithms/arrays_strings/find_first_bad_version.py diff --git a/algorithms/50algorithms/longest_substring.py b/algorithms/50algorithms/arrays_strings/longest_substring.py similarity index 100% rename from algorithms/50algorithms/longest_substring.py rename to algorithms/50algorithms/arrays_strings/longest_substring.py diff --git a/algorithms/50algorithms/max_water_contain.py b/algorithms/50algorithms/arrays_strings/max_water_contain.py similarity index 100% rename from algorithms/50algorithms/max_water_contain.py rename to algorithms/50algorithms/arrays_strings/max_water_contain.py diff --git a/algorithms/50algorithms/mountain_array.py b/algorithms/50algorithms/arrays_strings/mountain_array.py similarity index 100% rename from algorithms/50algorithms/mountain_array.py rename to algorithms/50algorithms/arrays_strings/mountain_array.py diff --git a/algorithms/50algorithms/move_zeros.py b/algorithms/50algorithms/arrays_strings/move_zeros.py similarity index 100% rename from algorithms/50algorithms/move_zeros.py rename to algorithms/50algorithms/arrays_strings/move_zeros.py diff --git a/algorithms/50algorithms/sliding_window.py b/algorithms/50algorithms/arrays_strings/sliding_window.py similarity index 100% rename from algorithms/50algorithms/sliding_window.py rename to algorithms/50algorithms/arrays_strings/sliding_window.py diff --git a/algorithms/50algorithms/backtracking/subsets.py b/algorithms/50algorithms/backtracking/subsets.py new file mode 100644 index 0000000..a885d0c --- /dev/null +++ b/algorithms/50algorithms/backtracking/subsets.py @@ -0,0 +1,39 @@ +"""Get subsets.""" + + +def subsets(nums: list[int]) -> list[list[int]]: + """Return subsets of list.""" + ans: list[list[int]] = [] + + # current options already taken + cur: list[int] = [] + + recursive_subsets(nums, ans, cur, 0) + + return ans + + +def recursive_subsets(nums: list[int], ans: list[list[int]], + cur: list[int], index) -> None: + """Recursivly find subsets.""" + + # we went through all numbers + if(index > len(nums)): + return + + ans.append(cur[:]) + for i in range(index, len(nums)): + # is num is not currently in selected list + if(nums[i] not in cur): + cur.append(nums[i]) + recursive_subsets(nums, ans, cur, i) + cur.pop() + + +res = subsets([1, 2]) + +print(f"subsets: {res}") + +res = subsets([1, 2, 3]) + +print(f"subsets: {res}")