常喝水

分类

未归档(1) 求职(4) 知识积累(1) 算法(10) 项目(4) 题解(69)

/ 注册

TA的专栏 6篇文章 1人订阅

6篇文章 6935人学习

全部文章（共91篇）

15. 二进制中1的个数

首先把n和1做与运算，判断n末尾是不是1，然后将flag左移一位，判断第二位是不是1，但是如果不设置flag<2**32,会陷入死循环 class Solution: def NumberOf1(self, n): # write code here ...

剑指offer 位运算

2019-12-10

0 719

14. 剪绳子

利用动态规划，需要O(n^2)时间和O(n)空间，也就是利用一个表，储存长度为1~n绳子的最大乘积。 class Solution: def cutRope(self, number): # write code here if number < 2: return 0...

剑指offer 数学

2019-12-09

15 1262

13. 机器人的运动方法

依然利用回溯法 class Solution: def movingCount(self, threshold, rows, cols): # write code here if threshold < 0 or rows <= 0 or col...

剑指offer 动态规划

2019-12-09

0 786

12. 矩阵中的路径

利用回溯的方法设置visited矩阵，当走过i，j点时，将此点设置为1，因为不能重复进入一个格子如果第ij个点与path中的字符一样且未走过，则暂时进入这个格子向四周搜寻下一步的走法，若无解，则证明上一个path路径不对，退回到前一个字符若正确，则重复上述过程，返回haspath cl...

剑指offer 动态规划

2019-12-09

0 692

11. 旋转数组的最小数字

1.利用二分法实现O(log n)的查找，但是要主要当index1 = index2 = midindex时，只能按顺序查找 class Solution: def minNumberInRotateArray(self, rotateArray): # write code...

剑指offer 数组二分法

2019-12-08

0 661

快速排序

思路分析：快速排序采用双向查找的策略，每一趟选择当前所有子序列中的一个关键字作为枢纽轴，将子序列中比枢纽轴小的前移，比枢纽轴大的后移，当本趟所有子序列都被枢轴按上述规则划分完毕后将会得到新的一组更短的子序列，他们将成为下趟划分的初始序列集。算法分析：分裂是O(log n),移动是O(n),综合起来...

排序算法

2019-12-05

0 804

归并排序Merge Sort

动画演示：https://www.runoob.com/python3/python-merge-sort.html 算法分析：将归并排序分为两个过程来分析：分裂和归并。分裂的过程，借鉴二分查找中的分析结果，是对数复杂度，时间复杂度是O(log n) 归并的过程，相对于分裂的每个部分，其所有数...

排序算法

2019-12-05

0 890

谢尔排序Shell Sort

谢尔排序以插入排序作为基础子列表的间隔一般从n/2开始大致介于O(n)和O(n^2)之间，如果将间隔保持在 (1,3,5,7,15,31等等)，谢尔排序的时间复杂度约为O( ) def shellSort(alist): sublistcount = len(alist)//2 ...

排序算法

2019-12-05

0 814

插入排序

比对复杂度是O(n^2) 假设数列第一个元素为已排序数列，剩余数列为未排序将待排序元素挨个插入到已排序数列中每次插入都必须保证数列是有序的，即通过比较和移动有序数列中的元素，将元素插入到合适的位置思路：如同玩扑克牌一样，每次摸牌都将它与手中的牌比较，始终将牌放在比它大的牌前面，比它小的牌后面。这样...

排序算法

2019-12-04

0 519

选择排序

选择排序对冒泡排序进行了改进，每趟都使当前最大项就位选择排序的时间复杂度比冒泡排序稍优：对比次数是O( ),交换次数减少为O(n) def selectionSort(alist): for fillslot in range(len(alist)-1,0,-1): po...

排序算法

2019-12-04

0 569