LeetCode上与数学相关的问题

  • 最伟大的普通股利(GCD)
  • 素数
  • 丑数
  • 最小的最大数

1.最大公约数(GCD)

两个数字的GCD(最大公因数)或HCF(最大公因数)是将两者相除的最大数。

  1. 1 GCD的基本欧几里得算法
    该算法基于以下事实。
  • 如果我们从较大的数字中减去较小的数字(我们减少较大的数字),则GCD不会改变。 因此,如果我们不断重复减去两个中的较大者,我们将得到GCD。
  • 现在,如果不进行减法运算,则除以较小的数字,当发现余数为0时,算法停止。
 def gcd(a, b): 
   if a == 0 : 
   return b 
   return gcd(b%a, a) 

最小公倍数(LCM)

如果GCD(x,y)* LCM(x,y)= xy

2.质数

质数是大于1的整数,只能被1及其自身整除。 前几个质数是:2 3 5 7 11 13 17 19 23…..

关于素数的一些有趣事实

  1. 2是唯一的偶数素数。
  2. 每个素数都可以6n + 1或6n-1的形式表示,其中n是自然数。
  3. 2,3也是两个连续的自然数,它们也是素数。
  4. 哥德巴赫猜想:大于2的每个偶数整数都可以表示为两个素数之和。
  5. 每个正整数都可以分解为素数的乘积。
  6. Prime的自然数的GCD始终为1。
  7. 费马小定理:如果n是素数,则对于每个a,1 <= a <n,
  a ^(n-1)≡1(mod n)或a ^(n-1)%n = 1 

质数定理:给定的,随机选择的数n是质数的概率与它的位数或n的对数成反比。

我们如何检查数字是否为素数?

  1. 天真的解决方案
    一个幼稚的解决方案是遍历2到n-1之间的所有数字,并检查每个数字是否除以n。 如果找到任何可除的数,则返回false。
  def isPrime(n): 
 # Corner case 
  if (n <= 1): 
  return False 
 # Check from 2 to n-1 
  for range(2, n): i in range(2, n): 
   if (n % i == 0): 
   return False 
  return True 

我们可以进行以下优化:

  1. 除了可以检查直到√n之外,我们还可以检查直到√n,因为n的较大因子必须是已检查的较小因子的倍数。 同样,因为即使大于2的数字也不是质数,所以我们可以将其设置为2。
  2. 通过观察除2和3外的所有素数都为6k±1的形式,可以进一步改进算法。因此,一种更有效的方法是测试n是否可以被2或3整除,然后检查所有形式为6k±1。

使所有素数均小于n的有趣解决方案

威尔逊定理说,如果数k为质数,则((k-1)!+ 1)%k必须为0。

以下是该方法的Python实现。 请注意,该解决方案在Python中有效,因为默认情况下Python支持大整数,因此可以计算大数阶乘。

Eratosthenes筛

生成素数列表。 它通过识别所有非质数都可以被质数整除而起作用。 一种优化是仅在素数列表中使用奇数,这样我们可以节省一半的空间和一半的时间。 唯一的区别是我们需要进行索引映射。

 素数= [真] * n 
primes [0] = primes [1] = False
对于范围在(2,int(n ** 0.5)+ 1)中的i:
#将i的剩余倍数除以i * i
 如果素数[i]: 
primes [i * i:n:i] = [False] * len(primes [i * i:n:i])#将这些值设置为false,start,end,step i ^ 2 + i是质数
返回和(素数)

