Skip to content

Instantly share code, notes, and snippets.

@shelling
Last active December 11, 2016 13:08
Show Gist options
  • Save shelling/60f737c936dfe56ddf6f to your computer and use it in GitHub Desktop.
Save shelling/60f737c936dfe56ddf6f to your computer and use it in GitHub Desktop.
def anagram?(s1, s2)
hash = Hash.new(0)
s1.each_char do |c|
hash[c] += 1
end
s2.each_char do |c|
hash[c] -= 1
end
hash.values.uniq == [0]
end
puts anagram?("hello", "llohe")
puts anagram?("foo", "bar")
#!/usr/bin/env ruby
$:.unshift(".")
require "node"
class Node
def min_depth
1 + [ left ? left.min_depth : 0, right ? left.min_depth : 0].min
end
def max_depth
1 + [left ? left.max_depth : 0, right ? right.max_depth : 0].max
end
def balance?
(max_depth - min_depth) <= 1
end
end
data = [1,
[2, [4], [5]],
[3, [6], [7]]]
tree = Node.from_array(data)
puts tree.inspect
def min(tree)
return 0 unless tree
1 + [min(tree.left), min(tree.right)].min
end
def max(tree)
return 0 unless tree
1 + [max(tree.left), max(tree.right)].max
end
puts tree.min_depth
puts min(tree)
puts tree.max_depth
puts max(tree)
puts tree.balance?
class NilClass
def value
" "
end
def left
end
def right
end
end
class Node
attr_accessor :value, :left, :right
def min_depth
1 + [ left ? left.min_depth : 0, right ? right.min_depth : 0 ].min
end
def max_depth
1 + [ left ? left.max_depth : 0, right ? right.max_depth : 0 ].max
end
def balance?
max_depth - min_depth <= 1
end
def inspect
current = [self]
nextlevel = []
maxd = max_depth
depth = 0
while !current.reject(&:!).empty?
gap = 2 ** (maxd - depth) - 1
prepend = gap / 2
puts " " * prepend + current.map(&:value).join(" " * gap)
for v in current
nextlevel.push(v.left ? v.left : nil)
nextlevel.push(v.right ? v.right : nil)
end
current = nextlevel
nextlevel = []
depth += 1
end
end
end
def binarytree(array)
return nil if array.length == 0
m = array.length / 2
tree = Node.new
tree.value = array[m]
tree.left = binarytree(array[0...m])
tree.right = binarytree(array[m+1...array.length])
tree
end
array = [1,2,3,4,5,6,7,8,9]
puts binarytree(array).balance?
puts binarytree(array).inspect
def search(array)
l, h = 0, array.length - 1
while l < h-1
m = (l + h) / 2
if array[l] > array[m]
h = m
else
l = m
end
end
[array[l], array[h]]
end
puts search([4,5,6,7,8,1,2,3]).inspect
def search(array, string)
l, h = 0, array.length - 1
while l <= h
m = (l + h) / 2
while array[m] == ""
m += 1
end
if array[m] > string
h = m
elsif array[m] < string
l = m
else
return m
end
end
end
puts search(["at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""], "ball")
#!/usr/bin/env ruby
def search(array, x, l = 0, h = array.length - 1)
while l <= h
m = (l + h) / 2
if x == array[m]
return m
elsif x < array[m]
h = m - 1
else
l = m + 1
end
end
end
a = ["hello", "world", "shelling", "ford", "here"].sort
puts a.inspect
for str in a
puts search(a, str)
end
def dfs(current, tokens, target, result)
sum = current.reduce(0, :+)
if sum == target
result.push(current)
elsif sum < target
rest = tokens.dup
token, count = rest.shift, 0
while token && (sum + token * count) <= target
dfs(current + Array.new(count, token), rest, target, result)
count += 1
end
end
end
def combination_sum(candidates, target)
result = []
dfs([], candidates, target, result)
result
end
puts combination_sum([2,3,6,7], 7).inspect
#!/usr/bin/env ruby
#
# map a-z to 1-26
# given a string containing only digits
# count all combinatorics to present digits in a-z
def count(string)
return 1 if string.length < 2
if string[0] == "1"
if string[1] == "0"
count(string[2..-1])
elsif ["1","2"].include?(string[1])
2 * count(string[2..-1]) + count(string[1..-1])
else
2 * count(string[2..-1])
end
elsif string[0] == "2"
if string[1] == "0"
count(string[2..-1])
elsif ["1","2"].include?(string[1])
2 * count(string[2..-1]) + count(string[1..-1])
elsif ["3","4","5","6"].include?(string[1])
2 * count(string[2..-1])
else
count(string[2..-1])
end
else
count(string[1..-1])
end
end
puts count("1313")
puts count("101")
puts count("313")
puts count("20")
puts count("2627")
# 1313
# 13-13
# 1-3-13
# 13-1-3
# 1-3-1-3
def countdup(string)
array = Array.new(26)
count = 0
string.downcase.each_byte.map(&:ord).map { |c| c - 97 }.each do |i|
count += 1 if array[i]
array[i] = true
end
count
end
def countdup(string)
count = 0
string.downcase.each_char.with_index do |c, index|
for i in 0...index
if string[i] == c
count += 1
break
end
end
end
count
end
puts countdup("shelling")
puts countdup("ababab")
puts countdup("aaabbb")
def dfs(ans, current, l, r)
ans.push(current) if l == 0 && r == 0
dfs(ans, current + "(", l - 1, r) if l > 0
dfs(ans, current + ")", l, r - 1) if r > l
end
result = []
dfs(result, "", 3, 3)
puts result.inspect
#!/usr/bin/env ruby
$:.unshift(".")
require "node"
class Graph
attr_accessor :list, :marked
def initialize(edges)
@list = {}
for v, w in edges
list[v] ||= []
list[w] ||= []
list[v].push(w)
list[w].push(v)
end
end
def dfs(from, &block)
marked = {}
stack = []
stack.push(from)
while !stack.empty?
v = stack.pop
if !marked[v]
block.call(v) if block
marked[v] = true
for adj in list[v].reverse
stack.push(adj)
end
end
end
end
def dfsr(from, visited = {}, &block)
visited[from] = true
block.call(from) if block
for adj in list[from]
if !visited[adj]
visited[adj] = true
dfsr(adj, visited, &block)
end
end
end
def bfs(from, &block)
marked = {}
queue = []
queue.push(from)
while !queue.empty?
v = queue.shift
if !marked[v]
block.call(v) if block
marked[v] = true
for adj in list[v]
queue.push(adj)
end
end
end
end
def bfsr(from, visited = {}, &block)
queue = []
for node in from
visited[node] = true
block.call(node) if block
for adj in list[node]
if !visited[adj]
queue.push(adj)
end
end
end
bfsr(queue, visited, &block) unless queue.empty?
end
end
data = [1,
[2, [4], [5]],
[3, [6], [7, [8], [9]]]]
g = Graph.new(Node.from_array(data).edges)
puts g.list
g.dfs(1) do |v|
print "#{v} "
end
puts
g.dfsr(1) do |v|
print "#{v} "
end
puts
g.bfs(1) do |v|
print "#{v} "
end
puts
g.bfsr([1]) do |v|
print "#{v} "
end
puts
#!/usr/bin/env ruby
class MaxHeap
attr_accessor :heap
def initialize(heap = [nil])
@heap = heap
end
def size
heap.length - 1
end
def insert(n)
heap.push(n)
swim(size)
end
def swim(k)
while k > 1 && heap[k/2] < heap[k]
heap[k/2], heap[k] = heap[k], heap[k/2]
k = k/2
end
end
def sink(k)
while (j = 2*k) <= size
j += 1 if j < size && heap[j] < heap[j+1]
break unless heap[k] < heap[j]
heap[k], heap[j] = heap[j], heap[k]
k = j
end
end
def pop
max = heap[1]
heap[1] = heap[size]
heap.pop
sink(1)
return max
end
def to_s
heap.to_s
end
end
heap = MaxHeap.new
for i in 1..7
heap.insert(i)
puts heap
end
while heap.size > 0
puts heap.pop
end
#!/usr/bin/env ruby
$:.unshift(".")
require "node"
data = [1,
[2, [4], [5]],
[3, [6], [7]]]
tree = Node.from_array(data)
puts tree.inspect
def lca(t, p, q)
return nil unless t
return t.data if t.data == p || t.data == q
left = lca(t.left, p, q)
right = lca(t.right, p, q)
return t.data if left && right
return left ? left : right
end
puts lca(tree, 4, 5)
puts lca(tree, 6, 7)
puts lca(tree, 4, 6)
puts lca(tree, 2, 3)
puts lca(tree, 2, 7)
#!/usr/bin/env ruby
class Graph
attr_accessor :list
def initialize(edges)
@list = {}
for v, w in edges
list[v] ||= []
list[w] ||= []
list[v].push(w)
list[w].push(v)
end
end
end
def levellist(graph, uplevel)
results = []
marked = {}
queue = []
for node in uplevel
marked[node] = true
end
while !uplevel.empty?
results.push(uplevel)
for node in uplevel
for adj in graph[node]
if !marked[adj]
marked[adj] = true
queue.push(adj)
end
end
end
uplevel = queue
queue = []
end
results
end
edges = [
[1,2],
[1,3],
[2,4],
[2,5],
[3,6],
[3,7],
[7,8],
[7,9]
]
g = Graph.new(edges)
puts g.list.inspect
puts levellist(g.list, [1]).inspect
#!/usr/bin/env ruby
def mark(matrix, m, n)
x, y = [], []
for i in 0...m
for j in 0...n
if matrix[i][j] == 0
x[i] = 0
y[j] = 0
end
end
end
for i in 0...m
for j in 0...n
matrix[i][j] = 0 if x[i] == 0 || y[j] == 0
end
end
end
data = [
(0..9).to_a,
(10..19).to_a,
(20..29).to_a,
(30..39).to_a,
(40..49).to_a,
(50..59).to_a,
(60..69).to_a,
(70..79).to_a,
(80..89).to_a,
(90..99).to_a
]
data[5][5] = 0
mark(data, 10, 10)
for row in data
puts row.inspect
end
class ListNode
attr_accessor :val, :next
def initialize(val)
@val, @next = val, nil
end
def inspect
"#{@val} -> #{self.next.inspect}"
end
end
class Array
def to_list
current = head = ListNode.new(self[0])
self[1..-1].each do |e|
current.next = ListNode.new(e)
current = current.next
end
head
end
end
def smallest(array)
result, i = array[0], 0
array.each.with_index do |list, index|
result, i = list, index if list && result.val > list.val
end
[result, i]
end
def merge_k_linked_list(array)
result, index = smallest(array)
array[index] = result.next
current = result
while true
list, index = smallest(array)
break unless list
array[index] = list.next
current.next = list
current = current.next
end
result
end
array = [
(7.upto(9)).to_a.to_list,
(4.upto(6)).to_a.to_list,
(1.upto(3)).to_a.to_list,
]
puts merge_k_linked_list(array).inspect
#!/usr/bin/env ruby
def merge(array, l, h)
i = l
mid = (l+h)/2
j = 1 + mid
aux = []
for k in l..h
aux[k] = array[k]
end
for k in l..h
if i > mid
array[k] = aux[j]; j+=1
elsif j > h
array[k] = aux[i]; i+=1
elsif aux[j] < aux[i]
array[k] = aux[j]; j+=1
else
array[k] = aux[i]; i+=1
end
end
array
end
def sort(array, l = 0, h = array.length - 1)
return if h <= l
mid = (l + h) / 2
sort(array, l, mid)
sort(array, mid+1, h)
merge(array, l, h)
end
puts merge([1,3,5,7,9,0,2,4,6,8], 0, 9).inspect
puts sort([9,8,7,6,5,4,3,2,1,0]).inspect
b = (0..5).to_a
a = (6..15).to_a + Array.new(b.length)
def merge(a, b)
i = a.length - 1
j = b.length - 1
while a[i] == nil
i -= 1
end
(a.length - 1).downto(0) do |p|
if i < 0
a[p] = b[j]; j -= 1; p -= 1;
elsif j < 0
a[p] = a[i]; i -= 1; p -= 1;
elsif b[j] > a[i]
a[p] = b[j]; j -= 1; p -= 1;
else
a[p] = a[i]; i -= 1; p -= 1;
end
end
a
end
puts merge(a, b).inspect
#!/usr/bin/env ruby
class String
def *(str)
maxshift = self.length + str.length - 2
results = Array.new(maxshift+1, 0)
self.split(//).map(&:to_i).each_with_index do |i, at1|
str.split(//).map(&:to_i).each_with_index do |j, at2|
results[maxshift - at1 - at2] += i * j
end
end
results.each_with_index do |i, shift|
if i > 9
results[shift+1] = results[shift+1].to_i + (i / 10)
results[shift] = i % 10
end
end
results.reverse.join
end
end
for i in 1..1000000
a = (i.to_s * i.to_s).to_i
b = i * i
unless a == b
puts a
puts b
end
end
class Node
attr_accessor :data, :left, :right
def initialize(data, left = nil, right = nil)
@data = data
@left = left
@right = right
end
def self.from_array(array)
array ? self.new(array.shift, from_array(array.shift), from_array(array.shift)) : nil
end
def edges
result = []
if left
result.push([data, left.data])
result += left.edges
end
if right
result.push([data, right.data])
result += right.edges
end
result
end
def inspect
"[#{data}, #{left.inspect}, #{right.inspect}]"
end
end
def palindrome(string)
hash = Hash.new(0)
string.each_char do |c|
hash[c] += 1
end
odd = hash.select { |k,v| v.odd? }
return nil if odd.length > 1
if k = odd.keys.first
v = hash.delete(k)
result = Array.new(v, k)
else
result = []
end
hash.each do |k,v|
(v/2).times { result.push(k); result.unshift(k) }
end
result.join
end
puts palindrome("aaaab")
puts palindrome("aabcbcbbdcdcd")
LEFT = ["(", "{", "[", "<"]
RIGHT = {
")" => "(",
"}" => "{",
"]" => "[",
">" => "<",
}
def balance?(string)
stack = []
string.split(//).each do |c|
puts stack.inspect
if LEFT.include?(c)
stack.push(c)
elsif RIGHT[c]
if stack.last == RIGHT[c]
stack.pop
else
return false
end
end
end
stack.empty? ? true : false
end
puts balance?("((<{}>)())")
puts balance?("()({(}))")
class TreeNode
attr_accessor :val, :left, :right
def initialize(val)
@val = val
@left, @right = nil, nil
end
end
tree = TreeNode.new(1)
tree.right = TreeNode.new(2)
tree.right.right = TreeNode.new(3)
tree.right.right.right = TreeNode.new(4)
tree.right.right.right.right = TreeNode.new(5)
def path_sum(root, sum)
return 0 unless root
result = 0
result += paths(root, sum)
result += path_sum(root.left, sum)
result += path_sum(root.right, sum)
result
end
def paths(tree, target)
return 0 unless tree
tmp = 0
tmp += 1 if tree.val == target
tmp += paths(tree.left, target - tree.val)
tmp += paths(tree.right, target - tree.val)
tmp
end
puts path_sum(tree, 3)
#!/usr/bin/env ruby
$:.unshift(".")
require "node"
data = [1,
[2, [4], [5]],
[3, [6], [7]]]
tree = Node.from_array(data)
puts tree.inspect
def path(tree, node)
return nil unless tree
return [node] if tree.data == node
return (subpath = path(tree.left, node) || path(tree.right, node)) ? subpath.unshift(tree.data) : nil
end
puts path(tree, 6)
def combination(element, target)
(0..target.length).select { |index| target[index] != element }.map { |index| target[0...index] + [element] + target[index...target.length] }
end
def permutation(array)
return [array] if array.length == 1
head = array.shift
permutation(array).map { |v| combination(head, v) }.reduce(:+)
end
puts permutation("aaa".split(//)).inspect
def list(n)
hash = Hash.new("")
1.upto(n/3) do |i|
hash[i*3] += "bug"
end
1.upto(n/5) do |i|
hash[i*5] += "fix"
end
hash.sort_by { |k,v| k }
end
list(30).each do |i, word|
puts "#{i}\t#{word}"
end
def list(n)
a, b = 3, 5
i, j = 0, 0
result = []
while i + a <= n || j + b <= n
if i + a == j + b
i += a
j += b
result.push([i, "bugfix"])
elsif i + a < j + b
i += a
result.push([i, "bug"])
else
j += b
result.push([j, "fix"])
end
end
result
end
list(30).each do |i, word|
puts "#{i}\t#{word}"
end
#!/usr/bin/env ruby
def sort(array, l = 0, h = array.length - 1)
return if h <= l
m = partition(array, l, h)
sort(array, l, m-1)
sort(array, m+1, h)
end
def partition(array, l, h)
i = l
j = h+1
m = array[l]
while true
while array[i+=1] < m; break if i == h; end
while array[j-=1] > m; break if j == l; end
break if i>=j
array[i], array[j] = array[j], array[i]
end
array[l], array[j] = array[j], array[l]
j
end
a = [3,4,5,2,1]
sort(a)
puts a.inspect
b = [9,8,7,6,5,4,3,2,1]
sort(b)
puts b.inspect
def removedup(string)
result = ""
for i in 0...string.length
exist = false
for j in 0...i
exist = true if result[j] == string[i]
end
result += string[i] unless exist
end
result
end
puts removedup("shelling")
puts removedup("aaabbb")
puts removedup("ababab")
def removedup(string)
return if string.length < 2
length = string.length
tail = 1
while true
break if tail >= length
for i in 0...tail
if string[i] == string[tail]
string[tail] = ""
length -= 1
break
end
tail += 1 if i == tail - 1
end
end
string
end
puts removedup("shelling")
puts removedup("aaaaaa")
puts removedup("aaabbb")
puts removedup("ababab")
class ListNode
attr_accessor :val, :next
def initialize(val)
@val, @next = val, nil
end
def inspect
"#{@val} -> #{self.next.inspect}"
end
end
class Array
def to_list
current = head = ListNode.new(self[0])
self[1..-1].each do |e|
current.next = ListNode.new(e)
current = current.next
end
head
end
end
puts [1,2,3,4,5,6,7].to_list.inspect
def reverse(head, c)
return head unless head
tail = head
c.times { |i|
if tail.next || i == c - 1
tail = tail.next
else
return head
end
}
pre = reverse(tail, c)
current = head
c.times {
tmp = current.next
current.next = pre
pre = current
current = tmp
}
pre
end
puts reverse((1..7).to_a.to_list, 2).inspect
puts reverse((1..3).to_a.to_list, 3).inspect
puts reverse((1..4).to_a.to_list, 3).inspect
class ListNode
attr_accessor :val, :next
def initialize(val)
@val, @next = val, nil
end
def inspect
"#{@val} -> #{self.next.inspect}"
end
end
class Array
def to_list
current = head = ListNode.new(self[0])
self[1..-1].each do |e|
current.next = ListNode.new(e)
current = current.next
end
head
end
end
l = [2,3,4,5].to_list
def reverse(head, c)
pre = head
c.times { pre = pre.next }
current = head
c.times do
tmp = current.next
current.next = pre
pre = current
current = tmp
end
pre
end
puts reverse(l,4).inspect
def reverse_between(head, m, n)
if m == 1
return reverse(head, n - m + 1)
else
p = head
(m-2).times { p = p.next }
p.next = reverse(p.next, n-m+1)
return head
end
end
puts reverse_between([1,2,3,4,5].to_list, 2, 4).inspect
#!/usr/bin/env ruby
def reverse(int)
flag = int < 0
int = int.abs
result = 0
while int > 0
result = result * 10 + int % 10
int /= 10
end
(flag ? -1 : 1) * result
end
puts reverse(321)
puts reverse(-100)
#!/usr/bin/env ruby
def rotate(matrix, m)
maxlevel = m / 2
for layer in 0..(maxlevel-1)
for i in layer..m-2-layer
# top, left, bottom, right = left, bottom, right, top
matrix[layer][i], matrix[m-i-1][layer], matrix[m-layer-1][m-i-1], matrix[i][m-layer-1] =
matrix[m-i-1][layer], matrix[m-layer-1][m-i-1], matrix[i][m-layer-1], matrix[layer][i]
end
end
end
data = [
[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]
]
rotate(data, 4)
for row in data
puts row.inspect
end
def rotate(matrix)
result = []
for j in 0...matrix.first.length
row = []
for i in 0...matrix.length
row.unshift(matrix[i][j])
end
result.push(row)
end
result
end
data = [
[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]
]
for row in rotate(data)
puts row.inspect
end
#!/usr/bin/env ruby
def search(array, x, l = 0, h = array.length - 1)
while l <= h
m = (l + h) / 2
if x == array[m]
return m
elsif array[l] <= array[m] # sorted left
if x < array[m] and x >= array[l]
h = m - 1
else
l = m + 1
end
else # sorted right
if x > array[m] and x <= array[h]
l = m + 1
else
h = m - 1
end
end
end
end
data = [15,16,19,20,25,1,3,4,5,7,10,14]
for i in data
puts search(data, i)
end
data = [10,14,15,16,19,20,25,1,3,4,5,7]
for i in data
puts search(data, i)
end
#!/usr/bin/env ruby
def intersect(first, second)
intersect = []
while !first.empty? && !second.empty?
if first[0] == second[0]
intersect.push first.shift
second.shift
elsif first[0] > second[0]
second.shift
else
first.shift
end
end
intersect
end
puts intersect [ 2,3, 6,7, 9,10],
[1,2,3,4,5,6,7,8]
def bsearch(array, n)
i = 0
j = array.length - 1
while i <= j
mid = (i + j) / 2
if n == array[mid]
return n
elsif n > array[mid]
i = mid + 1
else
j = mid - 1
end
end
end
for n in [ 2,3, 6,7, 9,10]
if found = bsearch([1,2,3,4,5,6,7,8], n)
puts found
end
end
def spiral(matrix)
result = []
left = 0
right = matrix.first.length - 1
top = 0
bottom = matrix.length - 1
while true
left.upto(right) {|j| result.push(matrix[top][j]) }
top += 1
break if top > bottom || left > right
top.upto(bottom) {|i| result.push(matrix[i][right]) }
right -= 1
break if top > bottom || left > right
right.downto(left) {|j| result.push(matrix[bottom][j]) }
bottom -= 1
break if top > bottom || left > right
bottom.downto(up) {|i| result.push(matrix[i][left]) }
left += 1
break if top > bottom || left > right
end
result
end
puts spiral([[1,2],[3,4]]).inspect
n = 9
matrix = Array.new()
n.times { matrix.push(Array.new(n)) }
matrix.each { |row| puts row.inspect }; puts
Direction = {
right: :down,
down: :left,
left: :up,
up: :right,
}
def right(matrix, i, j)
return [i, j] if matrix[i] && matrix[i][j+2] == "*"
return [i, j] if j >= matrix.first.length-1
matrix[i][j] = "*"
return [i, j+1]
end
def down(matrix, i, j)
return [i, j] if matrix[i+2] && matrix[i+2][j] == "*"
return [i, j] if i >= matrix.length-1
matrix[i][j] = "*"
return [i+1, j]
end
def left(matrix, i, j)
return [i, j] if j <= 0
return [i, j] if matrix[i] && matrix[i][j-2] == "*" && j != 1
matrix[i][j] = "*"
return [i, j-1]
end
def up(matrix, i, j)
return [i, j] if matrix[i-2] && matrix[i-2][j] == "*"
return [i, j] if i <= 0
matrix[i][j] = "*"
return [i-1, j]
end
def move(direction, matrix, i, j)
send(direction, matrix, i, j)
end
i, j = 0, 0
direction = :right
while true
x, y = i, j
i, j = move(direction, matrix, i, j)
direction = Direction[direction.to_sym] if i == x && j == y
if direction == :right &&
matrix[i][j+2] == "*" &&
matrix[i-2][j] == "*" &&
matrix[i+2][j] == "*"
matrix[i][j] = "*"
break
end
end
matrix.each { |row| puts row.inspect }
class Stack < Array
def sort
result = []
while !self.empty?
if result.last && result.last > self.last
tmp = self.pop
while result.last && result.last > tmp
self.push(result.pop)
end
result.push(tmp)
else
result.push(self.pop)
end
end
result
end
end
stack = Stack.new([9,8,7,6,5,4,3,2,1])
puts stack.sort.inspect
class StackWithMin < Array
def initialize
@mins = []
super
end
def push(e)
@mins.push(min ? [min, e].min : e)
super(e)
end
def pop
@mins.pop
super
end
def min
@mins.last
end
end
s = StackWithMin.new
s.push(3); puts s.min
s.push(2); puts s.min
s.push(1); puts s.min
s.pop; puts s.min
s.pop; puts s.min
s.pop; puts s.min
class StackQueue
attr_accessor :s1, :s2
def initialize
@s1 = []
@s2 = []
end
def add(obj)
@s1.push(obj)
self
end
def pop
if @s2.empty?
while obj = @s1.pop
@s2.push(obj)
end
end
@s2.pop
end
def to_s
s2.reverse.to_s + s1.to_s
end
end
sq = StackQueue.new
sq.add(1).add(2).add(3)
puts sq
puts sq.pop
puts sq
def subsets(set)
return [set] if set.length == 1
head = [set.shift]
tail = subsets(set)
return tail.map { |s| head + s } + [head] + tail
end
puts subsets([1,2,3]).inspect
def subsets(set)
max = 2 ** set.length
(1..max-1).map { |i| i.to_s(2).rjust(set.length, "0").split(//) }
.map { |flags|
flags.zip(set).select { |p| p[0] == "1" }.map { |p| p[1] }
}
end
puts subsets([1,2,3]).inspect
def dfs(current, tokens, result)
if tokens.empty?
result.push(current.map { |k,v| Array.new(v, k) }.reduce(:+))
else
rest = tokens.dup
char, count = rest.shift
(0..count).each do |c|
dfs(current.merge(char => c), rest, result)
end
end
end
def subsets(nums)
hash = Hash.new(0)
nums.each do |n|
hash[n] += 1
end
result = []
dfs({}, hash, result)
result
end
puts subsets([1,2,2]).inspect
def vowel?(c)
["a", "e", "i", "o", "u"].include?(c)
end
def swap(string)
i, j = 0, string.length - 1
while true
while !vowel?(string[i]); i+=1; end
while !vowel?(string[j]); j-=1; end
break if i >= j
string[i], string[j] = string[j], string[i]
i+=1
j-=1
end
string
end
puts swap("apple")
puts swap("friend")
#!/usr/bin/env ruby
$:.unshift(".")
require "node"
data = [1,
[2, [3], [5]],
[4]]
tree = Node.from_array(data)
def tracetree(t)
left, right = [], []
while true
left.push(t.data)
right.push(t.right.data) if t.right
break unless t = t.left
end
# left = [1,2,3]
# right = [4,5]
puts left.reverse
puts right.reverse
end
tracetree(tree)
#!/usr/bin/env ruby
$:.unshift(".")
require "node"
data = [1,
[2, [4], [5]],
[3, [6], [7]]]
tree = Node.from_array(data)
def dfs_level(tree, level = 0, result = [])
result[level] ||= []
dfs_level(tree.left, level+1, result) if tree.left
result[level].push(tree.data)
dfs_level(tree.right, level+1, result) if tree.right
result
end
puts dfs_level(tree).inspect
def bfs_level(current)
return if current.empty?
queue = []
for node in current
print node.data
queue.push(node.left) if node.left
queue.push(node.right) if node.right
end
puts
bfs_level(queue)
end
bfs_level([tree])
def uniqchar?(string)
index = Array.new(26)
string.split(//).map(&:downcase).map(&:ord).map { |c| c - 97 }.each do |i|
return false if index[i]
index[i] = true
end
return true
end
puts uniqchar?("shelling").inspect
def uniqchar?(string)
for i in 0...string.length
for j in i+1...string.length
return false if string[i].downcase == string[j].downcase
end
end
return true
end
puts uniqchar?("shelling").inspect
#!/usr/bin/env ruby
def zeroend(array)
i = -1
j = array.length
while true
while i += 1; break if array[i] == 0; end
while j -= 1; break if array[j] != 0; end
break if i >= j
array[i], array[j] = array[j], array[i]
end
array[0..j]
end
puts zeroend([1,0,2,0,3,0,4,0,5,0,6,0]).inspect
puts zeroend([1,2,3,4,0,0,0,0,5,6,7,8,0,0,9]).inspect
def next_position(i, j, row)
if (j % (row - 1) == 0) && (i < (row - 1))
return [i+1, j]
else
return [i-1, j+1]
end
end
def convert(string, row)
matrix = []
row.times { matrix.push([]) }
i, j = 0, 0
string.each_char do |c|
matrix[i][j] = c
i, j = next_position(i, j, row)
end
return matrix
end
result = convert("paypalishiring", 3)
for row in result
for c in row
if c
print c + " "
else
print " "
end
end
puts
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment