Ruby Leetcode

编程/技术 2019-06-20 @ 08:34:59 浏览数: 102 净访问: 71 By: skyrover

本博客采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本博客文章必须也遵循署名-非商业用途-保持一致的创作共用协议


要想学好一门语言,就得多用它。而刷leetcode既练习了算法,又能够深入掌握一门语言。

这里是Ruby刷题记录

2019-06-20

561. 数组拆分 I

最近进入这种状态:突然发现Ruby的语法很不适应,觉得不如Python简单。。

# @param {Integer[]} nums
# @return {Integer}
def array_pair_sum(nums)
  nums.sort!
  res = 0
  nums.each_with_index do |n, index|
    if index % 2 == 0
      res += n
    end
  end
  return res
end

944. 删列造序

一开始是这样的,但是会出错,具体原因未知

def min_deletion_size(a)
  # 将所有需要删除的删除掉,就可以了
  # 也就是相当于统计下降序的列数
  row = a.size
  col = a[0].size
  deleted = 0
  for j in 0...col
    for i in 1...row
      if a[i][j] < a[i-1][j]
        deleted += 1
        break
      end
    end
  end
  return deleted
end

后来改了一下,就可以了

def min_deletion_size1(a)
  ans = 0
  n = a[0].size
  m = a.size - 1
  n.times do |i|
    m.times do |j|
      if a[j][i] > a[j+1][i]
        ans += 1
        break
      end
    end
  end
  ans
end

2019-06-19

929. 独特的电子邮件地址

def num_unique_emails(emails)
  res = []
  emails.each do |email|
    ans = email.split('@')
    ans[0] = ans[0].split('+')[0]
    ans[0].gsub!(".", "")
    res.push(ans[0] << "@" << ans[1])
  end
  return (res | res).size
end

961. 重复 N 次的元素

def repeated_n_times(a)
  # 这道题用哈希表当然可以做,但是可以有更trick的方法
  # 因为2N个数组,至少有N次重复,那么将数组排序后
  # 重复元素一定在最中间元素左边或者右边
  a.sort!
  if a[a.size/2] == a[a.size/2 + 1]
    return a[a.size/2]
  else
    return a[a.size/2-1]
  end
end

500. 键盘行

笨办法,但是使用了Ruby的全局变量

line_1 = "qwertyuiop"
line_2 = "asdfghjkl"
line_3 = "zxcvbnm"
$word_map = {}
line_1.each_char do |item|
  $word_map[item] = 1
end
line_2.each_char do |item|
  $word_map[item] = 2
end
line_3.each_char do |item|
  $word_map[item] = 3
end

def find_words(words)
  res = []
  words.each do |item|
    if same_line(item)
      res.push(item)
    end
  end
  return res
end


def same_line(item)
  line = 0
  item.each_char{|s|
    s = s.downcase
    if line == 0
      line = $word_map[s]
    elsif line != $word_map[s]
      return false
    end
  }
  return true
end

使用字符串的delete方法,返回 str 的副本,参数交集中的所有字符会被删除。

def find_words(words)
  a = ["qwertyuiop", "asdfghjkl", "zxcvbnm"]
  words.select do |word|
    s = word.downcase
    s.delete(a[0]).empty? || s.delete(a[1]).empty? || s.delete(a[2]).empty?
  end
end

933. 最近的请求次数

class RecentCounter
  def initialize()
    @counter = []
  end


=begin
    :type t: Integer
    :rtype: Integer
=end
  def ping(t)
    threshold = t - 3000
    while !@counter.empty? and @counter[0] < threshold
      @counter.shift
    end
    @counter.push(t)
    return @counter.size
  end


end

344. 反转字符串

# @param {Character[]} s
# @return {Void} Do not return anything, modify s in-place instead.
def reverse_string(s)
  i = 0
  j = s.size - 1
  while i < j
    s[i], s[j] = s[j], s[i]
    i += 1
    j -= 1
  end
  return s
end

