沉梦听雨的编程指南
  • 计算机基础
  • 数据结构与算法
  • 力扣篇
沉梦听雨
2023-05-12
目录

刷题小记

# 刷题小记

# 数组

在 Java 中，数组是一种基础的数据结构，提供了一些内部方法来进行操作。

以下是一些常用的数组内部方法：

# 获取数组长度

  • length: 返回数组的长度。

# 复制数组

  • System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length): 将数组指定范围的元素复制到另一个数组。

# 数组排序

  • Arrays.sort(int[] a): 对整型数组进行升序排序。
  • Arrays.sort(char[] a): 对字符数组进行升序排序。
  • Arrays.sort(T[] a, Comparator<? super T> c): 使用自定义比较器对对象数组进行排序。

# 数组填充

  • Arrays.fill(int[] a, int val): 将整型数组的所有元素都设置为指定值。
  • Arrays.fill(char[] a, char val): 将字符数组的所有元素都设置为指定值。

# 查找元素

  • Arrays.binarySearch(int[] a, int key): 对升序数组进行二分查找，找到返回索引，否则返回负数。

# 数组转换为字符串

  • Arrays.toString(type[] a): 返回数组的字符串表示。

# 数组拷贝

  • Arrays.copyOf(type[] original, int newLength): 复制指定数组的指定长度。
  • Arrays.copyOfRange(type[] original, int from, int to): 复制指定数组的指定范围。

# 数组填充

  • Arrays.fill(type[] a, type val): 用指定的值填充整个数组。

# 使用指定的生成器函数生成数组的每个元素

Arrays.setAll()：

  • Arrays.setAll(T[] array, IntUnaryOperator generator): 使用指定的生成器函数生成数组的每个元素。
  • 这个方法接受一个 IntUnaryOperator 函数接口作为参数，该函数接受一个索引，返回对应索引位置上元素的值。
int[] array = new int[5];
Arrays.setAll(array, i -> i * i);
// 现在 array = [0, 1, 4, 9, 16]
1
2
3

# 在一个已排序的数组中搜索指定元素，并返回返回元素在数组中的索引

Arrays.binarySearch(arr, element) 是用于在一个已排序的数组 arr 中搜索指定元素 element 的方法。

  • 这个方法返回元素在数组中的索引，
  • 如果找不到元素则返回负数。

方法签名为：

int Arrays.binarySearch(type[] arr, type key)
1

其中，arr 是要搜索的数组，key 是要查找的元素。

注意事项：

  • 如果数组包含多个相等的元素，无法保证返回的是哪一个元素的索引。
  • 如果数组中不存在指定的元素，返回的是一个负数，表示元素应该插入数组中的位置，插入后数组仍保持有序。

示例：

int[] array = {1, 2, 3, 4, 5};
int index = Arrays.binarySearch(array, 3);

// index 的值为 2，因为元素 3 在数组中的索引为 2
1
2
3
4

如果数组中不存在要查找的元素，返回的值将是负数。

要获得正确的插入点，可以使用以下方式：

int[] array = {1, 2, 4, 5};
int key = 3;
int index = Arrays.binarySearch(array, key);

// index 的值为 -3，表示如果要插入元素 3，它应该插入到索引为 2 的位置
1
2
3
4
5

注意：在使用 binarySearch 方法之前，数组必须是有序的，否则结果是不确定的。如果数组无序，可以使用 Arrays.sort() 对数组进行排序。

# 位运算

在计算机中，位运算是指对二进制数进行的运算。Java中提供了位运算符来进行位运算操作，包括**按位与（&）、按位或（|）、按位异或（^）、按位取反（~）、左移位（<<）和右移位（>>）**等。

下面简单介绍一下位运算符的功能和使用方法：

# 1.按位与（&）

对两个二进制数进行位运算，如果两个数对应位都是 1，则结果为 1，否则为 0。例如：

int a = 0b1010; // 二进制数1010
int b = 0b1100; // 二进制数1100
int result = a & b; // 按位与运算，结果为1000（二进制）
1
2
3

# 2.按位或（|）

对两个二进制数进行位运算，如果两个数对应位都是 0，则结果为 0，否则为 1。例如：

int a = 0b1010; // 二进制数1010
int b = 0b1100; // 二进制数1100
int result = a | b; // 按位或运算，结果为1110（二进制）
1
2
3

# 3.按位异或（^）

对两个二进制数进行位运算，如果两个数对应位相同，则结果为 0，否则为 1。例如：

  • 相同为 0，不同为 1