可能性

  1. 0≤pr(A)≤1
  2. 所有可能结果的概率之和为1或100%。 如果ABC是唯一可能的结果,则pr(A)+ pr(B)+ pr(C)= 1
  3. 事件发生和不发生的概率之和为1。pr(A)+ pr(not A)= 1或pr(not A)= 1 — pr(A)
  4. 如果两个事件AB是独立的pr(A和B)= pr(A)·pr(B)
  5. 如果两个事件AB是互斥的(意味着A不能与B发生在同一时间发生),那么AB发生的概率就是它们各自概率的总和。 Pr(A或B)= pr(A)+ pr(B
  6. 如果两个事件AB不互斥(这意味着AB可能同时发生),则Pr(A或B)= pr(A)+ pr(B)-pr(A和B)
  7. 多个事件中发生至少一个事件的概率,pr(至少一个)= 1-pr(无)
  8. 如果事件B是事件A的子集,则B的概率小于或等于A的概率 pr(B)≤pr(A)
  9. 条件概率:贝叶斯定理, P(A / B)= P(A和B)/ P(B)
  10. 边际:

丑数

263.丑陋的数字

编写程序以检查给定的数字是否是丑陋的数字。

丑数是正数,其主要因子仅包括2, 3, 5 。 例如, 6, 8是丑陋的,而14不是丑陋的,因为它包括另一个素因7

注意:

  1. 1通常被视为丑数。
  2. 输入在32位有符号整数范围内。

解决方案:num = 2 ^ i3 ^ j5 ^ k,如果除数=== 0,则保持除法[2,3,5],否则停止。 返回False

  def isUgly(self,num): 
“”
:type num:int
:rtype:布尔
“”
如果num == 0:
返回False
因子= [2,3,5]
对于f因数:
而num%f == 0时:
num / = f
返回num == 1

264.丑陋的二号

编写程序以查找第n个丑数。

丑数是正数,其主要因子仅包括2, 3, 5 。 例如, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12是前10丑陋数字的序列。

请注意,通常将1视为丑数,并且n 不超过1690

两种解决方案:1.使用列表保存所有前1690个数字并对该列表进行排序。 2.要及时生成,使用三个指针,记录最后使用每个指针的结果。

  def nthUglyNumber(self,n): 
“”
:type n:整数
:rtype:整数
“”
#nums = []
#适用于范围内的我(int(log(1690,5))):
#用于范围内的j(int(log(1690,3))):
#用于范围内的k(int(log(1690,2))):
#nums.append((5 ** i)*(3 ** j)*(2 ** k))
#nums.sort()
#打印(len(数字))
#打印(数字)

nums = [1]
idx_2,idx_3,idx_5 = 0、0、0
对于范围(n-1)中的i:
next2 = nums [idx_2] * 2
next3 = nums [idx_3] * 3
next5 =数字[idx_5] * 5
next = min(next2,next3,next5)
nums.append(下一个)
如果next == next2:
idx_2 + = 1
如果next == next3:
idx_3 + = 1
如果next == next5:
idx_5 + = 1
返回数字[-1]

313.超级丑陋数字

编写程序以查找第n个超级丑陋的数字。

超丑数是正数,其所有素数都在给定的素数列表k primes中。 例如, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]是给定primes = [2, 7, 13, 19] primes [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]的前12个超级丑数的序列尺寸4。

注意:
(1) 1是给定质primes的超级丑primes
(2)给定的质数按升序排列。
(3)0 <k≤100,0 < primes[i] < primes[i] <1000。
(4)保证第n个丑陋的数字适合32位有符号整数。

解决方案:与上一个相同,除了素数不同

  def nthSuperUglyNumber(self,n,primes): 
“”
:type n:整数
:type素数:列表[int]
:rtype:整数
“”
nums = [1]
idexs = [0] * len(primes)#first是当前的idex
对于范围(n-1)中的i:
min_v =最大大小
min_j = []
对于j,枚举(idexs)中的idex:
v = nums [idex] * primes [j]
如果v <min_v:
min_v = v
min_j = [j]
elif v == min_v:
min_j.append(j)#如果有平局,我们可以得到多个j
nums.append(min_v)
对于min_j中的j:
idexs [j] + = 1
返回数字[-1]

基础

483.最小好的基础

对于整数n,如果n基k的所有数字均为1,则称k> = 2为n的良好基数

