你必須很努力

來個三題 LeetCode easy 吧

2019/11/07
字數統計: 434閱讀時間: 2 min

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

  1. 136. Single Number
  2. 258. Add Digits
  3. 448. Find All Numbers Disappeared in an Array

題目

題目(136. Single Number):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

1
2
3
4
5
# @param {Integer[]} nums
# @return {Integer}
def single_number(nums)

end

題目(258. Add Digits):

1
2
3
4
5
6
7
8
9
10
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?

1
2
3
4
5
# @param {Integer} num
# @return {Integer}
def add_digits(num)

end

題目(448. Find All Numbers Disappeared in an Array):

1
2
3
4
5
6
7
8
9
10
11
12
13
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]

1
2
3
4
5
# @param {Integer[]} nums
# @return {Integer[]}
def find_disappeared_numbers(nums)

end


答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 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


小結

  1. 先搞懂題目問什麼
  2. 可以先用 RSpec 在本地端測試 (可忽略步驟 2.)
  3. 再丟到 LeetCode 上測試
  4. 時間複雜度沒過再來思考如何解決 (先求有再求好)

原文連結:https://riverye.com/2019/11/07/來個三題-Leetcode-easy-吧/

發表日期:2019-11-07

更新日期:2019-11-07

CATALOG
  1. 1. 題目
    1. 1.1. 題目(136. Single Number):
    2. 1.2. 題目(258. Add Digits):
    3. 1.3. 題目(448. Find All Numbers Disappeared in an Array):
  2. 2. 答案
  3. 3. 小結