算法是面试中出现频次最高,也是比较烧脑的题目;但真正的大牛还是不会太在乎面试中出现的这些题目,因为在他们看来,这些已经在大脑中演算了上百次。
① 先“分苹果”
1.先判断数组总和是否可以被n整除,否则没法分均匀;
2.然后再判断每份苹果与平均值的差,若差不是2的倍数,也无法移动成功;
3.如果前两个条件满足就把比均值多的苹果数减去均值,将其总数除以2,就是得到的移动次数了。
count = int(input())
ls = [int(key) for key in input().split()]
sum() 方法对系列进行求和计算。
def split_apple(n, ls):
if sum(ls) % n != 0:
return -1
count = 0
avg = sum(ls) // n
for i in ls:
if (i - avg) % 2 != 0:
return -1
if i > avg:
count += (i - avg)
return (int(count // 2))
print(split_apple(count, ls))
② 字符串中找出连续最长的数字串
在于判断是不是数的这个isnumeric()函数
li = input()
curlen, curstr, maxlen, maxstr = 0, '', 0, ''
for key, value in enumerate(li):
if value.isnumeric():
curlen += 1
curstr += value
if curlen > maxlen:
maxlen = curlen
maxstr = curstr
else:
curlen = 0
curstr = ''
print(maxstr)
③ 青蛙跳台阶
题目:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
对于本题,前提只有 一次 1阶或者2阶的跳法。
a.如果两种跳法,1阶或者2阶,那么假定第一次跳的是一阶,那么剩下的是n-1个台阶,跳法是f(n-1);
b.假定第一次跳的是2阶,那么剩下的是n-2个台阶,跳法是f(n-2);
c.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2);
d.然后通过实际的情况可以得出:只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2;
e.可以发现最终得出的是一个斐波那契数列;
class Solution:
def jump_floor(self, number):
res = [1, 2]
while len(res) <= number:
res.append(res[-1] + res[-2])
if number == 1:
return 1
else:
return res[number - 1]