Time: 2025-02-20 Thursday 23:56:01
Author: Jackasher

黑马数据结构

动力节点的太烂啦，这个课程可是满神的课

算法

二分查找

二分查找必须是有顺序的使用，一半一半的切找值，其中切的过程注意使用位移运算，避免溢出，这里有个误解就是，计算机从来不会1001来表达-1，而是1111来表示-1，记住，计算机内部所有的数都是补码形式，

在 Java 中，int 类型是一个 32 位的有符号整数，其范围是 -2,147,483,648 到 2,147,483,647。这个范围是由 二进制补码表示法决定的。这里的 Integer.MAX_VALUE（2,147,483,647）只是用来表示 正数的最大值，实际上二进制本身并没有溢出。

这意味着补码是一个环状的表示方式，而不是简单的正数无限增大。以 32 位为例：

• 最大正数：01111111 11111111 11111111 11111111（2,147,483,647）。
• 最小负数：10000000 00000000 00000000 00000000（-2,147,483,648）。

在补码中，加法是连续的，即：

• 如果超出 2,147,483,647，下一个值就是 -2,147,483,648，并不是二进制的溢出，而是进入了负数范围。

代码：

这个代码可能就有点让人看不懂了，最后返回的i，就是那个索引位置 ，如果没有，就是比他小的所有数第一个靠右的位置，

int i = 0;
   int j = nums.length - 1;

   while(i <= j) {
       int midNum = (i + j) >>> 1;
       if(target <= nums[midNum]) {
           j = midNum - 1;
       }else {
           i = midNum + 1;
       }
   }
   return i;

如果这里去掉等号，return i-1；就是所有比他大的数第一个靠左的位置

target <= nums[midNum]

哪边有等号意味着，会不断往哪边靠

总结

我们知道啦二分查找的基本原理，并做了扩展，如果有重复元素怎么办，返回值怎么设置，于是有了leftMost和rightMost的情况

数组增删查，动态扩容及其缓存

主要还是这个缓存，看看以下代码他们的执行效率是不一样的，就因为cpu缓存会读取数组到缓存里面，如果是按行操作就会快很多，他这个只是形象的讲解，实际会复杂很多，所以即使数据量很小还是会有时间差

根据苹果发布的 M4 Pro（假设其遵循 M系列芯片的惯例），其缓存系统应当包括类似以下结构：

• L1 缓存：每个核心大约有 32KB 左右的 L1 数据缓存和指令缓存。
• L2 缓存：每个核心大约拥有 256KB 到 512KB 的 L2 缓存。
• L3 缓存：M4 Pro 芯片可能具有 12MB 到 16MB 的 L3 缓存（具体取决于核心数量和设计），多个核心共享。

public static void ij(int[][] a, int rows, int columns) {
    long sum = 0L;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            sum += a[i][j];
        }
    }
    System.out.println(sum);
}

public static void ji(int[][] a, int rows, int columns) {
    long sum = 0L;
    for (int j = 0; j < columns; j++) {
        for (int i = 0; i < rows; i++) {
            sum += a[i][j];
        }
    }
    System.out.println(sum);
}

链表

链表和节点是组合关系，特别适合写成内部类的形式

组合关系（Composition）确实非常适合使用内部类来实现，特别是在子类的生命周期紧密依赖于父类的情况下。内部类和组合关系都强调“整体-部分”的紧密关系，并且内部类的生命周期通常由外部类控制，符合组合关系的特征。

函数式方法：

在 实际工作 中，函数式接口非常常见，尤其是在以下场景中：

1. 数据转换和映射：使用 map() 和 Function。
2. 数据过滤：使用 filter() 和 Predicate。
3. 对数据执行操作：使用 forEach() 和 Consumer。
4. 生成和懒加载数据：使用 generate() 和 Supplier。
5. 数据合并和计算：使用 reduce() 和 BinaryOperator。

单项链表添加原来就一步啊，next设为head，并赋给head

head = new Node(value, head);

移除的话直接头移动，如果要返回值的话，先用first记录值，然后操作后，返回first

head = head.next;

而且不仅可以传值操作，也可以传节点

如何递归删除指定元素值,返回的都是节点p，如果是查找值，跳过，不是就返回当前的

这个也可以用于去重，if(p.value == value)这个条件的本质就是跳过复合条件的节点，最后构成新的节点链表

removeElemnets(Node p, value)
if(p == null) {
		return null;
}

if(p.value == value) {
  	return removeElements(p.next, value)
}else {
    p.next = removeElements(p.next, value)
    return p;
}

倒数排号删除

给倒数的节点设置n

recursion(Node p, int n) {
	if(p.next == null) {
    return 0;
  }
  
  int nth = recursion(p.next, n);
  if(nth == n) {
    p.next = p.next.next;
  }
  
  return nth + 1;
}

还有一个思路，这些根本不可能想得到啊

for(int i = 0; i < n + 1; i++) {
  p2 = p2.next; 
}

while(p2.next != null) {
  p1 = p1.next;
  p2 = p2.next;
}

p1.next = p1.next.next;

去重并直接全删掉

deleteDulicates(ListNode p) {
  if(p == null || p.next != null) {
    return p;
  }
  
  if(p.value == p.next.value) {
    ListNode x = p.next.next;
    if(p.value == x.value) {
      x = x.next;
    }
    return deleteDuplicates(x);
  }else {
    p.next = deleteDuplicates(p.next);
    return p;
  }
}

有序链表合并。双链表就构建新的链表，多链表就是递归

双链表

// 比较两个链表当前节点的值，将较小值的节点的next指向剩余节点的合并结果
if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
} else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
}

单链表

 // 当结束索引j达到链表数组的最大索引时，调用mergeTwoLists方法合并最后两个链表
    if(j == lists.length - 1) {
        return mergeTwoLists(lists[i], lists[j]);
    }

    i++;
    j++;

    // 递归调用merge方法，逐步合并链表
    ListNode listNode = merge(lists, i, j);
    return listNode;
}

递归

汉诺塔问题，递归的核心是如何拆解问题，一个问题的答案是更小规模改问题的答案类和，汉诺塔问题转化为，无论多少层，第一步把n-1层放在b,第二步把n层放在c，最后把n-1层放在c,第一步和最后，也就是该问题本身，第一步要先把n-1放到b就需要把n-2放在c，无限递归，就只需要，调用自身，交换bc位置，第二步直接转换，第三步类似

代码：

static void move(int n, LinkedList<Integer> from, LinkedList<Integer> to, LinkedList<Integer> other) {
        //无论多少层，第一步把n-1层放在b,把n层放在c，最后把n-1层放在c

        if( n == 0) {
            return;
        }

        // n-1层放在b
        move(n-1,  from, other, to);
        // 把n层放在c
        to.addLast(from.removeLast());
        // n-1层放在c
        move(n-1, other, to, from);
    }

队列

可以用链表实现队列，头尾指针，初始化哨兵指向自己，头尾指针指向哨兵，也可以使用环形数组，采用取模的思路，求余数的时候，不仅可以使用%，还可以使用&按位于，如果除数是2的密次方，那余数就是x & (n - 1)

队列的应用

如便利二叉树时，层级便遍历，就需要队列