想把一个网站屏蔽了怎么做,wordpress书本目录模板,网站职业技术培训学校,花店网站建设Leetcode面试经典150题刷题记录-系列Leetcod面试经典150题刷题记录——数组 / 字符串篇Leetcod面试经典150题刷题记录 —— 双指针篇Leetcod面试经典150题刷题记录 —— 矩阵篇Leetcod面试经典150题刷题记录 —— 滑动窗口篇Leetcod面试经典150题刷题记录 —— 哈希表篇Leetcod…Leetcode面试经典150题刷题记录-系列Leetcod面试经典150题刷题记录——数组 / 字符串篇Leetcod面试经典150题刷题记录 —— 双指针篇Leetcod面试经典150题刷题记录 —— 矩阵篇Leetcod面试经典150题刷题记录 —— 滑动窗口篇Leetcod面试经典150题刷题记录 —— 哈希表篇Leetcod面试经典150题刷题记录 —— 区间篇Leetcod面试经典150题刷题记录——栈篇Leetcod面试经典150题刷题记录——链表篇Leetcod面试经典150题刷题记录——二叉树篇Leetcod面试经典150题刷题记录——二叉树层次遍历篇Leetcod面试经典150题刷题记录——二叉搜索树篇 Leetcod面试经典150题刷题记录 —— 数学篇 1. 回文数解法1 字符串解法解法2 官方解法 2. 加一3. 阶乘后的零解法1解法2 考虑 [1,n] 中质因子 p 的个数。 4. x 的平方根 (扩展了解 快速平方根算法)5. Pow(x,n)6. 直线上最多的点数 1. 回文数 题目链接回文数 - leetcode 题目描述 给你一个整数 x 如果 x 是一个回文整数返回 true 否则返回 false 。回文数是指正序从左向右和倒序从右向左读都是一样的整数。例如121 是回文而 123 不是。 题目归纳 解题思路 解法 回文数 - leetcode官方题解 (1)转换成字符串进行求解。比较原始字符串与反转字符串。 (2)将数字的每一位存储至一个双向队列中依次比较队头和栈顶元素回文数 - Pensive Albattanicrq题解 (3)官方题解。上面两种方式都要完整遍历整个数字的位数而官方题解只需要遍历到其中一半的位置并且从空间使用效率上来说更高效。时间复杂度是 O ( l o g n ) O(logn) O(logn) n n n是数字的大小 l o g n logn logn是指数字总共有几位这应该不难理解。 解法1 字符串解法
class Solution:def isPalindrome(self, x: int) - bool:mylist list(str(x))while len(mylist) 1:if mylist.pop(0) ! mylist.pop():return Falsereturn True解法2 官方解法
class Solution:def isPalindrome(self, x: int) - bool:# 可以直接判断的特殊情况# (1)负数。不是回文数# (2)数值末尾为0则开头也为0那么只有0符合条件。if x 0 or (x%10 0 and x ! 0):return FalserevertX 0while x revertX:revertX 10 * revertX x % 10x // 10# 位数为偶数个 or 位数为奇数个return x revertX or revertX//10 x2. 加一 题目链接加一 - leetcode 题目描述 给定一个由 整数 组成的 非空 数组所表示的非负整数在该数的基础上加一。最高位数字存放在数组的首位 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外这个整数不会以零开头。 题目归纳 解题思路 解法 加一 - leetcode官方题解 class Solution:def plusOne(self, digits: List[int]) - List[int]:if len(digits) 1: return [] # 空数组carry 0 # 进位值digits digits[::-1] # 翻转方便操作n len(digits)p 0while p n:if p 0: # 第1位数字要加1result digits[0] 1 carrycarry result // 10digits[0] result % 10else:result digits[p] 0 carrycarry result // 10digits[p] result % 10p 1# 出来后若进位值carry仍大于0数组需要append(carry)if carry 0:digits.append(carry)return digits[::-1]3. 阶乘后的零 题目链接阶乘后的零 - leetcode 题目描述 给定一个整数 n 返回 n! 结果中尾随零的数量。提示 n! n * (n - 1) * (n - 2) * ... * 3 * 2 * 1 题目归纳 解题思路 解法 阶乘后的零 - leetcode官方题解 (1)因为 10 2 ∗ 5 102*5 102∗5求末尾0的个数即是求 m i n ( 质因子 5 的个数 , 质因子 2 的个数 ) min(质因子5的个数, 质因子2的个数) min(质因子5的个数,质因子2的个数)。 (2)再优化下质因子 5 的个数不会大于质因子 2 的个数 解法1
class Solution:def trailingZeroes(self, n: int) - int:# 寻找阶乘的末尾有几个0# n! 尾0的个数即 n!中因子10的个数而102*5因此转换成求n!中质因子2的个数和质因子5的个数的较小值即有多少个10参与了乘法是由质因子2和5更小的那个数量来决定的# 质因子 5 的个数不会大于质因子 2 的个数# 而n!中质因子5的个数 [1,n]的每个数的质因子5的个数之和因此通过遍历[1,n]的所有5的倍数求出ans 0for i in range(5, n1, 5):while i%5 0: # (1)i要是5的倍数。i // 5ans 1 # (2)将i中质因子5的个数累加起来比如25 5*5两个质因数都为5return ans解法2 考虑 [1,n] 中质因子 p 的个数。
class Solution:def trailingZeroes(self, n: int) - int:# 仅考虑额外贡献的质因子个数 floor(n/p)# n 不变p 越大质因子个数越少因此 [1,n] 中质因子 5 的个数不会大于质因子 2 的个数ans 0while n:n n // 5ans nreturn ans4. x 的平方根 (扩展了解 快速平方根算法) 题目链接x 的平方根 - leetcode 题目描述 给你一个非负整数 x 计算并返回 x 的 算术平方根 。由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。 题目归纳 既然考察的是数学那就请出牛顿提出的牛顿迭代法。这里可以拓展了解下 快速平方根倒数算法还有那句著名的 what the xxxx?。 解题思路 解法 x 的平方根 - leetcode官方题解 class Solution:def mySqrt(self, x: int) - int:# 牛顿迭代法if x 0: return 0C, x0 float(x), float(x)while True:xi 0.5*(x0 C/x0)if abs(x0 - xi) 1e-7: # 两次求解的结果差距小于指定误差可以返回return int(x0)x0 xireturn int(x0)参考文章或视频资料【什么代码让程序员之神感叹“卧槽”改变游戏行业的平方根倒数算法】- bilibili【没那么神秘的快速平方根倒数给你解释一下这个数是怎么来的】- bilibili
5. Pow(x,n) 题目链接Pow(x,n) - leetcode 题目描述 实现 pow(x, n) 即计算 x 的整数 n 次幂函数即xn 。 题目归纳 (1)常规思路。 x n x ⋅ x ⋅ x ⋅ x . . . ⋅ x x^n x · x · x · x \space\space ... \space\space· x xnx⋅x⋅x⋅x ... ⋅x这样方便理解但计算并不快速。 (2)快速幂运算思路。其实快速幂运算就像微信小程序里的召唤神龙游戏回忆下召唤神龙是3只蝌蚪合成1只青蛙3只青蛙合成1条鲤鱼 … … 实际中你几乎不会真的拿9只蝌蚪来合成鲤鱼而是遇到和自己一样大的动物就拉入自己的队伍朝着更大型的动物合成迈进这样的方式合并次数是最少的直到 … … 召唤神龙。数学术语的描述具体可以看leetcode官方题解。 解题思路 解法 Pow(x,n) - leetcode官方题解 class Solution:# 快速幂运算def quickMul(self, x: float, n: int) - float:ans 1.0while n 0:if n 1 1: # 末尾为1ans * xx x*x # x x**2 反而会有问题n n 1return ansdef myPow(self, x: float, n: int) - float:if n 0:return self.quickMul(x, n)else:return 1.0 / self.quickMul(x, -n)6. 直线上最多的点数 题目链接直线上最多的点数 - leetcode 题目描述 给你一个数组 points 其中 points[i] [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。 题目归纳 n n n个点可以画出 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n−1)条直线如果再把每个点代入看是否符合该直线的方程那时间复杂度将达到 O ( n 3 ) O(n^3) O(n3)这种算法绝对不可能被采用。 这里我插句题外话这个算法只在平面上适用比如说在《几何原本》中被奉为绝对真理的“两点确定一条直线”在教科书上的表述并不是“两点只能确定一条直线”因为在非欧几何中这个假设就不成立若考虑地球是完美球体那么地球的南极点到北极点有无数条经线对于地球上的蚂蚁而言这些经线毫无疑问就是其所处平面的直线我们人类对宇宙的探索又何尝不是火鸡呢谁知道两点之间有多少的连接可能性被空间本身的结构抛弃了。只做个人意见如有错误请指正。 如果向量数据库采用的仍旧是占据主流的平面几何的学说这是否符合大多数实际情况呢会不会有些情况是需要用到非欧几何的呢 解题思路 解法 直线上最多的点数 - leetcode官方题解 # 给一个数组points其中points[i] [x_i, y_i]# 求最多有多少个点在同一条直线上# 这道题对 向量数据库 应该非常重要是向量数据库的基础算法比如求向量之间的相似度与距离或者聚类# 可以考虑枚举所有point假设直线经过该point时该直线所能经过的最多的点数# 假设当前枚举到point{i}若直线同时经过另外两个不同的点j、k那么(i,j)所在直线的斜率 (i,k)所在直线的斜率# 于是我们可以统计其它所有点与point{i}所连直线的斜率出现次数最多的斜率即为经过点数最多的斜率其经过点数为 该斜率出现的次数1(1指point{i}自身)# 不采用浮点数记录斜率因为精度可能不够换用元组记录斜率的(分子,分母)的形式这种记录形式可能有以下问题需要解决# (A) 两个元组(1,2), (2,4)的斜率一致所以还涉及到约分即GCD最大公约数的求解# (B) 分子分母存在负数(-1,2), (1,-2)的斜率一致因此规定分母为非负整数如果分母为负数将二元组的两个数同时取反# (C) 直线为yC或xC时传统的斜截式无法表达采用特判法。# 再加以下4个小优化# (1)点的数量2用一条直线将所有点串联直接返回点的数量# (2)枚举到点i时只考虑编号 i的点 与 点i之间的斜率例如编号小于点i的点j当枚举到j自己的时候就已经计算过点j与点i的斜率即两点之间经过一条直线不重复计算两次# (3)当找到的一条直线已经经过了图中超过半数的点时直接确定该直线为经过最多点的直线然后继续按照该直线求点数# (4)当枚举到点i(编号从0开始)时最多只能找到n-i个点共线因为按优化(2)只考虑比自己编号大的。假设此前找到的共线的点数量最大值为k如果有kn-i此时即可停止枚举因为不可能再找到更大的答案了。class Solution:def gcd(self, a, b): # 迭代法求最大公约数while b ! 0:remain a % b # 余数a bb remainreturn adef maxPoints(self, points: List[List[int]]) - int:n len(points)if n 2: # 优化(1)return nret 0for i in range(n):if ret n-i or ret (n/2): # 优化(4)与优化(3)breakmp Counter()for j in range(i1, n): # 优化(2)只考虑比自己编号大的点delta_x points[i][0] - points[j][0] # △xdelta_y points[i][1] - points[j][1] # △y# 对记录形式的优化(C)。特例判断if delta_x 0:delta_y 1elif delta_y 0:delta_x 1else:if delta_y 0: # 对记录形式的优化(B)delta_x -delta_xdelta_y -delta_ygcdXY self.gcd(abs(delta_x), abs(delta_y))delta_x delta_x / gcdXYdelta_y delta_y / gcdXYmp[str(delta_y delta_x*20001)] 1 # 看官方题解maxn 0for k,v in mp.items():maxn max(maxn, v1)ret max(ret, maxn)return ret
