algorithm pactises

0_readme.md

移至 github

add_two_number.rb

#!/usr/bin/env ruby
# 把两个反向单链表对应节点相加
# 
require_relative './list_node.rb'
require_relative './reverse_linked_list.rb'
module Solution
  extend self

  def atn(list1, list2)
    rlist1 = Solution.rll(list1)
    rlist2 = Solution.rll(list2)
    sum_list = nil
    current = nil
    carry = 0
    while !rlist1.nil?
      val = (carry + rlist1.val + rlist2.val) % 10
      carry = (carry + rlist1.val + rlist2.val) / 10
      node = ListNode.new(val)
      if sum_list.nil?
        sum_list = node
        current = node
      else
        current.next = node
        current = current.next
      end
      rlist1 = rlist1.next
      rlist2 = rlist2.next

    end
    if carry != 0
      node = ListNode.new(carry)
      current.next = node
    end
    sum_list
  end
end


c = ListNode.new(3)
b = ListNode.new(2,c)
a = ListNode.new(1,b)

f = ListNode.new(6)
e = ListNode.new(5,f)
d = ListNode.new(9,e)

sum_list = Solution.atn(a,d)

ListNode.show(sum_list)

binary_tree_level_order_traversal.rb

#!/usr/bin/env ruby
require_relative './bst.rb'
module Solution
  extend self

  def btlot tree
    levels = []
    cur_s = []
    next_s = []
    i = 1
    return levels if tree.root.nil?

    cur_s.push tree.root
    loop do

      level = []
      loop do
        node = cur_s.shift
        level.push node.key
        next_s.push node.left unless node.left.nil?
        next_s.push node.right unless node.right.nil?

        break if cur_s.empty?
      end
      levels.push level

      cur_s = next_s
      next_s = []

      break if cur_s.empty?
    end

    levels
  end
end

bst = BST.new

bst.put('s',8)
bst.put('e',6)
bst.put('x',1)
bst.put('a',2)
bst.put('c',1)
bst.put('r',3)
bst.put('h',2)
bst.put('m',1)
bst.put('t',4)
bst.put('z',7)

result =  Solution.btlot bst
puts result.inspect

bst_inorder_traversal.rb

#!/usr/bin/env ruby
require_relative './bst.rb'
require_relative './stack.rb'
module Solution
  extend self

  def bit tree
    r = []
    s = Stack.new
    cur = tree.root

    while !s.empty? || !cur.nil?
      if !cur.nil?
        s.push cur
        cur = cur.left
      elsif !s.empty?
        cur = s.pop
        puts cur.key
        r.push cur
        cur = cur.right
      end
    end
    r
  end
end

bst = BST.new

bst.put('s',8)
bst.put('e',6)
bst.put('x',1)
bst.put('a',2)
bst.put('c',1)
bst.put('r',3)
bst.put('h',2)
bst.put('m',1)

Solution.bit bst

bst_postorder_traversal.rb

#!/usr/bin/env ruby
require_relative './bst.rb'
require_relative './stack.rb'
module Solution
  extend self

  def bpt tree
    r = []
    parent_stack = Stack.new
    node = tree.root
    loop do
      while !node.nil?
        parent_stack.push node
        node = node.left
      end
      last_visited_node = nil

      while !parent_stack.empty?
        node = parent_stack.pop
        # 右孩子不存在或者已访问过
        if node.right == last_visited_node
          r << node.key
          last_visited_node = node
        else
          parent_stack.push node
          node = node.right
          break
        end

      end

      break if parent_stack.empty?
    end
    r
  end
end

bst = BST.new

bst.put('s',8)
bst.put('e',6)
bst.put('x',1)
bst.put('a',2)
bst.put('c',1)
bst.put('r',3)
bst.put('h',2)
bst.put('m',1)
puts Solution.bpt bst

bst_postorder_traversal_v2.rb

#!/usr/bin/env ruby
# 把后序遍历当作是“前序”遍历的倒序,“前序”的顺序是: 中右左,它的倒序就是 左右中
# 用两个栈实现
require_relative './bst.rb'
require_relative './stack.rb'
module Solution
  extend self

  def bpt2 tree
    r = []
    rs = Stack.new
    s = Stack.new
    rs.push tree.root

    while !rs.empty?
      cur = rs.pop
      s.push cur
      rs.push cur.left if cur.left
      rs.push cur.right if cur.right
    end

    while !s.empty?
      r.push s.pop
    end

    r
  end
end

bst = BST.new

bst.put('s',8)
bst.put('e',6)
bst.put('x',1)
bst.put('a',2)
bst.put('c',1)
bst.put('r',3)
bst.put('h',2)
bst.put('m',1)

puts Solution.bpt2 bst

bst_preorder_traversal.rb

#!/usr/bin/env ruby
require_relative './bst.rb'
require_relative './stack.rb'
module Solution
  extend self

  def bpt tree
    r = []
    s = Stack.new
    s.push tree.root

    while !s.empty?
      cur = s.pop
      r.push cur
      s.push cur.right if cur.right
      s.push cur.left if cur.left
    end
    r
  end
end

bst = BST.new

bst.put('s',8)
bst.put('e',6)
bst.put('x',1)
bst.put('a',2)
bst.put('c',1)
bst.put('r',3)
bst.put('h',2)
bst.put('m',1)

puts Solution.bpt bst

