摩尔投票法
概念
提问
给定一个int型数组，找出该数组中 出现次数最多的int值。
解决方案
遍历该数组，统计每个int值出现次数，再遍历该集合，取出出现次数最大的int值。
这算是一个比较经典的解决办法，其中可能会用到Map来做统计。如果不使用Map，则时间复杂度会超过线性复杂度。除此之外，也没有什么特别好的办法。
今天在leetcode上遇到这样一道题目，
提问
给定一个int型数组，找出该数组中出现次数大于数组长度一半的int值。
解决方案
遍历该数组，统计每个int值出现次数，再遍历该集合，找出出现次数大于数组长度一半的int值。
同样的，该解决办法也要求使用Map，否则无法达到线性的时间复杂度。
那么对于这个问题，有没有什么不使用Map的线性算法呢？
答案就是今天我们要提到的 摩尔投票法。利用该算法来解决这个问题，我们可以达到线性的时间复杂度以及常量级的空间复杂度。
首先我们 注意到这样一个现象： 在任何数组中，出现次数大于该数组 长度一半的值只能有一个。
通过数学知识，我们可以证明它的正确性，但是这并不在我们这篇博客里涉及。
摩尔投票法的基本思想很简单，在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。这样不断的删除直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半。如果只存在一种元素，那么这个元素则可能为目标元素。
那么有没有可能出现最后有两种或两种以上元素呢？根据定义，这是不可能的，因为如果出现这种情况，则代表我们可以继续一轮投票。因此，最终只能是剩下零个或一个元素。
在算法执行过程中，我们使用常量空间实时记录一个候选元素c以及其出现次数 $f(c)$，c即为当前阶段出现次数超过半数的元素。根据这样的定义，我们也可以将摩尔投票法看作是一种动态规划算法。
程序开始之前，元素c为空，$f(c)=0$。遍历数组A：
- 如果f(c)为0，表示截至到当前子数组，并没有候选元素。也就是说之前的遍历过程中并没有找到超过半数的元素。那么，如果超过半数的元素c存在，那么c在剩下的子数组中，出现次数也一定超过半数。因此我们可以将原始问题转化为它的子问题。此时c赋值为当前元素, 同时f(c)=1。
- 如果当前元素
A[i] == c, 那么 $f(c) += 1$。(没有找到不同元素，只需要把相同元素累计起来) - 如果当前元素
A[i] == c, 那么 $f(c) += 1$。(没有找到不同元素，只需要把相同元素累计起来) - 如果当前元素
A[i] != c，那么 $f(c) -= 1$ (相当于删除1个c)，不对A[i]做任何处理(相当于删除A[i])
如果遍历结束之后，f(c)不为0，则找到可能元素。
再次遍历一遍数组，记录c真正出现的次数，从而验证c是否真的出现了超过半数。上述算法的时间复杂度为O(n)，而由于并不需要真的删除数组元素，我们也并不需要额外的空间来保存原始数组，空间复杂度为O(1)。
看java代码示例，为了保证每一步骤的清晰性，代码没有经过优化。
/**
* 算法基础：摩尔投票法
* @param nums
* @return
*/
public int majorityElement(int[] nums) {
int majority = -1;
int count = 0;
for (int num : nums) {
if (count == 0) {
majority = num;
count++;
} else {
if (majority == num) {
count++;
} else {
count--;
}
}
}
int counter = 0;
if (count <= 0) {
return -1;
} else {
for (int num : nums) {
if (num == majority) counter ++;
}
}
if (counter > nums.length / 2) {
return majority;
}
return -1;
}
其实这样的算法也可以衍生到其它频率的问题上，比如说，找出所有出现次数大于n/3的元素。同样可以以线性时间复杂度以及常量空间复杂度来实现。
常见解题思路
- 摩尔投票法。该算法用于1/2情况，它说：“在任何数组中，出现次数大于该数组长度一半的值只能有一个。”
- 数组中第一位数作为默认的候选人(cand_num)
- 依次向后遍历
- 当出现相同的数(cand_num) 则 投票数 count +1
- 当出现不同的数 则投票(count_num) 投票数 count -1
- 当 count ==0 ，则跟换候选人，并 count 重制为 1
- 遍历完后 count_num 则为最终答案
- 类似题目有
5. 最长回文串
- 难度：
中等 - 本题涉及算法：
中心扩展算法 - 思路：
中心扩展算法 - 类似题型:
题目 5. 最长回文子串
给定一个字符串 s ，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
方法一 中心扩展算法
解题思路
- 首先，要明白
expandAroundCenter函数作用是以一个中心向两侧扩展找到这个中心最长回文串的长度，参数left和right就是为了指定中心。 - 其次，中心可能是一个或两个字符。如：对于字符串“abcda”，“c”是中心；对于字符串“adccda”，“cc”是中心。
- 那么，
expandAroundCenter(s, i, i)就是在找以 i（一个字符）为中心的最长回文串的长度；expandAroundCenter(s, i, i + 1)是在找以 i 和i+1（两个字符）为中心的最长回文串的长度。 - 将得到的两个长度和缓存的最长回文串长度相比较。若新得到的长度较长，表达式：$start = i - (len - 1) / 2$;$end = i + len / 2$; 就得出了新的最长回文串的开始和结束位置。
- 最后，for循环遍历了一遍，以一个字符为中心总共找了 n 次，以两个字符为中心总共找了 n-1 次，所以说“总共有2n−1 个这样的中心”。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i); // 一个中心的情况 aba
int len2 = expandAroundCenter(s, i, i + 1); // 两个中心的情况 abba
int len = Math.max(len1, len2);
if (len > end - start) { // 每次循环 判断最长的回文串首尾
start = i - (len - 1) / 2; // 当一个中心的情况 start = i - len/2 当两个中心的情况 i 右边做了 i+1 操作 所以 len -1
end = i + len / 2; // 这个还好理解
}
}
return s.substring(start, end + 1);
}
// 中心扩展算法
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def longestPalindrome(self,s: str) -> str:
start , end = 0 , 0
for i in range(len(s)-1):
lenOne = self.expandAroundCenter(s,i,i) # 一个中心的情况 aba
lenTwo = self.expandAroundCenter(s,i,i+1) # 两个中心的情况 abba
lenMax = max(lenOne,lenTwo)
if lenMax > end - start: # 每次循环 判断最长的回文串首尾
start = i - (lenMax-1)//2 # // 当一个中心的情况 start = i - len/2 当两个中心的情况 i 右边做了 i+1 操作 所以 len -1
end = i + lenMax//2 # 这个还好理解
return s[start:end+1]
# 中心扩展算法
def expandAroundCenter(self,s:str ,left:int,right:int) ->int:
while left >= 0 and right < len(s) and s[left] == s[right]:
left = left -1
right = right +1
return right - left -1
if __name__ == "__main__":
st = 'abcba'
solution = Solution() # 有括号和没有括号的区别
res = solution.longestPalindrome(st)
print(res)
21. 合并两个有序链表
- 难度：
简单 - 本题涉及算法：
递归 - 思路：
递归 - 类似题型:
题目 21. 合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
方法一 递归
java
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
if (l2 == null)
return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
markdown常见数学符号和运算
MarkDown常用数学符号 记得一定要加$$才可以显示效果
显示效果
语法：
$ 数学符号必须加在运算符号前后
上标
语法：
$x^2$ $x^2$
下标
$x_i$ $x_i$
四则运算
加法运算，符号：$x+y=z$，如：$x+y=z$
减法运算，符号：$x-y=z$ ，如：$x-y=z$
加减运算，符号：$x \pm y=z$，如：$x \pm y=z$
减甲运算，符号：$x \mp y=z$，如：$x \mp y=z$
乘法运算，符号：$x \times y=z$，如：$x \times y=z$
点乘运算，符号：$x \cdot y=z$，如：$x \cdot y=z$
星乘运算，符号：$x \ast y=z$，如：$x \ast y=z$
除法运算，符号：$x \div y=z$，如：$x \div y=z$
斜法运算，符号：$x/y=z$，如：$x/y=z$
分式表示，符号：$\frac{x+y}{y+z}$，如：$\frac{x+y}{y+z}$
分式表示，符号：${x+y} \over {y+z}$，如：${x+y} \over {y+z}$
绝对值表示，符号：如：$|x+y|$，如：$|x+y|$
高级运算
平均数运算，符号：$\overline{xyz}$，如：$\overline{xyz}$
开二次方运算，符号：$\sqrt x$，如：$\sqrt x$
开方运算，符号：$\sqrt[3]{x+y}$，如：$\sqrt[3]{x+y}$
对数运算，符号：$\log(x)$，如：$\log(x)$
微分运算，符号：$\frac{\partial x}{\partial y}$，如：$\frac{\partial x}{\partial y}$
矩阵表示，符号：$\left[ \begin{matrix} 1 &2 &\cdots &4\5 &6 &\cdots &8\\vdots &\vdots &\ddots &\vdots\13 &14 &\cdots &16\end{matrix} \right]$，如：$\left[ \begin{matrix} 1 &2 &\cdots &4\5 &6 &\cdots &8\vdots &\vdots &\ddots &\vdots\13 &14 &\cdots &16\end{matrix} \right]$
逻辑运算
等于运算，符号：$x+y=z$，如：$x+y=z$
大于运算，符号：$x+y>z$，如：$x+y>z$
小于运算，符号：$x+y<z$，如：$x+y<z$
大于等于运算，符号：$x+y \geq z$，如：$x+y \geq z$
小于等于运算，符号：$x+y \leq z$，如：$x+y \leq z$
不等于运算，符号：$x+y \neq z$，如：$x+y \neq z$
不大于等于运算，符号：$x+y \ngeq z$，如：$x+y \ngeq z$
不大于等于运算，符号：$x+y \not\geq z$，如：$x+y \not\geq z$
不小于等于运算，符号：如：$x+y \nleq z$，如：$x+y \nleq z$
不小于等于运算，符号：如：$x+y \not\leq z$，如：$x+y \not\leq z$
约等于运算，符号：$x+y \approx z$，如：$x+y \approx z$
恒定等于运算，符号：$x+y \equiv z$，如：$x+y \equiv z$
包括整体
语法：
$Z^{yx}$ $Z^{yx}$
大括号
语法：
$ \left(大括号)\right. $ $\left(大括号)\right.$
分割线
语法：
$\frac{ x }{ y } $\frac{ x }{ y }$
开方
语法：
$ \sqrt{ x } $ $\sqrt{ x }$
$ \sqrt[ 3 ]{ x } $ $\sqrt[ 3 ]{ x }$
省略号
语法：
$ \ldots $ 表示与文本底线对齐的省略号，$ \cdots $ 表示与文本中线对齐的省略号 $\ldots $ $ \cdots$
矢量
语法：
$ \vec{ a } $ $\vec{ a }$
积分
语法：
$ \int_0^2 x^2 {\rm d}x $ $\int_0^2 x^2 {\rm d}x$
极限
语法：
$ \lim\limits_{n \rightarrow +\infty} \frac{1}{n(n+1)} $ $\lim\limits_{n \rightarrow +\infty} \frac{1}{n(n+1)}$
累加
语法：
$\sum_{i=0}^n$ $\frac{1}{i^2} $ $\sum_{i=0}^n$ $\frac{1}{i^2}$
累乘
语法：
$\prod_{i=0}^n \frac{1}{i^2}$ $\prod_{i=0}^n \frac{1}{i^2}$
希腊字母
$\alpha$ $\alpha$
$\beta$ $\beta$
$\gamma$ $\gamma$
$\Gamma$ $\Gamma$
$\delta$ $\delta$
$\Delta$ $\Delta$
$\epsilon$ $\epsilon$
$\varepsilon$ $\varepsilon$
$\zeta$ $\zeta$
$\eta$ $\eta$
$\theta$ $\theta$
$\Theta$ $\Theta$
$\vartheta$ $\vartheta$
$\iota$ $\iota$
$\kappa$ $\kappa$
$\lambda$ $\lambda$
$\Lambda$ $\Lambda$
$\mu$ $\mu$
$\nu$ $\nu$
$\xi$ $\xi$
$\Xi$ $\Xi$
$\pi$ $\pi$
$\Pi$ $\Pi$
$\varpi$ $\varpi$
$\rho$ $\rho$
$\varrho$ $\varrho$
$\sigma$ $\sigma$
$\varsigma$ $\varsigma$
$\tau$ $\tau$
$\upsilon$ $\upsilon$
$\Upsilon$ $\Upsilon$
$\phi$ $\phi$
$\Phi$ $\Phi$
$\varphi$ $\varphi$
$\chi$ $\chi$
$\psi$ $\psi$
$\Psi$ $\Psi$
$\omega$ $\omega$
$\Omega$ $\Omega$
关系运算符：
$\pm$ $\pm$
$\times$ $\times$
$\div$ $\div$
$\mid$ $\mid$
$\nmid$ $\nmid$
$\cdot$ $\cdot$
$\circ$ $\circ$
$\ast$ $\ast$
$\bigodot$ $\bigodot$
$\bigotimes$ $\bigotimes$
$\bigoplus$ $\bigoplus$
$\leq$ $\leq$
$\geq$ $\geq$
$\neq$ $\neq$
$\approx$ $\approx$
$\equiv$ $\equiv$
$\sum$ $\sum$
$\prod$ $\prod$
$\coprod$ $\coprod$
集合运算符：
$\emptyset$ $\emptyset$
$\in$ $\in$
$\notin$ $\notin$
$\subset$ $\subset$
$\supset$ $\supset$
$\subseteq$ $\subseteq$
$\supseteq$ $\supseteq$
$\bigcap$ $\bigcap$
$\bigcup$ $\bigcup$
$\bigvee$ $\bigvee$
$\bigwedge$ $\bigwedge$
$\biguplus$ $\biguplus$
$\bigsqcup$ $\bigsqcup$
对数运算符：
$\log$ $\log$
$\lg$ $\lg$
$\ln$ $\ln$
三角运算符：
$\bot$ $\bot$
$\angle$ $\angle$
$30^\circ$ $30^\circ$
$\sin$ $\sin$
$\cos$ $\cos$
$\tan$ $\tan$
$\cot$ $\cot$
$\sec$ $\sec$
$\csc$ $\csc$
微积分运算符：
$\prime$ $\prime$
$\int$ $\int$
$\iint$ $\iint$
$\iiint$ $\iiint$
$\iiiint$ $\iiiint$
$\oint$ $\oint$
$\lim$ $\lim$
$\infty$ $\infty$
$\nabla$ $\nabla$
逻辑运算符：
$\because$ $\because$
$\therefore$ $\therefore$
$\forall$ $\forall$
$\exists$ $\exists$
$\not=$ $\not=$
$\not>$ $\not>$
$\not\subset$ $\not\subset$
戴帽符号：
$\hat{y}$ $\hat{y}$
$\check{y}$ $\check{y}$
$\breve{y}$ $\breve{y}$
$\bar{a}$ $\bar{a}$
$\tilde{a}$ $\tilde{a}$
$\widetilde{A}$ $\widetilde{A}$
$\vec{a}$ $\vec{a}$
$\dot$ $\dot
$\ddot$ $\ddot
连线符号：
$\overline{a+b+c+d}$ $\overline{a+b+c+d}$
$\overbrace{a+\underbrace{b+c}{1.0}+d}^{2.0}$ $\overbrace{a+\underbrace{b+c}{1.0}+d}^{2.0}$
箭头符号：
$\uparrow$ $\uparrow$
$\downarrow$ $\downarrow$
$\Uparrow$ $\Uparrow$
$\Downarrow$ $\Downarrow$
$\rightarrow$ $\rightarrow$
$\leftarrow$ $\leftarrow$
$\Rightarrow$ $\Rightarrow$
$\Leftarrow$ $\Leftarrow$
$\longrightarrow$ $\longrightarrow$
$\longleftarrow$ $\longleftarrow$
$\Longrightarrow$ $\Longrightarrow$
$\Longleftarrow$ $\Longleftarrow$
分段函数
\[函数名=\begin{cases} 公式1 & 条件1 \\ 公式2 & 条件2 \\ 公式3 & 条件3 \end{cases}\]$$ 函数名=\begin{cases}
公式1 & 条件1 \\
公式2 & 条件2 \\
公式3 & 条件3
\end{cases}$$
$$
\left[
\begin{matrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{matrix}
\right] \tag{3}
$$
202. 快乐数
- 难度：
简单 - 本题涉及算法：
算数用HashSet检测循环快慢指针法 - 思路：
算数用HashSet检测循环快慢指针法 - 类似题型:
题目 202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
示例：
输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
方法一 算数
解题思路
- 根据题意 ，可得出伪代码
def getNum(n): while n!=0: a = n%10 n //= 10 return a - 使用 divmod 方法
def get_next(number): total_sum = 0 while number > 0: number, digit = divmod(number, 10) total_sum += digit ** 2 return total_sum - 根据题目发现判断条件
- 列出所有可能的条件
代码
class Solution:
def isHappy(self, n: int) -> bool:
cycle_members = {4, 16, 37, 58, 89, 145, 42, 20}
def get_next(number):
total_sum = 0
while number > 0:
number, digit = divmod(number, 10)
total_sum += digit ** 2
return total_sum
while n != 1 and n not in cycle_members:
n = get_next(n)
return n == 1
一路debug 得出的答案
- 根据题目发现判断条件
- 当 sumNum = 1 返回True
- 当 sumNum = 7 返回True 需要多 n = 1111111 单独判断
- 当 1 < sumNum < 10 即 循环后 n = 2 和 3 的会出现 无限循环的情况
- 当 sumNum > 10 ,则 赋值 n = sumNum 继续循环
代码
class Solution:
def isHappy(self, n: int) -> bool:
sumNum = 0;
while n!=0:
sumNum += (n%10)*(n%10)
n //= 10
if n == 0:
if sumNum == 1 or sumNum==7:
return True
if sumNum<10:
return False
else :
n = sumNum
sumNum = 0
方法二 用 HashSet 检测循环
解题思路
- 最终会得到 11。
- 最终会进入循环。
- 值会越来越大，最后接近无穷大。
- 检查数字是否在哈希集中需要 O(1) 的时间，而对于其他数据结构，则需要 O(n) 的时间
代码
```python func isHappy(n int) bool { m := map[int]bool{} for ; n != 1 && !m[n]; n, m[n] = step(n), true { } return n == 1 }
func step(n int) int { sum := 0 for n > 0 { sum += (n%10) * (n%10) n = n/10 } return sum }
### 方法三 快慢指针法
#### 解题思路
通过反复调用 getNext(n) 得到的链是一个隐式的链表。隐式意味着我们没有实际的链表节点和指针，但数据仍然形成链表结构。起始数字是链表的头 “节点”，链中的所有其他数字都是节点。next 指针是通过调用 getNext(n) 函数获得。
意识到我们实际有个链表，那么这个问题就可以转换为检测一个链表是否有环。因此我们在这里可以使用弗洛伊德循环查找算法。这个算法是两个奔跑选手，一个跑的快，一个跑得慢。在龟兔赛跑的寓言中，跑的快的称为 “乌龟”，跑得快的称为 “兔子”。
不管乌龟和兔子在循环中从哪里开始，它们最终都会相遇。这是因为兔子每走一步就向乌龟靠近一个节点（在它们的移动方向上）。
```python
def isHappy(self, n: int) -> bool:
def get_next(number):
total_sum = 0
while number > 0:
number, digit = divmod(number, 10)
total_sum += digit ** 2
return total_sum
slow_runner = n
fast_runner = get_next(n)
while fast_runner != 1 and slow_runner != fast_runner:
slow_runner = get_next(slow_runner)
fast_runner = get_next(get_next(fast_runner))
return fast_runner == 1
339 post articles, 43 pages.