算法题解析 #2
Description
前言
今天刷了一下网易往年的编程笔试题，之后我将做个总结。其实，对于一个前端开发的人来说，算法是一个可有可无的东西。因为你或许一辈子都不需要接触这个东西，至于界面打交道。但是，你的职业水平也会止步于此。我是一个热衷于算法的少年，由于需要模拟控制台的输入与输出，而js的实现又非常的拙劣，所以，我会选择python。一门与js一样神奇的语言。
第一题
题目：小易有一个圆心在坐标原点的圆，小易知道圆的半径的平方。小易认为在圆上的点而且横纵坐标都是整数的点是优雅的，小易现在想寻找一个算法计算出优雅的点的个数，请你来帮帮他。
例如：半径的平方如果为25
优雅的点就有：(+/-3, +/-4), (+/-4, +/-3), (0, +/-5) (+/-5, 0)，一共12个点。
输入描述:
输入为一个整数，即为圆半径的平方,范围在32位int范围内。
输出描述:
输出为一个整数，即为优雅的点的个数
输入例子1:
25
输出例子1:
12
理解：其实这道题我是这么考虑的类似与坐标轴上的四个象限，只需要去考虑其中的一个象限，但是象限的端点处只能取其中之一，如图：
然后就可以写py代码了：只要在这条曲线上的点，然后在总和中乘以4倍，即是返回值
代码部分
from math import sqrt
def main():
inputN = int(raw_input())
sum = 0
i = 1
while i * i <= inputN:
tem = sqrt(inputN - i * i)
if int(tem) == tem:
sum += 1
i += 1
print sum * 4
if __name__ == '__main__':
main()第二题
题目：小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3.......
这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。
例如：
N = 4，M = 24：
4->6->8->12->18->24
于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板
输入描述:
输入为一行，有两个整数N，M，以空格隔开。
(4 ≤ N ≤ 100000)
(N ≤ M ≤ 100000)
输出描述:
输出小易最少需要跳跃的步数,如果不能到达输出-1
输入例子1:
4 24
输出例子1:
5
理解：这一题其实是一题动态规划类的算法题，其实只要保证走x时，i+x是最小的，那么最后N，M之间的步数也会是最小的。下面我们来看一副图片理解一下：
看着图解之后，我们再来写一些这个动态规划的代码理解一下，py代码：
def factor(number):
res = []
i = 2
while i * i <= number:
if number % i == 0:
res.append(i)
if number / i != i:
res.append(number / i)
i += 1
return res
def main():
arr = raw_input().split(' ')
N = int(arr[0])
M = int(arr[1])
dp = []
for i in range(0, M+1):
dp.append(9999999) #fill array
dp[N] = 0
for i in range(N, M):
if dp[i] == 9999999:
dp[i] = 0 #9999999 mean can not to reach, set 0 mean to reduce space
continue
temp = factor(i)
for item in temp:
sum = item + i
if sum <= M:
dp[sum] = min(dp[sum], dp[i]+1) # get min dept
if dp[M] == 0:
print -1
else:
print dp[M]
if __name__ == '__main__':
main()总结
算法题还是比较好玩的，即使是前端开发的人也应该时常练习，时常刷一下leetcode和oj平台