Ruby on LeetCode
Ruby on LeetCode

你能在LeetCode看到很多面试题,用ruby,就是在开挂。PS: 仅限水题:)

Directory

1. Two Sum

原题two-sum

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
  hash = {}                 # 记录已经遍历的元素n和其下标i
  nums.each_with_index do |n, i|
    if hash[target - n]
      return [hash[target - n], i]
    else
      hash[n] = i
    end
  end
end

7. Reverse Integer

原题reverse-integer

# @param {Integer} x
# @return {Integer}
def reverse(x)
  tag = x > 0 ? 1 : -1
  ans = x.abs.to_s.reverse.to_i * tag
  ans.abs > 2147483647 ? 0 : ans
end

8. String to Integer (atoi)

原题string-to-integer-atoi

# @param {String} str
# @return {Integer}
def my_atoi(str)
  ans = str.to_i
  if ans > 0
    ans > 2147483647 ? 2147483647 : ans
  else
    ans < -2147483648 ? -2147483648 : ans
  end
end

9. Palindrome Number

原题palindrome-number

# @param {Integer} x
# @return {Boolean}
def is_palindrome(x)
  x.to_s == x.to_s.reverse
end

46. Permutations

原题permutations

# @param {Integer[]} nums
# @return {Integer[][]}
def permute(nums)
  nums.permutation.to_a
end

67. Add Binary

原题add-binary

# @param {String} a
# @param {String} b
# @return {String}
def add_binary(a, b)
  (a.to_i(2) + b.to_i(2)).to_s(2)
end

94. Binary Tree Inorder Traversal

原题binary-tree-inorder-traversal

# Definition for a binary tree node.
# class TreeNode
#   attr_accessor :val, :left, :right
#   def initialize(val)
#     @val = val
#     @left, @right = nil, nil
#   end
# end

# @param {TreeNode} root
# @return {Integer[]}
def inorder_traversal(root)
  return [] if root.nil?
  inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)
end

100. Same Tree

原题same-tree

# Definition for a binary tree node.
# class TreeNode
#   attr_accessor :val, :left, :right
#   def initialize(val)
#     @val = val
#     @left, @right = nil, nil
#   end
# end

# @param {TreeNode} p
# @param {TreeNode} q
# @return {Boolean}
def is_same_tree(p, q)
  return true if p.nil? && q.nil?
  return false if p.nil? || q.nil? || p.val != q.val
  is_same_tree(p.left, q.left) && is_same_tree(p.right, q.right)
end

104. Maximum Depth of Binary Tree

原题maximum-depth-of-binary-tree

# Definition for a binary tree node.
# class TreeNode
#   attr_accessor :val, :left, :right
#   def initialize(val)
#     @val = val
#     @left, @right = nil, nil
#   end
# end

# @param {TreeNode} root
# @return {Integer}
def max_depth (root)
  return 0 if root.nil?
  left_depth = max_depth(root.left)
  right_depth = max_depth(root.right)
  1 + (left_depth > right_depth ? left_depth : right_depth)
end

136. Single Number

原题single-number

# @param {Integer[]} nums
# @return {Integer}
def single_number(nums)
  nums.reduce(0) { |s, n| s ^ n }
end

144. Binary Tree Preorder Traversal

原题binary-tree-preorder-traversal

# Definition for a binary tree node.
# class TreeNode
#   attr_accessor :val, :left, :right
#   def initialize(val)
#     @val = val
#     @left, @right = nil, nil
#   end
# end

# @param {TreeNode} root
# @return {Integer[]}
def preorder_traversal(root)
  return [] if root.nil?
  [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)
end

169. Majority Element

原题majority-element

# @param {Integer[]} nums
# @return {Integer}
def majority_element(nums)
  nums.sort[nums.size / 2]
end

231. Power of Two

原题power-of-two

# @param {Integer} n
# @return {Boolean}
def is_power_of_two(n)
  n > 0 ? n & (n - 1) == 0 : false
end

242. Valid Anagram

原题valid-anagram

# @param {String} s
# @param {String} t
# @return {Boolean}
def is_anagram(s, t)
  s.chars.sort == t.chars.sort
end

258. Add Digits

原题add-digits

# @param {Integer} num
# @return {Integer}
def add_digits(num)
  num < 10 ? num : 1 + (num - 1) % 9
end

268. Missing Number

原题missing-number

# @param {Integer[]} nums
# @return {Integer}
def missing_number(nums)
  nums.size * (nums.size + 1) / 2 - nums.inject(:+)
end

292. Nim Game

原题nim-game

# @param {Integer} n
# @return {Boolean}
def can_win_nim(n)
  n % 4 != 0
end

326. Power of Three

原题power-of-three

# @param {Integer} n
# @return {Boolean}
def is_power_of_three(n)
  n > 0 && 1162261467 % n == 0
end

342. Power of Four

原题power-of-four

# @param {Integer} num
# @return {Boolean}
def is_power_of_four(num)
  num > 0 && num & (num - 1) == 0 && (num - 1) % 3 == 0
end

344. Reverse String

原题reverse-string

# @param {String} s
# @return {String}
def reverse_string(s)
  s.reverse
end

349. Intersection of Two Arrays

原题intersection-of-two-arrays

# @param {Integer[]} nums1
# @param {Integer[]} nums2
# @return {Integer[]}
def intersection(nums1, nums2)
  nums1 & nums2
end