Hilda

「离开世界之前 一切都是过程」

【算法题库1】几乎有序

已知一个几乎有序的数组。几乎有序是指,如果把数组排好顺序的话,每个元素移动的距离一定不超过k,并且k相对于数组长度来说是比较小的。 请选择一个合适的排序策略,对这个数组进行排序。 假设 k = 2,有一个数组 arr = [2, 1, 4, 3, 6, 5]。 原数组: [2, 1, 4, 3, 6, 5] 排好序的数组: [1, 2, 3, 4, 5, 6] 这个数...

【体系学习006】堆结构和堆排序

1.java中的比较器 Java 中主要有两种形式的比较器:Comparable 和 Comparator。 1.1 Comparable(内部比较器) Comparable 接口用于定义类的自然排序。只有一个方法 compareTo()。 实现形式: 你需要在需要排序的类(比如 Person 类)中实现 Comparable 接口,并重写 compareTo() 方法。 代码...

【体系学习005】归并排序2-力扣327

5.力扣327区间和的个数 https://leetcode.cn/problems/count-of-range-sum/description/ 这道题最暴利的解法就是\(O(n^3)\) 第一层循环 (i): 遍历数组,以确定区间的起始位置 i。i 从 0 遍历到 n-1。 第二层循环 (j): 遍历数组,以确定区间的结束位置 j。j 从 i 遍历到 n-1。这样...

【体系学习005】归并排序1

1.归并排序 1)整体是递归,左边排好序+右边排好序+merge让整体有序 2)让其整体有序的过程里用了排外序方法 3)利用master公式来求解时间复杂度 4)当然可以用非递归实现 \[T(N) = 2*T(N/2) + O(N^1)\] 根据master可知时间复杂度为\(O(N*logN)\) merge过程需要辅助数组,所以额外空间复杂度为O(N) ...

【体系学习004】一些基础的数据结构

1.单链表和双链表反转 单链表反转: 1 2 3 4 5 6 7 8 9 10 public static ListNode reverseListNode(ListNode head) { ListNode pre = null, next = null, cur = head; while (cur != null) { next = cur.ne...

【体系学习003】异或及其面试题

异或运算 (XOR) 是一种常见的二进制运算 异或运算的规则可以简单概括为:“相同为0,相异为1”。也可以理解为不进位的加法。 异或运算具有以下几个重要的数学性质,这些性质在计算机科学中应用广泛: 交换律:A⊕B=B⊕A 结合律:(A⊕B)⊕C=A⊕(B⊕C)—-可以通过“无进位相加”去理解 恒等律:任何数与 0 进行异或运算,结果仍是它本身。A⊕0=A 归零律:...

【力扣LCR181】LCR 181. 字符串中的单词反转

LCR 181. 字符串中的单词反转 1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public String reverseMessage(String message) { String[] s = message.split(" "); StringBuilder res = new StringB...

【力扣7】搜索二维矩阵

74. 搜索二维矩阵 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0) ret...

【力扣2】两数相加

2. 两数相加 首先,通过 listLen(ListNode l) 方法分别计算出两个链表 l1 和 l2 的长度。然后,它根据长度比较,将较长的链表赋给 l (long),将较短的链表赋给 s (short)。这么做是为了后续的加法操作能直接在较长的链表上进行修改,而不需要创建新的节点来存储结果(除了可能出现的最后一位进位)。 然后开始遍历链表,分为下面3个阶段: 同时遍历...

【力扣1】两数之和

1. 两数之和 1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i =...