ruby daily practice 4

给定能随机生成整数1到5的函数,写出能随机生成整数1到7的函数

我的想法:一个函数已经可以生成1到5的随机数了,那么只要在它的返回值,6,7中再随机返回一个,就是随机生成1到7的函数了。
题解:这道题目的关键是让生成的 1 到 7 的数出现概率相同
总结:我又想简单了:< ,按照我原先的想法,6,7的概率明显要高于1到5,所以这道题关键是如何将1到5等概率的放大。

解法1:

# n 个数中随机选出 1 到 n 个数,反复进行这种运算,直到剩下最后一个数即可
# 例如
arr = [1,2,3,4,5,6,7]
rand5 # => 返回1到5中任意一个数字
# 反复7次rand5函数得到一个数组
#
b = [3, 4, 4, 4, 2]

# arr 去除b中有的元素
c = arr -b # => [1,5,6,7]
# 这里c已经小于5了
# 下面可以自定义取值规则,但必须通过rand5函数
# 例如我们规定取调用rand5,最小值的位置
# 四次
d = [4,2,4,3]
# 最小值是2,位置是1,为什么这里可以这样呢?
# 因为在d中每个位置出现最小值的概率是一样的
所以最后的返回值为
c.at(1) #=> 5

ruby ugly number

题目:我们把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。 求按从小到大的顺序的第1500个丑数。

想法:判断一个数是否是丑数,其实就是看它的所有质数因子是否只有2,3,5,也就转化为求一个数的质数因子(素数因子)。后面会发现这个想法只是概念上的想法,实际上效率低的可怜

素数真是太有意思了,哥德巴赫猜想,素数的百度百科

# 判断是否为素数
class Integer
  def prime?
      # 1 不是素数
      return false if self == 1
      2.upto(self - 1) { |i| return false if self%i == 0}
      true
  end
end

#测试
73.prime? # => true

下面来求一个数所有的素因子

class Integer
  def primes
   (2..self).find_all { |i| self%i == 0 and i.prime?}
  end
end

#测试
100.primes # => [2,5]

判断是否为丑数

class Integer
  def ugly?
    self.primes.uniq.delete_if {|x| [2,3,5].include?(x)}.empty?
  end
end

#测试
14.ugly# => false

下面来求

arr = [1]
n = 2
loop do
  arr &lt;&lt; n if n.ugly?
  n = n.next
  break if arr.size == 99
end

p arr.last # => 1500

计算第99个已经用1s多了,第1500个不知道到什么时候呢,这样做只是用程序描诉了一遍概念,实际太耗时间了。

算法

可以看到丑数数组里面的每一个丑数是前面的丑数乘以2、3或者5得到的,由于顺序排列,必须将已知丑数组中最大数,假设是M,分别乘2,3,5,然后在得到的三个数中取出最小并且大于M的,这就是下一个丑数

改进后的写法

def find_ugly_number(index)
 # 初始队列
 queue = [1]
 # 临时队列
 temp = []
 # 初始值
 m = 1
 # 初始位置
 position = 1
 until (position == index)
  [2,3,5].each do |i|
    temp < < i * m
  end
  m = temp.uniq.sort[position -1]
  queue << m
  position += 1
  end
  queue.last
end

#测试 大概用时1s
p find_ugly_number(1500) #=> 859963392

ruby daily practice 3

谷歌面试题:1024! 末尾有多少个0?

分析:1024的阶乘,就是看1024有多少的2和5,2的个数比5多,那就是看有多少5。

5的倍数,1024/5 = 204
25的倍数,1024/25 = 40
125的倍数,1024/125 = 8
625的倍数:1024/625 = 1

#所以加起来一共 253个0

ruby daily practice 2

给定字符串,删除开始和结尾处的空格,并将中间的多个连续的空格合并成一个。
比如 “ I like http://www.zires.info ” 会变成 “I like http://www.zires.info”。

分析:分为两部分,先去除头尾的空格,再将中间的空格合并。

(一)ruby的string自带了N多方法,足够操作字符串了。

example = " i like      http://www.zires.info   ";
# 使用strip 去头尾空格
example.strip # = "i like       http://www.zires.info";
# 使用squeeze 去除中间空格
# squeeze 会根据传进去的str 把符合条件的str连续相同的合并
# 所以这里我们传进去一个空格
example.squeeze(" ") # ="i like http://www/zires.info";

#合起来写
example.strip.squeeze(" ")
完成

(二)没有比正则表达式更适合操作字符串了

example = " i like      http://www.zires.info   ";
# 同样先使用strip
# 接着使用gsub,匹配一个或多个空格,用""替代

# 完整写
example.strip.gsub(/s/,"")
# ="i like http://www.zires.info";

大功告成

ruby daily practice 1

题目:在排序数组中,找出给定数字的出现次数,比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。

最简单的方法

# 给定数组
arr = [224698362469]

# 使用count函数
arr.count(2)  #=&gt; 3

arr.count(1)  #=&gt; 0

So Easy

不过题目不会考你api方法的,考的应该是算法
二分搜索查找,时间复杂度O(log n)。

# 给Array添加新的instance_method
class Array
 def new_count(num, need_sort = true )
 # 初始为0
 count = 0
 return count if empty?
 # 排序  只有第一次需要
 sort_arr = need_sort ? self.sort : self   
 index = sort_arr.length/2
 last_index = sort_arr.length - 1
 # 取得中间的数    
 middle = sort_arr.at(index)
 if middle == num
   # 因为匹配成功才扫描,所以肯定有一个存在
   count = 1     
   # 向前扫描    
   (index -1).downto(0) do |idx|
     if sort_arr.at(idx) == num
  count += 1
     else
        break
     end
   end
   # 向后扫描
   (index + 1).upto(last_index) do |idx|
  if sort_arr.at(idx) == num
      count += 1
  else
     break
   end
    end
  elsif middle &gt; num
  sort_arr[0..(index -1)].new_count(num,false)
  elsif middle &lt; num
  sort_arr[(index + 1)..(last_index - 1)].new_count(num,false)     
  end
  return count
  end
end

# 测试
[1,4,4,3,4,4,4].new_count(3) # =&gt; 1
[1,4,4,3,4,2,4].new_count(4) # =&gt; 4