云计算开发python实例对象调用类方法python实例化对象参数理解
下载地址 https://share.weiyun.com/OvviwGnZ
资料目录
Python练习集100题
100道Python面试题
Python100经典练习题
Python经典题目100道题
Python题库(已收录100道真题）
Python100例视频讲解课程
菜鸟教程Python教程100例
130道python练习题，涵盖基础内容的方方面面
Python考试题复习知识点试卷试题
PYTHON测试题和答案
python第一阶段考试题
Python经典面试题和答案解析
python期末考试复习试卷
python习题集大全（附答案解析）
老男孩Python全栈7期练习题（面试真题模拟）
尚观python第一阶段考试（面试真题模拟）
《Python程序设计基础与应用》习题答案
《Python快速编程入门》——课后题答案
Python编程基础张健 , 张良均课后习题及答案
Python程序设计基础及实践（慕课版）郭炜习题答案
Python程序设计基础习题答案与分析
python基础试题(含答案)
举例 旋转数组
题目要求
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数，要求使用空间复杂度为 O(1) 的原地算法
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
思路分析
思路1，多次移动
如果没有空间复杂度为O(1)的要求，这个题目非常简单，简单的做一下切片处理就可以了
lst = [1, 2, 3, 4, 5, 6, 7]
lst = lst[len(lst)-3:] + lst[0:len(lst)-3]
print(lst)
但切片的过程就是一个复制的过程，我们使用了O(n)的空间，与题目要求不符。
我们只能使用一个O(1)的空间来临时存储数据，简单说，一次只能存储一个数字，但要向右移动K个位置。如果我们能找到一种算法，这个算法执行一次，只将数组向右移动1位，移动k个位置只需要执行这个算法K次就可以了。
考虑移动1位就简单了，用一个临时变量tmp将lst[-1]保存下来，然后从后向前，逐个向后移动，最后，将lst[0]赋值为tmp
tmp = lst[-1]
for i in range(len(lst)-1, 0, -1):
lst[i] = lst[i-1]
lst[0] = tmp
经过上面的算法，数组就从[1,2,3,4,5,6,7]变成了[7,1,2,3,4,5,6],如果希望将数组向右移动K个位置，只需要执行K次就可了
def move_ele_1(lst, k):
for j in range(k):
tmp = lst[-1]
for i in range(len(lst)-1, 0, -1):
lst[i] = lst[i-1]
lst[0] = tmp
if __name__ == '__main__':
lst = [1, 2, 3, 4, 5, 6, 7]
move_ele_1(lst, 3)
print(lst)
思路2， 原地翻转
将数组分为两个区域，第一个区域是从0到len(lst)-k-1, 余下的是第二个区域，两个区域分别做一次翻转，然后将整个数组做一次翻转，算法的过程如下
[1, 2, 3, 4, 5, 6, 7] 原始数据
[4, 3, 2, 1, 5, 6, 7] 第一个区域翻转
[4, 3, 2, 1, 7, 6, 5] 第二个区域翻转
[5, 6, 7, 1, 2, 3, 4] 整体翻转
一旦有了思路，算法就很容易写出来，但要注意处理边界条件
def reverse_lst(lst, start, end):
for i in range(0, (end-start)//2 + 1):
tmp = lst[start+i]
lst[start+i] = lst[end-i]
lst[end-i] = tmp
def move_ele_2(lst, k):
split_index = len(lst) - k - 1
reverse_lst(lst, 0, split_index)
print(lst)
reverse_lst(lst, split_index+1, len(lst)-1)
print(lst)
reverse_lst(lst, 0, len(lst)-1)
if __name__ == '__main__':
lst = [1, 2, 3, 4, 5, 6, 7]
move_ele_2(lst, 3)
print(lst)
|