Skip to content

Instantly share code, notes, and snippets.

@willgvfranco
Last active May 6, 2021 03:14
Show Gist options
  • Save willgvfranco/e57ab46dc66a956c6c7e2a3e7a15dffd to your computer and use it in GitHub Desktop.
Save willgvfranco/e57ab46dc66a956c6c7e2a3e7a15dffd to your computer and use it in GitHub Desktop.
algorithms
const containsCommonItem = (arr1, arr2) => arr1.some(item => arr2.includes(item))
var foo = [1, 2, 4]
var bar = [4, 4, 5]
console.log(containsCommonItem(foo, bar))
// Naive
function hasPairWithSum(arr, sum){
var len = arr.length;
for(var i =0; i<len-1; i++){
for(var j = i+1;j<len; j++){
if (arr[i] + arr[j] === sum)
return true;
}
}
return false;
}
// Better
function hasPairWithSum2(arr, sum){
const mySet = new Set();
const len = arr.length;
for (let i = 0; i < len; i++){
if (mySet.has(arr[i])) {
return true;
}
mySet.add(sum - arr[i]);
}
return false;
}
hasPairWithSum2([6,4,3,2,1,7], 9)
const foo = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]
let pequeno = foo.length > 27 ? true : false
// Insertion Sort = Poucos itens ou eu ja acho que ta em ordem
// Vai vendo 1 por 1 e inserindo onde devia estar baseado nos que ja viu
const insertionSort = array => {
const length = array.length;
for (let i = 0; i < length; i++) {
if (array[i] < array[0]) {
array.unshift(array.splice(i, 1)[0]);
} else {
for (let j = 1; j < i; j++) {
if (array[i] > array[j - 1] && array[i] < array[j]) {
array.splice(j, 0, array.splice(i, 1)[0]);
}
}
}
}
return array
}
const insertCall = foo => console.log('Insert Sort:', insertionSort(foo))
// QuickSort = muita coisa, sem problema de falta de memória
// Escolhe um pivot e vai jogando pra esquerda e direita dele e ai cada subarray faz a mesma coisa recursivamente
const quickSort = (originalList) => {
const list = [...originalList]
if (list.length < 2) {
return list
}
const pivot = list[Math.floor(list.length / 2)]
const smaller = list.filter((item) => item < pivot)
const bigger = list.filter((item) => item > pivot)
return [...quickSort(smaller), pivot, ...quickSort(bigger)]
}
const quickCall = foo => console.log('Quick Sort:', quickSort(foo))
// Mergesort = muita coisa, com problema de falta de memória
// Sai dividindo por 2 até ficar itens individuais, depois vai montando de 2 em 2
// os blocos ordenando. Meio que vai ordenando aos poucos, entao evita o pior caso em relacao ao quicksort
// mas gasta mais memória
const merge = (left, right) => {
const result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length &&
rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
}
const mergeSort = array => {
if (array.length === 1) {
return array
}
const length = array.length;
const middle = Math.floor(length / 2);
const left = array.slice(0, middle);
const right = array.slice(middle);
return merge(
mergeSort(left), mergeSort(right)
)
}
const mergeCall = foo => console.log('Merge Sort:', mergeSort(foo))
/* CONTROLE DE ESCOLHAS */
// let huge = true
let huge = false
// let PartialSorted = true
let partialSorted = false
let numeric = true
// let numeric = false
const QualUsar = partialSorted || pequeno ? insertCall(foo) : (numeric || huge ? quickCall(foo) : mergeCall(foo))
// console.log(QualUsar)
// arra1 = ['a', 'b', 'c']
// return = {
// a: true,
// b: true,
// c: true
// }
const ArrayToObjectTrue = (arr1) => {
let object = {}
for (let i=0; i< arr1.length; i++) {
if (!object[arr[i]]) {
const item = arr[i]
object[item] = true;
}
}
return object
}
const CheckArrayExistsOnObject = (arr2, ArrayToObjectTrue) => {
const object = ArrayToObjectTrue
for (let i=0; i < arr2.length; i++) {
if (object[arr2[i]]) {
return true
}
}
}
// fibonacci [0,1,1,2,3,5,8,13,21,34,55,89,144,233...]
const fibonacci = n => {
if (n < 2) {
return n
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
const fibonacciMemoized = (n) => {
let cache = {};
return function fibonacci(n) {
if (n in cache) {
return cache[n];
} else {
if (n < 2) {
return n;
} else {
cache[n] = fibonacci(n - 1) + fibonacci(n - 2);
return cache[n];
}
}
}()
}
const fibonacciMaster = n => {
let answer = [0, 1];
for (let i = 2; i <= n; i++) {
answer.push(answer[i - 2] + answer[i - 1])
}
return answer.pop()
}
console.log(fibonacciMemoized()(32))
const fibonacciMasterGod = n => {
// let answer = [0, 1];
if(n===1) {
return n;
}
let first = 1;
let second = 2;
for (let i = 3; i <= n; i++) {
// answer.push(answer[i - 2] + answer[i - 1])
const third = first+second;
first = second;
second=third;
}
return second
}
const memoizationAddTo80 = () => {
let cache = {}
return (n) => {
if (n in cache) {
return cache[n];
}
else [
cache[n] = n + 80;
return cache[n];
]
}
}
const memoized = memoizationAddTo80()
const ReverseString = str => [...str].reverse().join('')
const foo = "Testando uma String"
console.log(ReverseString(foo))
// gnirtS amu odnatseT
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment