算法题中常用的➷➷➷数学定理

╰+哭是因爲堅強的太久メ 2022-12-28 12:42 161阅读 0赞

### 牛顿迭代法 ###

详细见【[牛顿迭代法][Link 1]】

设r是**f(x) = 0**的根，选取x0作为r初始近似值，过点\*\*(x0, f(x0))\*\*作曲线y=f(x)的切线L，切线L的方程为

**y = f(x0) + f’(x0)(x-x0)**，求出L与x轴交点的横坐标 **x1 = x0 - f(x0) / f’(x0)** ，称x1为r的一次近似值

过点(x1, f(x1))作曲线y=f(x)的切线，以此迭代，其中`x(n+1)=x(n)-f(x(n))/f'(x(n))`，称为r的n+1次迭代值，上式为牛顿迭代公式

#### 【练习】求x的平方根 ####

[LeetCode x的平方根][LeetCode x]

可转化为求`x^2 - a = f(x)`的根

public int mySqrt(int x) {
        
    	if(x <= 1) {
        
    		return x;
    	}
    	int r = x / 2;
    	while(r > x / r) {
        
    		r = (r + x / r) / 2;
    	}
    	return r;
    }

public double sqrt(double c) {
        
        if(c < 0) return Double.NaN;    //not a number
        double err = le-15;
        double t = c;
        while(Math.abs(t - c/t) > err * t) {
        
            t = (t + c / t) / 2.0;
        }
        return t;
    }

#### 求m的开n次方根 ####

public static double mySqrtN(double m, double n) {
        
            if (m == 0) return 0;
            double err = 1e-8;
            double t = m / 2, pre = m;
            while (Math.abs(pre - t) > t * err) {
        
                pre = t;
                t = ((n - 1) * t + m / Math.pow(t, n - 1)) / n;
            }
            return t;
        }

--------------------

### 最大公约数 ###

#### 线性检测法 ####

public int gcd(int x, int y) {
        
        int res = 1;
        int min = Math.min(x, y);
        for(int i = 2; i <= min; i++) {
        
            if(x % i == 0 && y % i == 0) {
        
                res = i;
            }
        }
        return res;
    }

#### 更相减损法 ####

public int gcd(int x, int y) {
        
        while(x != y) {
        
            if(x > y) {
        
                x -= y;
            }else {
        
                y -= x;
            }
        }
        return x;
    }

#### 辗转相除法 ####

public int gcd(int x, int y) {
        
        return y == 0 ? x : gcd(y, x % y);
    }

### 最小公倍数 ###

最小公倍数为两数之积除以其最大公约数

public int lcm(int x, int y) {
        
        return (int)((long)x * y / gcd(x, y));
    }

--------------------

### 摩尔投票法 ###

详细见[知乎][Link 2]

算法解决的问题是如何在任意多的候选人（选票无序），选择获取票数最多的那个，即求**众数**

*  **在任何数组中，出现次数大于该数组长度一半的值只能有一个**
 *  **在任何数组中，出现次数大于该数组长度1/3的数最多有2个**

#### 【练习】多数元素 ####

[LeetCode 多数元素][LeetCode]

给定一个大小为 *n* 的数组，找到其中的多数元素。多数元素是指在数组中出现次数**大于** `⌊ n/2 ⌋` 的元素

例如：输入\[2,2,1,1,1,2,2\]，输出2

【**解题思路**】遇到相同的数，就投1票；遇到不同的数，就减1票，若当前候选数票数为0，则更新候选数，最后还存在票的数就是众数

public int majorityElement(int[] nums) {
        
    	int res = Integer.MIN_VALUE, count = 0;
    	for(int x : nums) {
        
    		if(x == res) {
        
    			count++;
    		}else {
        
    			count--;
    			if(count <= 0) {
        
    				res = x;
    				count = 1;
    			}
    		}
    	}
    	return res;
    }

#### 【练习】求众数II ####

[LeetCode 求众数II][LeetCode _II]

给定一个大小为 *n* 的整数数组，找出其中所有出现超过 `⌊ n/3 ⌋` 次的元素

【解题思路】使用两个变量one和two，和两个计数变量count1和count2，投票之后重新遍历数组看one和two的出现次数是否大于n/3

--------------------

### 费马平方和定理 ###