905. 按奇偶排序数组

def sort_array_by_parity(a)
  res = []
  a.each do |item|
    if item % 2 == 0
      res.unshift(item)
    else
      res.push(item)
    end
  end
  return res
end

双指针法

def sort_array_by_parity(a)
  i = 0
  j = a.size - 1
  while i < j
    while i < j and a[i] % 2 == 0
      i += 1
    end
    while i < j and a[j] % 2 != 0
      j -= 1
    end
    if i >= j
      break
    end
    a[i], a[j] = a[j], a[i]
  end
  return a
end

476. 数字的补数

def find_complement(num)
  res = ""
  num.to_s(2).each_char do |item|
    res.concat(item == "1" ? "0" : "1")
  end
  return res.to_i(2)
end

700. 二叉搜索树中的搜索

def search_bst(root, val)
  if root.nil?
    return nil
  end
  if root.val == val
    return root
  elsif val > root.val
    return search_bst(root.right, val)
  else
    return search_bst(root.left, val)
  end
end

852. 山脉数组的峰顶索引

其实就是2分法,要注意条件

# @param {Integer[]} a
# @return {Integer}
def peak_index_in_mountain_array(a)
  left = 0
  right = a.size
  while left < right
    mid = left + (right - left) / 2
    if a[mid-1] < a[mid] and a[mid] > a[mid+1]
      return mid
    elsif a[mid] >= a[mid-1]
      left = mid+1
    elsif a[mid] >= a[mid+1]
      right = mid
    end
  end
end

728. 自除数

def self_dividing_numbers(left, right)
  nums = left..right
  nums = nums.select do |num|
    cond = true
    old_num = num
    while num > 0
      ans = num.divmod(10)
      num, remain = ans[0], ans[1]
      if remain != 0 and old_num % remain != 0
        cond = false
        break
      elsif remain == 0
        cond = false
        break
      end
    end
    cond
  end
  return nums
end

292. Nim 游戏

所以题目实在没有辙,就找规律吧

# @param {Integer} n
# @return {Boolean}
def can_win_nim(n)
  # 4的时候赢不了,5,6,7都可以赢(对应先拿1个,2个,3个),也就是让对手进入剩4个的状态
  # 所以可以推到8个的时候赢不了(让对手进入了5,6,7状态),所以9,10,11可以赢,12不行
  # 找到规律 n%4!=0
  return n % 4 != 0
end

2019-06-18

942. 增减字符串匹配

def di_string_match(s)
  nums = (0..s.size).to_a
  res = []
  s.each_char do |item|
    if item == "I"
      res.push(nums.shift)
    else
      res.push(nums.pop)
    end
  end
  res.concat(nums)
  return res
end

104. 二叉树的最大深度

def max_depth(root)
  if root.nil?
    return 0
  end
  left_depth = max_depth(root.left)
  right_depth = max_depth(root.right)
  return [left_depth, right_depth].max + 1
end

1051. 高度检查器

def height_checker(heights)
  sort_heights = heights.sort
  count = 0
  heights.zip(sort_heights) do |height, sort_height|
    if height != sort_height
      count += 1
    end
  end
  return count
end

226. 翻转二叉树

def invert_tree(root)
  if root.nil?
    return
  end
  invert_tree(root.left)
  invert_tree(root.right)
  root.left, root.right = root.right, root.left
  return root
end

461. 汉明距离

def hamming_distance(x, y)
  return (x^y).to_s(2).count('1')
end

657. 机器人能否返回原点

最直观的解法

def judge_circle(moves)
  move_map = {
      "U" => [0, 1],
      "D" => [0, -1],
      "L" => [-1, 0],
      "R" => [1, 0]
  }
  origin = [0, 0]
  moves.each_char do |item|
    move_step = move_map[item]
    origin[0] += move_step[0]
    origin[1] += move_step[1]
  end
  return origin == [0, 0]
end

精巧的解法

