wowowo123

题解

动态规划(1) 未归档(4)

/ 注册

全部文章 / 题解（共93篇）

剑指二进制1的个数

通过&确定二进制最右位是否为1，然后再右移进位，这样循环判断32位中有多少为1。&表示整数与0……01（31个0）进行与计算。>>1表示二进制向右移1位， class Solution: def NumberOf1(self, n): # wri...

2021-03-16

0 514

剑指矩形覆盖

将这道题转换成斐波那契数列进行求解，将1，2，3等矩形的情况列出来，找规律，然后可以发现，求解当前矩形数目能覆盖的种类，和上一个矩形数目覆盖种类的关系是在上一个矩形数目的基础上，以竖着的矩形和横着的矩形两种方式进行拼接，横着的矩形拼接只能成对出现，也就是求解f(n-2)和f(n-1)的种类数。 c...

2021-03-16

0 468

判断链表中是否有环

快慢指针解决链表中是否有环，快指针每次走两步，慢指针每次走一步，如果相遇了就证明有环，如果没有相遇(快指针遇到了None)就证明没有环。其中需要注意的是判断空链表，以及快指针为空和即将为空的情况，quick!=None and quick.next!=None class Solution: ...

2021-03-14

0 528

快速排序

快速排序，需要注意第一个left>right 为跳出条件，不是right>left。同时在递归的时候需要剔除掉中间排好的值，left lo-1 lo+1 right 否则会递归深度太大。 class Solution: def MySort(self , arr ): ...

2021-03-14

0 537

链表节点每k个一组翻转

通过迭代翻转指针，首先是当前指针直接指向下一个的下一个指针，然后下一个指针指向头指针（注意是头指针）也就是pre.next，然后pre再指向它。相当于将当前指针与下一个下一个指针。然后看链表的长度是多少count，这样的反转进行count/k次，反转时的指针变换一共会进行k-1次，所以range(1...

星标

2021-03-14

0 629

剑指最大子序列和

当以n-1元素结尾最大子序列和为负数时，以n结尾最大子序列和是第n个元素，否则为全部加和。注意循环条件为（1,len(array)）和(1,len(array)+1)的不同 # -*- coding:utf-8 -*- class Solution: def FindGreatestSum...

2021-03-12

0 410

剑指中序前序构建二叉树

注意 pre 为空的条件判断。重建二叉树最开始需要通过TreeNode 构建一个根节点，将root,root.left,root.right进行构建。同时仍需要判断输入数组的index是否超出范围,也就是左子树的长度是否为0(左子树为空)，是否为len-1(右子树为空)o(n^2) 将查找inde...

2021-03-12

0 562

剑指数值的整数次方

快速幂，分奇数偶数讨论，指数分正负讨论，当指数为负数时需要将底数变为倒数进行求解。注意判断条件 0为底数时，指数为0或负无意义，如果指数为正则结果为0.求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。空间logn时间logn # -*- coding:utf-8 -*- cla...

2021-03-12

0 568

剑指斐波那契数列

斐波那契数列递归解法超时，需要记忆化递归，memo的值需要传入的函数里，因为使用递归方法，如果不传入的话，就会每次初始化，所以在函数里还需再写一个递归函数，也可以写在函数外面。时间复杂度O(N)没有重复计算。空间复杂度包括额外的数组以及递归栈递归的时间复杂度为o(2^n) 因为看递调用了多少次，...

2021-03-12

0 576

剑指旋转数组

二分查找，根据某个指标，排除一部分的元素，注意包括相等的元素,右边界排除一个元素。至于为什么返回left下标的值，则因为当mid==right对应的值是，right-=1。 # -*- coding:utf-8 -*- class Solution: def minNumberInRota...

2021-03-11

0 449