一个非负整数c能够表示为两个整数的平方和，当且仅当c的所有形如**4k+3的质因子的幂次均为偶数**

或：自然数n可以表示为两个平方数之和等价于n的每个形如p=4m+3的素因子的幂次为偶数

#### 【练习】平方数之和 ####

[LeetCode 平方数之和][LeetCode 1]

给定一个非负整数 `c` ，你要判断是否存在两个整数 `a` 和 `b`，使得 `a^2 + b^2 = c`

public boolean judgeSquareSum(int c) {
        
    	int count, x;
    	for(int i = 2; i <= Math.sqrt(c); i++) {
        
    		if(c % i == 0) {
        
    			count = 0;
    			while(c % i == 0) {
        
    				count++;
    				c /= i;
    			}
    			if(i % 4 == 3 && count % 2 != 0) {
        
    				return false;
    			}
    		}
    	}
    	return c % 4 != 3;
    }

--------------------

### 短路算法 ###

#### 【练习】求1+2+···+n的值 ####

[LeetCode 求1···n之和][LeetCode _1_n]

求 `1+2+...+n` ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）

public int sumNums(int n) {
        
    	int x = n;
    	boolean yn = x > 0 && (x += sumNums(n - 1)) > 0;
    	return x;
    }

--------------------

### 巴什博弈 ###

只有一堆n个物品，两人轮流从这堆物品中取，规定每次至少取一个，最多取m（m > 1）个，最后取光者获胜。

`若 n % (m + 1) != 0 ，先手可获胜`

`若 n % (m + 1) == 0，后手可获胜`

--------------------

### 完全平方数 ###

1 + 3 + 5 + ⋅ ⋅ ⋅ + ( 2 n + 1 ) = n 2 1+3+5+···+(2n+1)=n^2 1\+3\+5\+⋅⋅⋅\+(2n\+1)=n2

等 差 数 列 求 和 公 式 ： S = n S 1 + n ( n − 1 ) / 2 d 等差数列求和公式：S=nS\_1+n(n-1)/2 d 等差数列求和公式：S=nS1\+n(n−1)/2d

代 入 得 ： n + ( n ( n − 1 ) ) / 2 × 2 = n 2 代入得：n+(n(n-1))/2×2= n^2 代入得：n\+(n(n−1))/2×2=n2

【性质】

*  平方数的个位数只能是0、1、4、5、6、9
 *  完全平方数的个位是奇数时，其十位必为偶数。若个位为6时，十位必为奇数
 *  若a，b为完全平方数，则**a\*b**也是
 *  形式必为以下两种之一：**3k**，**3k+1**
 *  一个正整数是完全平方数的充分必要条件是n有**奇数个因数**（包括1和n本身）

--------------------

### 杨辉三角 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

第 n 行 第 i 个 为 ： C ( n , i ) = n ! / ( i ! × ( n − i ) ! ) 第n行第i个为： C(n,i)=n!/(i!×(n-i)!) 第n行第i个为：C(n,i)=n!/(i!×(n−i)!)

第 i + 1 项 是 第 i 项 的 （ n − i ) / ( i + 1 ) 倍 第i+1项是第i项的（n-i)/(i+1)倍 第i\+1项是第i项的（n−i)/(i\+1)倍

--------------------

### 一日属于一周中星期几 ###

【注意】以下两公式需注意，若为一月和二月，则看做去年的13月和14月输入，同时在年份上减1

即**m+12**，**y-1**

#### 蔡勒公式（Zeller’s congruence） ####

1582年10月4日之后

*  w：星期0-6为星期日-六
 *  c：年份前两位数
 *  y：年份后两位数
 *  m：月
 *  d：日
 *  \[　\]：称作高斯符号，代表向下取整，即，取不大于原数的最大整数

w = ( y + \[ y / 4 \] + \[ c / 4 \] − 2 c + \[ 26 ( m + 1 ) / 10 \] + d − 1 ) w=(y+\[y/4\]+\[c/4\]-2c+\[26(m+1)/10\]+d-1) w=(y\+\[y/4\]\+\[c/4\]−2c\+\[26(m\+1)/10\]\+d−1)

w = ( w % 7 + 7 ) % 7 w=(w\\%7+7)\\%7 w=(w%7\+7)%7

#### 基姆拉尔森计算公式（Kim larsen） ####

*  y：年份
 *  m：月份
 *  d：日数

w = ( d + 2 m + 3 / 5 ( m + 1 ) + y + y / 4 − y / 100 + y / 400 + 1 ) m o d 7 w=(d+2m+3/5 (m+1)+y+y/4-y/100+y/400+1)mod7 w=(d\+2m\+3/5(m\+1)\+y\+y/4−y/100\+y/400\+1)mod7

--------------------

### 蒙特卡罗法 ###

Monte Carlo方法，或称为计算机随机模拟法，是一种基于“随机数”的计数方法

//java随机数产生方法
    int x = (int)(Math.random()*100)+222;
    //-------
    Random r = new Random();
    int x = r.nextInt(100) + 50;

【练习】一个数组中有一个数字出现了两次，其他的都出现了1次，找出这个数

当数据量较大时，特别耗时

public int findSameNum(int[] nums) {
        
        int n = nums.length;
        Random r = new Random();
        while(true) {
        
            int i = r.nextInt(n);
            int j = r.nextInt(n);
            if(i != j && nums[i] == nums[j]) {
        
                return nums[i];
            }
        }
    }

--------------------

### 纳什均衡 ###

纳什平衡，又称为非合作博弈均衡，是博弈论的一个重要术语，以约翰·纳什命名。在一个博弈过程中，无论对方的策略选择如何，当事人一方都会选择某个确定的策略，则该策略被称为支配性策略。如果任意一位参与者在其他所有参与者的策略确定的情况下，其选择的策略是最优的，那么这个组合就被称为**纳什平衡**

一个策略组合被称为纳什平衡，当每个博弈者的平衡策略都是为了达到自己期望收益的最大值，与此同时，其他所有博弈者也遵循这样的策略

--------------------

### 一笔画问题 ###

`奇点数目是0或者是2`

*  凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点作为起点，最后一定能以这个点为终点画完此图
 *  凡是只有两个奇点的连通图（其余点都为偶点），一定可以一笔画画完。画时必须把一个奇点作为起点，另一个奇点作为终点
 *  其他情况的图都不能一笔画画出（由偶数个奇结点除以2可以算出此图至少需要几笔画成）

--------------------

### 康托展开 ###

康拓展开是一个全排列到一个自然数的双射，常常用于构建哈希表时的空间压缩。康拓展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的  
 X = a n ( n − 1 ) ! + a ( n − 1 ) ( n − 2 ) ! + ⋯ + a 1 × 0 ! X=a\_n (n-1)!+a\_(n-1\_) (n-2)!+⋯+a\_1×0! X=an(n−1)!\+a(n−1)(n−2)!\+⋯\+a1×0!  
其中，ai为整数，并且ai属于\[0，i\]，i属于\[i，n\]

`ai表示原数的第i位在当前末出现的元素中是排在第几个（排在它后面比它大的数字有几个）`

如（1,2,3,4,5）5个数，计数**34152**的康托展开值为  
 X = 2 × 4 ! + 2 × 3 ! + 0 × 2 ! + 1 × 1 ! + 0 × 0 ! = 61 X=2×4!+2×3!+0×2!+1×1!+0×0!=61 X=2×4!\+2×3!\+0×2!\+1×1!\+0×0!=61  
不难理解，首位比3小的数字有1和2，所以有两种可能，剩下的随意放，共有2x4!种情况，忽略最高位（即小于30000的排列共有2x4!种情况），接下来考虑比4152小的全排列个数，比最高位4小的数有1和2，即共有2x3!种情况，34000之前的已计算完，之后再考虑152，以此类推······

**逆康托展开举例**：如（1,2,3,4,5）求其第62个

则排在其前面有61个

61/4! = 2···13 a\[5\]=2 首位为3

13/3! = 2···1 a\[4\]=2 第二位为4

1/2! = 0···1 a\[3\]=0 第三位为1

1/1! = 1···0 a\[2\]=1 第四位为5

\------------------ a\[1\]=0 第五位为2

即为 **34152**

详细见搜狗百科[康托展开][Link 3]

#### 【练习】排列序列 ####

[LeetCode排列序列][LeetCode 2]

输入n和k，返回1-n按其升序排列的第k个排列序列

按大小顺序列出所有排列情况，并一一标记，当 `n = 3` 时, 所有排列如下：

