面试常用算法

面试常用算法

1、斐波那契数列

# 用python实现斐波那契数列，F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)def fibonacci(num):fibonacci_list = list()a, b = 0, 1i = 0while i < num:fibonacci_list.append(a)a, b = b, a+bi += 1return fibonacci_listdef main():num = int(input("请输入fibonacci位数："))for i in fibonacci(num):print(i)if __name__ == "__main__":main()

2、冒泡排序

# 冒泡排序
def main(arr):for i in range(len(arr)-1):for j in range(len(arr)-1 - i):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]return arrif __name__ == "__main__":arr = [1, 3, 9, 3, 2, 4]main(arr)

3、快速排序

# 快速排序
def quick_sort(arr):# 如果列表长度为1，则直接返回if len(arr) < 2:return arr# 基准数，可以随便取，这里取中间数mid = arr[len(arr) // 2]# 从列表删除基准数ve(mid)# 定义两个列表,遍历large = list()diminutive = list()for i in arr:if i < mid:diminutive.append(i)else:large.append(i)# 递归分区并合并return quick_sort(diminutive) + [mid] + quick_sort(large)def main(arr):return quick_sort(arr)if __name__ == "__main__":arr = [1, 2, 1, 4, 8, 3]print(main(arr))    

4、两数之和

"""
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。"""
# 第一种思路
class Solution:def twoSum(self, nums, target):for i in range(len(nums)-1):for j in range(i+1, len(nums)):if nums[i] + nums[j] == target:return i, jdef main(nums, target):s = Solution()re = s.twoSum(nums, target)return reif __name__ == "__main__":print(main([2, 7, 3, 8], 9))
# 第二
class Solution:def twoSum(self, nums, target):num_dict = dict()for key, value in enumerate(nums):num = target - valueif num in num_dict:return num_dict[num], keynum_dict[value] = keydef main(nums, target):s = Solution()re = s.twoSum(nums, target)return reif __name__ == "__main__":print(main([2, 7, 3, 8], 9))

5、九九乘法表

# for 循环实现方式
def func():for i in range(1, 10):for j in range(1, i+1):print("%dX%d=%d" % (j, i, j*i), end="t")print()# while 循环实现方式
def main():i = 1while i < 10:j = 1while j < i+1:print("%dX%d=%d" % (j, i, j*i), end="t")j += 1print()i += 1if __name__ == "__main__":func()main()

 6、求中位数

def main(num_list):num_list.sort()if len(num_list) % 2 == 0:median = (num_list[len(num_list) // 2] + num_list[len(num_list) // 2 - 1]) / 2print("中位数是：%.1f" % median)else:median = num_list[len(num_list) // 2]print("中位数是：%.1f" % median)if __name__ == "__main__":main([2, 1, 6, 4, 5, 3])

7、n的阶乘

# n的阶乘
def main(num):ret = 1if num < 0:print("请输入输入正整数")elif num == 0:ret = 0else:for i in range(1, num+1):ret *= ireturn retif __name__ == "__main__":num = int(input("请输入一个正整数："))print(main(num))

8、版本号比较

# 第一种，如果出现"1.10.1", "1.9.1"这种会不准确，如果位数一致没问题，第二种可解决
def version(v1, v2):if len(v1) > len(v2):different = len(v1.split('.')) - len(v2.split('.'))for i in range(different):v2 += '.0'elif len(v2) > len(v1):different = len(v2.split('.')) - len(v1.split('.'))for i in range(different):v1 += '.0'if v1 == v2:print("版本号相同")returnreturn v1 if v1 > v2 else v2# 第二种
def version1(v1, v2):if v1 == v2:print("版本号相同")returnv1_list = v1.split(".")v2_list = v2.split(".")if len(v1_list) > len(v2_list):for i in range(len(v1_list) - len(v2_list)):v2_list.append(0)elif len(v1_list) < len(v2_list):for i in range(len(v2_list) - len(v1_list)):v1_list.append(0)# for i in range(len(v1_list)):#     if int(v1_list[i]) > int(v2_list[i]):#         return v1#     elif int(v2_list[i]) > int(v1_list[i]):#         return v2for i, j in zip(v1_list, v2_list):if int(i) > int(j):return v1elif int(j) > int(i):return v2if __name__ == "__main__":print(main("2.2.1", "2.2.0"))

9、求一个字符串中哪一个字符出现的次数最多并且输出这个数

# 第一种，比较笨的做法
def str_count(strs):str_dict = dict()for i in range(len(strs)):if strs[i] in str_dict.keys():str_dict[strs[i]] += 1else:str_dict[strs[i]] = 1return str_dictdef main(strs):str_dict = str_count(strs)values = list()for key, value in str_dict.items():values.append(value)values_max = max(values)ret = list()for key, value in str_dict.items():if value == values_max:return key, value
# 第二种
def main2(strs):strs_dict = dict()for str in strs:if str not in strs_dict:strs_dict[str] = 1else:strs_dict[str] += 1return max(strs_dict, key=)if __name__ == "__main__":print(main("avabcvcx"))print(main2("avabcvcx"))