IT蛋的个人博客

冒泡排序逻辑重复地遍历待排序的元素，每次比较相邻的两个元素，并交换它们的位置，直到整个序列按照从小到大的顺序排列 因为不会交换相等值，所以冒泡排序是稳定排序 复杂度分析平均时间复杂度：O(n^2) 空间复杂度：O(1) 最差情况的时间复杂度，待排序数组是倒序排列的，需要进行n-1次比较和交换操作，因此最坏情况下的时间复杂度为O(n^2) 代码实现class Main { public static void bubbleSort(int[] arr) { int len = arr.length; // i用于记录已经放好的最大值数组 for(int i = 0; i < len-1; i++) { // 用于向后冒泡，依次交换大值 for(int j = 0; j < len - i - 1; j++) { if(arr[j] > arr[j+1]){ ...

希尔排序逻辑希尔排序是一种改进后的插入排序， 它涉及在不同的间隔之间进行子序列的插入排序，所以 希尔排序是不稳定排序 复杂度分析平均时间复杂度：取决于具体的间隔序列 空间复杂度：O(1) 最差情况的时间复杂度是O(n^2)，此时希尔排序退化为直接插入排序，即间隔为1。 最好的情况下可以达到O(n log n) 代码实现class Main { public static void shellSort(int[] arr) { int len = arr.length; // 取间隔，从arr长度的一半开始，每次减少一半 for(int mid = len / 2; mid>0 ; mid /= 2) { // 对每个小组内进行直接插入排序（视小组前面的数是有序的，依次插入合适的位置） for(int i = mid; i < len; i++) { int temp = arr[i]; ...

直接插入排序逻辑将数组分为有序和无序两部分，有序在前，无序在后，首先默认数组第一位是一个只有一位数字的有序数组 每次将一个无序的数按有序要求插入有序之中，循环到每个无序都插入有序 因为是依次插入有序数组中，等值的数不会发生位置交换，所以 直接插入排序是稳定排序 复杂度分析平均时间复杂度：O(n^2) 空间复杂度：O(1) 最差情况的时间复杂度是在输入数组逆序的情况下，此时每次插入都需要将已排序部分中的所有元素后移，时间复杂度为O(n^2) 最好情况的时间复杂度是在输入数组基本有序的情况下，时间复杂度接近O(n) 代码实现class Main { public static void insertSort(int[] arr) { if(arr == null || arr.length < 2) return; int len = arr.length; // i之前的数组有序 for(int i = 1; i < len; i++) { // 每次 ...

Git上传常见问题基本操作合并分支在 GitHub 上，一些仓库可能具有两个分支：main 和 master。如果您想将这两个分支合并成一个分支，可以按照以下步骤操作： 确认您已经克隆了该仓库。在终端运行以下命令以克隆该仓库： Copy Codegit clone https://github.com/username/repo.git 切换到 main 分支。在终端运行以下命令以切换到 main 分支： Copy Codegit checkout main 将 master 分支合并到 main 分支。在终端运行以下命令以将 master 分支合并到 main 分支： Copy Codegit merge master 推送变更。在终端运行以下命令以将本地变更推送到远程仓库： Copy Codegit push origin main 可选：删除 master 分支。如果您已将 master 分支合并到 main 分支，并且您不再需要 master 分支，您可以删除它。在终端运行以下命令以删除 master 分支： Copy Codegit branch -d ma ...

重写与重载 什么是重写 什么是重载 常见的面试题 什么是重写子类对父类中已有的方法进行重新定义，让子类可以根据自己需要重新实现父类继承的方法 子类重新实现父类方法 重写要求： 1. 子类重写方法必须与父类中被重写的方法具有相同的方法名称，返回类型和参数列表 2. 子类重写方法的访问权限不能低于父类被重写的方法的访问权限 3. 子类重写的方法不能抛出比父类被重写方法更多或更宽泛的异常 4. 子类无法重写父类中被final关键词修饰的方法 需要重写的情况： 子类需要根据自己的需要来重新实现父类继承的方法，来实现自己特有的功能 父类中的方法对于子类来说并不合适，需要重新实现 父类的方法存在缺陷或需要改进，子类需要重新实现以改进原有功能 特殊情况：重写方法的返回值类型可以是父类方法返回值类型的子类，这个特性在java5后出现，也被称作是Java中的”协变返回类型” 需要满足： 1. 返回值类型为父类返回类型的子类 2. 方法参数列表及访问修饰符都与父类方法相同或更为宽松 什么是重载在同一个类中，可以定义多 ...

接口与抽象类 什么是接口 什么是抽象类 接口与抽象类的相同点 接口与抽象类的不同点 常见面试题 什么是接口Java 中的一种特殊数据类型，可以被看作是一个纯粹的规范或者协议，它声明了一组方法的签名，但不包含任何实现代码 简单来说：负责声明方法，但不实现方法 特点：interface关键字修饰，不能实例化 作用：分离接口与实现，使得代码修改时与接口本身无关 实现要求： 1. 类使用 implements 关键字实现接口，实现（重写）接口中所有方法 ​ 2. 实现方法时：方法名称，参数列表（甚至参数顺序），返回类型都要与接口一致 ​ 3. 实现类重写方法时必须使用 public 访问修饰符（重写的要求就是访问修饰符要和父类访问一致或更加宽松，接口设计初衷就是为了给外部调用，所以接口方法默认 public , 实现类也就需要是public） ​ 4. 实现类不能完全实现接口时，实现类应该声明为抽象类 ​ 5. 一个实现类可以实现多个接口，中间使用逗号隔开 什么是抽象类Java 中一种实现抽象的机制，它是一种不能直接实例化的类, 只能 ...

打印从1到最大的n位数Easy 原题连接：打印从1到最大的n位数 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。 示例： 输入: n = 1 输出: [1,2,3,4,5,6,7,8,9] 解题思路 扩容结果数组：n是几就扩到几位数 遍历补数据 Java代码class Solution { public int[] printNumbers(int n) { int nSize = 1; while(n>0){ nSize *= 10; n--; } int[] fin = new int[nSize-1]; for(int i=0; i<nSize-1; i++) { fin[i] = i+1; } return fin;  ...

正则表达式匹配Hard 原题连接：正则表达式匹配 请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。 示例： 输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。 输入: s = "aa" p = "a*" 输出: true 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。 输入: s = "ab" p = ".*" 输出: true 解释: ".*" 表 ...

序列化二叉树Hard 原题连接：序列化二叉树 请实现两个函数，分别用来序列化和反序列化二叉树。 你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。 示例： 输入：root = [1,2,3,null,null,4,5] 输出：[1,2,3,null,null,4,5] 解题思路 如何序列化二叉树（以什么顺序序列化） 先序遍历：根 （左）（右）的顺序，根（根左右）（根左右）,可以确定当前第一个是根节点，遍历左子树，直到叶子节点，之后是右子树 中序遍历：（左） 根 （右）的顺序，很难判断出根节点的位置， 后序遍历：（左）（右） 根 的顺序，同上不便判断出根节点和左右节点之间的区分 二叉树有几种状态需要区别 当前节点：直接把值当字符存储，空节点（叶子节点的子节点）使用特殊字符 ...