candy.rb

#!/usr/bin/env ruby
# 每个孩子至少分到 1 粒
# 等级高的比前后等级低的分到的要多
# 最少要有多少粒糖
module Solution
  extend self
  def candy(arr)
    record = Array.new(arr.length) { 0 }
    index = 1
    count = 1
    while index < arr.length
      if arr[index] > arr[index - 1]
        record[index] = count
        count += 1
      else
        count = 1
      end
      index += 1
    end
    index = arr.length - 2
    count = 1
    while index >= 0
      if arr[index] > arr[index + 1]
        record[index] = [record[index], count].max
        count += 1
      else
        count = 1
      end
      index -= 1
    end
    record.reduce(arr.length) { |memo, item| memo + item }
  end
end

puts Solution.candy([1,4,6,4,8,5,4])

puts Solution.candy([1,2,2,2,2])

climbing_stairs.rb

#!/usr/bin/env ruby
# 用数学公式可做到时间/空间复杂度都是 O(1)
module Solution
  extend self
  def cs(n)
    return 1 if n < 2
    prev = 1
    cur = 1
    (n-1).times do
      prev, cur = cur, prev + cur
    end
    cur
  end

end

puts Solution.cs(4)

contains_duplicate_k.rb

#!/usr/bin/env ruby
module Solution
  extend self
  # 时间复杂度 O(n) ,空间复杂度 O(n)
  def cdk(arr, k)
    h = Hash.new
    exists = false
    arr.each_with_index do |item, index|
      if h.include?(item)
        distance = index - h[item]
        if distance <= k
          exists = true
          break
        else
          h[item] = index
        end
      else
        h[item] = index
      end
    end
    exists
  end
end

puts Solution.cdk([1,2,3,4,1], 3)
puts Solution.cdk([1,2,3,4,1,1], 3)

contains_duplicate_k_t.rb

#!/usr/bin/env ruby
# 判断数组中有没有两个元素,它俩的值相差不大于 k ,且它俩的索引相差不大于 t

require_relative './binary_search_symbol_tree.rb'
module Solution
  extend self
  def cdkt(arr, k, t)
    bst = BSST.new
    result = false
    arr.each_with_index do |item, index|
      if bst.is_empty?
        bst.put item, index
      else
        floor = bst.floor(item)
        ceiling = bst.ceiling(item)
        if floor != nil && (item <= floor + k)
          result = true
          break
        end
        if ceiling != nil && (item >= ceiling - k)
          result = true
          break
        end
        bst.put item, index
        if bst.size > t
          bst.delete arr[index - t]
        end
      end
    end
    result
  end
end

puts Solution.cdkt([1,50,100,9,70,30,2], 8, 3)

copy_list_with_random_pointer.rb

#!/usr/bin/env ruby
require_relative './list_node.rb'
# 难度就在于复制 random pointer 指向的节点
# 需要建立旧节点 random pointer 指向的节点 跟新节点 random pointer 指向的节点的关系
# 把新节点放在对应的旧节点以建立上面提到的关系,因为旧节点 random pointer 指向的节点,再往后一个,就是新节点random pointer 指向的节点
module Solution
  extend self

  def clrp(list)
    # 1 新节点插入到旧节点中
    p = list
    while p
      new_node = ListNode.new(p.val)
      new_node.next = p.next
      p.next = new_node
      p = new_node.next
    end

    # 2 复制 random pointer
    p = list
    while p
      if p.point_to
        p.next.point_to = p.point_to.next
      end
      p = p.next.next
    end
    # 3 解除新旧节点的关系
    p = list
    n = p.next
    new_head = p.next
    while n
      p.next = n.next
      if n.next
        p = n.next
        n.next = p.next
        n = p.next
      else
        break
      end
    end


    new_head
  end
end

e = ListNode.new(5)
d = ListNode.new(4,e)
c = ListNode.new(3,d)
b = ListNode.new(2,c)
a = ListNode.new(1,b)
list = ListNode.new(0, a)
list.add_pointer(b)
b.add_pointer(c)
d.add_pointer(a)

# ListNode.show(list)

result = Solution.clrp(list)

ListNode.show(result)
ListNode.show(list)

count_and_say.rb

#!usr/bin/env ruby
module Solution
  extend self

  def cas(n)
    return '1' if n == 1
    result = ''
    prev = cas(n-1)

    current = nil
    count = 0
    prev.each_char do |c|
      if current == nil
        current = c
        count = 1
      elsif c != current
        result << count.to_s + current.to_s
        current = c
        count = 1
      else
        count += 1
      end
    end
    result << count.to_s + current.to_s
  end
end

r = Solution.cas(7)
puts r

evaluate_reverse_polish_notation.rb

#!/usr/bin/env ruby
require_relative './stack.rb'
module Solution
  extend self
  def erpn(arr)
    s = Stack.new

    arr.each do |item|
      case item
        when /\d+/
          s.push item
        when /\+/
          op_2 = s.pop
          op_1 = s.pop
          s.push(op_1.to_i + op_2.to_i)
        when /-/
          op_2 = s.pop
          op_1 = s.pop
          s.push(op_1.to_i - op_2.to_i)
        when /\*/
          op_2 = s.pop
          op_1 = s.pop
          s.push(op_1.to_i * op_2.to_i)
        when /\//
          op_2 = s.pop
          op_1 = s.pop
          s.push(op_1.to_i / op_2.to_i)
      end
      puts s.top
    end
    s.top
  end
