闲来无事，不如试着用ruby刷刷题
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
solution:
# @param {Integer[]} nums # @param {Integer} target # @return {Integer[]} def two_sum(nums, target) hash = {} nums.each_with_index do |number, index| if hash[target - number] return [hash[target - number], index] else hash[number] = index end end end
Given a 32-bit signed integer, reverse digits of an integer.
Example 1:
Input: 123 Output: 321
Example 2:
Input: -123 Output: -321
Example 3:
Input: 120 Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
Solution:
# @param {Integer} x # @return {Integer} def reverse(x) if x.negative? x = (x.to_s.reverse.to_i * -1) else x = x.to_s.reverse.to_i end x.bit_length > 31 ? 0 : x end
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Example 1:
Input: 121 Output: true
Example 2:
Input: -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:
Input: 10 Output: false Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Follow up:
Coud you solve it without converting the integer to a string?
Solution
# @param {Integer} s # @return {Boolean} def is_palindrome(s) s.to_s ==s.to_s.reverse end
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000
For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
Ican be placed beforeV(5) andX(10) to make 4 and 9.Xcan be placed beforeL(50) andC(100) to make 40 and 90.Ccan be placed beforeD(500) andM(1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
Example 1:
Input: "III" Output: 3
Example 2:
Input: "IV" Output: 4
Example 3:
Input: "IX" Output: 9
Example 4:
Input: "LVIII" Output: 58 Explanation: L = 50, V= 5, III = 3.
Example 5:
Input: "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Solution:
# @param {String} s # @return {Integer} def roman_to_int(s) hash = { 'I' => 1, 'V' => 5, 'X' => 10, 'L' => 50, 'C' => 100, 'D' => 500, 'M' => 1000 } total = 0 prev = s[0] s.each_char do |curr_char| if hash[curr_char] > hash[prev] total -= hash[prev] total += (hash[curr_char] - hash[prev]) else total += hash[curr_char] end prev = curr_char end return total end
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll" Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba" Output: -1
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
Constraints:
haystackandneedleconsist only of lowercase English characters.
Solution:
# @param {String} haystack # @param {String} needle # @return {Integer} def str_str(haystack, needle) return haystack.index(needle).nil? ? -1: haystack.index(needle) end
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5 Output: 2
Example 2:
Input: [1,3,5,6], 2 Output: 1
Example 3:
Input: [1,3,5,6], 7 Output: 4
Example 4:
Input: [1,3,5,6], 0 Output: 0
Solution:
# @param {Integer[]} nums # @param {Integer} target # @return {Integer} def search_insert(nums, target) return 0 if nums.nil? nums.each_with_index{|num,idx| if num>=target return idx end } return nums.length end
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Solution:
# @param {Integer[]} nums # @return {Integer} def max_sub_array(nums) best, curr = nums[0], 0; nums.each { |n| best = [best, curr = [n, curr+n].max].max }; best end
Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word (last word means the last appearing word if we loop from left to right) in the string.
If the last word does not exist, return 0.
Note: A word is defined as a maximal substring consisting of non-space characters only.
Example:
Input: "Hello World" Output: 5
# @param {String} s # @return {Integer} def length_of_last_word(s) return 0 if s.length ==0 s.split("s").last.nil? ? 0: s.split("s").last.length end
Given a non-empty array of digits representing a non-negative integer, increment one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.
Example 1:
Input: [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123.
Example 2:
Input: [4,3,2,1] Output: [4,3,2,2] Explanation: The array represents the integer 4321.
Solution:
# @param {Integer[]} digits # @return {Integer[]} def plus_one(digits) arr =[] digits.shift if digits[0] ==0 digits = digits.join(",").gsub(",","").to_i+1 digits.to_s.each_char{|c| arr<<c.to_i} arr end
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Example 1:
Input: 1 1
/ /
2 3 2 3
[1,2,3], [1,2,3]
Output: true
Example 2:
Input: 1 1
/
2 2
[1,2], [1,null,2]
Output: false
Solution 1:
# Definition for a binary tree node. # class TreeNode # attr_accessor :val, :left, :right # def initialize(val = 0, left = nil, right = nil) # @val = val # @left = left # @right = right # end # end # @param {TreeNode} p # @param {TreeNode} q # @return {Boolean} def is_same_tree(p, q) return true if p.nil? && q.nil? return (is_same_tree(p.left, q.left) && is_same_tree(p.right, q.right)) if p&.val == q&.val false end
Solution 2：面向对象OOP 解法：
# Definition for a binary tree node. # class TreeNode # attr_accessor :val, :left, :right # def initialize(val = 0, left = nil, right = nil) # @val = val # @left = left # @right = right # end # end # # @param {TreeNode} p # @param {TreeNode} q # @return {Boolean} class TreeNode # 重写方法 def ==(tree) val == tree&.val && left == tree&.left && right == tree&.right end end def is_same_tree(p, q) p == q end