现在给定一个表示n的字符串,您应该以字符串格式返回n的最小有效底数。

范例1:

  输入: “ 13” 
输出: “ 3”
说明: 13的基数3是111。

范例2:

  输入: “ 4681” 
输出: “ 8”
说明: 4681以8为底的是11111。

范例3:

  输入: “ 1000000000000000000” 
输出: “ 999999999999999999”
说明: 1000000000000000000基数999999999999999999为11。

注意:

  1. n的范围是[3,10 -1]。
  2. 表示n的字符串始终有效,并且不会有前导零。

解决方案:对于返回最小的问题,例如查找,我们使用二进制搜索。 我们需要基数为[2,n-1],如果基数最小,则’111’的大小应为最大,[2,log(num + 1,base)+1]。 因此,我们可以计算大小[2,log(num + 1,base)+1],并设置l = 2,r = n-1,开始二进制搜索。 如果数学背景为n = 1 + k +k²+k³+…+ k ^(m-1)> k ^(m-1)=> k <n ^(1 /(m-1)),则基数成为[2,n ^(1 / /(m-1))+ 1]。

 从数学导入日志 
类解决方案:
def minimumGoodBase(self,n):
“”
:type n:str
:rtype:str
“”
num = int(n)

#倒数尺寸
对于范围内的大小(int(log(num + 1,2)),1,-1):
#找到基地
l,r = 2,num-1#或r = int(pow(num,1.0 /(size-1))+1)
而l <= r:
中= l +(rl)// 2
总和= 0
对于我在range(size)中:#以base为单位获取size的值
sum = sum * mid + 1 #value =最后一个值* base + digit
如果sum == num:
返回str(mid)
elif sum <num:#增加基数
l =中+1
否则:#重置基数
r =中-1
返回str(num-1)

组合

750.直角矩形的数量

给定一个网格,其中每个条目只有0或1,请找到角矩形的数量。

角矩形是网格上4个不同的1,形成轴对齐的矩形。 请注意,只有角需要具有值1。而且,所使用的所有四个1必须是不同的。

范例1:

  输入: grid = 
[[1,0,0,1,0],
[0,0,1,0,1],
[0,0,0,1,0],
[1、0、1、0、1]]
输出 1
说明:只有一个角矩形,其角为grid [1] [2],grid [1] [4],grid [3] [2],grid [3] [4]。

范例2:

  输入: grid = 
