二叉树遍历
https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
递归解法
前序遍历
public static void preOrderRecur(TreeNode head) { if (head == null) { return; } System.out.print(head.value + " "); preOrderRecur(head.left); preOrderRecur(head.right); } 作者:golandscape 链接:https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
中序遍历
public static void preOrderRecur(TreeNode head) { if (head == null) { return; } preOrderRecur(head.left); System.out.print(head.value + " "); preOrderRecur(head.right); } 作者:golandscape 链接:https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
后序遍历
public static void postOrderRecur(TreeNode head) { if (head == null) { return; } postOrderRecur(head.left); postOrderRecur(head.right); System.out.print(head.value + " "); } 作者:golandscape 链接:https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
迭代解法
本质上是在模拟递归,因为在递归的过程中使用了系统栈,所以在迭代的解法中常用
Stack
来模拟系统栈。
前序遍历
public static void preOrderIteration(TreeNode head) { if (head == null) { return; } Stack<TreeNode> stack = new Stack<>(); stack.push(head); while (!stack.isEmpty()) { TreeNode node = stack.pop(); System.out.print(node.value + " "); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } } 作者:golandscape 链接:https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
中序遍历
public static void inOrderIteration(TreeNode head) { if (head == null) { return; } TreeNode cur = head; Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || cur != null) { while (cur != null) { stack.push(cur); cur = cur.left; } TreeNode node = stack.pop(); System.out.print(node.value + " "); if (node.right != null) { cur = node.right; } } } 作者:golandscape 链接:https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
后顺遍历
public static void postOrderIteration(TreeNode head) { if (head == null) { return; } Stack<TreeNode> stack1 = new Stack<>(); Stack<TreeNode> stack2 = new Stack<>(); stack1.push(head); while (!stack1.isEmpty()) { TreeNode node = stack1.pop(); stack2.push(node); if (node.left != null) { stack1.push(node.left); } if (node.right != null) { stack1.push(node.right); } } while (!stack2.isEmpty()) { System.out.print(stack2.pop().value + " "); } } 作者:golandscape 链接:https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
层序遍历
class Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp; int res = 0; while(!queue.isEmpty()) { tmp = new LinkedList<>(); for(TreeNode node : queue) { if(node.left != null) tmp.add(node.left); if(node.right != null) tmp.add(node.right); } queue = tmp; res++; } return res; } } 作者:Krahets 链接:https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/solutions/159058/mian-shi-ti-55-i-er-cha-shu-de-shen-du-xian-xu-bia/
排序算法
https://leetcode.cn/circle/article/Gwd1Z5/
https://leetcode.cn/circle/discuss/eBo9UB/#%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
选择排序
public int[] selectionSortDouble(int[] arr) { if (arr.length < 2) return arr; int n = arr.length; for (int i = 0; i < n - 1 - i; i++) { // 每轮确定两个数字,因此上界也会动态变化 int minIdx = i, maxIdx = i; for (int j = i + 1; j < n - i; j++) { if (arr[j] < arr[minIdx]) minIdx = j; if(arr[j] > arr[maxIdx]) maxIdx = j; } if(minIdx == maxIdx) break; // 若本轮最大值等于最小值,说明未排序部分所有元素相等,无需再排序 swap(arr, i, minIdx); if(maxIdx == i) maxIdx = minIdx; // 在交换 i 和 minIdx 时,有可能出现 i 即 maxIdx 的情况,此时需要修改 maxIdx 为 minIdx swap(arr, n - 1 - i, maxIdx); } return arr; } 作者:yukiyama 链接:https://leetcode.cn/circle/discuss/eBo9UB/
简单插入排序
// 简单插入排序:内层用 for public int[] insertionSortUseWhile(int[] arr) { if (arr.length < 2) return arr; for (int i = 1; i < arr.length; i++) { int target = arr[i], j = i - 1; for (; j >= 0; j--) { if(target < arr[j]) arr[j + 1] = arr[j]; else break; } arr[j + 1] = target; } return arr; } 作者:yukiyama 链接:https://leetcode.cn/circle/discuss/eBo9UB/
双轴快排
public int[] dualPivotQuickSort(int[] arr) { if (arr.length < 2) return arr; dualPivotQuickSort(arr, 0, arr.length - 1); // 后两个参数是下标值 return arr; } /* * 区间1 区间2 区间3 * +------------------------------------------------------------+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | * +------------------------------------------------------------+ * ^ ^ ^ * | | | * lower index upper */ private void dualPivotQuickSort(int[] arr, int left, int right) { if(left < right) { // 排序对象是right大于left的区间(即大小大于等于2的区间) // 令左右两端元素中较小者居左,以left为初始pivot1,right为初始pivot2 // 即arr[left]为选定的左轴值,arr[right]为选定的右轴值 if(arr[left] > arr[right]) { swap(arr, left, right); } int index = left + 1; // 当前考察元素下标 int lower = left + 1; // 用于推进到pivot1最终位置的动态下标,总有[left, lower)确定在区间1中 int upper = right - 1; // 用于推进到pivot2最终位置的动态下标,总有(upper, right]确定在区间3中 // [lower, index)确定在区间2中,[index, upper]为待考察区间。 // upper以右(不含upper)的元素都是确定在区间3的元素,所以考察元素的右界是upper while(index <= upper) { // 若arr[index] < arr[left],即arr[index]小于左轴值,则arr[index]位于区间1 if (arr[index] < arr[left]) { // 交换arr[index]和arr[lower],配合后一条lower++,保证arr[index]位于区间1 swap(arr, index, lower); // lower++,扩展区间1,lower位置向右一位靠近pivot1的最终位置 lower++; } // 若arr[index] > arr[right],即arr[index]大于右轴值,则arr[index]位于区间3 else if(arr[index] > arr[right]) { // 先扩展区间3,使得如下while结束后upper以右(不含upper)的元素都位于区间3 // 区间3左扩不可使index == upper,否则之后的第二条upper--将导致upper为一个已经确定了区间归属的元素的位置(即index - 1) while(arr[upper] > arr[right] && index < upper) { upper--; } // 交换arr[index]和arr[upper],配合后一条upper--,保证arr[index]位于区间3 swap(arr, index, upper); upper--; // 上述交换后,index上的数字已经改变,只知道此时arr[index] ≤ arr[right],arr[index]有可能在区间1或区间2, // 若arr[index] < arr[left],即arr[index]小于左轴值,则arr[index]位于区间1 if(arr[index] < arr[left]) { // 交换arr[index]和arr[lower],配合后一条lower++,保证arr[index]位于区间1 swap(arr, index, lower); // lower++,扩展区间1,lower位置向右一位靠近pivot1的最终位置 lower++; } } index++; // 考察下一个数字 } // while(index <= upper)结束后最后一个确定在区间1的元素的下标是lower--, // 最后一个确定在区间3的元素下标是upper++。 lower--; upper++; // 双轴归位。此时的lower,upper即分别为最终pivot1(初始时为left),最终pivot2(初始时为right)。 swap(arr, left, lower); swap(arr, upper, right); // 对三个子区间分别执行双轴快排 dualPivotQuickSort(arr, left, lower - 1); // 区间1 dualPivotQuickSort(arr, lower + 1, upper - 1); // 区间2 dualPivotQuickSort(arr, upper + 1, right); // 区间3 } } 作者:yukiyama 链接:https://leetcode.cn/circle/discuss/eBo9UB/
堆排序
https://www.cnblogs.com/jiangym/p/17521231.html
链表
反转链表
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while(cur != null){ ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } }
环形链表
public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast = head, slow = head; while (true) { if (fast == null || fast.next == null) return null; fast = fast.next.next; slow = slow.next; if (fast == slow) break; } fast = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return fast; } } 作者:Krahets 链接:https://leetcode.cn/problems/linked-list-cycle-ii/solutions/12616/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
给定一个链表的头节点 head
,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos
是 -1
,则在该链表中没有环。注意:pos
不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
题解
设两指针 fast
,slow
指向链表头部 head
,fast
每轮走 2步,slow
每轮走 1步;
双指针第一次相遇:
第一种结果: fast
指针走过链表末端,说明链表无环,直接返回 null
;
第二种结果: 当fast == slow
时, 两指针在环中 第一次相遇 。
指针 位置不变 ,将fast
指针重新 指向链表头部节点 ;slow
和fast
同时每轮向前走 1 步;
返回slow
指针指向的节点。
标签:index,head,right,arr,记录,int,常用,算法,null From: https://www.cnblogs.com/jiangym/p/17534114.html