end

# r = Solution.erpn(['2','1','+','3','*'])
r = Solution.erpn(['4','13','5','/','+'])

puts r

gas_station.rb

#!usr/bin/env ruby
# gas station
# 时间复杂度 O(n)
# 保证只有一个解,要么是-1,要么是 index
# 
module Solution
  extend self

  def gs(gas, cost)
    sum = 0
    total = 0
    j = 0
    gas.each_with_index do |item, i|
      sum += item - cost[i]
      total += item - cost[i]
      if(sum < 0)
        sum = 0
        j = i
      end
    end
    total < 0 ? -1 : j+1
  end
end

puts Solution.gs([2,1,2,1,1,2,2],[1,3,1,2,2,1,1])
puts Solution.gs([2,1,2,6],[3,2,3,2])
puts Solution.gs([2,1,2,3],[3,2,3,2])

increasing_triplet_subsequence.rb

#!/usr/bin/env ruby
# 三个递增序列
# 只要扫描一遍数组,依次更新当前最小的元素,倒数第二小的元素
# 如果遇到比倒数第二小的元素还要大的元素,就表明存在三个元素递增序列
module Solution
  extend self

  def its(arr)
    min = Float::INFINITY
    min_2 = Float::INFINITY
    result = false
    arr.each do |item|
      if item < min
        min = item
      elsif item < min_2
        min_2 = item
      else
        result = true
        break
      end
    end
    result
  end
end


puts Solution.its([8,3,8,7,4])
puts Solution.its([8,3,8,7,4,2,5])

invert_bst.rb

#!/usr/bin/env ruby
require_relative './bst.rb'
require_relative './stack.rb'
module Solution
  extend self
  def ibst tree
    return if tree.nil? || tree.root.nil?

    s = Stack.new
    s.push tree.root

    loop do
      node = s.pop

      s.push node.left unless node.left.nil?
      s.push node.right unless node.right.nil?

      revert(node)

      break if s.empty?
    end
    tree
  end
  private
  def revert node
    return if node.nil?
    tmp_node = node.left
    node.left = node.right
    node.right = tmp_node
    tmp_node = nil
  end
end

bst = BST.new

bst.put('s',8)
bst.put('e',6)
bst.put('x',1)
bst.put('a',2)
bst.put('c',1)
bst.put('r',3)
bst.put('h',2)
bst.put('m',1)

result = Solution.ibst bst
puts result.inspect

largest_rectangle_in_histogram.rb

#!/usr/bin/env ruby
require_relative './stack.rb'
module Solution
  extend self

  def lrh(arr)
    s = Stack.new
    max_area = 0
    arr.each do |item|
      if s.empty?
        s.push item
      elsif item >= s.top
        s.push item
      elsif item < s.top
        i = 1
        while !s.empty? && s.top >= item
          area = s.pop * i
          i += 1
          max_area = area if area > max_area
        end
        s.push item
      end
    end

    i = 1
    while !s.empty?
      area = s.pop * i
      i += 1
      max_area = area if area > max_area
    end
    max_area
  end
end

# r = Solution.lrh([2,1,5,6,3,2])
r = Solution.lrh([2,1,2,3,4,4])
puts r

linked_list_cycle.rb

#!/usr/bin/env ruby
require_relative './list_node.rb'
# 有点像在学校跑道里被跑得快的人超出一圈
module Solution
  extend self

  def llc(list)
    fast = list
    slow = list
    cycle = false
    while !cycle
      if fast && fast.next
        fast = fast.next.next
      else
        break
      end

      if slow
        slow = slow.next
      else
        break
      end

      if fast == slow
        cycle = true
      end

    end

    cycle
  end
end


c = ListNode.new(3)
b = ListNode.new(2,c)
a = ListNode.new(1,b)
c.next = b
list = ListNode.new(0, a)

# ListNode.show(list)

result = Solution.llc(list)

puts "cycle: #{result}"

linked_list_cycle_2.rb

#!/usr/bin/env ruby
# http://www.cnblogs.com/hiddenfox/p/3408931.html
# 画个图,有一个重要的假设: 快指针的速度是慢指针的2倍,因此在相遇时路程也是它的2倍
require_relative './list_node.rb'
module Solution
  extend self

  def llc2(list)
    fast = list
    slow = list
    cycle = false
    while !cycle
      if fast && fast.next
        fast = fast.next.next
      else
        break
      end

      if slow
        slow = slow.next
      else
        break
      end

      if fast == slow
        cycle = true
      end

    end

    if cycle
      slow = list
      while slow != fast
        slow = slow.next
        fast = fast.next
      end
      slow
    else
      null
    end

  end
end


c = ListNode.new(3)
b = ListNode.new(2,c)
a = ListNode.new(1,b)
c.next = a
list = ListNode.new(0, a)

# ListNode.show(list)

result = Solution.llc2(list)

puts "result value #{result.val}"

list_node.rb

#!/usr/bin/env ruby
class ListNode
  attr_accessor :val, :next, :point_to
  def initialize(value, nx = nil)
    @val = value
    @next = nx
  end

  def add_pointer(target=nil)
    @point_to = target
  end

  def self.show(head)
    return nil if head.nil? || head.val.nil?
    while true
      puts "node: #{head} , values: #{head.val} , point to #{head.point_to}"
      if !head.next.nil?
        head = head.next
      else
        break
      end
    end
  end