[[1,1,1],
[1,1,1],
[1、1、1]
输出: 9
说明:有四个2x2矩形,四个2x3和3x2矩形以及一个3x3矩形。

解决方案:我们将有四个位置(i,j),(i,j + n),(i + m,j),(i + m,j + n),然后可以形成一个矩形。 如果使用蛮力,则需要枚举i,j和m,n,这对于行中的i,列中的j,列(1,rows-i)中的m,列(1,cols-j)中的m 。 复杂度将为O(m * n * m * n)。 如果我们只枚举开始行和结束行,然后通过cols检查grid [start_row] [col] == 1和grid [end_row] [col] == 1。 然后,我们可以找到可用于形成矩形的列数。 组合公式为C(cnt,2)= cnt *(cnt-1)/ 2。

  def countCornerRectangles(自身,网格): 
“”
:type grid:List [List [int]]
:rtype:整数
“”
如果不是网格:
返回0
行= len(网格)
cols = len(grid [0])
ANS = 0

对于s_r范围(行):
对于范围(s_r + 1,行)中的e_r:
零=
#count cols
对于col范围(cols):
如果grid [s_r] [col] == 1且grid [e_r] [col] == 1:
cnt + = 1
ans + =(cnt *(cnt-1))/ 2
返回int(ans)

224.基本计算器

实现一个基本的计算器来评估一个简单的表达式字符串。

表达式字符串可以包含打开(和右括号) ,加号+或减号-非负整数和空白  

您可以假设给定的表达式始终有效。

一些例子:

  “ 1 +1” = 2 
“ 2-1 + 2” = 3
“(1+(4 + 5 + 2)-3)+(6 + 8)” = 23

解决方案:使用堆栈将结果保存在寄生中,并使用符号跟踪符号。 堆栈[previous_Result,符号]

 解决方案(对象): 
  def运算(self,s): 
res,num,sign,stack = 0,0,1,[] #sign从1开始
对于s中的ss:
#获取号码
如果ss.isdigit():
num = 10 * num + int(ss)
[[-],[+]]中的elif ss:#如果它是运算符,则累加结果
res + =符号*数字
num = 0#重置编号
符号= [-1,1] [ss ==“ +”]#如果'+',获取+,设置新符号
elif ss ==“(”:#left parathese,保存旧结果并签名
stack.append(res)
stack.append(签名)
符号,res = 1,0#重置符号和res以从当前的假肢中获得结果
elif ss ==“)”:#rifht parathese,获取当前结果在paratheses内部,然后累加堆栈的res(第一个签名),然后添加前一个结果
res + =符号*数字
res * = stack.pop()
res + = stack.pop()
num = 0#现在设置num
返回res + num * sign

最小大号

556.下一个更大元素III

给定正32位整数n ,您需要找到最小的32位整数,该整数与整数n中存在的数字完全相同,并且值大于n。 如果不存在这样的正32位整数,则需要返回-1。

范例1:

  输入 12 
输出: 21

范例2:

  输入: 21 
输出: -1

分析:第一个解决方案是获取所有数字[1,2],并生成所有排列[[1,2],[2,1]],然后再次生成整数,然后对生成的整数进行排序,以便我们可以选择更大的下一个。 但是时间复杂度是O(n!)。

现在,让我们考虑更多示例以在此处找到规则:
435798-> 435879
1432-> 2134”`
如果我们从最后一个数字开始,则向左看,找到值较小的最接近的数字,然后切换此数字,如果找不到该数字,则搜索第二个最后一个数字。 如果没有找到,那么我们找不到。 像21.返回-1。 这个过程是我们在右边获得第一个更大的数字。
[5、5、7、8,-1,-1]
[2,-1,-1,-1]
之后,我们用7切换8:
4358 97
2431
对于提醒数字,我们进行排序并将其放回那些数字以得到最小值

Python代码:

 类解决方案: 
def getDigits(self,n):
数字= []
而n:
digits.append(n%10)#最不重要的位置
n =整数(n / 10)
返回数字
def getSmallestLargerElement(self,nums):
如果不是数字:
返回[]
rst = [-1] * len(数字)
 对于i,v中的enumerate(nums): 
minimumLargerNum = sys.maxsize
指数= -1
对于范围(i + 1,len(nums))中的j:
如果nums [j]> v,并且smallestLargerNum> nums [j]:
索引= j
minimumLargerNum = nums [j]
如果minimumLargerNum <sys.maxsize:
rst [i] =索引
返回第一个


def nextGreaterElement(self,n):
“”
:type n:整数
:rtype:整数
“”
如果n == 0:
返回-1

数字= self.getDigits(n)
digits = digits [::-1]
#打印(数字)

rst = self.getSmallestLargerElement(digits)
#打印(rst)
stop_index = -1

#开关
对于范围(len(rst)-1,-1,-1)中的i:
如果rst [i]!=-1:#switch
打印('开关')
stop_index =我
digits [i],digits [rst [i]] = digits [rst [i]],digits [i]
打破
如果stop_index == -1:
返回-1

#打印(数字)

#从stop_index + 1到末尾排序
digits [stop_index + 1:] =排序(digits [stop_index + 1:])
打印(数字)
  #将数字化答案转换为整数 
nums = 0
位数= 1
为我的数字[::-1]:
nums + =位数* i
位数* = 10
如果nums> 2147483647:
返回-1


返回数字