macOS Catalina(10.15.4)/IntelliJ IDEA 2018.3/Tomcat 9.0.33/Maven项目调试时报错,这个项目以前是可以正常调试的，一段时间之后，就不能正常调试之下了。
ubuntu 18.04系统/var/log/auth.log文件不存在
通过 /var/log/auth.log 文件可以查看一些关于 ssh 登陆、sudo 命令的信息。尤其是 denyhosts 依赖这个日志拦截非法的登陆攻击。 但是，我最近遇到了一个问题，在阿里云的一些主机上没有这个文件，或者日志文件在自动备份（比如被重命名成 /var/log/auth.log.1 ）之后，没有重新生成新的 /var/log/auth.log 。
检查 /var/log 目录的所有者信息，如下：
|
1 2 |
$ ls -l /var/ | grep log drwxr-xr-x 23 root syslog 4096 Apr 8 18:04 log |
这里的所有者权限信息是不正确的，缺少所有者所在组的文件创建权限，导致文件创建出现问题。因此需要如下命令：
|
1 2 3 4 |
$ chmod -R 775 /data/log $ ls -l /var/ | grep log drwxrwxr-x 23 root syslog 4096 Apr 8 18:04 log |
接着手工创建日志文件，如下：
|
1 2 3 4 5 6 7 |
$ touch /var/log/auth.log $ chmod 640 /var/log/auth.log $ chown syslog.adm /var/log/auth.log $ ls -la /var/log/auth.log |
参考链接
ubuntu 18.04编译OpenSCAD源代码
ubuntu 18.04编译OpenSCAD源代码，本意想研究一下如何加速 CGAL 的计算过程，目前还没完成。
编译过程如下：
|
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 27 |
$ git clone git://github.com/openscad/openscad.git $ cd openscad $ git submodule update --init # 每次重新编译，都需要先执行此脚本，否则会出现环境变量设置问题 $ sudo ./scripts/uni-get-dependencies.sh # #include <Qsci/qsciglobal.h> $ sudo apt-get install libqscintilla2-dev $ sudo apt-get install libqscintilla2-qt5-dev # 大量软件被卸载，但是可惜的是，如果不卸载 libpulse0 没办法安装 libpulse-dev # 不安装 libpulse-dev 就没办法安装 qtmultimedia5-dev $ sudo apt-get remove libpulse0 $ sudo apt-get install libpulse-dev # Project ERROR: Unknown module(s) in QT: multimedia $ sudo apt-get install qtmultimedia5-dev # 如果安装过 anaconda 则要在路径中去除 anaconda，否则会出现编译问题 $ qmake openscad.pro $ make |
ubuntu 18.04使用apt-get安装eclipse无法启动
ubuntu 18.04使用apt-get安装eclipse无法启动,报告如下错误：
解决Windows 10(1909)玩红色警戒 2卡顿
1.找到游戏根目录里面的Ra2.ini/RA2MD.INI，有的计算机会不显示文件的“.ini”后缀
无刷电机的工作原理
无刷电机的工作原理
匈牙利算法
零、前言
匈牙利算法是一个经典的解决二部图最小权值匹配问题的算法。网上也有不少资料，但是看完之后总觉得有两个核心问题没有解决：算法为什么一定能得到最优匹配？算法复杂度为什么不再是指数级了？
最后读到了python的库函数scipy.optimize.linear_sum_assignment源代码里引用的文章，才算理解算法的实现，再花了一点时间弄清楚了上边两个问题。
Munkres' Assignment Algorithm
Assignment Problem - Let C be an nxn matrix representing the costs of each of n workers to perform any of n jobs. The assignment problem is to assign jobs to workers so as to minimize the total cost. Since each worker can perform only one job and each job can be assigned to only one worker the assignments constitute an independent set of the matrix C.
求最长公共子序列
最长递增子序列（Longest Increasing Subsequence）
最长递增子序列的解法，可以转化为 求最长公共子序列，也就是生成从目标序列从小到大排序之后的新序列，然后计算原始序列与新序列的 最长公共子序列。但是遇到重复数字的时候，会出现问题。也就是这个解法只能解决无重复数字的最长递增子序列。
另外需要注意的就是 最长公共子串（Longest Common Substring）与 最长公共子序列（Longest Common Subsequence）的区别： 子串要求在原字符串中是连续的，而子序列则只需保持相对顺序，并不要求连续。
整个的求解过程其实很好理解：
- 假定要计算的序列为 K = {K1,K2,K3,……,Kn,Kn+1,……,Km}
- 初始化计数数组 N = {N1,N2,N3,……,Nn,Nn+1,……,Nm} ，（计数数组跟序列的长度相同，Kn 的最长递增子序列长度计数对应于 Nn）用来记录最长递增子序列的长度，每个项的初始化值都设置为 1 （即使最小的项，项本身也算一个长度，因此最小的长度是 1）
- 必须从头部(K1)开始遍历
- 当计算 Kn 结尾的最长递增子序列的时候，只要遍历序列 K 的前 [0 ~ n-1] 个项，找到数值 小于(或者小于等于） Kn （必须遍历，Kn 之前的最长递增子序列不一定是 Kn-1 对应的 Nn-1 ），并且在计数数组 N 中对应的计数最大的项 Ni ，然后 Nn = Ni + 1 。
本方法的时间复杂度是 O(n2)
例子：
设数组 K = { 2， 5， 1， 5， 4， 5 } 那么求最长递增子序列的代码如下：
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <iostream> #include <vector> int calcMaxLISLength(const std::vector<int>& K) { std::vector<int> N(K.size(), 1); int maxL = 0; for(int i = 0; i < K.size(); i++) { int Ki = K[i]; int maxNi = 0; for(int j = 0; j < i; j++) { int Kj = K[j]; if(Kj < Ki) { int Nj = N[j]; if(Nj > maxNi) { maxNi = Nj; } } } int Ni = maxNi + 1; N[i] = Ni; if(maxL < Ni) { maxL = Ni; } } return maxL; } int main(int argc, char** argv) { // 2 5 1 5 4 5 // 3 std::vector<int> K = {2, 5, 1, 5, 4, 5}; int r = calcMaxLISLength(K); std::cout << r << std::endl; // 17 K = {317, 211, 180, 187, 104, 285, 63, 117, 320, 35, 288, 299, 235, 282, 105, 231, 253, 74, 143, 148, 77, 249, 310, 137, 191, 184, 88, 8, 194, 12, 117, 108, 260, 313, 114, 261, 60, 226, 133, 61, 146, 297, 291, 13, 198, 286, 254, 96, 135, 48, 135, 307, 23, 155, 203, 258, 168, 42, 301, 45, 164, 193, 26, 290, 280, 172, 94, 230, 156, 36, 250, 174, 47, 188, 148, 138, 194, 89, 71, 119, 218, 325, 136, 63, 271, 210, 320, 309}; r = calcMaxLISLength(K); std::cout << r << std::endl; return 0; } |
第二个测试用例的数据如下：
|
1 2 3 4 5 6 7 8 |
输入数据个数 88 实际数据 317 211 180 187 104 285 63 117 320 35 288 299 235 282 105 231 253 74 143 148 77 249 310 137 191 184 88 8 194 12 117 108 260 313 114 261 60 226 133 61 146 297 291 13 198 286 254 96 135 48 135 307 23 155 203 258 168 42 301 45 164 193 26 290 280 172 94 230 156 36 250 174 47 188 148 138 194 89 71 119 218 325 136 63 271 210 320 309 期望结果 17 |
涉及到的面试题目如下类型：
梅花桩问题
合唱队问题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
题目描述 : Redraiment是走梅花桩的高手。Redraiment总是起点不限，从前到后，往高的桩子走，但走的步数最多，不知道为什么？你能替Redraiment研究他最多走的步数吗？ 样例输入 6 2 5 1 5 4 5 样例输出 3 提示 Example: 6个点的高度各为 2 5 1 5 4 5 如从第1格开始走,最多为3步, 2 4 5 从第2格开始走,最多只有1步,5 而从第3格开始走最多有3步,1 4 5 从第5格开始走最多有2步,4 5 所以这个结果是3。 输入例子: 6 2 5 1 5 4 5 输出例子: 3 |
合唱队问题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
题目描述 计算最少出列多少位同学，使得剩下的同学排成合唱队形 说明： N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 输入描述: 整数N 输出描述: 最少需要几位同学出列 示例1 输入 8 186 186 150 200 160 130 197 200 输出 4 |
合唱队问题其实是 求最长递增子序列 与 最长递减子序列 的 和 最大。
最长递减子序列的求法其实就是把原始序列反序，然后 求最长递增子序列 然后把最后的结果反序即可。
代码如下：
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <iostream> #include <vector> static void calcMaxLIS(const std::vector<int>& K, std::vector<int>& N) { for(int i = 0; i < K.size(); i++) { int Ki = K[i]; int maxNi = 0; for(int j =0; j<i; j++) { int Kj = K[j]; if(Ki > Kj) { int Nj = N[j]; if(maxNi < Nj) { maxNi = Nj; } } } N[i] = maxNi + 1; } } static void calcMaxLDS(const std::vector<int>& K, std::vector<int>& N) { std::vector<int> rK(K.rbegin(), K.rend()); std::vector<int> rN(N); calcMaxLIS(rK, rN); for(int i = 0; i<rN.size(); i++) { N[i] = rN[rN.size() - 1 - i]; } } static int calcMaxVal(const std::vector<int>& K) { std::vector<int> N(K.size(), 1); std::vector<int> rN(K.size(), 1); std::vector<int> KN(K.size(), 0); calcMaxLIS(K, N); calcMaxLDS(K, rN); // /*for(int i = 0; i<N.size(); i++) { std::cout << N[i]; } std::cout << std::endl; for(int i = 0; i<rN.size(); i++) { std::cout << rN[i]; } std::cout << std::endl;*/ for(int i = 0; i<N.size(); i++) { KN[i] = N[i] + rN[i]; } /* for(int i = 0; i<KN.size(); i++) { std::cout << KN[i]; } std::cout << std::endl;*/ int maxL = 0; for(int i = 0; i < KN.size(); i++) { if(maxL < KN[i]) { maxL = KN[i]; } } return maxL - 1; } static void test_calcMaxVal() { std::vector<int> K = {186, 186, 150, 200, 160, 130, 197, 200}; int r = calcMaxVal(K); std::cout << K.size() - r << std::endl; } static void main_test() { test_calcMaxVal(); } static void main_task() { int n = 0; while(std::cin >> n) { std::vector<int> K; for(int i = 0; i<n; i++) { int v = 0; std::cin >> v; K.push_back(v); } int r = calcMaxVal(K); std::cout << n - r << std::endl; } } int main(int argc, char** argv) { //main_test(); main_task(); return 0; } |
解法介绍
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
首先计算每个数在最大递增子串中的位置 186 186 150 200 160 130 197 200 quene 1 1 1 2 2 1 3 4 递增计数 然后计算每个数在反向最大递减子串中的位置--->计算反向后每个数在最大递增子串中的位置 200 197 130 160 200 150 186 186 反向quene 1 1 1 2 3 2 3 3 递减计数 然后将每个数的递增计数和递减计数相加 186 186 150 200 160 130 197 200 quene 1 1 1 2 2 1 3 4 递增计数 3 3 2 3 2 1 1 1 递减计数 4 4 3 5 4 2 4 5 每个数在所在队列的人数+1（自己在递增和递减中被重复计算） 如160这个数 在递增队列中有2个人数 150 160 在递减队列中有2个人数 160 130 那么160所在队列中就有3个人 150 160 130 每个数的所在队列人数表达就是这个意思 总人数 - 该数所在队列人数 = 需要出队的人数 |