xzs_xiaobai-CSDN博客

原创二叉树的非递归遍历、求高、节点数等方法

/** * 前序 * @param root */ public static void preOrder(TreeNode root) { if (root == null) { return; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack..

2020-08-09 10:40:59 312

原创 http连接基于tcp还是udp以及tcp与udp的区别（简述）

http与tcp的关系：（1）首先，http、tcp、udp并不是在一个层（osi七层模型）中，http在应用层，tcp和udp在传输层。（2）http是基于tcp的，因为发送http请求时，会先进行tcp三次握手的连接。（3）http的长连接与短连接，其实就是tcp的长连接与短连接。http1.1开始默认使用长连接，也就是 connection 默认使用 keep-alive关键字。长连接就是只需要在第一次连接时进行tcp三次握手，接下来就不需要了，可以一直使用这个连接，不会立即关闭，与短连接

2020-08-02 08:37:47 9417

原创堆排序--java实现

package nomal;public class HeapSort { public static void main(String[] args) { int[] arr = {23,3, 54, 12, 7, 99, 88, 65}; heapSort(arr); for (int i : arr) { System.out.print(i + " "); } } private.

2020-08-02 08:13:04 161

原创插值查找--java实现

package nomal;import java.util.Arrays;public class InsertSearch { public static boolean insertSearch (int[] arr, int num, int low, int high) { if (low > high || num <arr[0] || num > arr[arr.length -1]){ return false; .

2020-07-18 14:12:00 141

原创查找和排序算法--Java实现

排序算法冒泡排序快速排序插入排序归并排序查找算法二分查找

2020-07-18 13:50:25 109

原创二分查找--java实现

package nomal;import java.util.Arrays;public class BinarySearch { public static boolean binarySearch(int[] arr, int numbers) { int low = 0; int high = arr.length - 1; int mid; while (low <= high) { mi.

2020-07-18 13:44:22 92

原创归并排序--java实现

package nomal;public class MergeSort { public static void mergeSort(int[] numbers, int low, int high) { int center = (low + high) / 2; if (low < high) { mergeSort(numbers, low, center); mergeSort(numbers, .

2020-07-18 13:13:39 89

原创插入排序--java实现

package nomal;public class InsertSort { public static void insertSort (int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int temp = arr[i + 1]; int pre = i; while (pre >= 0 && arr[pre] .

2020-07-18 12:20:01 76

原创冒泡排序--java实现

package nomal;public class BubbleSort { public static void bubbleSort(int[] arr) { int temp; for (int i = 0; i < arr.length - 1; i++) { boolean flag = true; for (int j = 0; j < arr.length - 1 - .

2020-07-18 12:06:18 85

原创快速排序--java实现

private int partition(int[] arr, int low, int high) { //指定左指针i和右指针j int i = low; int j= high; //将第一个数作为基准值。挖坑 int x = arr[low]; ...

2020-07-18 11:44:51 108

原创出鞘之剑指offer-第43题 (1 ~ n整数中 1 出现的次数)

题目：输入一个整数 n ，求 1 ~ n 这 n 个整数的十进制表示中 1 出现的次数。分析一：借鉴博客代码一：package offer.xzs.fourty2fourtynine.fourtythree;public class Demo01 { public static void main(String[] args) { int count = getCount(12); System.out.println(count..

2020-05-30 21:31:56 214

原创出鞘之剑指offer-第42题 (连续子数组的最大和)

题目：输入一个整数数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)。分析一：代码一：package offer.xzs.fourty2fourtynine.fourtytwo;public class Demo01 { public static void main(String[] args) { int[] array = { 1, -2, 3, 10, -4, 7, 2,..

2020-05-30 20:58:30 126

原创出鞘之剑指offer-第41题 (数据流中的中位数)

题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。分析一：用两个堆，大顶堆和小顶堆，分别存储中位数左边的数值和右边的数值。代码一：package offer.xzs.fourty2fourtynine.fourtyone;import java.util.PriorityQueue;public class Demo01 { ..

2020-05-30 09:50:17 135

原创出鞘之剑指offer-第40题 (最小的k个数)

题目：输入 n 个整数，找出其中最小的 k 个数。例如输入 4、5、1、6、2、7、3、8 这 8 个数字，则最小的 4 个数字是 1、2、3、4。分析一：代码一：

2020-05-27 16:45:57 112

原创出鞘之剑指offer-第39题 (数组中出现次数超过一半的数字)

题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组 { 1, 2, 3, 2, 2, 2, 5, 4, 2 } 。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2 。分析一：使用摩尔投票算法，也是多数投票算法。代码一：package offer.xzs.thirty2thirtynine.thirtynine;public class Demo01 { public static void mai..

2020-05-27 16:36:38 158

原创出鞘之剑指offer-第38题 (字符串的排列)

题目：输入一个字符串，打印出该字符串中字符的所有排列。分析一：用递归代码一：package offer.xzs.thirty2thirtynine.thirtyeight;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Demo01 { public static List<String> result = new Arra.

2020-05-27 15:36:38 168

原创出鞘之剑指offer-第37题 (序列化二叉树)

题目：实现两个函数，序列化和反序列化二叉树。分析一：代码一：package offer.xzs.thirty2thirtynine.thirtyseven;import java.util.Arrays;public class Demo01 { public static String deserializeStr = null; public static void main(String[] args) { int[] pre ..

2020-05-27 13:17:24 168

原创出鞘之剑指offer-第36题 (二叉搜索树与双向链表)

题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中结点指针的指向。分析一：代码一：package offer.xzs.thirty2thirtynine.thirtysix;import java.util.Arrays;public class Demo01 { public static BinaryTree head = null; public static BinaryTree pre = ..

2020-05-27 12:51:04 111

原创出鞘之剑指offer-第35题 (复杂链表的复制)

题目：实现函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 sibling 指针指向链表中的任意节点或者 null 。分析一：分三步：先复制next，在复制sibling，最后拆开。代码一：package offer.xzs.thirty2thirtynine.thirtyfive;public class Demo01 { public static void main(String[] args) { ..

2020-05-27 11:37:23 147

原创出鞘之剑指offer-第34题 (二叉树中和为某一值的路径)

题目：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。分析一：代码一：package offer.xzs.thirty2thirtynine.thirtyfour;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Demo01 { public s..

2020-05-27 11:07:25 136

原创出鞘之剑指offer-第33题 (二叉搜索树的后序遍历序列)

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。返回 true 或者 false 。假设输入的数组任意两个数字都互不相同。分析一：由于后序遍历的最后一个节点是一棵树的根节点，而且，二叉搜索树是根节点的左子树的值小于根节点小于右子树的值。所以可以用递归的方式，重复一个过程。代码一：package offer.xzs.thirty2thirtynine.thirtythree;public class Demo01 { public static v..

2020-05-26 19:13:41 126

原创出鞘之剑指offer-第32题 (从上到下打印二叉树)

题目：题目一：不分行从上到下打印二叉树从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。分析一：层次遍历，使用队列。代码一：package offer.xzs.thirty2thirtynine.thirtytwo;import java.util.*;public class Demo01 { public static void main(String[] args) { int[] pre1 = { 8, 6, 5,..

2020-05-26 16:42:10 143

原创出鞘之剑指offer-第31题 (栈的压入、弹出序列)

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 { 1, 2, 3, 4, 5 } 是某栈的压入顺序，序列 { 4, 5, 3, 2, 1 } 是该压栈序列对应的一个弹出序列，但 { 4, 3, 5, 1, 2 } 就不可能是该压栈序列的弹出序列。分析一：用一个栈来模拟这个过程，当栈顶元素等于序列的第一个数时，出栈的同时要使序列的下标再往后移一位。代码一：package offer.xzs.thi

2020-05-26 15:31:38 109

原创出鞘之剑指offer-第30题 (包含min函数的栈)

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。分析一：定义一个辅助栈，用来存储每次压入栈的最小值。代码一：package offer.xzs.thirty2thirtynine.thirty;import java.util.Stack;public class Demo01 { private static Stack<Integer> d..

2020-05-26 09:53:22 132

原创出鞘之剑指offer-第29题 (顺时针打印矩阵)

题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。分析一：考虑好坐标，然后按照顺时针遍历。代码一：package offer.xzs.twentyone2thirty.twentynine;import java.util.ArrayList;import java.util.List;public class Demo01 { public static void main(String[] args) { int[][] a.

2020-05-26 09:26:15 140

原创出鞘之剑指offer-第28题 (对称的二叉树)

题目：实现一个函数，用来判断二叉树是不是对称的。如果一个二叉树和他的镜像二叉树一样，他就是对称的。分析一：代码一：package offer.xzs.twentyone2thirty.twentyeight;import java.util.Arrays;public class Demo01 { public static void main(String[] args) { int[] pre1 = { 8, 6, 5, 7, 6, 7, 5..

2020-05-24 21:16:44 106

原创出鞘之剑指offer-第27题 (二叉树的镜像)

题目：输入一棵二叉树，输出他的镜像。分析一：代码一：package offer.xzs.twentyone2thirty.twentyseven;import java.util.Arrays;public class Demo01 { public static void main(String[] args) { int[] pre1 = { 8, 8, 9, 2, 4, 7, 7 }; int[] mid1 = { 9, 8..

2020-05-24 21:06:06 180

原创出鞘之剑指offer-第26题 (树的子结构)

题目：输入两棵二叉树 A 和 B ，判断 B 是不是 A 的子结构。分析一：使用递归的方式。代码一：package offer.xzs.twentyone2thirty.twentysix;import java.util.Arrays;public class Demo01 { public static void main(String[] args) { int[] pre1 = { 8, 8, 9, 2, 4, 7, 7 }; ..

2020-05-24 20:47:39 130

原创出鞘之剑指offer-第25题 (合并两个排序的链表)

题目：输入两个递增排序的链表，合并之后仍有序。分析一：使用递归。代码一：package offer.xzs.twentyone2thirty.twentyfive;public class Demo01 { public static void main(String[] args) { ListNode head1 = new ListNode(1); ListNode node1 = new ListNode(2); ..

2020-05-24 15:11:31 76

原创出鞘之剑指offer-第24题 (反转链表)

题目：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。分析一：使用头插法。代码一：package offer.xzs.twentyone2thirty.twentyfour;public class Demo01 { public static void main(String[] args) { ListNode head = new ListNode(1); ListNode node1 = new List.

2020-05-24 14:39:15 105

原创出鞘之剑指offer-第23题 (链表中环的入口节点)

题目：如果链表中包含环，如何找出环的入口节点？分析一：代码一：package offer.xzs.twentythree;public class Demo01 { public static void main(String[] args) { ListNode head = new ListNode(1); ListNode node1 = new ListNode(2); ListNode node2 = new..

2020-05-23 13:49:45 110

原创出鞘之剑指offer-第22题 (链表中倒数第k个节点)

题目：输入一个链表，输出这个链表的第 k 个节点。本题从 1 开始计数，即链表的尾节点是倒数第 1 个节点。分析一：设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到第 N - K 个节点处，该位置就是倒数第 K 个节点。代码一：package offer.xzs.twentytwo;public class Demo01 { public .

2020-05-23 13:00:04 159

原创出鞘之剑指offer-第21题 (调整数组顺序使奇数位于偶数前面)

题目：输入一个整数数组，实现一个函数调整该数组中数字的顺序使得所有奇数位于数组前半部分，所有偶数位于数组后半部分。分析一：设两个指针，进行奇偶数交换。代码一：package offer.xzs.twentyone;public class Demo01 { public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5, 6 }; int[] sort = s...

2020-05-23 12:40:49 149

原创出鞘之剑指offer-第20题 (表示数值的字符串)

题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如：字符串 "+100"、"5e2"、"-123"、"3.1416"、及 "-1E-16" 都表示数值，但 "12e"、"1a3.14"、"1.2.3"、"+-5"、"12e+5.4" 都不是。分析一：代码一：...

2020-05-19 09:58:08 161

原创出鞘之剑指offer-第19题 (正则表达式匹配)

题目：实现一个函数用来匹配 '.' 和 '*' 的正则表达式。模式中的字符 '.' 表示任意一个字符，而 '*' 表示他前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。分析一：代码一：...

2020-05-19 09:53:40 161

原创出鞘之剑指offer-第18题 (删除链表的节点)

题目：题目一：在O(1)时间内删除链表节点给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。链表节点定义如下：struct ListNode { int value; ListNode next; }void DeleteNode ( ListNode head, ListNode temp)分析一：如果节点是尾节点，则，从头结点开始遍历，遍历到前一个节点删除，如果不是，则将要删除节点的后一个节点的值赋值给前一个节点。代码一：pack...

2020-05-19 09:47:07 136

原创出鞘之剑指offer-第17题 (打印从1到最大的n位数)

题目：输入数字n，按顺序打印出从1到最大的n位十进制数，比如输入3，则打印出1，2，3一直到最大的3位数999。分析一：由于没有说不考虑大数，所以用字符串模拟代码一：package offer.xzs.seventeenth;public class Demo01 { public static void main(String[] args) { printNumbers(2); } public static void pri...

2020-05-19 09:08:54 165

原创出鞘之剑指offer-第16题 (数值的整数次方)

题目：实现函数double Power (double base, int exponent) ，求 base 的exponent次方，不得使用库函数，不用考虑大数问题。分析一：代码一：package offer.xzs.sixteenth;public class Demo01 { public static void main(String[] args) { double power = getPower(2, 10); ...

2020-05-19 07:56:05 123