def judge_circle(moves)
  return moves.count('U') == moves.count('D') && moves.count('L') == moves.count('R')
end

977. 有序数组的平方

太精简了

def sorted_squares(a)
  a.map!{|item| item ** 2}
  a.sort!
  return a
end

617. 合并二叉树

发现Ruby的执行效率比Python高

def merge_trees(t1, t2)
  if t1.nil? and t2.nil?
    return
  end
  if t1.nil? and !t2.nil?
    return t2
  elsif !t1.nil? and t2.nil?
    return t1
  else
    t1.val += t2.val
    t1.left = merge_trees(t1.left, t2.left)
    t1.right = merge_trees(t1.right, t2.right)
    return t1
  end
end

804. 唯一摩尔斯密码词

# @param {String[]} words
# @return {Integer}
def unique_morse_representations(words)
  word_map = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
  morse = []
  words.each do |item|
    morse_res = ""
    item.each_char do |item_char|
      morse_res << word_map[item_char.ord - 97]
    end
    if !morse.include?(morse_res)
      morse.push(morse_res)
    end
  end
  return morse.size
end

2019-06-17

832. 翻转图像

def flip_and_invert_image(a)
  row_len = a.size
  col_len = a[0].size
  i = 0
  while i < row_len
    a[i].reverse!
    j = 0
    while j < col_len
      a[i][j] = a[i][j] == 1 ? 0 : 1
      j += 1
    end
    i += 1
  end
  return a
end

709. 转换成小写字母

def to_lower_case(str)
  res = ""
  str.each_char do |item|
    item_ord = item.ord
    if 65 <= item_ord and item_ord <= 90
      res.concat((item_ord + 32).chr)
    else
      res.concat(item)
    end
  end
  return res
end

另一种直接调用现有方法的

def to_lower_case(str)
  return str.downcase
end

237. 删除链表中的节点

这道题是脑筋急转弯吧

def delete_node(node)
  node.val = node.next.val
  node.next = node.next.next
end

938. 二叉搜索树的范围和

# 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
# @param {Integer} l
# @param {Integer} r
# @return {Integer}
def traverse_sum(node, l, r)
  if node.nil?
    return 0
  end
  if node.val < l
    sub_left_sum = 0
    sub_right_sum = traverse_sum(node.right, l, r)
    node_val = 0
  elsif node.val > r
    sub_left_sum = traverse_sum(node.left, l, r)
    sub_right_sum = 0
    node_val = 0
  else
    sub_left_sum = traverse_sum(node.left, l, r)
    sub_right_sum = traverse_sum(node.right, l, r)
    node_val = node.val
  end
  return sub_left_sum + sub_right_sum + node_val
end

def range_sum_bst(root, l, r)
  if root.nil?
    return 0
  end
  return traverse_sum(root, l, r)
end

2019-06-16

1021. 删除最外层的括号

虽然算法很简单,但是切换一个语言真是有点记不清楚,不太熟练。。

def remove_outer_parentheses(s)
  stack = [s[0]]
  i = 1
  start = 0
  res = ""
  length = s.size
  while i < length
    ele = s[i]
    if stack[-1] == "(" and ele == ")"
      stack.pop
    elsif stack.empty?
      res.concat(s[start+1...i-1])
      start = i
      stack.push(ele)
    else
      stack.push(ele)
    end
    i += 1
  end
  res.concat(s[start+1...length-1])
  return res
end

771. 宝石与石头

# @param {String} j
# @param {String} s
# @return {Integer}
def num_jewels_in_stones(j, s)
  count = Hash.new(0)
  s.each_char do |item|
    count[item] += 1
  end
  res = 0
  j.each_char do |item|
    if count.key?(item)
      res += count[item]
    end
  end
  return res
end

其实还有一种更简单的方法,直接调用字符串的count方法

# @param {String} j
# @param {String} s
# @return {Integer}
def num_jewels_in_stones(j, s)
  s.count(j)
end


点赞走一波😏


评论

提交评论