end

# e = ListNode.new(5)
# d = ListNode.new(4,e)
# c = ListNode.new(3,d)
# b = ListNode.new(2,c)
# a = ListNode.new(1,b)
# list = ListNode.new(0, a)
#
# ListNode.show(list)

longest_palindromic_substring.rb

#!/usr/bin/env ruby
# 最长回文子串
# https://www.felix021.com/blog/read.php?entryid=2040&page=1&part=1
# 聪明之处在于第一步的变换和第二步的复用之前求得的最长子串
# 时间复杂度是 O(n)
module Solution
  extend self

  def lps(str)
    #给 str 加上 #
    new_str = '#' + str.split(//).join('#') + '#'

    id = 0
    mx = 0

    i = 0
    p = Array.new(new_str.length) { 1 }
    while i < new_str.length
      p[i] = i < mx ? [p[2*id-i], mx - i].min : 1
      while new_str[i + p[i]] == new_str[i - p[i]]
        p[i] += 1
      end
      if mx < p[i] + i
        id = i
        mx = p[i] + i
      end
      i += 1
    end

    max_len = 0
    max_len_index = 0
    p.each_with_index do |item, index|
      if item > max_len
        max_len = item
        max_len_index = index
      end
    end
    begining = max_len_index - max_len + 2
    count = 0
    result = ''
    while count < max_len - 1
      result << new_str[begining]
      begining += 2
      count += 1
    end

    result
  end
end

r = Solution.lps('12212331')

puts r

longest_valid_parentheses.rb

#!/usr/bin/env ruby

require_relative './stack.rb'

module Solution
  extend self

  def lvp(str)
    s = Stack.new
    max_len = 0
    current = 0
    str.each_char do |c|
      if c == '('
        s.push c
      elsif c == ')'
        if !s.empty? && s.top == '('
          s.pop
          current += 2
        else
          max_len = current if current > max_len
          current = 0
        end
      end
    end

    max_len < current ? current : max_len
  end
end

r = Solution.lvp('()()()')
r = Solution.lvp('())())())()()(')
r = Solution.lvp('(((')
r = Solution.lvp(')))')

puts r

majority_element.rb

#!/usr/bin/env ruby
module Solution
  extend self
  # 时间复杂度 O(n) ,空间复杂度 O(n)
  def me(arr)
    record = Hash.new { 0 }
    len = arr.length
    arr.each do |item|
      record[item] += 1
      break item if record[item] > len / 2
    end
  end
  # 时间复杂度 O(nlogn) ,空间复杂度 O(1)
  def me_2(arr)
    arr_sorted = arr.sort
    # 因为 majority element 肯定存在,所以一定是位于中间的那个元素
    arr_sorted[arr_sorted.length / 2]
  end
  # 时间复杂度 O(n) ,空间复杂度 O(1)
  def me_3(arr)
    majority_item = nil
    count = 0
    arr.each do |item|
      if count == 0
        majority_item = item
        count = 1
      elsif majority_item == item
        count += 1
      else
        count -= 1
      end
    end
    majority_item
  end
end

puts Solution.me([0,1,2,3,1,2,1,1,2,1,1])
puts Solution.me_2([0,1,2,3,1,2,1,1,2,1,1])
puts Solution.me_3([0,1,2,3,1,2,1,1,2,1,1])

move_zeroes.rb

#!/usr/bin/env ruby

module Solution
  extend self
  def mz(arr)
    index = 0
    arr.each do |item|
      if 0 != item
        arr[index] = item
        index += 1
      end

    end
    while index < arr.length
      arr[index] = 0
      index += 1
    end
    arr
  end
end

puts Solution.mz([2,0,1,6,0,0,3,12,0])

next_permutation.rb

#!/usr/bin/env ruby
# 1896775 -> 1897567
# 8765 -> 5678
module Solution
  extend self
  def np(arr)
    return arr if arr.length < 2

    i = arr.length - 2
    t_index = while i >= 0
      if arr[i] < arr[i+1]
        break i
      end
      i -= 1
    end

    if t_index
      j = arr.length - 1
      s_index = while j >= 0
                  break j if arr[j] >= arr[t_index]
                  j -= 1
                end
      arr[t_index],arr[s_index] = arr[s_index], arr[t_index]
    else
      t_index = -1
    end

    k = arr.length - 1
    while k > t_index
      arr[t_index+1],arr[k] = arr[k],arr[t_index+1]
      t_index += 1
      k -= 1
    end
    arr
  end
end

puts Solution.np([1,8,9,6,7,7,5])
puts Solution.np([8,7,6,5])

palindrome_linked_list.rb

#!/usr/bin/env ruby
# 判断单链表是否回文
require_relative './list_node.rb'
module Solution
  extend self
  def pll(list)
    return true if list.nil? || list.next.nil?
    #获取链表长度
    n = 0
    current = list
    while current
      n += 1
      current = current.next
    end

    mid = (n / 2.0).ceil

    # 断开中间节点之后的 list ,再反转后半段 list
    current = list
    while mid > 1
      current = current.next
      mid -= 1
    end

    half_list = current.next
    current.next = nil
    reverse_half_list = reverse(half_list)

    # 以被反转后的链表为基准,逐个比较节点
    current = reverse_half_list
    is_palindrome = true
    while current
      if current.val != list.val
        is_palindrome = false
        break
      end
      current = current.next
      list = list.next
    end
    is_palindrome
  end

  def reverse(list)
    return list if list.nil? || list.next.nil?
    prev = list
    current = prev.next
    next_item = current.next
    while current
      current.next = prev
      prev = current
      current = next_item
      next_item = next_item ? next_item.next : nil
    end

    list.next = nil
    prev
  end
end

d = ListNode.new(0)
c = ListNode.new(1,d)
b = ListNode.new(2,c)
a = ListNode.new(1,b)
list = ListNode.new(0,a)

# ListNode.show(list)

result = Solution.pll(list)

if result
  puts 'is palindrome'
else
  puts 'is not palindrome'
end

partition_list.rb

#!/usr/bin/env ruby
# 给出一个 x ,把小于 x 的节点挪到链表的前面
require_relative './list_node.rb'
module Solution
  extend self

  def pl(list, x)
    head = list
    new_head = nil
    greater_head = nil
    less_current = nil
    greater_current = nil

    while !list.nil?
      if list.val < x
        new_head = list
        less_current = list
        break
      end
      list = list.next
    end
    return head if new_head.nil?

    list = head
    while !list.nil?
      if list.val >= x
        greater_head = list
        greater_current = list
        break
      end
      list = list.next
    end
    return head if greater_head.nil?

    list = head
    while !list.nil?
      if list.val < x && list != less_current
        less_current.next = list
        less_current = less_current.next
      elsif list.val >= x && list != greater_current
        greater_current.next = list
        greater_current = greater_current.next
      end
      list = list.next
    end
    less_current.next = greater_head
    greater_current.next = nil
    new_head
  end
end

d = ListNode.new(1)
c = ListNode.new(0,d)
b = ListNode.new(2,c)
a = ListNode.new(4,b)
list = ListNode.new(1, a)

# ListNode.show(list)

result = Solution.pl(list, 2)

ListNode.show(result)

product_array_except_self.rb

#!/usr/bin/env ruby
# product of array except self
# [1,2,3,4] => [24,12,8,6]
# [a1,a2,a3,a4] =>
# [1,a1,a1*a2,a1*a2*a3]
# [a2*a3*a4,a3*a4,a4,1]
# O(n)
# 以空间换时间
module Solution
  extend self

  def paes(arr)
    left = [1]
    i = 0
    while i < arr.length - 1
      left << left[i] * arr[i]
      i += 1
    end
    right = [1]
    j = arr.length - 1
    while j > 0
      right.unshift(right[0] * arr[j])
      j -= 1
    end

    result = []
    arr.length.times do |k|
      result << left[k] * right[k]
    end
    result
  end

  # 空间复杂度 O(1)
  def paes2(arr)
    left = [1]
    i = 0
    while i < arr.length - 1
      left << arr[i] * left[i]
      i += 1
    end
    right = 1
    j = arr.length - 1
    while j >= 0
      left[j] *= right
      right *= arr[j]
      j -= 1
    end
    left
  end
end

puts Solution.paes([1,2,3,4])
puts Solution.paes2([1,2,3,4])

regular_expression_matching.rb

#!/usr/bin/env ruby
#为什么能想到用递归?
#http://www.cnblogs.com/grandyang/p/4461713.html
module Solution
  extend self

  def rem(s, m)
    #先从最简单的情况开始
    # 如果 m 为空
    return s.empty? if m.empty?

    return false if s.empty?

    # 如果 m 长度为 1
    if m.length == 1
      return s.length == 1 && (s[0] == m[0] || m[0] == '.')
    end

    # 如果 m 长度大于 1
    # 如果第 2 个字符不是 *
    if m[1] != '*'
      return false if (s[0] != m[0] && m[0] != '.')
      return rem(s[1..-1],m[1..-1])
    end

    # 如果 m 长度大于 1
    # 如果第 2 个字符是 *
    # 下面这几行想不到。。。。
    while !s.empty? && (s[0] == m[0] || m[0] == '.')
      return true if rem(s, m[2..-1])
      s = s[1..-1]
    end

    rem(s, m[2..-1])
  end
end

if Solution.rem('abcbb','a*.c.b')
  puts 'match'
else
  puts 'not match'
end

reorder_list.rb

#!/usr/bin/env ruby
require_relative './list_node.rb'
# L0 →L1 →⋯→Ln−1 →Ln
#=> L0 →Ln →L1 →Ln−1 →L2 →Ln−2 →⋯
module Solution
  extend self

  def rl(list)
    # 先遍历一次 list ,找到中间节点
    current = list
    index = 0
    while current
      index += 1
      current = current.next
    end
    mid = (index / 2.0).ceil

    puts "mid #{mid}"

    # 断开中间节点之后的 list ,再反转后半段 list
    current = list
    while mid > 1
      current = current.next
      mid -= 1
    end

    last_half = current.next
    current.next = nil

    puts "last_half #{last_half}"

    reverse_last_half = reverse(last_half)



    # 把反转的后半段节点逐个插入到前半段节点中
    current = list
    while current && reverse_last_half
      current_next = current.next
      current.next = reverse_last_half
      reverse_last_half_next = reverse_last_half.next
      reverse_last_half.next = current_next
      current = current_next
      reverse_last_half = reverse_last_half_next
    end

    list
  end

  def reverse(list)
    return list if list.nil? || list.next.nil?
    prev = list
    current = prev.next
    next_item = current.next
    while current
      current.next = prev
      prev = current
      current = next_item
      next_item = next_item ? next_item.next : nil
    end

    list.next = nil
    ListNode.show(prev)
    prev
  end
end

d = ListNode.new(4)
c = ListNode.new(3,d)
b = ListNode.new(2,c)
a = ListNode.new(1,b)
list = ListNode.new(0, a)

# ListNode.show(list)

result = Solution.rl(list)

ListNode.show(result)

reverse_linked_list.rb

#!/usr/bin/env ruby
require_relative './list_node.rb'
module Solution
  extend self

  def rll(head)
    return nil if head.nil?
    prev = nil
    curr = head
    next_item = curr.next

    while !next_item.nil?
      curr.next = prev
      prev = curr
      curr = next_item
      next_item = next_item.next
    end

    curr.next = prev

    curr

  end
end

c = ListNode.new(3)
b = ListNode.new(2,c)
a = ListNode.new(1,b)
list = ListNode.new(0, a)

# ListNode.show(list)

result = Solution.rll(list)

ListNode.show(result)

reverse_node_in_k.rb

#!/usr/bin/env ruby
# given k not larger than list's length
require_relative './list_node.rb'
module Solution
  extend self

  def rnik(list, k)
    return list if list.nil? || list.next.nil? || k < 2
    dummy = ListNode.new(-1)
    dummy.next = list

    current = dummy
    slice_head = dummy.next
    slice_tail = dummy.next

    while slice_head

      i = 1
      temp = slice_head
      while i < k && temp
        slice_tail = temp.next
        temp = temp.next
        i += 1
      end

      break if slice_tail.nil?

      next_slice_head = slice_tail.next
      slice_tail.next = nil

      head, tail = reverse(slice_head)

      current.next = head
      tail.next = next_slice_head

      current = tail
      slice_head = next_slice_head

    end

    dummy.next
  end

  # 反转链表,并返回头尾节点
  def reverse(list)
    return [list,list] if list.nil? || list.next.nil?

    dummy = ListNode.new(-1)
    dummy.next = list
    prev = list
    current = prev.next
    next_item = current.next

    while current
      current.next = prev
      prev = current
      current = next_item
      next_item = next_item ? next_item.next : nil
    end

    dummy.next.next = nil
    tail = dummy.next
    dummy.next = prev

    [prev, tail]
  end
end

c = ListNode.new(3)
b = ListNode.new(2,c)
a = ListNode.new(1,b)
list = ListNode.new(0, a)

# ListNode.show(list)

# head, tail = Solution.reverse(list)

# puts "head #{head.val}"
# puts "tail #{tail.val}"

# ListNode.show(head)

result = Solution.rnik(list, 2)


ListNode.show(result)

rotate_image.rb

#!/usr/bin/env ruby

# rotate 2D images, clockwise, 90deg
module Solution
  extend self
  def ri(matrix)
    #up_down_fold
    #switch
    row = matrix.length
    col = matrix[0].length
    j = 0
    while j < row / 2
      up_row = matrix[j]
      down_row = matrix[row-j-1]

      i = 0
      while i < col
        up_row[i],down_row[i] = down_row[i], up_row[i]
        i += 1
      end

      j += 1
    end

    j = 0
    while j < row
      i = j + 1
      while i < col
        matrix[j][i],matrix[i][j] = matrix[i][j],matrix[j][i]
        i += 1
      end
      j += 1
    end
    matrix
  end
end

puts Solution.ri([[1,2],[3,4]])
puts Solution.ri([[1,2,3],[4,5,6],[7,8,9]])

simplify_path.rb

#!/usr/bin/env ruby
#
module Solution
  extend self

  def sp(str)
    states = []
    inputs = str.split('/')
    inputs.each do |dir|
      case dir
        when /\w+/
          states << dir
        when /\.\./
          if states.last == nil
            states << nil
          else
            states.pop
          end
      end
    end
    '/' + states.join('/')
  end
end

r = Solution.sp('/a/./b/c')
r = Solution.sp('/a/./b/../../c/')
r = Solution.sp('/../')
r = Solution.sp('/home////a/')

puts r

stack.rb

#!/usr/bin/env ruby

class Stack

  def initialize
    @head = DualListNode.new(-1)
    @tail = DualListNode.new(-1)
    @head.next = @tail
    @tail.prev = @head
  end

  def push val
    current_ = @tail.prev
    @tail.prev = DualListNode.new(val, current_, @tail)
    current_.next = @tail.prev

    val
  end

  def empty?
    @head.next == @tail
  end

  def top
    if empty?
      return nil
    end
    @tail.prev.val
  end

  def pop
    if empty?
      return nil
    end
    current_ = @tail.prev
    prev_ = current_.prev
    prev_.next = current_.next
    current_.next = nil
    @tail.prev = current_.prev
    current_.prev = nil

    current_.val
  end

  def show
    current = @head.next
    str = '@head=>'
    while current != @tail
      str << (current.val.to_s + '=>')
      current = current.next
    end

    str << '@tail'
  end

  private
  class DualListNode
    attr_accessor :val, :prev, :next
    def initialize(value, pv = nil, nx = nil)
      @val = value
      @next = nx
      @prev = pv
    end
  end
end


# stack = Stack.new
# stack.push(1)
# stack.push(2)
# stack.push(3)
# stack.top
# stack.push(4)
# stack.pop
# stack.pop
# stack.pop
#
# puts stack.top.inspect

str_str.rb

#!/usr/bin/env ruby
module Solution
  extend self
  def strstr(str1, str2)
    return nil if str2.length > str1.length
    index = 0
    current = 0
    found = false
    while index <= str1.length - str2.length
      while current < str2.length && str1[index + current] == str2[current]
        current += 1
      end
      if current >= str2.length
        found = true
        break
      end
      index += 1
    end

    found ? index : nil
  end

  #Rabin-Karp
  # Num 是随便取的一个较大的质数
  Num = 997
  # R 是 ascii 码的进制
  R = 128
  def strstr2(str1, str2)

    return nil if str2.length > str1.length

    len1 = str1.length
    len2 = str2.length

    # 保存字符串最大值是进制的多少倍,取余防止数值太大
    i = 0
    rm = 1
    while i < len2 - 1
      rm = rm * R % Num
      i += 1
    end

    target = calc(str2)

    hash = calc(str1[0,len2])
    current = 0
    while hash != target && current < len1 - len2
      # 计算下一个字符串的 hash 值
      # 思路是现有值减去最大的那一位,再整体乘以进制,最后加上新的下一位
      # (hash + Num) 只是防止减出负数来
      hash = (((hash + Num) - str1[current].ord * rm % Num) % Num * R + str1[current + len2].ord) % Num
      current += 1
    end

    if hash == target
      current
    else
      nil
    end

  end
  # 计算字符串的 hash 值
  # 从左到右计算字符串的 hash 值,适当地对结果取余,防止数值过大
  def calc(str)
    sum = 0
    i = 0
    while i < str.length
      sum = (sum * R + str[i].ord) % Num
      i += 1
    end
    sum
  end
  #Rabin-Karp

  #Boyer-Moore
  def strstr3(str1, str2)
    #要建立一个记录元素最右位置的跳跃表
    right = {}
    i = 0
    len1 = str1.length
    len2 = str2.length

    while i < len2
      right[str2[i]] = i
      i += 1
    end
    index = 0
    current = len2 - 1

    while index <= len1 - len2
      while current > -1 && str2[current] == str1[index + current]

        current -= 1
      end

      if current <= -1
        break
      end

      if right[str1[index + current]]
        if right[str1[index + current]] > current
          right_step = 1
        else
          right_step = current - right[str1[index + current]]
        end
      else
        right_step = len2
      end
      current = len2 - 1
      index += right_step
    end

    if current <= -1
      index
    else
      nil
    end

  end
  #Boyer-Moore

end

# r = Solution.strstr3('abc','abc')
# r = Solution.strstr3('abc','bc')
# r = Solution.strstr3('abc','ab')
# r = Solution.strstr3('bca','d')
# r = Solution.strstr3('bca','a')
r = Solution.strstr3('findinahaystackneedle','needle')

puts "result #{r}"

swap_nodes_in_pairs.rb

#!/usr/bin/env ruby
require_relative './list_node.rb'
module Solution
  extend self

  def snip(list)
    return list if list.nil? || list.next.nil?
    dummy = ListNode.new(-1)
    dummy.next = list
    prev = dummy
    current = list
    next_item = current.next


    while next_item
      prev.next = current.next
      current.next = next_item.next
      next_item.next = current

      prev = current
      if current.next.nil?
        break
      else
        current = current.next
      end
      if current.next.nil?
        break
      else
        next_item = current.next
      end
    end

    dummy.next
  end
end

e = ListNode.new(5)
d = ListNode.new(4)
c = ListNode.new(3,d)
b = ListNode.new(2,c)
a = ListNode.new(1,b)
list = ListNode.new(0, a)

result = Solution.snip(list)

ListNode.show(result)

trapping_rain_water.rb

#!/usr/bin/env ruby
module Solution
  extend self
  def trw(arr)
    left_side_higher = Array.new(arr.length, 0)
    right_side_higher = Array.new(arr.length, 0)

    arr.each_with_index do |item, index|
      if index > 0
        left_side_higher[index] = [left_side_higher[index-1], item].max
      else
        left_side_higher[index] = item
      end
    end
    i = arr.length - 1
    while i >= 0
      if i == arr.length - 1
        right_side_higher[i] = arr[i]
      else
        right_side_higher[i] = [right_side_higher[i+1], arr[i]].max
      end
      i -= 1
    end
    sum = 0
    arr.each_with_index do |item, index|
      min_higher = [left_side_higher[index], right_side_higher[index]].min
      if min_higher > item
        sum += (min_higher - item)
      end
    end
    sum
  end
end

puts Solution.trw([0,1,0,3,1,0,1,3,2,1,2,1])

valid_number.rb

#!/usr/bin/env ruby
#http://www.bo-song.com/leetcode-valid-number/

#判断一个字符串是否是 数字
#可以是开关和结尾有空格
#可以有正负号
#可以用科学记数法

#思路是根据上面的规则写正则表达式
#然后把正则表达式翻译成 确定有限状态自动机

#1 包含 正负号和数字
# (-|\+)?\d+
#2 在 1 的基础上 包含小数
# (-|\+)?(\d+|\d+\.|\d+\.\d+|\.\d+) => (-|\+)?(\d+\.?\d*|\.\d+)
#3 在 2 的基础上 包含科学记数法
# (-|\+)?(\d+\.?\d*|\.\d+)(e(-|\+)?\d+)?

#画出 DFA 之后，用二维数组代表在每个状态下面对可能的输入，应该跳转到的下一个状态

module Solution
  extend self

  def vn(str)
    trim_str = str.strip
    # 有 5 种输入: 正负号/数字/小数点/e/其他
    # 有 9 个状态(包含一个非法状态)
    mapping = [
        [1,3,2,-1,-1], # 初始状态 0 ,分别对应 5 种输入跳转到其他状态
        [-1,3,2,-1,-1], # 状态 1
        [-1,4,-1,-1,-1], # 状态 2
        [-1,3,4,5,-1], # 状态 3
        [-1,4,-1,5,-1], # 状态 4
        [6,7,-1,-1,-1], # 状态 5
        [-1,7,-1,-1,-1], # 状态 6
        [-1,7,-1,-1,-1], # 状态 7
    ]
    # 设定初始状态
    state = 0
    trim_str.each_char do |c|
      case c
        when /-|\+/
          state = mapping[state][0]
        when /\d/
          state = mapping[state][1]
        when /\./
          state = mapping[state][2]
        when /e/
          state = mapping[state][3]
        else
          state = mapping[state][4]
      end
      break if state == -1
    end
    [3,4,7].include?(state) ? true : false
  end
end

if Solution.vn('+0.1e102  ')
  puts 'valid number'
else
  puts 'not valid number'
end

valid_parentheses.rb

#!/usr/bin/env ruby

require_relative './stack.rb'

module Solution
  extend self

  def vp(str)
    valid = true
    stack = Stack.new
    mapping = {
        ')'=> '(',
        ']'=> '[',
        '}'=> '{'
    }
    str.each_char do |c|
      case c
        when /[\(\[\{]/
          stack.push c
        when /[\)\]\}]/
          if stack.empty?
            valid = false
            break
          elsif stack.top == mapping[c]
            stack.pop
          else
            valid = false
            break
          end
      end
    end
    valid
  end
end

puts Solution.vp('([])')

validate_palindrome.rb

#!/usr/bin/env ruby
module Solution
  extend self

  def vp(str)
    return true if str.nil? || str.length < 2
    head = 0
    tail = str.length - 1
    is_palindrome = true
    while head < tail
      while str[head] && !(65..122).include?(str[head].ord)
        head += 1
      end
      while str[tail] && !(65..122).include?(str[tail].ord)
        tail -= 1
      end
      if str[head].downcase != str[tail].downcase
        is_palindrome = false
        break
      else
        head += 1
        tail -= 1
      end
    end
    is_palindrome
  end
end

# result = Solution.vp("A man, a plan, a canal: Panama")
# result = Solution.vp("race a car")
# result = Solution.vp("")
# result = Solution.vp("a")
result = Solution.vp("aa")

if result
  puts 'is palindrome'
else
  puts 'is not palindrome'
end

validate_sukodu.rb

#!/usr/bin/env ruby
module Solution
  extend self

  def vs(matrix)
    def checkX(matrix, current, i)
      return true if current == 0
      ocurrents = 0
      9.times do |x|
        if matrix[i][x] == current
          ocurrents += 1
        end
      end
      puts "#{current} #{i} : #{ocurrents}"
      ocurrents == 1
    end
    def checkY(matrix, current, j)
      return true if current == 0
      ocurrents = 0
      9.times do |x|
        if matrix[x][j] == current
          ocurrents += 1
        end
      end
      ocurrents == 1
    end

    def checkG(matrix, current, i, j)
      return true if current == 0
      near_x = (i / 3) * 3 + 1
      near_y = (j / 3) * 3 + 1
      ocurrents = 0
      ((near_x - 1)..(near_x + 1)).each do |x|
        ((near_y - 1)..(near_y + 1)).each do |y|
          if matrix[x][y] == current
            ocurrents += 1
          end
        end
      end
      ocurrents == 1
    end
    valid = true
    9.times do |i|
      9.times do |j|
        current = matrix[i][j]
        valid = checkX(matrix, current, i) && checkY(matrix, current, j) && checkG(matrix, current, i,j)
        break if !valid
      end
      break if !valid
    end
    valid

  end
end

puts Solution.vs([[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]])

wildcard_matching.rb

#!/usr/bin/env ruby
module Solution
  extend self

  def wm(s, p)
    # p 为空字符串
    return s.empty? if p.empty?

    # p 长度为 1
    if p.length == 1
      return (s.length == 1 && (s[0] == p[0] || p[0] == '?')) || p[0] == '*'
    end
    # p 长度大于 1 ,且第一个字符不是 *
    if p[0] != '*'
      return !s.empty? && (s[0] == p[0] || p[0] == '?') && wm(s[1..-1], p[1..-1])
    end
    # p 长度大于 1 ,且第一个字符是 *
    while !s.empty?
      return true if wm(s, m[1..-1])
      s = s[1..-1]
    end

    return wm(s, m[1..-1])

  end
end

if Solution.wm('ab', '?*')
  puts 'match'
else
  puts 'not match'
end