int a = 0b1010; // 二进制数1010
int b = 0b1100; // 二进制数1100
int result = a ^ b; // 按位异或运算，结果为0110（二进制）
1
2
3

# Integer.bitCount(x ^ y)

bitCount 实现的功能是计算一个（byte,short,char,int统一按照int方法计算）int, long 类型的数值在二进制下 “1” 的数量。

// 求汉明距离
class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}
1
2
3
4
5
6

# 4.按位取反（~）

对一个二进制数进行位运算，将所有的 0 变为 1，将所有的 1 变为 0。例如：

int a = 0b1010; // 二进制数1010
int result = ~a; // 按位取反运算，结果为0101（二进制）
1
2

# 5.左移位（<<）-- 乘

将一个二进制数向左移动指定的位数，移动后右侧补 0。例如：

  • 左移一位，数变大，相当于乘于 2
int a = 0b1010; // 二进制数1010
int result = a << 2; // 左移2位，结果为101000（二进制）

size << 1 // 左移一相当于乘于2
1
2
3
4

# 6.右移位（>>）-- 除

将一个二进制数向右移动指定的位数，移动后左侧补 0。例如：

  • 左移一位，数变大，相当于除于 2
int a = 0b1010; // 二进制数1010
int result = a >> 2; // 右移2位，结果为0010（二进制）

size >> 1 // 右移一相当于除于2
1
2
3
4
  • 需要注意的是，位运算符只能用于整数类型（byte、short、int、long）的数据。
  • 另外，在进行位运算时，需要特别注意数据类型的符号位，因为有些位运算符（如右移位运算符）会保留符号位。

# 异或性质：

1.任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。

2.任何数和其自身做异或运算，结果是 a⊕a=0。

3.异或运算满足交换律和结合律，即a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
1
2
3
4
5

# 问题

# 为什么 -5 右移一位是 -3，而 -5/2 是 -2

-3 的由来

这是由于负数的二进制表示以及右移操作的工作原理所导致的。在计算机中，负数通常以二进制的补码形式表示。

首先，让我们来看看 -5 的二进制表示：

  • 正数5的二进制表示是：00000101。
  • 负数的补码表示是将对应正数的二进制取反（将 0 变成 1，将 1 变成 0），然后加 1。所以 -5 的补码表示是：11111011。

现在，让我们将 -5 右移一位：

  • 右移一位后，最高位（符号位）仍然为 1，表示这仍然是一个负数。
  • 新的补码表示是：11111101。

接下来，我们将这个补码转换回十进制，就得到了 -3。

按位操作和除法操作是不一样的。

# String 类

String 类是 Java 中的一个基础类，提供了许多有用的方法来操作字符串。

以下是一些常用的 String 内部方法：

# 获取字符串长度

  • length(): 返回字符串的长度。

# 获取字符

  • charAt(int index): 返回指定索引处的字符。

# 子串操作

  • substring(int beginIndex): 返回从指定索引开始到字符串末尾的子字符串。（包含索引为 beginIndex 的元素）
  • substring(int beginIndex, int endIndex): 返回从指定索引开始到指定索引结束的子字符串。（不包含索引为 endIndex 的元素）

# 连接字符串

  • concat(String str): 将指定字符串连接到此字符串的末尾。

# 查找子字符串

  • indexOf(String str): 返回指定子字符串在此字符串中第一次出现的索引。
  • lastIndexOf(String str): 返回指定子字符串在此字符串中最后一次出现的索引。

# 字符串比较

  • equals(Object obj): 将此字符串与指定对象进行比较。
  • equalsIgnoreCase(String anotherString): 按字典顺序比较两个字符串，不考虑大小写。

# 字符串替换

  • replace(char oldChar, char newChar): 返回一个新字符串，它是通过用 newChar 替换此字符串中出现的所有 oldChar 得到的。

# 字符串分割

  • split(String regex): 根据给定正则表达式的匹配拆分此字符串。
  • split(String regex, int limit): 根据给定正则表达式的匹配拆分此字符串，最多拆分出 limit 个子字符串。

# 字符串转换

  • toLowerCase(): 将此字符串转换为小写。
  • toUpperCase(): 将此字符串转换为大写。

# 去除空格

  • trim(): 返回一个字符串，其值为此字符串，并删除了所有前导空白和尾部空白。

# 链表 LinkedList

常用方法如下：

  • add(E e): 将元素添加到链表。
  • remove(E e): 从链表中移除指定元素。
  • get(int index): 获取链表中指定索引处的元素。
  • size(): 返回链表的大小。

# 哈希表 HashMap

常用方法如下：

  • put(K key, V value): 将键值对存入哈希表。
  • get(K key): 获取键对应的值。
  • containsKey(K key): 判断是否包含指定键。
  • remove(K key): 移除指定键的映射。
  • keySet(): 返回哈希表中所有键的集合。

# 集合 HashSet

常用方法如下：

  • add(E e): 将元素添加到集合。
  • remove(E e): 从集合中移除指定元素。
  • contains(E e): 判断集合是否包含指定元素。

# 队列 queue

在 Java 中，Queue 是一个接口，它表示队列的基本行为，即一个先进先出（FIFO）的数据结构。Queue 接口定义了一组方法，用于操作队列，这些方法包括：

# 1.queue.poll()

queue.poll() 是 Java 中 Queue 接口定义的一个方法，用于获取并移除队列的头部元素，如果队列为空则返回 null。

# 2.queue.add()

add(E e)：将指定元素插入队列中，如果队列已满，则抛出一个 IllegalStateException 异常。

# 3.queue.offer()

offer(E e)：将指定元素插入队列中，如果队列已满，则返回 false。

# 4.queue.remove()

remove()：获取并移除队列头部的元素，如果队列为空，则抛出一个 NoSuchElementException 异常。

# 5.queue.element()

element()：获取但不移除队列头部的元素，如果队列为空，则抛出一个 NoSuchElementException 异常。

# 6.queue.peek()

peek()：获取但不移除队列头部的元素，如果队列为空，则返回 null。

此外，Queue 接口还扩展了 Collection 接口，因此还可以使用 size()、isEmpty()、contains(Object o)、iterator()、toArray() 等方法。

在 Java 中，Queue 接口有多个实现类，包括：

  1. ArrayDeque：基于数组实现的双端队列。
  2. LinkedList：基于链表实现的队列。
  3. PriorityQueue：基于堆实现的优先队列。

不同的实现类可能会有不同的方法和行为，但它们都实现了 Queue 接口，因此都支持上述的方法和行为。

# 代码示例

/**
 * 层序遍历方式反转（也相当于广度优先）
 */
public TreeNode invertTreeByQueue(TreeNode root) {
    if (root == null) {
        return null;
    }
    Queue<TreeNode> queue = new ArrayDeque<>();
    // 插入
    queue.offer(root);
    while (!queue.isEmpty()) {
        // 弹出
        TreeNode node = queue.poll();
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        if (node.left != null) {
            // 插入左节点
            queue.offer(node.left);
        }
        if (node.right != null) {
            // 插入右节点
            queue.offer(node.right);
        }
    }
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 双端队列 Deque

在 Java 中，Deque 接口（双端队列）有以下一些常用的方法：

# 插入操作

  • addFirst(E e) 或 offerFirst(E e): 在队头插入元素。
  • addLast(E e) 或 offerLast(E e): 在队尾插入元素。

# 移除操作

  • removeFirst() 或 pollFirst(): 移除并返回队头的元素。
  • removeLast() 或 pollLast(): 移除并返回队尾的元素。

# 访问操作

  • getFirst() 或 peekFirst(): 获取但不移除队头的元素。
  • getLast() 或 peekLast(): 获取但不移除队尾的元素。

# 其他操作

  • size(): 返回队列的大小。
  • isEmpty(): 判断队列是否为空。
  • clear(): 清空队列。

这些方法允许你在双端队列的两端执行插入、移除和访问操作，使得双端队列在解决算法问题时非常灵活。在题解中，你可能会经常看到这些方法的使用，尤其是在实现滑动窗口等问题时。

# 优先队列 PriorityQueue

常用方法如下：

  • add(E e) 或 offer(E e): 将元素插入队列。
  • poll(): 移除并返回队列中最小（或最大）的元素。
  • peek(): 获取但不移除队列中最小（或最大）的元素。
  • size(): 返回队列的大小。

# 栈stack

在 Java 中，Stack 是一个 LIFO（后进先出）的数据结构，它继承自 Vector 类，同时也实现了 List 接口。

虽然 Stack 类在 Java 中仍然可用，但是在 Java SE 5 中，推荐使用 Deque 接口的实现类 LinkedList 来代替 Stack 类，因为 LinkedList 类实现了 Deque 接口，提供了与 Stack 类相同的方法，并且更加高效。

常用方法如下：

  • push(E item): 将元素压入栈顶。
  • pop(): 弹出并返回栈顶元素。
  • peek(): 获取但不移除栈顶元素。
  • empty(): 判断栈是否为空。
上次更新: 2024/9/25 11:16:13
总结
解法描述

← 解法描述→

Theme by Vdoing | Copyright © 2023-2024 沉梦听雨 | MIT License