翻转（逆序）算法总结 |
您所在的位置：网站首页 › 什么是倒序数 › 翻转（逆序）算法总结 |
|
概述
翻转类算法的题目类型挺多的，有数组翻转、字符串翻转、链表翻转、二叉树翻转等。有些题目虽然不叫翻转，但类型接近，比如倒序输出一组数字等。 分析翻转算法有哪些实现方式？ 方式一 ：栈在数据结构中有一个天然实现倒序的辅助工具——栈。栈先进后出的特性可以处理绝大数的翻转题。这里举个例子： 从尾到头打印链表 private static void printReverseSingleNode(SingleNode head){ Stack stack = new Stack(); while (head != null){ stack.push(head.data); head = head.next; } while (!stack.empty()){ System.out.print(stack.pop()); } }这里需要注意的是，栈里面我仅仅只是存的链表节点的值，并没有存放链表节点，这样实现起来也是最容易的。如果使用栈去倒序链表，有点得不偿失，因为需要最后会创建一个新的链表，空间复杂度高，且实现起来会比较麻烦。 方式二 ：递归关于递归的学习，我之前一直存在一个误区，就是想搞懂递归执行的每一个细节，然后我最后发现，当你深究细节时，你就糊涂了（有点类似于量子力学的测不准原理。。。）所以，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。递归算法在二叉树上的使用非常常见，这里用二叉树举个例子： 翻转二叉树 /** * 递归版本，其实就是左右交换 * 由于树中每一个节点都需要被访问，因此时间复杂度就是O(n),其中n 是节点个数 * 本方法使用了递归，在最坏情况下栈内存需要存放O(h)个方法调用，其中h是树的高度，由于h属于O(n)，可得空间复杂度是O(n) */ private static TreeNode reverseTree1(TreeNode root){ if (root == null){ return null; } TreeNode temp = root.leftChild; root.leftChild = reverseTree1(root.rightChild); root.rightChild = reverseTree1(temp); return root; } 方式三 ：迭代这里使用的是双指针的方法。有的时候面试官可能不会让你使用递归去实现一个算法（例如二叉树的前、中、后的遍历，使用递归写太过简单），又或者你自身对递归思想理解的不深刻（最好还是要深刻下，递归很重要），那这个时候，使用迭代的方法处理问题，相比前面两种方式，就不是那么的绕。举个例子： 反转字符串 /** * 反转方法，使用双指针法 * @param s */ private static void reverseString(char[] s) { int left = 0; int right = s.length -1; char temp; int len = s.length; for (int i = 0; i |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |