网站优化协议,wordpress qqoq主题,菜单设计制作,建设网站申请本系列坚持格式#xff1a;1个抖机灵算法2个较简单但是天秀的算法1个较难天秀算法。 bogo排序
Bogo排序(Bogo-sort)#xff0c;又被称为猴子排序#xff0c;是一种恶搞排序算法。
将元素随机打乱#xff0c;然后检查其是否符合排列顺序#xff0c;若否#xff0c;则继续…本系列坚持格式1个抖机灵算法2个较简单但是天秀的算法1个较难天秀算法。 bogo排序
Bogo排序(Bogo-sort)又被称为猴子排序是一种恶搞排序算法。
将元素随机打乱然后检查其是否符合排列顺序若否则继续进行随机打乱继续检查结果直到符合排列顺序。 Bogo排序的最坏时间复杂度为O(∞)一辈子也不能输出排序结果平均时间复杂度为O(n·n!)。
这让我想到了另一个理论猴子理论只要让一只猴子一直敲打计算机理论上会有一天它能敲出一本圣经出来但是这个概率小到宇宙毁灭也很难敲出来。。
真的不知道这个排序应该叫做天才还是垃圾哈哈哈但是闲的没事的我就把他实现出来了。
public class Main {public static void main(String[] args) {int[] arr { 9,8,7,6,5,4,3,2,1};System.out.println(排序次数 bogo(arr));for (int i : arr) {System.out.print(i );}}public static int bogo(int[] arr) {int count 0;while (!isOrdered(arr)) {shuffle(arr);count;}return count;}// 判断是否有序方法public static boolean isOrdered(int[] arr) {for (int i 1; i arr.length; i) {if (arr[i - 1] arr[i]) {return false;}}return true;}// 随机排序方法public static void shuffle(int[] arr) {int temp;for (int i 0; i arr.length; i) {int j (int) (Math.random() * arr.length);temp arr[i];arr[i] arr[j];arr[j] temp;}}}9是中国最大的数字嘛我就把数组长度设为9结果平均排序次数要60万次不知道我的运气怎么样哈哈你们也试试吧 然而有个看似笑话的方法声称可以用O(n)实现Bogo排序依照量子理论的平行宇宙解释使用量子随机性随机地重新排列元素不同的可能性将在不同的宇宙中展开总有一种可能猴子得到了正确的顺序量子计算机找到了这个宇宙后就开始毁灭其他排序不成功的宇宙剩下一个观察者可以看到的正确顺序的宇宙。
如果想要迈出这个看似荒诞但令人无比兴奋的高效算法的第一步请先证明平行宇宙解释的正确性。
位运算
关于位运算有很多天秀的技巧这里举一个例子。
给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。
说明你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗
示例 1:
输入: [2,2,1]输出: 1 示例 2:
输入: [4,1,2,1,2]输出: 4
思路拿mapset都不符合要求那怎么办呢
我们知道什么数字和自己异或都等于0.
什么数字和0异或都等于它本身
异或又符合交换律
所以全部异或一遍答案就是那个出现一次的数字。
class Solution {public int singleNumber(int[] nums) {int ans 0;for(int i :nums)ans ^ i;return ans;}
}
有没有被秒了 打擂台
给定一个大小为 n 的数组找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
把狂野般的思绪收一收咱们来看看最优解。
class Solution {public int majorityElement(int[] nums) {int count 0;//当前答案出现的次数Integer candidate null;//答案for (int num : nums) {if (count 0) candidate num;count (num candidate) ? 1 : -1;}return candidate;}
}
我来解释一下策略记录当前的答案candidate 记录count。这时我们遍历了一个新的数字如果和candidate 一样我们就让count1否则让count-1.如果count变成了0那candidate 就下擂台换新的擂主数字上也就是说把candidate 更新成新的数字count也更新成1.
最后在擂台上的一定是答案。
肯定有人怀疑这个做法的正确性吧我就来说一下它为啥对
首先我们想像一下对最终隐藏答案ans最不利的情况每个其他数字全部都打擂这个答案ans那ans的count最后也会剩1不会被打下来。
正常情况呢其他数字还会互相打擂这些数字如此“内耗”又怎么能斗得过最终答案ans呢对不对 morris遍历
通常实现二叉树的前序preorder、中序inorder、后序postorder遍历有两个常用的方法一是递归(recursive)二是使用栈实现的迭代版本(stackiterative)。这两种方法都是O(n)的空间复杂度递归本身占用stack空间或者用户自定义的stack我分别给出一个例子
递归
void PreorderTraversal( BinTree BT )
{if(BTNULL)return ;printf( %c, BT-Data);PreorderTraversal(BT-Left);PreorderTraversal(BT-Right);
}
非递归
*proot;
while(p || !st.empty())
{if(p)//非空{//visit(p);进行操作st.push(p);//入栈p p-lchild;左} else//空{p st.top();//取出st.pop();p p-rchild;//右}
}
为啥这个O(n)的空间就是省不掉呢因为我们需要空间来记录之前的位置好在遍历完了可以回到父节点。所以这个空间是必须的如下图 比如我们遍历2想遍历4这时候我们要保证遍历完4以后还能回到2我们好去继续遍历5等等结点所以必须花空间记录。 但是还就有这么一种算法能实现空间O(1)的遍历服不服。
你们可能会问你刚说的必须有空间来记录路径怎么又可以不用空间了呢
这就是morris遍历它其实是利用了叶子节点大量的空余空间来实现的只要把他们利用起来我们就可以省掉额外空间啦。
我们不说先序中序后序先说morris遍历的原则
1、如果没有左孩子继续遍历右子树比如 这个2就没有左孩子这时直接遍历右孩子即可。
2、如果有左孩子找到左子树最右节点。
比如上图6就是2的最右节点。 1如果最右节点的右指针为空说明第一次遇到把它指向当前节点当前节点向左继续处理。
修改后 2如果最右节点的右指针不为空说明它指向之前结点把右指针设为空当前节点向右继续处理。 这就是morris遍历。
请手动模拟深度至少为4的树的morris遍历来熟悉流程。
下面给出实现
定义结点 public static class Node {public int value;Node left;Node right;public Node(int data) {this.value data;}}
先序完全按规则写就好。
//打印时机第一次遇到发现左子树最右的孩子右指针指向空或无左子树。public static void morrisPre(Node head) {if (head null) {return;}Node cur1 head;Node cur2 null;while (cur1 ! null) {cur2 cur1.left;if (cur2 ! null) {while (cur2.right ! null cur2.right ! cur1) {cur2 cur2.right;}if (cur2.right null) {cur2.right cur1;System.out.print(cur1.value );cur1 cur1.left;continue;} else {cur2.right null;}} else {System.out.print(cur1.value );}cur1 cur1.right;}System.out.println();}
morris在发表文章时只写出了中序遍历。而先序遍历只是打印时机不同而已所以后人改进出了先序遍历。至于后序是通过打印所有的右边界来实现的对每个有边界逆序打印再逆序回去。注意要原地逆序否则我们morris遍历的意义也就没有了。
完整代码
public class MorrisTraversal {public static void process(Node head) {if(head null) {return;}// 1//System.out.println(head.value);process(head.left);// 2//System.out.println(head.value);process(head.right);// 3//System.out.println(head.value);}public static class Node {public int value;Node left;Node right;public Node(int data) {this.value data;}}//打印时机向右走之前public static void morrisIn(Node head) {if (head null) {return;}Node cur1 head;//当前节点Node cur2 null;//最右while (cur1 ! null) {cur2 cur1.left;//左孩子不为空if (cur2 ! null) {while (cur2.right ! null cur2.right ! cur1) {cur2 cur2.right;}//找到最右//右指针为空指向cur1cur1向左继续if (cur2.right null) {cur2.right cur1;cur1 cur1.left;continue;} else {cur2.right null;}//右指针不为空设为空}System.out.print(cur1.value );cur1 cur1.right;}System.out.println();}//打印时机第一次遇到发现左子树最右的孩子右指针指向空或无左子树。public static void morrisPre(Node head) {if (head null) {return;}Node cur1 head;Node cur2 null;while (cur1 ! null) {cur2 cur1.left;if (cur2 ! null) {while (cur2.right ! null cur2.right ! cur1) {cur2 cur2.right;}if (cur2.right null) {cur2.right cur1;System.out.print(cur1.value );cur1 cur1.left;continue;} else {cur2.right null;}} else {System.out.print(cur1.value );}cur1 cur1.right;}System.out.println();}//逆序打印所有右边界public static void morrisPos(Node head) {if (head null) {return;}Node cur1 head;Node cur2 null;while (cur1 ! null) {cur2 cur1.left;if (cur2 ! null) {while (cur2.right ! null cur2.right ! cur1) {cur2 cur2.right;}if (cur2.right null) {cur2.right cur1;cur1 cur1.left;continue;} else {cur2.right null;printEdge(cur1.left);}}cur1 cur1.right;}printEdge(head);System.out.println();}
//逆序打印public static void printEdge(Node head) {Node tail reverseEdge(head);Node cur tail;while (cur ! null) {System.out.print(cur.value );cur cur.right;}reverseEdge(tail);}
//逆序类似链表逆序public static Node reverseEdge(Node from) {Node pre null;Node next null;while (from ! null) {next from.right;from.right pre;pre from;from next;}return pre;}public static void main(String[] args) {Node head new Node(4);head.left new Node(2);head.right new Node(6);head.left.left new Node(1);head.left.right new Node(3);head.right.left new Node(5);head.right.right new Node(7);morrisIn(head);morrisPre(head);morrisPos(head);}}
