首先我们看一个非对称加密在现实中的具体应用(笑 有学生没带作业, 老师需要在群里提醒家长, 但直接发学生的照片就会被所有家长知道没带作业的学生是谁, 这样会导致学生和家长都很没面子. 所以老师使用了公钥(大家都能看到的): 学生的鞋子. 大家看到的只是三个学生的鞋子, 并不知道学生具体是谁, 即看到的是密文. 家长看到了鞋子, 因为拥有私钥(即只有家长自己知道自己家孩子穿的什么样的鞋), 所以可以知道老师发的照片中学生是谁, 破解了密文, 这就完成了一次非对称性的加密和解密. 换成严谨一点的语言描述, 如下: A要向B发送信息，A和B都要产生一对用于加密和解密的公钥和私钥。 A的私钥保密，A的公钥告诉B；B的私钥保密，B的公钥告诉A。 A要给B发送信息时，A用B的公钥加密信息，因为A知道B的公钥。 A将这个消息发给B（已经用B的公钥加密消息）。 B收到这个消息后，B用自己的私钥解密A的消息。其他所有收到这个报文的人都无法解密，因为只有B才有B的私钥。 从上文可以看出, 非对称加密体系不要求通信双方事先传递密钥或有任何约定就能完成保密通信，并且密钥管理方便，可实现防止假冒和抵赖，因此，更适合网络通信中的保密通信要求. 原理 根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥. 获取公钥私钥过程 选择两个很大的素数p和q 这里取$p=67,q=71$ 计算$n=p⋅q, n$公开, 即为公钥的一部分. (如果$n=p⋅q=4757_{(10)}=1001010010101_{(2)}$, 二进制的n为13位, 则称该加密为13位加密, 实际应用中一般才用1024位或2048位的加密来保证安全). 计算 n 的欧拉函数 $φ(n)$ 设$m=φ(n)=φ(q)⋅φ(q)=(q−1)(p−1)=66×70=4620.$ 在数论，对正整数n，欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1(1), φ(8)=4(1,3,5,7）, 这里的p,q都是质数, 所以从1到(n-1)都与其互质, φ(n)=n−1 再选一个数字e, e与m互质, 且1<e<m, e也是公开的, 即公钥的另一部分. 这里取e=101, 这里e的选择有一个小坑, 我们一会再说 找到一个整数 d，可以使得 e∗d 等价于$e*d−1=y∗m, y∈N+$, 将数字带入$101×d−1=y×4757$, 这里可用扩展欧几里得算法解, 下文给出过程, 这里省略. 给出结果$(d,y)=(1601,35)$, 即$d=1601$, 从这里可以看出, d是由我们上面第4步任意取的e决定的, 所以我们只要选取不同的e, 就可以得到不同的d, 就是不同的密钥对. ...

问题描述 给定一个只包括 '(', ')', '{', '}', '[', ']' 的字符串, 判断字符串是否有效. 有效字符串需满足： 左括号必须用相同类型的右括号闭合. 左括号必须以正确的顺序闭合. 注意空字符串可被认为是有效字符串. 题目地址:https://leetcode-cn.com/problems/valid-parentheses/ (看了评论才知道是B站开发岗面试题) 示例 输入: "()" 输出: true 输入: "()[]{}" 输出: true 输入: "(]" 输出: false 输入: "([)]" 输出: false 输入: "{[]}" 输出: true 解答 思路一 class Solution: def isValid(self, s): while '{}' in s or '()' in s or '[]' in s: s = s.replace('{}', '') s = s.replace('[]', '') s = s.replace('()', '') return s == '' 对于正确的来说, 每次都能去掉一对括号, 最后就成了空. 思路二 其实这个题主要是考大家关于栈的应用 原理 栈先入后出特点恰好与本题括号排序特点一致, 即若遇到左括号入栈, 遇到右括号时将对应栈顶左括号出栈, 则遍历完所有括号后 stack 仍然为空； 建立哈希表dic构建左右括号对应关系：key 左括号, value 右括号；这样查询 2 个括号是否对应只需 $O(1)$ 时间复杂度；建立栈 stack, 遍历字符串s 并按照算法流程一一判断. 流程 如果 c 是左括号, 则入栈 push； 否则通过哈希表判断括号对应关系, 若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应, 则提前返回 false. ...

透视的原理 单点透视 根据常识我们可以知, 走廊两边的墙一般是平行的直线, 但在摄影作品中我们会发现, 体现在照片中的走廊趋势并不是平行的, 具体体现 画一下透视可以看出 所有物理上不平行于视线的线, 延长后最终趋近于一点, 本文是探讨一下为什么会出现这种结果. 设这么一个场景 已知摄像机位置, 也就是漫画中我们读者的视角或者照片中相机所在的位置. 其距离1点的物理距离为 $L_1=\sqrt{x^2+R^2}$ , 距离2点则为$L_2=\sqrt{x^2+(2R)^2}$, 即距离n点的位置为$L_n=\sqrt{x^2+(nR)^2}$, x固定不变, 当n逐渐增大的时候, $\lim\limits_{\substack{n\to\infty }} L_n=nR$, x可以忽略不计, 此时两点的距离(图中橙色的部分) 两个橙色的长度在极限距离可以视作相等, 根据上述距离公式$L_n=\sqrt{x^2+(nR)^2}$(自变量为$n$)可以知道, 此函数一阶导数为$L_n’=\dfrac{R^2}{\sqrt{\dfrac{x^2}{n^2}+R^2}}$, 随着n的增大, 导数值逐渐变大, 最终趋向1, 即最终L最终等于R(常数),

只出现一次的数字 问题描述 给定一个非空整数数组, 除了某个元素只出现一次以外, 其余每个元素均出现两次. 找出那个只出现了一次的元素. 题目地址: https://leetcode-cn.com/problems/single-number/ 说明 你的算法应该具有线性时间复杂度. 你可以不使用额外空间来实现吗？ 示例 输入: [2,2,1] 输出: 1 输入: [4,1,2,1,2] 输出: 4 解答 开始想的是用collection函数来统计次数, 但发现题目的说明讲到了不使用额外的空间, 所以作罢. 后来想用sort来进行排序, 再进行for num in nums进行遍历, 来判断相邻两个是否相同从而找出不同的元素, 但这样O(n)的时间复杂度就太高了. 而且严格来说sort也使用了额外的空间(见下文解释) python的sort方法 见python源码中的sort实现 int PyList_Sort(PyObject *v) { if (v == NULL || !PyList_Check(v)) { PyErr_BadInternalCall(); return -1; } v = list_sort_impl((PyListObject *)v, NULL, 0); if (v == NULL) return -1; Py_DECREF(v); return 0; } 使用的是Timsort算法, 从时间复杂度来讲, 这个算法是高效的. 从空间复杂度来讲，需要的开销在数量大的时候会增大. 下面是JSE7 中Timsort实现代码中的一段话，可以很好的说明Timsort的优势： A stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays. Like all proper mergesorts, this sort is stable and runs O(n log n) time (worst case). In the worst case, this sort requires temporary storage space for n/2 object references; in the best case, it requires only a small constant amount of space. ...

问题描述 已知有一个长度为 26 的整型数组, 分别代表 26 个字母的个数, 问这些字母能组成多少种不同的字符串(取模 1000000007). 问题求解 纯暴力 开始觉得很简单, 纯迭代问题, 抬手就来. int calc(int[] nums) { int ret = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { nums[i]--; ret += calc(nums); ret %= 1000000007; nums[i]++; } } return ret > 0 ? ret : 1; } 结果超时, 不行, 看来只能用数学方法求解. 数学方法 $$ Sum=\dfrac{A_{字母总数}^{字母总数}}{A_{A的数量}^{A的数量}\times……\times A_{2}^{2}} $$ 题目没有讲太清楚(是否这些字母一定要全部使用), 这里为了简单就假设全部使用. 解法一：排列组合. 生成字符串长度是 $sum=a_0+a_1+a_2+…+a_{25}$. 放 $a$ , 有$(sum, a0)$种选择的方法; 放$ b$, 有$(sum - a0, a1)$种方法; 放 $c$, 有$(sum - a0 - a1, a2)$种方法…..直到最后 程序 private long solve1(int[] letters) { int sum = 0; for (int c : letters) { sum += c; } BigInteger r = BigInteger.ONE; for (int c : letters) { BigInteger s = choose(sum, c); r = r.multiply(s); sum -= c; } return r.longValue(); } private static BigInteger choose(int n, int k) { BigInteger r = BigInteger.ONE; for (int i=0; i<k; i++) { r = r.multiply(BigInteger.valueOf(n - i)); } for (int i=2; i<=k; i++) { r = r.divide(BigInteger.valueOf(i)); } return r; } 解法 2: EGF (指数生成函数)。 这是个排列问题所以用指数生成函数. ...