学做网站培训,自己做的网站如何盈利,大连网站建设意动科技,网页传奇装备1. 在给定的一些数字中找出2个数#xff0c;使得它们的和为N
题目要求
如给定5个数字 [3#xff0c;4#xff0c;9#xff0c;7#xff0c;10] 从中选择两个数使用它们的和为11。必须保证这些数据中有答案#xff0c;并且只有一个答案。
1.1 解题思路一#xff1a;双…1. 在给定的一些数字中找出2个数使得它们的和为N
题目要求
如给定5个数字 [349710] 从中选择两个数使用它们的和为11。必须保证这些数据中有答案并且只有一个答案。
1.1 解题思路一双指针
把数据放在列表中使用双指针方法解决。注双指针要求原始列表中的数据已经排序。先将列表中的数据从小到大排序排序时需要保留原来数据的下标。设置两个指针一个指向第一个数据left一个指向最后一个数据(right)。如果两个指针所指向数据之和大于目标值则right减少。如果小于目标值则left增加。
编码实现
nums [3, 4, 9, 7, 10]
#对数列排序
sort_nums sorted(nums)
# 左指针
left 0
# 右指针
right len(nums) - 1
# 目标值
target 11while left right:if sort_nums[left] sort_nums[right] target:breakelif sort_nums[left] sort_nums[right] target:right - 1else:left 1
# 找到数据在原数列中的位置可以使用线性查找
for i in range(len(nums)):if sort_nums[left] nums[i]:print(sort_nums[left], i)if sort_nums[right] nums[i]:print(sort_nums[right], i)算法分析
**时间复杂度为 O(n)。**这里没有考虑排序时间复杂度。空间复杂度o(n) 空间复杂度一般指算法执行过程中需要借用的空间。这里需要借用一个列表保存原列表中的数据。
1.2 解题思路二哈希查询
建立字典存放数据和下标对应关系
编码实现
def twoSum(nums, target):dict_ {}for i in range(len(nums)):# m为当前待查询的数字m nums[i]# 判断target-m是否已经在字典中if target - m in dict_:# 存在返回这两个数的下标return (dict_[target - m] , i )# 不存在则记录键值对dict_[m] inums [3, 4, 9, 7, 10]
target 11
res twoSum(nums, target)
print(res)算法分析
时间复杂度O(n)。因没有排序环节时间复杂度在优于第一种解题方案。空间复杂度o(n)。需要字典存储数据与位置。
1.3 解题思路三使用列表的 index 方法
这个思路并不能称为思路而是直接使用 Python 已经编好的底层实现。
nums [3, 4, 9, 7, 10]
target 11for i in range(len(nums)):if target - nums[i] in nums:print(i, nums.index(target - nums[i]))break2. 给出n个整数其中有整数是重复的要求找出这重复的整数。
题目要求 如有数列[2,1,7,1,9,10,4,9]。其中数字1和9存在重复 输出复复的数字以及重复的次数。 1 2 9 2
2.1 解题思路一循环嵌套方案。
第一层循环从列表中按顺序拎出每一个数字。第二层循环再次扫描列表查找是否有与第一次循坏中拎出来相同的数字。
编码实现
nums [2, 1, 7, 1, 9, 10, 4, 9]
for i in range(len(nums)):for j in range(i 1, len(nums)):if nums[i] nums[j]:print(nums[i])算法分析
时间复杂度O(n2)空间复杂度O(1)
2.2 解题思路二字典缓存法
使用字典记录每一个数字在列表中的出现的次数
nums [2, 1, 7, 1, 9, 10, 4, 9]
dic {}
for i in nums:if i not in dic:dic[i] 1else:dic[i] 1
print([(k, v) for k, v in dic.items() if v 1])算法分析
时间复杂度为On空间复杂度为On
2.3 解题思路三使用列表的count方法
nums [2, 1, 7, 1, 9, 10, 4, 9]
for i in nums:if nums.count(i)1:print(i)3、在一间房间总共有n个人下标0n-1只能有最后一个人活命。
**题目需求**假设一个房间总共有 10 个人每一个人都有编号0~9现按照如下规则排除人。
所有人围成一圈然后输入一个基数如 3。顺时针报数每次报到3的人将被排除掉的人将从房间内被移走。然后从被kill掉的下一个人重新报数继续报 3再清除直到剩余一人。求解最后留下来的人的编号是多少。
上述问题名为约瑟夫环问题是一个经典的数学问题。
3.1 解题思路一
思路每一次列表中最前面的 3 个数字移动列表的最后面然后删除第 3 个数字。列表最后留下来的数字就是幸存数字。
nums [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
base_num 3
right len(nums) - 1
while right ! 0:for i in range(3):if i right:i 0nums.append(nums.pop(0))nums.pop()right len(nums) - 1print(nums, right: str(right))可以稍许修改一下不删除通过右指针缩小列表长度。
nums [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
base_num 3
right len(nums) - 1
while right ! 0:for i in range(3):if i right:i 0nums.insert(right, nums.pop(0))right - 1print(nums, right: str(right))4. 亲密数
题目需求
如果整数A的全部因子包括1不包括A本身之和等于B且整数B的全部因子包括1不包括B本身之和等于A则将整数A和B称为亲密数。求3000以内的全部亲密数。 提示按照亲密数定义要判断整数a是否有亲密数只要计算出a的全部因子的累加和将其存到变量b再计算b的全部因子的累加和设为n若n等于a则可判定a和b是亲密数。
编码实现
for i in range(3000):numa iyzs 0for i in range(1, numa):if numa % i 0:yzs is1 0for i in range(1, yzs):if yzs % i 0:s1 iif s1 numa:print(numa, yzs)5. 求100以内的所有勾股数。
题目需求 所谓勾股数是指能够构成直角三角形三条边的三个正整数abc。根据“勾股数”定义所求三角形三边应满足条件a2b2c^2。可以在所求范围内利用穷举法找出满足条件的数。
for a in range(1, 100):for b in range(1, 100):for c in range(1, 100):if a ** 2 b ** 2 c ** 2:print(a, b, c)6. 有多少个重复数字
用1、2、3、4共4个数字能组成多少个互不相同且无重复数字的三位数都是多少求互不相同的三位数可以一位一位地去确定先确定百位再确定十位和个位各位上的数值进行比较若互不相同则输出。
for i in range(1, 5):for j in range(1, 5):if i j:continuefor k in range(1, 5):if k j or k i:continueprint(i, j, k)7. 求素数
请找出 10000之内的所有素数素数指只能被1和自身整除的数字
for i in range(10000):is_zs Truefor j in range(2, i):if i % j 0:is_zs Falsebreakif is_zs:print(i)8.4位反序数
假设N是一个四位数它的9倍恰好是其反序数求N。反序数就是将整数的数字倒过来的形成的整数。
for i in range(1000,9999):if str(i*9)[::-1]str(i*9):print(i)9. 回文数
请验证程序运行时输入的数字是不是一个回文数12321就是回文数从左向右从右向左都相同
i12321
if str(i)[::-1] str(i):print(i,是回文数)10. 完全数
如果一个数恰好等于他的因子之和则成为“完全数”。如6的因子是1、2、3而6123则6是个“完全数”。试求出1000以内的全部“完全数”。
nums 6
s 0
for i in range(1, nums):if nums % i 0:s i
if s nums:print(nums, 是完美数)以上题目都会有多种解决方案。
请同学们自行思考。
