來個三題 LeetCode easy 吧

Leetcode 刷題

 2019/11/07

字數統計: 420閱讀時間: 2 min

近期被問到用 Ruby 解三題 LeetCode easy 題目，分別是：

題目

題目()：

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1
Example 2:

Input: [4,1,2,1,2]
Output: 4

# @param {Integer[]} nums
# @return {Integer}
def single_number(nums)

end

題目()：

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

Input: 38
Output: 2
Explanation: 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?

# @param {Integer} num
# @return {Integer}
def add_digits(num)

end

題目()：

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

# @param {Integer[]} nums
# @return {Integer[]}
def find_disappeared_numbers(nums)

end

答案

# 136. Single Number
def single_number(nums)
  # 原本寫法 (時間複雜度不會過)
  # nums.select{ |x| nums.count(x) == 1}.first


  # 後來寫法
  # XOR 數位邏輯的互斥或閘(XOR)
  nums.inject(:^)
end



# 258. Add Digits
def add_digits(num)
  # 原本寫法
  return num if num < 10
  add_digits(num / 10 + num % 10)


  # 後來寫法
  # 使用三元運算、遞迴
  num < 10 ? num : add_digits(num / 10 + num % 10)
end



# 448. Find All Numbers Disappeared in an Array
def find_disappeared_numbers(nums)
  [*1..nums.size] - nums
end