Skip to content

Instantly share code, notes, and snippets.

View derekli66's full-sized avatar
🤓
Being.a.nerd()

Chien-Ming (Derek) Lee derekli66

🤓
Being.a.nerd()
28 followers · 74 following
View GitHub Profile
@derekli66
derekli66 / SortedArrayToBST.swift
Last active August 8, 2018 02:19
Transform a sorted array to a balanced BST. Cracking_Problem 4.2 on page 109
import Foundation
//-------------Basic BST Operation-------------------
class Node
{
var key: Int?
var left: Node?
var right: Node?
var description: String {
@derekli66
derekli66 / Knapsack_Problem.swift
Created May 7, 2019 06:12
This gist is the practice of knapsack problem. The solution without optimization by using memoization.
import Foundation
func knapsack(_ weights: Array<Int>,_ values: Array<Int>,_ index: Int,_ remainingWeight: Int) -> Int {
if (index < 0) { return 0 }
var choosedValue: Int = 0
if (remainingWeight >= weights[index]) {
// Choose
choosedValue = values[index] + knapsack(weights, values, index - 1, remainingWeight - weights[index])
@derekli66
derekli66 / Knapsack_Problem_Optimized.swift
Created May 7, 2019 07:25
This is another solution for knapsack problem. In this version, there is a 2-D array cache parameter with inout property in knapsack function. Use 2-D array to solve DP problem.
import Foundation
func knapsack(_ weights: Array<Int>,_ values: Array<Int>,_ index: Int,_ remainingWeight: Int,_ cache: inout Array<Array<Int>>) -> Int {
if (index < 0) { return 0 }
if (cache[index][remainingWeight] != -1) {
return cache[index][remainingWeight]
}
@derekli66
derekli66 / MaxHeap_Practice.swift
Created July 20, 2019 03:27
import UIKit
var arr = [Int?]()
arr.append(nil)
func parent(_ i: Int) -> Int {
return i/2
}
@derekli66
derekli66 / 322_Coin_Change.py
Last active June 5, 2021 15:31
Solution for 322 coin change problem.
import typing
from typing import List
import sys
class Solution:
def __init__(self) -> None:
self.amount_memorization = {}
def coinChange(self, coins: List[int], amount: int) -> int:
@derekli66
derekli66 / 1046_Last_Stone_Weight.swift
Created April 10, 2022 13:45
The solution to the LeetCode problem, 1046. Last Stone Weight, https://leetcode.com/problems/last-stone-weight/
class MaxHeap {
private var array = Array<Int>()
func leftChild(_ i:Int) -> Int {
return 2*i+1
}
func rightChild(_ i:Int) -> Int {
return 2*i+2
@derekli66
derekli66 / 67_Add_Binary.swift
Created May 9, 2022 07:04
LeetCode problem 67. Given two binary strings a and b, return their sum as a binary string.
class Solution {
func addBinary(_ a: String, _ b: String) -> String {
var result = ""
let aStrArr = Array(String(a.reversed())).map{ String($0) }
let bStrArr = Array(String(b.reversed())).map{ String($0) }
var index = 0
var advanced = 0
while index < aStrArr.count && index < bStrArr.count {
@derekli66
derekli66 / Queue.swift
Created May 12, 2022 16:44
Queue Implementation
private class ListNode {
var next: ListNode?
var prev: ListNode?
var key: Int = 0
}
/*
push to back, peek/pop from front, size and is empty
*/
class Queue {
private var head: ListNode?
@derekli66
derekli66 / Stack.swift
Created May 12, 2022 16:45
Stack Implementation
private class ListNode {
var next: ListNode?
var prev: ListNode?
var key: Int = 0
}
class Stack {
private var head: ListNode?
private var tail: ListNode?
private var count: Int = 0
@derekli66
derekli66 / stack_using_queues.swift
Created May 13, 2022 21:02
Solution to LeetCode problem, 225 Implement Stack using Queues. https://leetcode.com/problems/implement-stack-using-queues/
class ListNode {
var next: ListNode?
var key: Int = 0
}
/*
push to back, peek/pop from front, size and is empty
*/
class LinkedList {
private var head: ListNode?
private var tail: ListNode?