colie

题解

未归档(29)

/ 注册

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

题解 | #二进制中1的个数#

【剑指offer】二进制中1的个数（python）思路：n&(n-1)位运算可以将n的位级表示中最低的那一位1置0。不断将1设置为0，直到n为0。负数时注意补码转换。补码：设某负数X，则X+X（反）= 0xFFFFFFFF，所以X+X（反）+1 = 0，可以得出 0 ...

2021-04-14

0 515

题解 | #整数中1出现的次数（从1到n整数中1出现的次数）#

【剑指offer】从1到n整数中1出现的次数（python）数字->字符串->字符列表 list(str)将字符串转为字符列表 # -*- coding:utf-8 -*- class Solution: &nbs...

2021-04-14

0 464

题解 | #孩子们的游戏(圆圈中最后剩下的数)#

【剑指offer】圆圈中最后剩下的数（python） class Solution: def LastRemaining_Solution(self, n, m): # write code here # f(n)=(f(n-1)+m)%n，递归不可以AC，用...

2021-04-14

0 419

题解 | #数组中出现次数超过一半的数字#

【剑指offer】出现次数超过一半的数字（python）摩尔投票法 Boyer-Moore majority vote algorithm，时间O(n)空间O(1) 假如数组中存在众数，那么众数一定大于数组的长度的一半。思想就是：如果两个数不相等，就消去这两个数，最坏情况下，每次消...

2021-04-14

0 422

题解 | #丑数#

【剑指offer】丑数（python）我们只用比较3个数：用于乘2的最小的数、用于乘3的最小的数，用于乘5的最小的。 # -*- coding:utf-8 -*- class Solution: def GetUglyNumber_Solution(self, index): ...

动态规划

2021-04-14

0 496

题解 | #年终奖#

【剑指offer】礼物的最大价值（python）使用动态规划求解，DFS过于复杂，不是最优解。每次都求到达相邻的两个列中的最大值。 # -*- coding:utf-8 -*- class Bonus: def getMost(self, board): # write ...

动态规划

2021-04-14

0 657

题解 | #连续子数组的最大和#

【剑指offer】连续子数组的最大和（python） python初始化整数的最大值和最小值这是聪明法，这个sum的设置，想不到 # -*- coding:utf-8 -*- import sys class Solution: def FindGreatestSumOfSubArr...

动态规划分治

2021-04-14

0 431

题解 | #跳台阶扩展问题#

【剑指offer】变态跳台阶（python）动态规划，跳上n阶台阶可以从n-1跳1，也可以从n-2跳2，。。。f(n)=f(n-1)+f(n-2)+...+f(0)其实就是算了一个等比数列。 # -*- coding:utf-8 -*- class Solution: def jumpFl...

动态规划

2021-04-14

0 482

题解 | #矩形覆盖#

【剑指offer】矩形覆盖（python）覆盖n为1时，只有一种覆盖方法。覆盖n为2时，有两种覆盖方法。要覆盖2xn的大矩形，可以先覆盖2x1的矩形，再覆盖2x(n-1)的矩形；或者先覆盖2x(n-2)的矩形。而覆盖2x(n-1)的矩形和2x(n-2)的矩形可以看成子问题。递推公式就有了。 # -...

动态规划

2021-04-14

0 477

题解 | #斐波那契数列#

【剑指offer】裴波那契数列（Python）动态规划是“自下而上”求解，从最基础的base解到最终解。这里基础解就是第0项和第1项，第2项=第0项+第1项，从第2项开始往上。时间复杂度：O（n）空间复杂度：O（1） # -*- coding:utf-8 -*- class Solution: ...

动态规划

2021-04-14

0 484