Last active
November 23, 2020 18:57
-
-
Save marclerodrigues/b6be572808315e00eca44f79b4ffb92e to your computer and use it in GitHub Desktop.
Leet Code Problems
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/split-a-string-in-balanced-strings/ | |
# @param {String} s | |
# @return {Integer} | |
def balanced_string_split(s) | |
balance = 0 | |
total_count = 0 | |
s.split("").each do |value| | |
if value == "R" | |
balance += 1 | |
end | |
if value == "L" | |
balance -= 1 | |
end | |
if balance == 0 | |
total_count += 1 | |
end | |
end | |
total_count | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# @param {Integer[]} nums | |
# @return {Integer[]} | |
def decompress_rl_elist(nums) | |
a = [] | |
nums.each_slice(2) do |pair| | |
freq, value = pair | |
freq.times { a.push(value) } | |
end | |
a | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/decompress-run-length-encoded-list/ | |
# @param {Integer[]} nums | |
# @return {Integer[]} | |
class Array | |
alias_method :chupa, :push | |
end | |
def decompress_rl_elist(nums) | |
neto = [] | |
nums.each_slice(2) do |pair| | |
freq, pinto = pair | |
freq.times { neto.chupa(pinto) } | |
end | |
neto | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/subtract-the-product-and-sum-of-digits-of-an-integer/ | |
# @param {Integer} n | |
# @return {Integer} | |
def subtract_product_and_sum(n) | |
digits = n.to_s.split("") | |
product = 1 | |
sum = 0 | |
digits.map do |digit| | |
product *= digit.to_i | |
sum += digit.to_i | |
end | |
product - sum | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/jewels-and-stones/ | |
# @param {String} j | |
# @param {String} s | |
# @return {Integer} | |
def num_jewels_in_stones(j, s) | |
jewels = j.split("") | |
total = 0 | |
s.split("").each do |stone| | |
total += 1 if jewels.include?(stone) | |
end | |
total | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/ | |
# @param {Integer[]} candies | |
# @param {Integer} extra_candies | |
# @return {Boolean[]} | |
def kids_with_candies(candies, extra) | |
max_candies = candies.max | |
candies.map do |candy| | |
candy + extra >= max_candies | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/maximum-69-number/ | |
# @param {Integer} num | |
# @return {Integer} | |
def maximum69_number (num) | |
found_digit = false | |
num.digits.reverse.map do |d| | |
if !found_digit && d == 6 | |
found_digit = true | |
9 | |
else | |
d | |
end | |
end.join.to_i | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/ | |
# @param {Integer[]} nums | |
# @return {Integer} | |
def max_product(nums) | |
a, b = nums.sort.last(2) | |
(a - 1) * (b - 1) | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/ | |
def number_of_steps(num) | |
counter = 0 | |
while num != 0 | |
num = num.even? ? num / 2 : num - 1 | |
counter += 1 | |
end | |
counter | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/ | |
def number_of_steps(num) | |
steps = 0 | |
while num != 0 | |
num.even? ? num /= 2 : num -= 1 | |
steps += 1 | |
end | |
puts steps | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/ | |
def number_of_steps(num) | |
steps = 0 | |
while num != 0 | |
if num.even? | |
num = num/2 | |
steps +=1 | |
end | |
if num.odd? | |
num -= 1 | |
steps +=1 | |
end | |
end | |
steps | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/ | |
# @param {Integer} num | |
# @return {Integer} | |
def number_of_steps(num) | |
next_step(num, 0) | |
end | |
def next_step(value, step_count) | |
return step_count if value.zero? | |
if value.odd? | |
next_step(value - 1, step_count + 1) | |
else | |
next_step(value / 2, step_count + 1) | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/running-sum-of-1d-array/ | |
# @param {Integer[]} nums | |
# @return {Integer[]} | |
def running_sum(nums) | |
result = [] | |
nums.each do |el| | |
previous_value = result.last || 0 | |
result.push(previous_value + el) | |
end | |
result | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/self-dividing-numbers/ | |
# @param {Integer} left | |
# @param {Integer} right | |
# @return {Integer[]} | |
def self_dividing_numbers(left, right) | |
array = [] | |
(left..right).each do |value| | |
array.push(value) if value.digits.all? do |n| | |
n.zero? ? false : (value % n) == 0 | |
end | |
end | |
array | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/ | |
# @param {Integer[]} nums | |
# @return {Integer[]} | |
def smaller_numbers_than_current(nums) | |
sorted_array = nums.sort | |
nums.map do |number| | |
sorted_array.index(number) | |
end | |
end | |
# Big O = O(n * log n) + O(n) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/shuffle-the-array/ | |
# @param {Integer[]} nums | |
# @param {Integer} n | |
# @return {Integer[]} | |
def shuffle(nums, n) | |
(0..n). do |index| | |
first_half = nums[0...n] | |
second_half = nums[n..-1] | |
result = [] | |
(0...n).each do |index| | |
result.push(first_half[index], second_half[index]) | |
end | |
result | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/shuffle-the-array/ | |
# @param {Integer[]} nums | |
# @param {Integer} n | |
# @return {Integer[]} | |
def shuffle(nums, n) | |
(0...n).flat_map do |index| | |
[nums[index], nums[index + n]] | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/create-target-array-in-the-given-order/ | |
# @param {Integer[]} nums | |
# @param {Integer[]} index | |
# @return {Integer[]} | |
def create_target_array(nums, index) | |
a = [] | |
index.each_with_index do |i, ii| | |
value = nums[ii] | |
a.insert(i, value) | |
end | |
a | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/two-sum/ | |
# @param {Integer[]} nums | |
# @param {Integer} target | |
# @return {Integer[]} | |
def two_sum(nums, target) | |
hash = {} | |
nums.each_with_index do |n, i| | |
t = target - n | |
if hash[t] | |
return [i, hash[t]] | |
else | |
hash[n] = i | |
end | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/two-sum/ | |
# @param {Integer[]} nums | |
# @param {Integer} target | |
# @return {Integer[]} | |
# Marcle' Implementation 4s of execution time | |
def two_sum(nums, target) | |
(0...nums.length).each do |i| | |
(i+1...nums.length).each do |j| | |
return [i, j] if nums[i] + nums[j] == target | |
end | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/two-sum/ | |
# @param {Integer[]} nums | |
# @param {Integer} target | |
# @return {Integer[]} | |
# Renata's & Luca's Implementation 4s of execution time | |
def two_sum(nums, target) | |
nums.each_with_index do |value, i| | |
(i+1...nums.length).each do |j| | |
if value + nums[j] == target | |
return [i,j] | |
end | |
end | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/xor-operation-in-an-array/ | |
# @param {Integer} n | |
# @param {Integer} start | |
# @return {Integer} | |
def xor_operation(n, start) | |
acc = 0 | |
n.times { |i| acc ^= (start + 2 * i)} | |
acc | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Problem: https://leetcode.com/problems/xor-operation-in-an-array/ | |
# @param {Integer} n | |
# @param {Integer} start | |
# @return {Integer} | |
def xor_operation(n, start) | |
array = [] | |
n.times { |i| array.push(start + 2 * i)} | |
acc = 0 | |
array.each do |value| | |
acc ^= value | |
end | |
acc | |
end |
# @param {Integer} x
# @return {Integer}
def reverse(x)
result = x.abs.to_s.reverse
if x.negative?
result = result.to_i * (-1)
else
result = result.to_i
end
return 0 if result >= 2147483647 || result <= -2147483647
result
end
# @param {Integer} x
# @return {Boolean}
def is_palindrome(x)
x.to_s == x.to_s.reverse
end
clock angle
RENATA
simple version
def clock_angle(hour, minute)
angle_hour = 0
angle_minute = 0
hour = 0 if hour == 12
hour.times do
angle_hour -= 30
end
minute.times do
angle_minute += 6
end
(angle_hour + angle_minute).abs
end
final version
def clock_angle(hour, minute)
default_angle_hour = 0
default_angle_minute = 0
angle_hour = 30.0
angle_minute = 6.0
total_minutes = 60
hour = 0 if hour == 12
angle_variance = (minute * angle_hour)/total_minutes
default_angle_hour = -angle_hour * hour
default_angle_minute = angle_minute * minute
(default_angle_hour + default_angle_minute - angle_variance).abs
end
LUCAS
def generate_degrees(hour, minutes)
hour = 0.0 if hour == 12.0
minutes = 0.0 if minutes == 60.0
runned_degrees = (minutes * 30.0) / 60.0
((hour * 30.0) + runned_degrees) - (minutes * 6.0).abs
end
MARCLE
def hours_to_degrees(hour, minutes)
((((hour == 12 ? 0 : hour) * 30.0) + (minutes * 30 / 60.0)) - (minutes * 6.0)).abs
end
class AngleBetweenPointers
DEGREES_PER_MINUTE = 6
DEGREES_PER_HOUR = 30
MINUTES_PER_HOUR = 60.0
NOON = 12
def self.call(hours, minutes)
new(hours, minutes).call
end
def initialize(hours, minutes)
@hours = hours
@minutes = minutes
end
def call
(hours_degrees + variation - minutes_degrees).abs
end
private
def minutes_degrees
minutes * DEGREES_PER_MINUTE
end
def hours_degrees
hours * DEGREES_PER_HOUR
end
def hours
noon? ? 0 : @hours
end
def noon?
@hours == NOON
end
def variation
@minutes * DEGREES_PER_HOUR / MINUTES_PER_HOUR
end
end
run-length encoding
encode:
# input
encode("WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB")
# output
=> "12WB12W3B24WB"
decode:
# input
decode("12WB12W3B24WB")
# output
=> "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB"
Renata
def encode(string)
count = 1
result = []
splitted_string = string.chars
splitted_string.each_with_index do |s, index|
if s == splitted_string[index+1]
count += 1
elsif count > 1
result.append(count,s)
count = 1
else
result.append(s)
end
end
result.join
end
def decode(string)
string.scan(/(\d*)([a-z])/i).map do |size,char|
size = size.to_i
size = 1 if size == 0
char * size
end.join
end
Samuel
def encode(input)
input
.chars
.chunk_while {|a,b| a == b}
.map {|n| "#{n.length if n.length > 1}#{n.first}" }
.join
end
REGEX = /(\d*)(\D)/
def decode(input)
input
.scan(REGEX)
.map do |size, char|
size = size == '' ? 1 : Integer(size)
char * size
end
.join
end
Eduardo
REGEX = /(\d*)(\D)/
def decode(string)
string.scan(REGEX).map { |i| i.first.empty? ? i.second : i.second * i.first.to_i }.join
end
Armstrong
Neto
function convertNumberToArray(num) {
let number = num
const result = []
while(number > 0) {
result.push(number % 10)
number = Math.floor(number/10)
}
return result
}
function ArmstrongNumber(num) {
const arr = convertNumberToArray(num)
const result = arr.reduce((sum, item ) => sum += item**arr.length, 0)
return result === num
}
Renan
def armstrong?(number)
digits = number.digits
size = digits.count
armstrong = digits.inject(0) { |sum, n| sum + n ** size }
armstrong == number
end
Lucas
# frozen_string_literal: true
class Armstrong
def armstrong?(number)
digits = divide(number, [])
sum(digits, digits.length) == number
end
private
def divide(number, array)
return array if number <= 0
array.append(number % 10)
number /= 10
divide(number, array)
end
def sum(digits, exp)
digits.map { |d| d**exp }
.sum
end
end
Renata
def armstrong?(number)
numbers = number.digits
sum = []
length = numbers.count
numbers.each do |n|
sum.append(n**length)
end
number == sum.sum
end
Samuel
def armstrong?(number)
digits = number.digits
exponent = digits.count
total = digits.reduce(0) do |total, digit|
digit**exponent
end
number == total
end
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
two_sum.rb
3080ms