LEETCODE leetcode.com 一个在线编程网站, 收集了 IT 公司的面试题, 包括算法, 数据库和 shell 算法题支持多种语言, 包括 C, C++, Java, Python 等 2015 年 3 月份加入了 R

Size: px

Start display at page:

Download "LEETCODE leetcode.com 一个在线编程网站, 收集了 IT 公司的面试题, 包括算法, 数据库和 shell 算法题支持多种语言, 包括 C, C++, Java, Python 等 2015 年 3 月份加入了 R"

徵玳慕
9 years ago
Views:

1 用 RUBY 解 LEETCODE 算法题 RUBY CONF CHINA 2015

2 LEETCODE leetcode.com 一个在线编程网站, 收集了 IT 公司的面试题, 包括算法, 数据库和 shell 算法题支持多种语言, 包括 C, C++, Java, Python 等 2015 年 3 月份加入了 Ruby 的支持

3 算法题编程界面

4 为什么要做算法题面试 - 涵盖了各种经典算法题学习 - 理解数据结构和解题思路休闲 - 每天花 5~30 分钟做几道题目

5 为什么要用 RUBY 来做算法题体验 Ruby 语言的生产力学习 Ruby 的不常用方法其他的语言... 我不熟 :(

6 // 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].

7 体验 RUBY 语言的生产力 (I) Permutations def permute(nums) nums.permutation.to_a

8 体验 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

9 体验 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: = 11, = 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)

10 学习 RUBY 的不常用方法 (I) Add Binary Given two binary strings, return their sum (also a binary string). For example, a = "11" b = "1" Return "100". {String} a {String} b {String} def add_binary(a, b) (a.to_i(2) + b.to_i(2)).to_s(2)

11 学习 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). {Integer[]} prices {Integer} def max_profit(prices) prices.each_cons(2).inject(0){ s,a [s+a[1]-a[0], s].max}

12 学习 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"] ] {String[]} strs {String[][]} def group_anagrams(strs) strs.inject(hash.new([])) do h, s h[s.chars.sort.join] += [s] h.map{ k, v v.sort}

13 关于作弊 (I) Regular Expression Matching Implement regular expression matching with support for '.' and '*'.

14 关于作弊 (I) 使用 Ruby 内置对象 {String} s {String} p {Boolean} def is_match(s, p) s =~ /^#{p}$/? true : false

15 关于作弊 (II) Count Primes Count the number of prime numbers less than a non-negative number.

16 关于作弊 (II) require {Integer} n {Integer} require 'prime' def count_primes(n) Prime.each(n - 1).count

17 关于作弊 (III) N-Queens II Follow up for N-Queens problem. Now, instead outputting board config urations, return the total number of distinct solutions.

18 关于作弊 (III) Test Driven Development {Integer} n {Integer} def total_n_queens(n) [0,1,0,0,2,10,4,40,92,352,724,2680,14200,73712, , , , , ][n]

19 我的解法 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: = 11, = 2. Since 2 has only one digit, return it. Follow up: Could you do it without any loop/recursion in O(1) runtime? # def add_digits(num) 1 + (num - 1) % 9 类似直接用算数公式证明的题目比如 :Perfect Squares

20 我的解法 V.S 别人的解法 (II) Single Number Given an array of integers, every element appears twice except for o ne. Find that single one. {Integer[]} nums {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 系列的通用解法

21 我的解法 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. {Integer[]} nums {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] 算法出处以及单步演示

22 刷题能帮我应聘到好职位吗? 我也不知道呢... 不过... 如果你刷了很多 Leetcode, 想换个工作的话... 我们正在招聘 Ruby 程序员, 投递简历到邮箱 : [email protected] 毫无广告植入痕迹 ^_^

23 Q & A

C/C++ - 字符输入输出和字符确认

C/C++ - 字符输入输出和字符确认 C/C++ Table of contents 1. 2. getchar() putchar() 3. (Buffer) 4. 5. 6. 7. 8. 1 2 3 1 // pseudo code 2 read a character 3 while there is more input 4 increment character count 5 if a line has been read,

LEETCODE leetcode.com 一 个 在 线 编 程 网 站, 收 集 了 IT 公 司 的 面 试 题, 包 括 算 法, 数 据 库 和 shell 算 法 题 支 持 多 种 语 言, 包 括 C, C++, Java, Python 等 2015 年 3 月 份 加 入 了 R

LEETCODE leetcode.com 一个在线编程网站, 收集了 IT 公司的面试题, 包括算法, 数据库和 shell 算法题支持多种语言, 包括 C, C++, Java, Python 等 2015 年 3 月份加入了 R