使用 leetcode 学习算法,并将每一道算法题记录下来

October 11, 2018 23:38
访问量:200
摘要:记录一下自己做的每一道算法题目。

1.两数之和

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

ruby实现代码:

#@param {Integer[]} nums
#@param {Integer} target
#@return {Integer[]}

def two_sum(nums, target)
  indexes_hash = {}

  nums.each_with_index do |num, index|
      return [indexes_hash[target - num], index] if indexes_hash[target - num]
      indexes_hash[num] = index
  end
end

2.反转整数

给定一个 32 位有符号整数,将整数中的数字进行反转。

示例 1: 输入: 123 输出: 321

示例 2: 输入: -123 输出: -321

示例 3: 输入: 120 输出: 21

注意:

假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。根据这个假设,如果反转后的整数溢出,则返回 0。

ruby实现代码1:(该方法比下面哪种运行速度要快)

INT_BIT = 32
INT_MAX =  2 ** (INT_BIT - 1) - 1

def reverse(x)
  result, x_remaining = 0, x.abs

  while x_remaining > 0
    result = result * 10 + x_remaining % 10
    x_remaining /= 10
  end

  result = x < 0 ? -result : result

  if result < 0
    result < -INT_MAX ? 0 : result
  else
    result > INT_MAX ? 0 : result
  end
end

实现2:

# @param {Integer} x
# @return {Integer}
def reverse(x)
    result = x.to_s.split('').reverse.join.to_i
    result *= -1  if x < 0
    result = 0 if result > 2**31 - 1 || result < - 2**31 
    result
end

3.从数组中找出唯一重复出现的2次的数字

arr中只有唯一一个数字出现了两次其余均一次

#题目一
#arr = [100, 121, 4433, 10000, 121, 10]
#find_repeated_number(arr) => 121

def find_repeated_number(arr)
  hash = {}
  arr.each do |n|
    hash[n] = 0 unless hash[n]
    hash[n] += 1
    return n if hash[n] == 2
  end
end

arr = [100, 121, 4433, 10000, 121, 10]
print find_repeated_number(arr)

#分析: 统计该数组每个出元素出现的次数,使用hash的存储方式, 元素为key, 次数为value, 当value==2时跳出循环。
#时间复杂度是O(n)。 优点:高效,缺点:消耗的内存空间过大。

4. 按倒序合并两个排序后的数组(要求算法 时间复杂度是O(n))

# 倒序合并两个排序后的数组
# a = [1,2,3,4,5]
# b = [2,3,4,5,6,7]

a = [1,2,3,4,5]
b = [2,3,4,5,6,7]

def reverse_merge_sort_array(a,b)
  c = a + b
  #c.sort.reverse  一般就用sort方法就行
  min = c.min
  max = c.max
  new_arr = Array.new(max-min+1, 0)

  c.each do |n|
    new_arr[n-min] += 1
  end

  (0...new_arr.size).map{|i| [i+min]*new_arr[i]}.flatten.reverse
end

print reverse_merge_sort_array(a,b) #=> [7, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1]

评论

暂无相关评论,快来抢占沙发吧!
评论框离家出走了,点击找回!
昵称
邮箱
网站
昵称
邮箱
网站