Oh~Sunny - 个人主页动态

2020-02-14 14:35

下面为大家介绍三种解法,参照剑指offer官方题解,欢迎指正!!!!1.右移解法首先抛出来一个例子: 假如我们有整数5,他的二进制表示为 0000 0101, 我们需要统计这个里面1的个数,首先初始化一个计数器 count = 0,不难想到的是我们可以使用 1 & 0000 0101 得到 1,则count += 1,在将5进行右移得到 0000 0010, 与 1 进行与运算,此时为0,计数器不加,继续将5右移一位得到 0000 0001, 1 & 0000 0001 得到1,count += 1,此时count = 2. 我们由此得到最终的结果.但我们考虑下如果是负数的情...

0 点赞评论收藏

2020-02-13 14:13

好未来_小猴_算法工程师

2020-02-13

在牛客打卡4天，今天学习：刷题 56 道/代码提交 56 次

0 点赞评论收藏

2020-02-13 14:08

好未来_小猴_算法工程师

python官方题解--剪绳子(3种解法)

此题作为面试中经常考到的类型,涉及到我们熟悉的递归,动态规划,贪婪算法这三种,此文会介绍这三种解法. 递归我们先定义函数f(n)为把绳子剪成若干段之后的各段长度乘积的最大值.在剪第一刀的时候,我们会有n-1种可能的选择,也就是说剪出来的第一段绳子的长度可能为1,2,......n-1.因此就有了递归公式 f(n) = max(f(i)*f(n-i)),其中0<i<n.代码如下: #递归写法 class Solution: def cutRope(self, number): # write code here if number < 2: ...

sagii：贪心算法：如果target大于3，那么要求出的乘积的最大值一定是被剪裁过的（4看作2*2），要使结果积的数值最大，要避免剪裁出来1的情况，而又已知了当这个数值大于3时，要经过剪裁才能获取最大值，可以得出结论这个数值是被剪裁为2和3的，而且尽量剪裁3（如6：2*2*2与3*3，9：3*3*3，2*2*2*3）。楼主的代码的意思是如果这个数能够被3整除的话，就把这个数分解为3，也就是pow(3, timesOf3),如果余数为1，就分解出来2个2，其余为3，如果余数为2，就分解出来一个2其他为3.

0 点赞评论收藏

2020-02-12 14:25

好未来_小猴_算法工程师

python官方题解--机器人的运动范围

此题与<<矩阵中的路径>>那一题为同一类问题,方法是采用回溯法来解决,我同样参照剑指offer官方的解释进行了代码实现,思路可以看我<<矩阵中的路径>>的那一题,他们是很相似的哦!!!如果您看到我的代码有什么问题或者需要改进的请您指正哦!!!!! class Solution: def movingCount(self, threshold, rows, cols): # write code here if threshold < 0: return 0 vi...

0 点赞评论收藏

2020-02-11 16:31

好未来_小猴_算法工程师

python官方题解--矩阵中的路径

此题采用回溯发来进行求解,在说之前我想告诉大家,如果大家看过之前别人提交的py版本的代码,会发现不能通过全部的测试用例,现在我根据剑指offer书中的思路写下如下py的代码,希望您批评指正!!! class Solution: def hasPath(self, matrix, rows, cols, path): # write code here if not matrix or not path : return False visited = [0] * len(matrix) resu...

0 点赞评论收藏

2020-02-10 13:11

好未来_小猴_算法工程师

python官方题解

此题大家如有想到的方法就是直接进行顺序的查找,复杂度为O(n).但是我们看到题中是给出的有序的旋转数组,我们可以采用二分法来进行求解,其复杂度为O(logn).这里我们需要利用带有条件的二分法来进行求解: 第一步我们可以将这个旋转的数组看作是前后两个有序的子数组,然后设定我们的中间值 mid = (start + end) // 2. 第二步我们能够看到,当我们选取的中间值 mid 所对应的值大于 start 所对应的值时,说明此时 mid 还在第一有序的数组中,而我们所要求解的最小值是在第二个有序数组的第一个位置,此时也就是在 mid 的后面,我们就将 start 移到 mid 所在的位...

牛客762086323号：for i in range(start,end + 1): if temp < rotateArray[i]: temp = rotateArray[i] return temp 这块应该是temp>rotateArray[i]吧；另外因为是有序的，只要找到第一个比初始值小的数，应该就可以break，返回了吧

0 点赞评论收藏