1.  \[123\]
2.  \[132\]
3.  \[213\]
4.  \[231\]
5.  \[312\]
6.  \[321\]

当k = 4时应输出“231”

class Solution {
        
        public String getPermutation(int n, int k) {
        
            int[] factor = new int[n];
            factor[0] = 1;
            for(int i = 1; i < n; i++) {
        
                factor[i] = factor[i - 1] * i;
            }
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 1; i <= n; i++) {
        
                list.add(i);
            }
            k--;
            StringBuffer sb = new StringBuffer();
            for(int i = n - 1; i >= 0; i--) {
        
                int t = k / factor[i];
                //使用remove()方法恰到好处，若不使用，可标记已经用过的数字来实现查找
                sb.append(list.remove(t));  
                k %= factor[i];
            }
            return sb.toString();
        }
    }

--------------------

### 埃氏筛选法 ###

[LeetCode 计算质数][LeetCode 3]

统计所有小于非负整数 *`n`* 的质数的数量

下图来自力扣题解[Sweetiee][]

![在这里插入图片描述][20201217095206270.gif_pic_center]

public int countPrimes(int n) {
        
    	int count = 0;
    	boolean[] isPrime = new boolean[n];
    	Arrays.fill(isPrime, true);
    	for(int i = 2; i < n; i++) {
        
    		if(isPrime[i]) {
        
    			count++;
    			if((long)i * i < n) {
        
    				for(int j = i * i; j < n; j += i) {
        
    					isPrime[j] = false;
    				}
    			}
    		}
    	}
    	return count;
    }

时间复杂度：O\*(*n*loglog\*n)  
空间复杂度：O(n)

--------------------

### 贝祖定理 ###

对于任何整数a，b和它们的`最大公约数d`，关于未知数x和y的线型不定方程（称为贝祖等式）：若a，b是整数，且gcd(a, b) = d，那么对于任意的整数x，y，ax+by都一定是d的倍数，特别地，一定存在整数x，y，使  
 a x + b y = d ax+by=d ax\+by=d  
成立

#### 【练习】水壶问题 ####

[LeetCode 水壶问题][LeetCode 4]

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水

你允许：

*  装满任意一个水壶
 *  清空任意一个水壶
 *  从一个水壶向另外一个水壶倒水，直到装满或者倒空

class Solution {
        
        public boolean canMeasureWater(int x, int y, int z) {
        
            if(x + y < z) {
        
                return false;
            }
            if(x == 0 || y == 0) {
        
                return z == 0 || x + y == z;
            }
            return z % gcd(x, y) == 0;
        }
        private int gcd(int x, int y) {
        
           return y == 0 ? x : gcd(y, x % y);
        }
    }

【方法二】使用栈来模拟（超时）

/*
    初始化栈为int[]{0, 0}
    把x灌满
    把y灌满
    把x倒空
    把y倒空
    把x倒入y，直至x空或者y满
    把y倒入x，直至x满或者y空
    */

--------------------

最后编辑于2021.2.20  
此篇持续更新中······

[Link 1]: https://baike.sogou.com/v1846821.htm?fromTitle=%E7%89%9B%E9%A1%BF%E8%BF%AD%E4%BB%A3%E6%B3%95
[LeetCode x]: https://leetcode-cn.com/problems/sqrtx/
[Link 2]: https://zhuanlan.zhihu.com/p/104609555
[LeetCode]: https://leetcode-cn.com/problems/majority-element/
[LeetCode _II]: https://leetcode-cn.com/problems/majority-element-ii/
[LeetCode 1]: https://leetcode-cn.com/problems/sum-of-square-numbers/
[LeetCode _1_n]: https://leetcode-cn.com/problems/qiu-12n-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/10da3c788e54491598d4edeacb7b3763.png
[Link 3]: https://baike.sogou.com/v55671042.htm?fromTitle=%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80
[LeetCode 2]: https://leetcode-cn.com/problems/permutation-sequence/
[LeetCode 3]: https://leetcode-cn.com/problems/count-primes/
[Sweetiee]: https://leetcode-cn.com/problems/count-primes/solution/kuai-lai-miao-dong-shai-zhi-shu-by-sweetiee/
[20201217095206270.gif_pic_center]: /images/20221120/6692618f4e9f49358c32016fe25adb24.png
[LeetCode 4]: https://leetcode-cn.com/problems/water-and-jug-problem/