形式化分析 LeetCode 2048. Next Greater Numerically Balanced Number
Problem
2048. Next Greater Numerically Balanced Number
Analysis
这是上周周赛的一道题,早该写了。
根据题意,111 要么不出现,要么只能出现 111 次,222 同理只能出现 000 或 222 次,则 iii 的出现次数记为 xix_ixi 的话,就有 xi∈{0,i}x_i \in \{0, i\}xi∈{0,i}。
我们不妨记一个 balanced number 的数位有 mmm 个,显然这 mmm 个数字只能从集合 {1,2,...,m}\{1,2,...,m\}{1,2,...,m} 里面取,因为如果你取了 m+1m+1m+1,则根据规则它必须出现 m+1m+1m+1 次,我们只有 mmm 个数位,显然放不开,至于 0。它只能出现 0 次,直接没法用。
既然知道了每个数位的取值集合,那我们就可以考察集合内每个元素在 mmm 个数位中的出现次数,不妨记数字 iii 出现了 xix_ixi 次,其中 i∈{1,2,...,m},xi∈{0,i}i \in \{1,2,...,m\}, x_i \in \{0, ...
数学证明 LeetCode 31. Next Permutation
Problem
31. Next Permutation
Proof
这个题目有个很绝妙的算法,在这里有介绍,文章里给出了直觉上的认识,通俗易懂但是不够严格,我这里再证明一下。先把原图搬过来。想偷懒的原文其实可以不看,只看这张图就能知道这算法干了什么。
我们主要关心这个算法的正确性如何。不妨令数组为nums,把第2步中的pivot记为i,则数组被分为nums[0:i]和nums[i+1, n-1]两部分,算法会确保后者是非递增的。那么这么个操作流程下来,最终生成的排列PPP到底是不是 第一个 比原排列OOO大的排列呢,我们用反证法,先假设如下命题为真:
存在一个更优的解——排列QQQ,它比这个排列PPP更小,且比原排列OOO更大
首先注意到P和原排列O的nums[0:i-1]位完全一致,即有P[0:i−1]=Q[0:i−1]P[0:i-1] = Q[0:i-1]P[0:i−1]=Q[0:i−1],而Q的大小在他们之间,所以毫无疑问P[0:i−1]=O[0:i−1]=Q[0:i−1]P[0:i-1] = O[0:i-1] = Q[0:i-1]P[0:i−1]=O[0:i−1]=Q[0: ...
数学证明 LeetCode 41. First Missing Positive
这个证明思路是昨晚洗澡时想好的,现在写下来。
Problem
41. First Missing Positive
Proof
首先有如下引理:
如果第一个缺失的正数是 a,那么 [1, a-1] 区间上的每一个数一定是数组内的元素。
我们先用反证法证明这个引理。
设立两个简单命题,并组成复合命题:
简单命题 p:p:p: 第一个缺失的正数是 a
简单命题 q:q:q: ∃b∈[1,a−1],b∉array\exists b \in [1, a-1], b \notin array∃b∈[1,a−1],b∈/array
复合命题 P:P:P: p⇒qp \Rightarrow qp⇒q
命题 ppp 是我们的基本设定,值为真,命题 q 是我们要考察的命题,暂时不知道真假。
我们首先假设命题 PPP 成立,又因为 ppp 为真,所以推出 qqq 也为真。又因为 b∈[1,a−1]b \in [1, a-1]b∈[1,a−1] 即 b<ab < ab<a,那么就有 (b<a)∧(b∉array)\left (b < a\right ) \wedge \ ...
数学证明 LeetCode 189. Rotate Array
这篇证明当初做完题就该写了,我太懒了,留了个坑,两周了才来补全。
Problem
189. Rotate Array
Proof
把数组元素个数记为 nnn,旋转数目记为 kkk,我们对这个题目的思路是可以先把位置 iii 的元素放入到 (i+k) mod n(i+k) \bmod n(i+k)modn 的位置,这样此位置的原元素会被逐出,我们再把逐出的元素放到它该去的位置即 ((i+k) mod n+k) mod n((i+k) \bmod n + k) \bmod n((i+k)modn+k)modn 下标处。这样一直进行下去,最终会不会绕一圈即目标位置刚好是 iii 呢。这是肯定的。我们把这期间经历的步数记为 mmm。则有:
n∑j=1mcoeffj=mk(1)n\sum_{j=1}^{m}coeff_{j}=mk \tag{1}
nj=1∑mcoeffj=mk(1)
这玩意儿咋得来的。其实很简单,下标 iii 的元素其目标位置是 (i+k) mod n(i+k) \bmod n(i+k)modn,(i+k) mod n(i+k) \bmod n(i+k)modn 元素的目标 ...