用 RUBY 解 LEETCODE 算 法 题 RUBY CONF CHINA 2015 By @quakewang
LEETCODE leetcode.com 一 个 在 线 编 程 网 站, 收 集 了 IT 公 司 的 面 试 题, 包 括 算 法, 数 据 库 和 shell 算 法 题 支 持 多 种 语 言, 包 括 C, C++, Java, Python 等 2015 年 3 月 份 加 入 了 Ruby 的 支 持
算 法 题 编 程 界 面
为 什 么 要 做 算 法 题 面 试 - 涵 盖 了 各 种 经 典 算 法 题 学 习 - 理 解 数 据 结 构 和 解 题 思 路 休 闲 - 每 天 花 5~30 分 钟 做 几 道 题 目
为 什 么 要 用 RUBY 来 做 算 法 题 体 验 Ruby 语 言 的 生 产 力 学 习 Ruby 的 不 常 用 方 法 其 他 的 语 言... 我 不 熟 :(
// Java public List<List<Integer>> permute(int[] num) { LinkedList<List<Integer>> res = new LinkedList<List<Integer>>(); res.add(new ArrayList<Integer>()); for (int n : num) { int size = res.size(); for (; size > 0; size--) { List<Integer> r = res.pollfirst(); for (int i = 0; i <= r.size(); i++) { List<Integer> t = new ArrayList<Integer>(r); t.add(i, n); res.add(t); } } } return res; 体 验 RUBY 语 言 的 生 产 力 (I) Permutations Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
体 验 RUBY 语 言 的 生 产 力 (I) Permutations def permute(nums) nums.permutation.to_a
体 验 RUBY 语 言 的 生 产 力 (II) Length of Last Word Given a string s consists of upper/lower-case alphabets and empty sp ace characters ' ', return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a character sequence consists of non-spac e characters only. For example, Given s = "Hello World", return 5. def length_of_last_word(s) words = s.split(' ') words.last? words.last.length : 0
体 验 RUBY 语 言 的 生 产 力 (III) Add Digits Given a non-negative integer num, repeatedly add all its digits unti l the result has only one digit. For example: Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it. def add_digits(num) r = num.to_s.chars.map(&:to_i).reduce(:+) r <= 9? r : add_digits(r)
学 习 RUBY 的 不 常 用 方 法 (I) Add Binary Given two binary strings, return their sum (also a binary string). For example, a = "11" b = "1" Return "100". # @param {String} a # @param {String} b # @return {String} def add_binary(a, b) (a.to_i(2) + b.to_i(2)).to_s(2)
学 习 RUBY 的 不 常 用 方 法 (II) Best Time to Buy and Sell Stock II Say you have an array for which the ith element is the price of a gi ven stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple tran sactions at the same time (ie, you must sell the stock before you bu y again). # @param {Integer[]} prices # @return {Integer} def max_profit(prices) prices.each_cons(2).inject(0){ s,a [s+a[1]-a[0], s].max}
学 习 RUBY 的 不 常 用 方 法 (III) Group Anagrams Given an array of strings, group anagrams together. For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return: [ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ] # @param {String[]} strs # @return {String[][]} def group_anagrams(strs) strs.inject(hash.new([])) do h, s h[s.chars.sort.join] += [s] h.map{ k, v v.sort}
关 于 作 弊 (I) Regular Expression Matching Implement regular expression matching with support for '.' and '*'.
关 于 作 弊 (I) 使 用 Ruby 内 置 对 象 # @param {String} s # @param {String} p # @return {Boolean} def is_match(s, p) s =~ /^#{p}$/? true : false
关 于 作 弊 (II) Count Primes Count the number of prime numbers less than a non-negative number.
关 于 作 弊 (II) require # @param {Integer} n # @return {Integer} require 'prime' def count_primes(n) Prime.each(n - 1).count
关 于 作 弊 (III) N-Queens II Follow up for N-Queens problem. Now, instead outputting board config urations, return the total number of distinct solutions.
关 于 作 弊 (III) Test Driven Development # @param {Integer} n # @return {Integer} def total_n_queens(n) [0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712, 365596,2279184,14772512,95815104,666090624][n]
我 的 解 法 V.S 别 人 的 解 法 (I) Add Digits Given a non-negative integer num, repeatedly add all its digits unti l the result has only one digit. For example: Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it. Follow up: Could you do it without any loop/recursion in O(1) runtime? # https://en.wikipedia.org/wiki/digital_root def add_digits(num) 1 + (num - 1) % 9 类 似 直 接 用 算 数 公 式 证 明 的 题 目 比 如 :Perfect Squares
我 的 解 法 V.S 别 人 的 解 法 (II) Single Number Given an array of integers, every element appears twice except for o ne. Find that single one. # @param {Integer[]} nums # @return {Integer} def single_number(nums) nums.sort.each_slice(2).find{ s s[0]!= s[1]}[0] def single_number(nums) nums.inject(:^) 用 XOR 操 作 解 Single Number 系 列 的 通 用 解 法
我 的 解 法 V.S 别 人 的 解 法 (III) Majority Element Given an array of size n, find the majority element. The majority el ement is the element that appears more than n/2 times.you may as sume that the array is non-empty and the majority element always exi st in the array. # @param {Integer[]} nums # @return {Integer} def majority_element(nums) nums.sort[nums.size/2] def majority_element(nums) nums.inject([0, 0]) { (x, c), i c == 0 x == i? [i, c+1] : [x, c-1] }[0] 算 法 出 处 以 及 单 步 演 示
刷 题 能 帮 我 应 聘 到 好 职 位 吗? 我 也 不 知 道 呢... 不 过... 如 果 你 刷 了 很 多 Leetcode, 想 换 个 工 作 的 话... 我 们 正 在 招 聘 Ruby 程 序 员, 投 递 简 历 到 邮 箱 : quake@chanyouji.com 毫 无 广 告 植 入 痕 迹 ^_^
Q & A