优创智汇高端网站建设,小红书推广费用,长沙市人才网,媒体发稿公司防止新手错误的神级代码
#define ture true
#define flase false
#difine viod void
#define mian main
#define #xff1b; ;
以后有新手问题就把这几行代码给他就好啦。 不用额外空间交换两个变量
a 5 b 8 #计算a和b两个点到原点的距离之和#xff0c;并且赋值给…防止新手错误的神级代码
#define ture true
#define flase false
#difine viod void
#define mian main
#define ;
以后有新手问题就把这几行代码给他就好啦。 不用额外空间交换两个变量
a 5 b 8 #计算a和b两个点到原点的距离之和并且赋值给a a ab #使用距离之和减去b到原点的距离 #a-b 其实就是a的原值a到原点的距离现在赋值给了b b a-b #再使用距离之和减去b (a到原点的距离) #得到的是b的原值b到原点的距离现在赋值给了a a a-b
八皇后问题神操作
是一个以国际象棋为背景的问题如何能够在 8×8 的国际象棋棋盘上放置八个皇后使得任何一个皇后都无法直接吃掉其他的皇后为了达到此目的任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题这时棋盘的大小变为n1×n1而皇后个数也变成n2。而且仅当 n2 ≥ 1 或 n1 ≥ 4 时问题有解。
皇后问题是非常著名的问题作为一个棋盘类问题毫无疑问用暴力搜索的方法来做是一定可以得到正确答案的但在有限的运行时间内我们很难写出速度可以忍受的搜索部分棋盘问题的最优解不是搜索而是动态规划某些棋盘问题也很适合作为状态压缩思想的解释例题。
进一步说皇后问题可以用人工智能相关算法和遗传算法求解可以用多线程技术缩短运行时间。本文不做讨论。
本文不展开讲状态压缩以后再说
一般思路
N*N的二维数组在每一个位置进行尝试在当前位置上判断是否满足放置皇后的条件这一点的行、列、对角线上没有皇后。
优化1
既然知道多个皇后不能在同一行我们何必要在同一行的不同位置放多个来尝试呢
我们生成一维数组recordrecord[i]表示第i行的皇后放在了第几列。对于每一行确定当前record值即可因为每行只能且必须放一个皇后放了一个就无需继续尝试。那么对于当前的record[i]查看record[0...i-1]的值是否有j record[k]同列、|record[k] - j| | k-i |同一斜线的情况。由于我们的策略无需检查行每行只放一个。
public class NQueens {public static int num1(int n) {if (n 1) {return 0;}int[] record new int[n];return process1(0, record, n);}public static int process1(int i, int[] record, int n) {if (i n) {return 1;}int res 0;for (int j 0; j n; j) {if (isValid(record, i, j)) {record[i] j;res process1(i 1, record, n);}}//对于当前行依次尝试每列return res;}
//判断当前位置是否可以放置public static boolean isValid(int[] record, int i, int j) {for (int k 0; k i; k) {if (j record[k] || Math.abs(record[k] - j) Math.abs(i - k)) {return false;}}return true;}public static void main(String[] args) {int n 8;System.out.println(num1(n));}
}位运算优化2
分析棋子对后续过程的影响范围本行、本列、左右斜线。 黑色棋子影响区域为红色
1本行影响不提根据优化一已经避免
2本列影响一直影响D列直到第一行在D放棋子的所有情况结束。
3左斜线每向下一行实际上对当前行的影响区域就向左移动
比如
尝试第二行时黑色棋子影响的是我们的第三列
尝试第三行时黑色棋子影响的是我们的第二列
尝试第四行时黑色棋子影响的是我们的第一列
尝试第五行及以后几行黑色棋子对我们并无影响。
4右斜线则相反
随着行序号增加影响的列序号也增加直到影响的列序号大于8就不再影响。 我们对于之前棋子影响的区域可以用二进制数字来表示比如:
每一位用01代表是否影响。
比如上图对于第一行就是00010000
尝试第二行时数字变为00100000
第三行01000000
第四行10000000 对于右斜线的数字同理
第一行00010000之后向右移00001000000001000000001000000001直到全0不影响。 同理我们对于多行数据也同样可以记录了
比如在第一行我们放在了第四列 第二行放在了G列这时左斜线记录为00100000第一个棋子的影响00000010当前棋子的影响00100010。
到第三行数字继续左移01000100然后继续加上我们的选择如此反复。 这样我们对于当前位置的判断其实可以通过左斜线变量、右斜线变量、列变量按位或运算求出每一位中三个数有一个是1就不能再放。
具体看代码
注怎么排版就炸了呢。。。贴一张图吧 public class NQueens {public static int num2(int n) {// 因为本方法中位运算的载体是int型变量所以该方法只能算1~32皇后问题// 如果想计算更多的皇后问题需使用包含更多位的变量if (n 1 || n 32) {return 0;}int upperLim n 32 ? -1 : (1 n) - 1;//upperLim的作用为棋盘大小比如8皇后为00000000 00000000 00000000 11111111//32皇后为11111111 11111111 11111111 11111111return process2(upperLim, 0, 0, 0);}public static int process2(int upperLim, int colLim, int leftDiaLim,int rightDiaLim) {if (colLim upperLim) {return 1;}int pos 0; //pos所有的合法位置int mostRightOne 0; //所有合法位置的最右位置//所有记录按位或之后取反并与全1按位与得出所有合法位置pos upperLim (~(colLim | leftDiaLim | rightDiaLim));int res 0;//计数while (pos ! 0) {mostRightOne pos (~pos 1);//取最右的合法位置pos pos - mostRightOne; //去掉本位置并尝试res process2(upperLim, //全局colLim | mostRightOne, //列记录//之前列本位置(leftDiaLim | mostRightOne) 1, //左斜线记录//左斜线变量本位置左移 (rightDiaLim | mostRightOne) 1); //右斜线记录//右斜线变量本位置右移高位补零}return res;}public static void main(String[] args) {int n 8;System.out.println(num2(n));}
}完整测试代码
32皇后结果/时间
暴力搜时间就太长了懒得测。。。 public class NQueens {public static int num1(int n) {if (n 1) {return 0;}int[] record new int[n];return process1(0, record, n);}public static int process1(int i, int[] record, int n) {if (i n) {return 1;}int res 0;for (int j 0; j n; j) {if (isValid(record, i, j)) {record[i] j;res process1(i 1, record, n);}}return res;}public static boolean isValid(int[] record, int i, int j) {for (int k 0; k i; k) {if (j record[k] || Math.abs(record[k] - j) Math.abs(i - k)) {return false;}}return true;}public static int num2(int n) {if (n 1 || n 32) {return 0;}int upperLim n 32 ? -1 : (1 n) - 1;return process2(upperLim, 0, 0, 0);}public static int process2(int upperLim, int colLim, int leftDiaLim,int rightDiaLim) {if (colLim upperLim) {return 1;}int pos 0;int mostRightOne 0;pos upperLim (~(colLim | leftDiaLim | rightDiaLim));int res 0;while (pos ! 0) {mostRightOne pos (~pos 1);pos pos - mostRightOne;res process2(upperLim, colLim | mostRightOne,(leftDiaLim | mostRightOne) 1,(rightDiaLim | mostRightOne) 1);}return res;}public static void main(String[] args) {int n 32;long start System.currentTimeMillis();System.out.println(num2(n));long end System.currentTimeMillis();System.out.println(cost time: (end - start) ms);start System.currentTimeMillis();System.out.println(num1(n));end System.currentTimeMillis();System.out.println(cost time: (end - start) ms);}
}马拉车——字符串神级算法
Manachers Algorithm 马拉车算法操作及原理
package advanced_001;public class Code_Manacher {public static char[] manacherString(String str) {char[] charArr str.toCharArray();char[] res new char[str.length() * 2 1];int index 0;for (int i 0; i ! res.length; i) {res[i] (i 1) 0 ? # : charArr[index];}return res;}public static int maxLcpsLength(String str) {if (str null || str.length() 0) {return 0;}char[] charArr manacherString(str);int[] pArr new int[charArr.length];int C -1;int R -1;int max Integer.MIN_VALUE;for (int i 0; i ! charArr.length; i) {pArr[i] R i ? Math.min(pArr[2 * C - i], R - i) : 1;while (i pArr[i] charArr.length i - pArr[i] -1) {if (charArr[i pArr[i]] charArr[i - pArr[i]])pArr[i];else {break;}}if (i pArr[i] R) {R i pArr[i];C i;}max Math.max(max, pArr[i]);}return max - 1;}public static void main(String[] args) {String str1 abc1234321ab;System.out.println(maxLcpsLength(str1));}}问题查找一个字符串的最长回文子串
首先叙述什么是回文子串回文就是对称的字符串或者说是正反一样的
小问题一请问子串和子序列一样么请思考一下再往下看 当然不一样。子序列可以不连续子串必须连续。
举个例子”123”的子串包括1231223123(一个字符串本身是自己的最长子串)而它的子序列是任意选出元素组成他的子序列有123121323123””,空其实也算但是本文主要是想叙述回文没意义。
小问题二长度为n的字符串有多少个子串多少个子序列 子序列每个元素都可以选或者不选所以有2的n次方个子序列包括空
子串以一位置开头有n个子串以二位置开头有n-1个子串以此类推我们发现这是一个等差数列而等差序列求和有n*(n1)/2个子串(不包括空)。
(这里有一个思想需要注意遇到等差数列求和基本都是o(n^2)级别的)
一、分析枚举的效率
好我们来分析一下暴力枚举的时间复杂度上文已经提到过一个字符串的所有子串数量是o(n^2)级别所以光是枚举出所有情况时间就是o(n^2)每一种情况你要判断他是不是回文的话还需要o(n)情况数和每种情况的时间应该乘起来也就是说枚举时间要o(n^3)效率太低。
二、初步优化
思路我们知道回文全是对称的每个回文串都会有自己的对称轴而两边都对称。我们如果从对称轴开始 向两边阔如果总相等就是回文扩到两边不相等的时候以这个对称轴向两边扩的最长回文串就找到了。
举例1 2 1 2 1 2 1 1 1
我们用每一个元素作为对称轴向两边扩
0位置左边没东西只有自己
1位置判断左边右边是否相等11所以接着扩然后左边没了所以以1位置为对称轴的最长回文长度就是3
2位置左右都是2相等继续左右都是1继续左边没了所以最长为5
3位置左右开始扩112211左边没了所以长度是7
如此把每个对称轴扩一遍最长的就是答案对么
你要是点头了。。。自己扇自己两下。
还有偶回文呢比如1221123321.这是什么情况呢这个对称轴不是一个具体的数因为人家是偶回文。
问题三怎么用对称轴向两边扩的方法找到偶回文容易操作的
我们可以在元素间加上一些符号比如/1/2/1/2/1/2/1/1/1/这样我们再以每个元素为对称轴扩就没问题了每个你加进去的符号都是一个可能的偶数回文对称轴此题可解。。。因为我们没有错过任何一个可能的对称轴不管是奇数回文还是偶数回文。
那么请问加进去的符号有什么要求么是不是必须在原字符中没出现过请思考 其实不需要的大家想一下不管怎么扩原来的永远和原来的比较加进去的永远和加进去的比较。不举例子说明了自己思考一下
好分析一波时间效率吧对称轴数量为o(n)级别每个对称轴向两边能扩多少最多也就o(n)级别一共长度才n; 所以n*n是o(n^2) (最大能扩的位置其实也是两个等差数列这么理解也是o(n^2)用到刚讲的知识) 小结
这种方法把原来的暴力枚举o(n^3)变成了o(n^2),大家想一想为什么这样更快呢
我在kmp一文中就提到过我们写出暴力枚举方法后应想一想自己做出了哪些重复计算错过了哪些信息然后进行优化。
看我们的暴力方法如果按一般的顺序枚举012345012判断完接着判断0123我是没想到可以利用前面信息的方法因为对称轴不一样啊右边加了一个元素左边没加。所以刚开始老是想找一种方法左右都加一个元素这样就可以对上一次的信息加以利用了。
暴力为什么效率低永远是因为重复计算举个例子12121211下标从0开始判断1212121是否为回文串的时候其实21212和121等串也就判断出来了但是我们并没有记下结果当枚举到21212或者121时我们依旧是重新尝试了一遍。(假设主串长度为n对称轴越在中间长度越小的子串被重复尝试的越多。中间那些点甚至重复了n次左右本来一次搞定的事
还是这个例子我换一个角度叙述一下比较直观如果从3号开始向两边扩12121212最后扩到1212121时间复杂度o(n),用枚举的方法要多少时间如果主串长度为n枚举尝试的子串长度为357....n,等差数列大家读到这里应该都知道了等差数列求和o(n^2)。
三、Manacher原理
首先告诉大家这个算法时间可以做到o(n),空间o(n).
好的开始讲解这个神奇的算法。
首先明白两个概念
最右回文边界R挺好理解就是目前发现的回文串能延伸到的最右端的位置(一个变量解决
中心c第一个取得最右回文边界的那个中心对称轴举个例子:12121二号元素可以扩到12121三号元素 可以扩到121右边界一样我们的中心是二号元素因为它第一个到达最右边界
当然我们还需要一个数组p来记录每一个可能的对称轴最后扩到了哪里。
有了这么几个东西我们就可以开始这个神奇的算法了。
为了容易理解我分了四种情况依次讲解 假设遍历到位置i如何操作呢 1iR:也就是说i以及i右边我们根本不知道是什么因为从来没扩到那里。那没有任何优化直接往右暴力 扩呗。
下面我们做i关于c的对称点i’
2iR:
三种情况
i’的回文左边界在c回文左边界的里面
i’回文左边界在整体回文的外面
i’左边界和c左边界是一个元素
(怕你忘了概念c是对称中心c它当初扩到了RR是目前扩到的最右的地方现在咱们想以i为中心看能扩到哪里。)
按原来o(n^2)的方法直接向两边暴力扩。好的魔性的优化来了。咱们为了好理解分情况说。首先大家应该知道的是i’其实有人家自己的回文长度我们用数组p记录了每个位置的情况所以我们可以知道以i’为中心的回文串有多长。
2-1i’的回文左边界在c回文的里面看图
我用这两个括号括起来的就是这两个点向两边扩到的位置也就是i和i’的回文串为什么敢确定i回文只有这么长和i’一样我们看c其实这个图整体是一个回文串啊。
串内完全对称(1是括号左边相邻的元素2是右括号右边相邻的元素34同理) 由此得出结论1
由整体回文可知点2点3点1点4 当初i’为什么没有继续扩下去因为点1点2。
由此得出结论2点1点2 因为前面两个结论所以34所以i也就到这里就扩不动了。而34中间肯定是回文因为整体回文和12中间对称。 2-2i’回文左边界在整体回文的外面了看图
这时我们也可以直接确定i能扩到哪里请听分析
当初c的大回文扩到R为什么就停了因为点2点4----------结论1
2’为2关于i’的对称点当初i’左右为什么能继续扩呢说明点2点2’---------结论2
由c回文可知2’3由结论2可知点2点2’所以23
但是由结论一可知点2点4所以推出34所以i扩到34为止了34不等。
而34中间那一部分因为c回文和i’在内部的部分一样是回文所以34中间部分是回文。 2-3最后一种当然是i’左边界和c左边界是一个元素
点1点2点2点3就只能推出这些只知道34中间肯定是回文外边的呢不知道啊因为不知道3和4相不相等所以我们得出结论点3点4内肯定是继续暴力扩。
原理及操作叙述完毕不知道我讲没讲明白。。。
四、代码及复杂度分析 看代码大家是不是觉得不像o(n)其实确实是的来分析一波。。
首先我们的i依次往下遍历而R最右边界从来没有回退过吧其实当我们的R到了最右边就可以结束了。再不济i自己也能把R一个一个怼到最右
我们看情况一和四R都是以此判断就向右一个移动一次需要o(1)
我们看情况二和三直接确定了p[i]根本不用扩直接遍历下一个元素去了每个元素o(1).
综上由于i依次向右走而R也没有回退过最差也就是i和R都到了最右边而让它们移动一次的代价都是o(1)的所以总体o(n)
可能大家看代码依旧有点懵其实就是code整合了一下我们对于情况23虽然知道了它肯定扩不动但是我们还是给它一个起码是回文的范围反正它扩一下就没扩动不影响时间效率的。而情况四也一样给它一个起码是回文不用验证的区域然后接着扩四和二三的区别就是。二三我们已经心中有B树它肯定扩不动了而四确实需要接着尝试。
要是写四种情况当然也可以。。但是我懒的写太多了。便于理解分了四种情况解释code整合后就是这样子 我真的想象不到当初发明这个算法的人是怎么想到的向他致敬。
