面试题 - 总结

require "rubygems"

##
#1.平衡点问题
#  平衡点：比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的总和为24，25后面的总和也是24，25这个点就是平衡点；假如一个数组中的元素，其前面的部分等于后面的部分，那么这个点的位序就是平衡点
#要求：返回任何一个平衡点

puts "平衡点问题" + "* " * 20

#初始化常量
numbers = [1, 3, 5, 7, 8, 25, 4, 20]
len = numbers.size - 1
head_sum = 0;tail_sum = 0
head= 0;tail =len

#开始计算
for i in 0..len
  (puts "mid is :#{numbers[i]} sum is:#{head_sum}";break) if head_sum.eql?(tail_sum) and head_sum > 0
  (head_sum += numbers[head];head += 1) if head_sum <=tail_sum
  (tail_sum += numbers[tail]; tail -= 1) if tail_sum <= head_sum
end

##
#2.支配点问题：
#支配数：数组中某个元素出现的次数大于数组总数的一半时就成为支配数，其所在位序成为支配点；比如int[] a = {3,3,1,2,3};3为支配数，0，1，4分别为支配点；

puts "支配点问题" + "* " * 20

h_count = {} #用于存储数量
h_index = {} #用于存储位置
Hash
a = [3,3,1,2,3]
a.each_index do |i|
  h_count[a[i]]=0 if h_count[a[i]].nil?  
  h_count[a[i]] += 1
  h_index[a[i]] = [] if h_index[a[i]].nil?
  h_index[a[i]] << i
end

list = h_count.sort {|a,b| b[1]<=> a[1]}
puts "支配数是:#{list[0][0]} 数量:#{list[0][1]}"
puts "支配点数:#{h_index[list[0][0]].join(",")}"

##
#3.最大公约数，辗转相除法

a,b = 5767,4453
... temp = a
... while temp:
...     temp = a % b
...     if temp == 0:
...       print b
...     else:
...         print a,b
...         
...     a = b
...     b = temp

最小公倍数：公式法
　　可以证明，甲、乙两个自然数和它们的最大公约数与最小公倍数有如下关系：
　　甲×乙=最大公约数×最小公倍数因此，可以根据公式：
　　最小公倍数=甲×乙÷最大公约数来求两个数的最小公倍数。

##
#4.大数求余
原理将大数分开计算,按位计算
23 = 2*10 + 3
23%n = 2%n*10 + 3%n

d = 1232132131
f = 7
mod = 0
... for i in str(d):
...     mod = mod * 10 + int(i)
...     mod = mod % f
...     print mod,f