1、判断字符是否唯一

1.1、题目描述

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

1.2、解题思路

  • 使用一个数组来解决这个问题，创建一个长度为 256 的数组（ascii 码数目）
  • 循环遍历字符串转换而成的字符数组，当遍历到一个字符时，判断这个字符对应的 ascii 码对应的值是否为 1 ，如果是，直接返回 false ，否则将字符 ascii 码对应的那个元素置为 1

这道题也可以用集合来做，但没必要

1.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isUnique(String astr) {
    if (astr == null || astr.length() == 0 || "".equals(astr.trim())) {
        return true;
    }
    int[] memo = new int[256];
    char[] array = astr.toCharArray();
    for(int i = 0;i < array.length;i++) {
        if (memo[array[i]] > 0) {
            return false;
        }
        memo[array[i]] = 1;
    }
    return true;
}

2、字符串压缩

2.1、题目描述

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串 aabcccccaaa 会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

2.2、解题思路

  • 使用快慢指针完成这道题

  • 初始化两个指针，慢指针 slow 一开始指向下标为 0 的元素，快指针 fast 一开始指向下标为 1 的元素

  • 当 fast 指向的元素等于 slow 指向的元素时，此时让 right 往后移

  • 当 fast 指向的元素不等于 slow 指向的元素时，此时进行结果字符串拼接，将 left 指向的字符拼接到结果字符串中，然后再将 right - slow 的值拼接到结果字符串中，然后让 left 移动到 right 的位置，同时 right 后移

2.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public String compressString(String S) {
    if (S == null) return "";
    if (S.length() < 2) return S;
    // 初始化 slow 指针为 0
    int slow = 0;
    // 初始化 fast 指针为 1
    int fast = 1;
    StringBuilder builder = new StringBuilder();
    while (fast < S.length()) {
        if (S.charAt(slow) != S.charAt(fast)) {
            builder.append(S.charAt(slow)).append(fast - slow);
            // 然后让 slow 来到 fast 的位置
            slow = fast;
            fast++;
        } else {
            // 当两个指针指向的元素相等时，表示此时还不能进行结果字符串的拼接
            // 直接让 fast 指针后移即可
            fast++;
        }
    }
    // 在最后，需要进行收尾，对此时 left 指向的元素进行拼接，否则会丢失最后一个字符及其出现次数
    builder.append(S.charAt(slow)).append(fast - slow);
    return builder.toString().length() >= S.length() ? S : builder.toString();
}

3、字符串轮转

3.1、题目描述

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。

  • 示例1:

    1
    2
    输入：s1 = "waterbottle", s2 = "erbottlewat"
    输出：True

  • 示例2:

    1
    2
    输入：s1 = "aa", s2 = "aba"
    输出：False

3.2、解题思路

  • 两个字符串排序后判断是否相等
  • 将两个 s2 进行拼接，得到结果串 Str ，然后判断 Str 是否含有 s1 ，如果有，返回 true ，否则返回 false

3.3、解题代码

  • 排序后判断是否相等
1
2
3
4
5
6
7
8
9
public boolean isFlipedString(String s1, String s2) {
    if (s1 == null && s2 == null) return true;
    if (s1.length() != s2.length()) return false;
    char[] array1 = s1.toCharArray();
    char[] array2 = s2.toCharArray();
    Arrays.sort(array1);
    Arrays.sort(array2);
    return new String(array1).equals(new String(array2));
}
  • 拼接后判断
1
2
3
4
5
6
public boolean isFlipedString(String s1, String s2) {
    if (s1 == null && s2 == null) return true;
    if (s1.length() != s2.length()) return false;
    String result = s2 + s2;
    return result.contains(s1);
}

4、字符串回文排列

4.1、题目描述

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。

回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。

回文串不一定是字典当中的单词。

4.2、解题思路

  • 要想一个字符串可以回文排列，那么必须满足以下条件之一
  1. 字符串有奇数个字符，同时只能有一个字符与其他字符不同，剩下的字符必须两两成对
  2. 字符串有偶数个字符，此时字符串中的字符必须两两成对。

使用一个 HashSet 来解决这个问题，遍历字符串中的每一个字符，然后尝试将其加入到 set 中，如果添加成功，那么什么都不做，如果添加失败，证明 set 中已经存在过当前遍历的字符，我们需要将其从 set 中剔除。

遍历完成后，判断 set 中的元素个数，如果小于等于 1 ，那么返回 true ，否则返回 false

4.3、解题代码

1
2
3
4
5
6
7
8
9
public boolean canPermutePalindrome(String s) {
    Set<Character> set = new HashSet<>();
    for (char c : s.toCharArray()) {
        if (!set.add(c)) {
            set.remove(c);
        }
    }
    return set.size() <= 1;
}

5、一次编辑

5.1、题目描述

字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

5.2、解题思路

  • 如果两个字符串长度相差一，那么直接返回 false
  • 如果两个字符串长度相等，那么只需要逐个比较字符串中的字符即可，使用一个标识符来标识是否编辑过，当遇到第一个不等字符时，将这个标识符从 false 置为 true ，表示已经编辑过，如果在之后的遍历中遇到另外的不等字符，那么直接返回 false 即可。
  • 如果两个字符串长度不相等，那么此时我们记长的字符串为 long ，短的字符串为 small ，仍然使用一个标识符来表示是否编辑过，这里使用双指针遍历两个字符串，如果两个指针指向的字符不等，那么将标识符从 false 置为 true ，表示已经编辑过，然后将用于遍历长字符串的指针后移

因为对于这次编辑来说，如果是添加，那么这个多出来的元素可能是短字符串中缺少的元素，此时我们需要让长字符串的下一个字符与当前短字符串的字符相比。

删除同理，将不等的那个字符删掉后，比较长字符串下一个字符与短字符串当前字符是否相等。

5.3、解题代码

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
28
29
30
31
32
33
public boolean oneEditAway(String first, String second) {
    // 如果两个字符串的长度相差大于 1 ，那么直接返回 false
    int firstLength = first.length();
    int secondLength = second.length();
    if (Math.abs(firstLength - secondLength) > 1) {
        return false;
    }

    boolean isEdit = false;
    int left = 0,right = 0;
    while (left <= firstLength - 1 && right <= secondLength - 1) {
        // 如果两个指针指向的元素相等，那么直接让两个指针共同后移即可
        if (first.charAt(left) == second.charAt(right)) {
            left++;
            right++;
        } else {
            if(!isEdit){
                if (firstLength == secondLength) {
                    left++;
                    right++;
                } else if (firstLength < secondLength) {
                    right++;
                } else{
                    left++;
                }
                isEdit = true;
            } else{
                return false;
            }
        }
    }
    return true;
}

6、移除重复节点

6.1、题目描述

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

6.2、解题思路

  • 使用一个 Set 来解决这道题，初始化两个指针 pre 和 cur ，一个指向头节点，用于结果返回，第二个用于遍历链表
  • 每遍历到一个节点，就尝试着将其加入到 set 中，如果加入成功，那么继续遍历，如果添加不成功，则删除那个无法加入到 set 之中的节点
  • 最后返回头节点即可

6.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode removeDuplicateNodes(ListNode head) {
    if (head == null || head.next == null) return head;
    Set<Integer> nodeSet = new HashSet<>();
    nodeSet.add(head.val);
    ListNode cur = head;
    while (cur.next != null) {
        if (nodeSet.add(cur.next.val)) {
            // 如果能放入 set 中，那么继续遍历
            cur = cur.next;
        } else {
            // 否则移除 cur.next 这个节点
            cur.next = cur.next.next;
        }
    }
    return head;
}

7、旋转矩阵

7.1、题目描述

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像顺时针旋转 90 度。

  • 示例 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
  • 示例 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

7.2、解题思路

  • 从外到内进行处理，在进行顺时针九十度旋转时，外圈和内圈的元素不会进行交换，也就是说，外圈元素只是和外圈元素进行交换，而内圈元素也仅和内圈元素进行交换
  • 我们先处理最外圈的元素，以示例二的矩阵为例
1
2
3
4
[ 5, 1, 9,11],
[ 2,      10],
[13,       7],
[15,14,12,16]

  • 在我们处理完最外圈元素后，我们再处理第二层的元素，此时只需要将左上角点向右下角移动，右下角点向左上角点移动即可处理第二圈…

  • 在一个圈内，我们可以将这个 n * n 的圈的元素分为 n - 1 组，然后进行交换，下面以 4 * 4 的圈为例

我们将同组元素用相同的形状划分，在进行顺时针九十度旋转时，每个元素都根据箭头的指向进行元素覆盖

  • 我们记这个圈的左上角点的行号为 sR ，右下角点的列号为 eC ，那么
  1. 第 i 组的第一个元素就可以表示为 martix[sR] [sR + i]
  2. 第 i 组的第二个元素就可以表示为 martix[sR + i] [eC] （第 i 组的第二个元素全部都在最后一列）
  3. 第 i 组的第三个元素就可以表示为 martix[eC] [eC - i]
  4. 第 i 组的第四个元素就可以表示为 martix[eC - i] [sR] （第 i 组的第四个元素一定在第一列）

image-20211024155919089

  • 如何交换元素，以上面的外圈矩阵为例
  1. 先使用一个变量保存第 i 组第一个元素的值
  2. 然后用第四个元素的值覆盖第一个元素的位置
  3. 用第三个元素的值覆盖第四个元素的位置
  4. 用第二个元素的值覆盖第三个元素的位置
  5. 最后用临时变量中第一个元素的值覆盖第二个元素的位置

7.3、解题代码

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
28
29
30
31
32
33
34
35
36
public void rotate(int[][] matrix) {
    // 用两个变量来表示矩阵的左上角点，初始化为 (0,0)
    int startRow = 0, startColumn = 0;
    // 用两个变量来表示矩阵的右下角点，初始化为 (matrix.length - 1, matrix[0].length - 1)
    int endRow = matrix.length - 1, endColumn = matrix[0].length - 1;
    // 当 startRow < endRow 时，表示左上角点和右上角点还能构成一个待处理矩阵，所以需要进行处理
    while (startRow < endRow) {
        // 处理完外圈后，要让左上角点向右下角移动，右上角点向左上角移动
        rotateCircle(matrix, startRow++, startColumn++, endRow++, endColumn++);
    }
}
/**
 * 对以点 (startRow,startColumn) 作为左上角点，以点 (endRow,endColumn) 作为右下角点的外围元素进行交换
 * @param matrix
 */
private void rotateCircle(int[][] matrix, int startRow, int startColumn, int endRow, int endColumn) {
    int times = endRow - startRow;
    // 这个变量用于交换
    int temp = 0;
    // 对于一个 n * n 的圈，我们需要分为 n - 1 组处理
    for (int i = 0; i < times; i++) {
        // 先保存第 i 组第一个元素的值
        temp = matrix[startRow][startRow + i];
        // 第 i 组第二个元素的值：matrix[startRow + i][endColumn]
        // 第 i 组第三个元素的值：matrix[endRow][endColumn - i]
        // 第 i 组第四个元素的值：matrix[endRow - i][startColumn]
        // 先用第四个元素的值覆盖第一个元素的位置
        matrix[startRow][startColumn + i] = matrix[endRow - i][startColumn];
        // 然后用第三个元素的值覆盖第四个元素的位置
        matrix[endRow - i][startColumn] = matrix[endRow][endColumn - i];
        // 用第二个元素的值覆盖第三个元素的位置
        matrix[endRow][endColumn - i] = matrix[startRow + i][endColumn];
        // 用临时变量中第一个元素的值覆盖第二个元素的位置
        matrix[startRow + i][endColumn] = temp;
    }
}

8、分割链表

8.1、题目描述

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

8.2、解题思路

  • 使用快慢指针遍历链表，当快指针指向的节点的 val 大于等于 x 时，此时慢指针不动，而快指针右移
  • 当快指针指向的节点的 val 小于 x 时，此时交换慢指针指向节点的值和快指针指向的节点的值，然后快慢指针一起后移

8.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode partition(ListNode head, int x) {
    if (head == null || head.next == null) return head;
    ListNode slow = head, fast = head;
    // 这个值用于交换使用
    int temp = 0;
    while (fast != null) {
        // 如果此时快指针指向的节点的值小于 x
        if (fast.val < x) {
            // 此时需要将 slow.val 和 fast.val 的值进行交换，然后将 slow 后移
            temp = fast.val;
            fast.val = slow.val;
            slow.val = temp;
            slow = slow.next;
        }
        fast = fast.next;
    }
    // 由于只是进行值的交换，没有涉及节点的移动和增删，所以可以直接返回
    return head;
}

9、回文链表

9.1、题目描述

编写一个函数，检查输入的链表是否是回文的。

9.2、解题思路

  • 使用快慢指针找到链表的中间结点，然后将中间结点之后的部分反转
  • 比较链表前半部分和后半部分是否相同，如果相同，则证明是回文链表

9.3、解题代码

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
28
29
30
31
32
33
34
public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    // 初始化快慢指针指向 head 结点
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    // 如果 fast 不为空，证明为奇数个结点
    if (fast != null) {
        slow = slow.next;
    }
    // 反转后半段链表
    slow = reverseList(slow);
    // 让 fast 从头开始，比较前半部分和后半部分的值
    fast = head;
    while (slow != null) {
        if (slow.val != fast.val) {
            return false;
        }
        slow = slow.next;
        fast = fast.next;
    }
    return true;
}
public ListNode reverseList(ListNode head) {
    if(head == null || head.next == null) {
        return head;
    }
    ListNode reverseNode = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return reverseNode;
}

10、最小栈

10.1、题目描述

请设计一个栈，除了常规栈支持的 pop 与 push 函数以外，还支持 min 函数，该函数返回栈元素中的最小值。**执行push、pop和min操作的时间复杂度必须为O(1)**。

10.2、解题思路

  • 定义一个 Node 类，这个类包含两个属性
  1. value：结点的值
  2. min：这个 Node 对象为栈顶元素时，当前栈的最小值
  • push 方法

当我们将一个值 x 压入栈中时，判断这个 x 与栈顶元素的关系

  1. 如果 x 小于当前栈顶元素的值，那么构造出一个 Node 对象压入栈中，这个 Node 对象的 value 为 x ，min 为 x
  2. 如果 x 大于等于当前栈顶元素的值，那么构造一个 Node 对象压入栈中，这个 Node 对象的 value 为 x ，min 为 stack.peek().min （栈顶元素的 min 值）
  • pop、peek 方法

返回栈顶 Node 对象的 value 值即可

  • getMin() 方法

返回栈顶 Node 对象 的 min 值即可

10.3、解题代码

  • Node 类
1
2
3
4
5
6
7
8
9
class Node {
    int value;
    int min;

    public Node (int val, int minValue) {
        min = minValue;
        value = val;
    }
}
  • MinStack 实现
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
public class MinStack {
    private Stack<Node> minStack;
    /** initialize your data structure here. */
    public MinStack() {
        minStack = new Stack<>();
    }

    public void push(int x) {
        if (x < minStack.peek().min || minStack.empty()) {
            minStack.push(new Node(x, x));
        } else {
            minStack.push(new Node(x, minStack.peek().min));
        }
    }

    public void pop() {
        minStack.pop();
    }

    public int top() {
        return minStack.peek().value;
    }

    public int getMin() {
        return minStack.peek().min;
    }
}

11、Sqrt(x)

11.1、题目描述

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5)

11.2、解题思路

  • 使用二分法来解决这个问题，假设我们要求 104 的算术平方根
  1. 104 的算术平方根一定处于 [1,104] 之间，先求出 (1 + 104) / 2 的值，向下取整后得到 52
  2. 计算 52 * 52 的值，由于 52 * 52 的值远远大于 104 ，故 104 的算术平方根一定不会落在 [52, 104] 之间
  3. 所以我们从 [1,51] 中继续二分查找 104 的算术平方根
  • 按照上面的步骤，我们可以一步步地缩减查找的范围

  1. 查找 1 - 51 之间的中位数，发现 26 * 26 的值大于 104 ，故我们缩减范围，在 [1,25] 之间查找

  2. 查找 1 - 25 之间的中位数，由于 13 * 13 的值大于 104 ，所以我们在 [1,12] 之间查找

  3. 在 1 - 12 之间查找，由于 6 * 6 的值小于 104 ，所以我们在 7 - 12 之间查找

  4. 在 7 - 12 之间查找，由于 9 * 9 的值小于 104 ，所以我们在 10 - 12 之间查找

  5. 在 10 - 12 之间查找，由于 11 * 11 的值大于 104 ，所以我们得到结果为 10

11.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int mySqrt(int x) {
    if (x == 0) return 0;
    if (x < 3) return 1;
    long result = 1;
    // 初始化左右边界的值
    long left = 1;
    long right = x;
    long mid = 0;
    while (left <= right) {
        mid = (left + right) >> 1;
        if (mid * mid <= x) {
            // 如果计算出来的结果小于等于 x 
            // 那么先记录答案，然后看看有没有更接近的
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return (int) result;
}

12、最小覆盖子串

12.1、题目描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。

如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

  • 示例 1：

    1
    输入：s = "sabsbbcca", t = "aabbc"

12.2、解题思路

  • 只有当 s 长度大于等于 t 长度时，才需要进行讨论

  • 创建一张“欠债表”，这张表中初始化为 t 字符串中出现的字符及其出现次数，并使用一个变量 all 记录欠债表中所有字符的个数，初始化为 t 字符串的长度

  • 遍历 s 字符串，根据遍历到的内容对欠债表中内容和 all 变量中的值进行修改

  • 以示例一为例

  1. 初始化一张欠债表，欠债表中的内容为字符串 t 中出现的字符及其出现次数，即 {“a”：2，”b”：2 ，”c”：1}，并初始化 all 为 t 字符串的长度 5
  2. 初始化两个指针，一开始均指向下标为 0 的元素，一开始，保持 left 不动，而 right 向右移动。根据遍历到的字符串的字符来修改欠债表和 all 的值

当遍历到 ‘s’ 字符时，由于 t 字符串中没有对应的字符，所以在欠债表中添加一条记录 s：-1 ，不修改 all ；

遍历到 ‘a’ 字符时，由于 t 字符串中含有 a ，所以修改欠债表和 all 的值，将欠债表中 a 记录对应的值 - 1，然后如果此时 a 记录对应的值不小于 0 ，那么我们称这次修改为 有效修改，所以我们将 all 的值 -1

遍历到 ‘b’ 时，此时修改欠债表和 all 的值；

遍历到 ‘s’ 时，修改欠债表中 s 对应的值为 -2 ，不修改 all

遍历到第二个 ‘b’ 时，修改欠债表和 all 的值，在遍历到第三个 ‘b’ 时，由于修改欠债表后，b 对应的值变为 -1 ，所以此时不是有效修改，不修改 all 的值

遍历到第二个 a 后，此时 all 的值已经变为 0 ，同时 right 来到第二个 ‘a’ 下。

  1. 当 all 变为 0 时，我们就找到了题目的一个解 [left ,right ]，此时我们保持 right 不动，让 left 后移，如果 left 后移后不会使 s 字符串变为“欠款”状态（欠债表中有记录值大于 0）

如果不会，那么让 left 继续后移

如果会，那么让 right 继续往后移，直到重新恢复未欠款状态

  • 这样我们就可以得到所有的答案，之后在所有的答案中选出一个最短的即可。

12.3、解题代码

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public String minWindow(String s, String t) {
    // 如果 t 的长度大于 s 的长度，那么直接返回空串
    if (s.length() < t.length()) return "";
    char[] strArray = s.toCharArray();
    char[] targetArray = t.toCharArray();
    // 欠债表，初始化为 target 中字符及其出现次数
    int[] map = new int[256];
    for (char ch : targetArray) {
        map[ch]++;
    }
    // 欠债总额，初始化为 target 字符串的长度
    int all = targetArray.length;
    // 初始化双指针
    int left = 0, right = 0;
    int minLen = -1;
    // 答案窗口，用于记录最佳答案的左右下标
    int resultLeft = -1, resultRight = -1;
    while (right < strArray.length) {
        // 根据遍历到的字符修改欠债表中的记录
        map[strArray[right]]--;
        // 如果修改后对应记录的值大于等于 0 ，那么说明这次修改是有效修改
        if (map[strArray[right]] >= 0) {
            all--;
        }
        // 如果 all 为 0 ，证明找到了一个答案
        if (all == 0) {
            // 如果此时左指针指定的值在欠债表中为负数，那么证明让左指针后移
            // 也不会变为负债状态，所以直接让左指针后移
            // 同时修改欠债表中的内容
            while (map[strArray[left]] < 0) {
                // 修改欠债表中的内容
                map[strArray[left]]++;
                // 左指针后移
                left++;
            }
            // 如果此时左右指针形成的窗口大小小于 minLen 的值
            // 或者 minLen == -1
            if (minLen == -1 || minLen > right - left + 1) {
                minLen = right - left + 1;
                resultLeft = left;
                resultRight = right;
            }
            // 当以当前 left 为开头的结果弄完后，需要将 left 后移
            // 寻找下一个以 left 为开头的结果
            all++;
            map[strArray[left++]]++;
        }
        right++;
    }
    return minLen == -1 ? "" : s.substring(resultLeft, resultRight + 1);
}

13、汉诺塔问题

13.1、题目描述

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:

  • 每次只能移动一个盘子;
  • 盘子只能从柱子顶端滑出移到下一根柱子;
  • 盘子只能叠在比它大的盘子上。

请编写程序，将所有盘子从第一根柱子移到最后一根柱子。

13.2、解题思路

  • 使用递归来解决这个问题，我们需要将 A 中的 A.size() 个盘子从 source 柱（A 集合所表示的柱子）移动到 target 柱（C 集合所表示的柱子）
  • 先将 A.size() - 1 个从 source 柱借助 target 柱移动到 help 柱，然后此时 source 柱上只剩下一个柱子，此时直接将 source 柱子上的最后一个盘子直接从 source 柱放到 target 柱上即可。
  • 将存放了 A.size() - 1 个柱子的 help 柱看为新的 source 柱，重复以上步骤，借助 target 柱将 A.size() - 2 个盘子放到原来的 source 柱，然后将第 A.size() - 1 个盘子放到 target 柱…
  • 重复以上步骤，问题就得到了解决。

13.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
    move(A.size(), A, B, C);
}
private void move(int size, List<Integer> source, List<Integer> help, List<Integer> target) {
    if (size == 1) {
        // 直接将 source 柱子上的盘子弹出，放在 target 柱子上
        target.add(source.remove(source.size() - 1));
        return;
    }
    // 先将上面的 size - 1 个盘子，借助 target 移动到中间的 help 柱子上
    move(size - 1, source, target, help);
    // 将最下面的第 size 个盘子，直接从 source 移动到 target 
    target.add(source.remove(source.size() - 1));
    // 将存放着 size - 1 个盘子的 help 柱看为新的 source 柱，我们需要将这 size - 1 个盘子移动到 target 柱
    move(size - 1, help, source, target);
}

14、二叉树的锯齿形层序遍历

14.1、题目描述

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

  • 示例

image-20211027201123446

返回：

[

​ [a],

​ [c,b],

​ [d,e,f],

​ [j,i,h,g]

]

14.2、解题思路

  • 使用一个双端队列来解决这道题

在将一层节点全部加入队列之后，我们需要记录一个 size ，来让我们知道什么时候该更改遍历的顺序

  1. 当节点从左往右遍历时，我们将节点从队列尾部放入，从队列头部弹出

当一个节点从队列头部弹出时，我们先将该节点的左子树加入队列，然后将它的右孩子加入队列，注意，此时需要将子节点从尾部放入

  1. 节点从右往左遍历时，我们将节点从队列头部放入，从队列尾部弹出

当一个节点从队列尾部弹出时，我们先将该节点的右子树加入队列，然后将其左子树加入队列，注意，此时需要将子节点从头部放入

  • 假设在一个双端队列中存放着 4 个元素，它们是二叉树中某一层的所有元素，此时的方向是从左往右遍历，同时它们也存在子节点，情况如下

image-20211027203723688

  1. 确定 size 为 4
  2. 由于是从左往右遍历，所以需要将节点从 头 弹出，同时先加左节点再加右节点，需要从尾部加入

将 a 弹出，同时将 L 节点从尾巴加入到队列中，size – ，此时队列中元素从左到右依次为：b c d L

将 b 弹出，同时将 M N 依次从尾部加入到队列中，size – ，此时队列元素从左到右依次为：c d L M N

当 c、d 依次弹出后，队列中的元素变为 L M N O P Y Z

  1. 当 c、d 弹出后，由于 size == 0 ，所以表示当前层已经遍历完毕，我们需要调换遍历顺序，此时元素应该从尾部弹出，同时添加子节点时先添加右节点，后加左节点，子节点从头部加入。

此时弹出的顺序为 Z Y P O N M L

14.3、解题代码

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    LinkedList<TreeNode> deque = new LinkedList<>();
    // 开始前，先将根节点加入到双端队列中
    deque.add(root);
    // 如何判断一层已经遍历完，使用一个 size 遍历来判断
    int size = 0;
    // 遍历方向，一开始为从左往右
    boolean leftDirection = true;
    while (!deque.isEmpty()) {
        size = deque.size();
        List<Integer> curLevel = new ArrayList<>();
        if (leftDirection) {
            for (int i = 0;i < size;i++) {
                // 从左往右遍历时，节点从头弹出
                TreeNode cur = deque.pollFirst();
                curLevel.add(cur.val);
                // 先将左节点，后加右节点，从尾巴加入
                if (cur.left != null) {
                    deque.addLast(cur.left);
                }
                if (cur.right != null) {
                    deque.addLast(cur.right);
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                // 从右往左遍历，节点从尾部弹出
                TreeNode cur = deque.pollLast();
                curLevel.add(cur.val);
                if (cur.right != null) {
                    deque.addFirst(cur.right);
                }
                if (cur.left != null) {
                    deque.addFirst(cur.left);
                }
            }
        }
        result.add(curLevel);
        // 改变遍历方向
        leftDirection = !leftDirection;
    }
    return result;
}

15、填充每个节点的下一个右侧节点指针

15.1、题目描述

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
  • 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。
  • 如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
  • 初始状态下，所有 next 指针都被设置为 NULL。

15.2、解题思路

  • 可以利用一个队列，按照层序遍历的原理将遍历到的每一个节点都连起来
  • 创建一个单向的队列，这个单向队列中的元素为 Node 对象

Node 类定义如下

1
2
3
4
5
6
7
class Node {
    int val;
    Node left;
    Node right;
    Node next;
    ...
}
  • MyQueue 实现如下
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class MyQueue {
    public Node head;
    public Node tail;
    public int size;

    public MyQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    /**
     * 判断这个单向队列是否为空
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 向单向队列中添加元素的方法
     * @param cur
     */
    public void offer(Node cur) {
        size++;
        if (head == null) {
            // 如果此时队列为空，那么由于 cur 是队列中的唯一元素，那么头和尾都是它
            head = cur;
            tail = cur;
            return;
        }
        // 如果队列不为空，那么证明该队列存在一个尾巴
        // 需要将原来尾巴的 next 指向新添加的元素
        tail.next = cur;
        // 然后这个新添加进来的元素变为新尾巴
        tail = cur;
    }

    public Node peek() {
        return isEmpty() ? null : head;
    }


    public Node poll() {
        size--;
        // 使用一个变量保存 head， 队列从尾部进，头部出
        Node result = head;
        // 队列的头指针后移
        head = head.next;
        // 然后让 result.next 指向空
        result.next = null;
        return result;
    }
}
  • 以下面的树为例，先将根加入到队列中，此时队列中只有 a

image-20211028200447546

  1. 此时队列不为空，将 a 节点弹出，然后如果它的左节点不为空，那么先将它的左节点加入到队列中；

  2. 如果右节点不为空，那么将它的右节点加入到队列中

弹出 a 后，因为它的左右节点均不为空，所以 b 和 c 会被加入到队列中，所以 b 的next 域会置为 c ，也就是说 b 的 next 已经填充为了 c ，此时队列中的值为 b c

  1. 此时队列不为空，那么会先弹出 b ，然后将 d、e 加入到队列中，此时 d 的 next 域被置为了 e ，当两个节点都被弹出后，队列中的值为 d -> e -> f -> g

15.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public Node connect(Node root) {
    if (root == null) return null;
    MyQueue queue = new MyQueue();
    queue.offer(root);
    while (!queue.isEmpty()) {
        // 记录当前队列这一层的元素个数
        int size = queue.size;
        for (int i = 0;i < size;i++) {
            // 从队头拿出元素
            Node node = queue.poll();
            // 进行连接，当 i 小于 size - 1 时进行连接
            // 即这一层的最后一个元素的 next 应该为空
            if (i < size - 1) {
                node.next = queue.peek();
            }
            // 将它的左右节点加入到队列中
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return root;
}

16、买卖股票的最佳时机 I

16.1、题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

  • 示例一
1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
  • 示例二
1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

16.2、解题思路

  • 如果拥有的股票必须在 i 时间段卖出，那么在 min{nums[0:i]} 时段买入利润最大
  • 遍历数组，在每一个位置根据上面的规则求出在 i 位置能获取利润的最大值，然后在这些最大值中再求一个最大值，就得到了我们想要的答案

16.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) return 0;
    // nums[0:i] 这一段上的最小值，初始化为 0 
    int min = prices[0];
    int result = 0;
    for (int i = 0; i < prices.length; i++) {
        // 获取数组 [0:i] 这一段数据的最小值
        min = Math.min(min, prices[i]);
        // 使用当前卖出价格 - [0:i] 上的最小值
        // 就得到了在当前位置所能获取的最大利润
        result = Math.max(result, prices[i] - min);
    }
    return result;
}

17、买卖股票的最佳时机 II

17.1、题目描述

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

  • 示例 1:
1
2
3
4
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
  • 示例 2:
1
2
3
4
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

17.2、解题思路

  • 对于所有 i ，如果 prices[i] > prices[i - 1] ，那么将 prices[i] - prices[i - 1] 的值累加到 result 中

因为此时可以进行无数次交易，因为如果满足 prices[i] > prices[i - 1] ，那么证明在 i - 1 位置买入，在 i 位置卖出有利可图，所以我们只需要将每一个位置的利润都累加起来，就可以得到最终利润。

17.3、解题代码

1
2
3
4
5
6
7
8
9
10
public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) return 0;
    int result = 0;
    for (int i = 1;i < prices.length;i++) {
        if (prices[i - 1] < prices[i]) {
            result += prices[i] - prices[i - 1];
        }
    }
    return result;
}

18、买卖股票的最佳时机 III

18.1、题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

18.2、解题思路

  • 在 i 位置卖出第二支股票，如何在 i 位置卖出第二支股票时，获得最大收益？

我们需要考虑两个条件，即在 [0,i - 1] 位置中卖出第一支股票时，获得最大利润，同时在卖出后以一个最有利的低价买进第二支股票。

  1. 在 [0, i - 1] 选择一个合适的卖出时机 x ，在 x 卖出第一支股票时，获得利润 a
  2. 在 [x + 1,i - 1] 中选择一个合适的买入时机以价格 b 买入第二支股票

我们要求 a - b 最大

  • 此时在 i 位置卖出第二支股票，能得到的全局收益就为上一步中获取的 Max(a - b) 与当前位置股票价格的和

18.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int maxProfit(int[] prices) {
    // 如果数组长度小于 2 ，那么直接返回 0 即可
    // 当数组只存在一个元素时，那么此时两次买入，两次卖出的时机都在 0 位置
    if (prices == null || prices.length < 2) return 0;
    // 结果
    int result = 0;
    // 这个变量表示第一次卖出，同时买入第二支股票后得到的利润最大值
    // 设第一次卖出后赚得的利润为 a ，第二次买入时花费的钱为 b
    // 那么这个变量的意义就是 max(a - b)
    int firstDoneMinusBuyMax = -prices[0];
    // 卖出第一支股票获取的最大收益
    int firstDoneMax = 0;
    int min = prices[0];
    for (int i = 1; i < prices.length; i++) {
        // 0 - i 位置的价格最小值
        min = Math.min(min, prices[i]);
        // 第一次卖出股票且第二次买入股票后获取的纯利润 + 当前 i 位置卖出的价格，就是两次交易的利润总和
        // 拿这个数和 result 对比
        result = Math.max(result, firstDoneMinusBuyMax + prices[i]);
        firstDoneMax = Math.max(firstDoneMax, prices[i] - min);
        firstDoneMinusBuyMax = Math.max(firstDoneMinusBuyMax, firstDoneMax - prices[i]);
    }
    return result;
}

19、二叉树的最大路径和

19.1、题目描述

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

  • 示例一

img

1
2
3
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
  • 示例二

img

1
2
3
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

19.2、解题思路

  • 对于一棵以 x 节点为头节点的树（x 不一定为整棵树的根节点，可以是某棵子树的根节点），它的最大路径和可能存在以下几种可能性

  • 它的最大路径和与 x 节点无关，此时它的最大路径和是 x 节点内某一棵更小的子树的最大路径和

比如，在示例二中的树中，以 -10 为根节点的树它的最大路径和与 -10 无关，而是它的一棵子树（以 20 为根节点的子树）的最大路径和

此时结果为该节点左子树最大路径和与右子树最大路径和中的最大值，即 maxPath(root) = Math.max {maxPath(root.left), maxPath(root.right)}

  • 它的最大路径与 x 节点有关，此时yi x 为根节点的树的最大路径和有以下几种可能性
  1. x 节点的最大路径和只包括 x 节点的值
  2. x 节点的最大路径和包括 x 节点，我们记 x 节点的值为 a ，同时在以 x.left 为出发点的前提下，设 x.left 的最大路径和 b ，这个可能性下的值为 a + b
  3. x 节点的最大路径和包括 x 节点，我们记 x 节点的值为 c，同时在以 x.right 为出发点的前提下，设 x.right 的最大路径和 d ，这个可能性下的值为 c + d
  4. 最后一种可能性，即上面两种可能的性的总和，此时最大路径和经过 x 节点同时与 x 的左右节点均关联。
  • 根据递归套路，我们需要向子树要什么信息？
  1. 不要求从 x 出发时，子树 x 的最大路径和，在这个条件下，最大路径不必从 x 节点出发
  2. 要求从 x 出发时，子树 x 的最大路径和， 这个条件下，最大路径和中必须从 x 出发

比如在示例二的右子树中，如果要求从 20 出发，那么最大路径和为 20 + 15 ；如果不要求从 20 出发，那么最大路径和为 15 + 20 + 7

img

19.3、解题代码

  • 创建一个类，用于封装左右子树返回的数据
1
2
3
4
5
6
7
8
public static class Info {
    public int maxPathSum;
    public int maxPathSumContainHead;
    public Info(int path, int head) {
        maxPathSum = path;
        maxPathSumContainHead = head;
    }
}
  • 递归过程
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
28
29
30
31
32
33
34
public int maxPathSum(TreeNode root) {
    if (root == null) return 0;
    // 只需要返回最大路径和信息即可，不要求一定以 root 为出发点
    return process(root).maxPathSum;
}
public Info process(TreeNode root) {
    if (root == null) return null;
    // 分别向左向右获取信息
    Info leftInfo = process(root.left);
    Info rightInfo = process(root.right);
    //1 可能性 1 ，结果为左树的最大路径和（这个最大路径和不包括左子树的根节点）
    int firstCase = Integer.MIN_VALUE;
    if (leftInfo != null) firstCase = leftInfo.maxPathSum;
    //2 可能性 2 ，同上，但结果为右子树
    int secondCase = Integer.MIN_VALUE;
    if (rightInfo != null) secondCase = rightInfo.maxPathSum;
    //3 可能性 3 ，最大路径只包括 root 自己
    int thirdCase = root.val;
    //4 可能性 4 ，此时与 root 节点有关，root.val + 必须以 root.left 出发的最大路径和
    int fourthCase = Integer.MIN_VALUE;
    if (leftInfo != null) fourthCase = root.val + leftInfo.maxPathSumFromHead;
    //5 可能性 5 ，此时与 root 节点有关，和上一个可能性类似，但是向右
    int fifthCase = Integer.MIN_VALUE;
    if (rightInfo != null) fifthCase = root.val + rightInfo.maxPathSumFromHead;
    // 可能性 6 ，前面两种情况的集合
    int sixthCase = Integer.MIN_VALUE;
    if (leftInfo != null && rightInfo != null) sixthCase = root.val + leftInfo.maxPathSumFromHead + rightInfo.maxPathSumFromHead;
    int maxSum = Math.max(Math.max(Math.max(firstCase, secondCase), Math.max(thirdCase, fourthCase)), Math.max(fifthCase, sixthCase));
    // 必须为 root 为开头的最大路径和怎么求？
    // 只包含 root 、包含 root 同时只往左子树深入(fourthCase)、包含 root 同时只往右子树深入(fifthCase)
    // 上面三个值求一个最大值
    int maxSumFromHead = Math.max(thirdCase, Math.max(fourthCase, fifthCase));
    return new Info(maxSum, maxSumFromHead);
}

20、验证回文串

20.1、题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

  • 示例一
1
2
3
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
  • 示例二
1
2
3
输入: "race a car"
输出: false
解释："raceacar" 不是回文串

20.2、解题思路

  • 使用双指针求解，左指针从下标 0 位置开始，右指针从下标 s.length() - 1 位置开始
  • 只有当左右指针指向的值为有效字符时，才进行比较，循环时，左指针向右移，右指针向左移

20.3、解题代码

  • 方法一，判断字符为有效字母或者有效数字的方法
1
2
3
4
5
6
7
8
9
10
11
public boolean isValidChar(char ch) {
    return isLetter(ch) || isNumber(ch);
}

private boolean isNumber(char ch) {
    return ch >= '0' && ch <= '9';
}

public boolean isLetter(char ch) {
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
  • 方法二，判断两个字符是否相等的方法
1
2
3
4
5
6
public boolean equals(char ch1, char ch2) {
    if (isNumber(ch1) || isNumber(ch2)) {
        return ch1 == ch2;
    }
    return (ch1 == ch2) || (Math.max(ch1, ch2) - Math.min(ch1, ch2) == 32);
}
  • 判断字符串是否为回文串的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isPalindrome(String s) {
    if (s == null || s.length() == 0) return true;
    int left = 0, right = s.length() - 1;
    char[] charArray = s.toCharArray();
    while (left < right) {
        if (isValidChar(charArray[left]) && isValidChar(charArray[right])) {
            if (!equals(charArray[left], charArray[right])) {
                return false;
            }
            left++;
            right--;
        } else {
            left += isValidChar(charArray[left]) ? 0 : 1;
            right -= isValidChar(charArray[right]) ? 0 : 1;
        }
    }
    return true;
}

21、单词接龙

21.1、题目描述

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

  • 序列中第一个单词是 beginWord 。
  • 序列中最后一个单词是 endWord 。
  • 每次转换只能改变一个字母。
  • 转换过程中的中间单词必须是字典 wordList 中的单词。

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

  • 示例一
1
2
3
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
  • 示例二
1
2
3
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

21.2、解题思路

  • 我们以 startWord 为基准，构造一个字典，字典中存放与 startWord 只有一字之差的字符串，我们将这些字符串称为 startWord 的下一层
  • 以 startWord 下一层的元素为基准，分别构造它们各自的下一层元素，然后逐层构建下去
  • 当 endWord 在字典中首次出现时，我们就找到了一条最短路径

如何创建这个字典？我们假设所有的词都只有小写字母

  1. 先将所有字符串都放在一个 HashSet 对象中
  2. 遍历基准词中的每一个字符，对它的每一次字符都进行一次变化，然后判断这个变化后的词在不在 HashSet 对象中

假设当前基准词为 abc ，那么我们先对 a 进行变化，变为 bbc ，cbc … zbc ，然后每变化一次，判断变化后的词是否在 HashSet 中

同理，将 abc 中的第二个字符进行变化，判断 aac … azc 是否在 HashSet 中，最后变化 c ，比较判断

  1. 在上一步变化判断的过程中，如果发现有变化后的字符串在 set 中（要求不和原始字符串相同），那么就将当前变化后的字符串加入到该基准词的下一层元素中。
  • 同理，可以从 endWord 逐步向上推，在字典第一次出现 startWord 时，也找到了最短路径，所以我们可以这样进行优化

假设从 startWord 向下推时，发现它的字典中含有 n 个字符串，而从 endWord 向上推时，发现它的字典中含有 m 个字符串，而 n > m ，那么我们此时从 endWord 向上推，如果 n < m ，那么从 startWord 向下推。

每次都选择发散小的路走，可以少走一点弯路。

22、最长连续序列

22.1、题目描述

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

  • 示例 1：
1
2
3
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
  • 示例 2：
1
2
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

22.2、解题思路

  • 使用两张哈希表完成这道题，其中一张为头表（存放连续区间的头），一张为尾表（存放连续区间的尾）

以数组 {100,1,200,3,4,0,2} 为例

  1. 遍历到 100 时，由于 100 可以单独作为一个区间，所以在头表中插入键值对 100 - 1 ，表示以 100 作为连续区间头的区间当前只有一个数，同时在未表中插入键值对 100 - 1 ，表示以 100 作为连续区间尾的区间当前只有一个数

  2. 在尾表中查询有没有以 99 作为结尾的区间，发现没有，所以什么都不做；

  3. 在头表中查询有没有以 101 作为头部的区间，发现没有，所以什么都不做；

  4. 遍历到 1 ，同理在头尾表中插入 {1 - 1} ， 此时发现尾表中没有以 0 结尾的区间、在头表中没有以 2 为开头的区间，所以什么都不做

  5. 同理，200、3也是这样，加入头尾表后不做修改

  6. 遍历到 4 ，此时将 4 - 1 作为键值对插入头尾表中，然后遍历头表，发现此时没有以 5 作为开头的数据，所以什么都不做，遍历尾表，发现确实有以 3 作为结尾的序列，且序列长度为 1 ，现在我们需要将 3 -> 3 序列变为 3 -> 4 序列

将以 3 作为结尾的记录从尾表中删除，将以 4 作为开头的记录从头表中删除，同时修改头表中的记录，将 3 开头的序列长度从 1 改为 2 ，即头表中元素变为 { 3- 2}，同理尾表中记录也变为 {4 - 2}

  1. …
  • 使用 HashSet 解决这个问题，先将给的数组所有元素加入到 HashSet 中

对于一个连续序列，它一定存在一个左边界，如果一个序列以 num 作为左边界，那么 num - 1 就不应该存在与 HashSet 中；

因此，如果对于一个 num ，满足 num - 1 不在 HashSet 中，那么这个 num 就可以作为连续序列的左边界。

  1. 将数组中的所有元素加入到一个 HashSet 中
  2. 遍历数组，对于每一个元素 num ，进行判断，如果

num - 1 存在于 HashSet 中，那么 num 不可能作为连续序列的左边界，直接跳过遍历下一个即可；

num - 1 不存在于 HashSet 中，那么 num 会是一个左边界，我们再不断查找 num + 1、num + 2 … 是否存在于 HashSet 中，来看以 num 作为左边界的连续序列有多长

  1. 遍历后，我们就知道了对于每一个可能的左边界，所括出的最长连续序列的长度，再在这些长度中取最大值即可

22.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    // 将所有元素加入到集合中
    for (int num : nums) {
        set.add(num);
    }
    int maxLen = 0;
    for (int num : nums) {
        if (set.contains(num - 1)) {
            continue;
        } else {
            // 记录以 num 为左边界能括出的连续序列的最大长度
            int len = 0;
            while (set.contains(num)) {
                len++;
                num++;
            }
            // 将以 num 为左边界能括出的连续序列的最大长度的值与全局最大长度的值做对比，取大的
            maxLen = Math.max(maxLen, len);
        }
    }
    return maxLen;
}

23、单词拆分

23.1、题目描述

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

  • 说明
  1. 拆分时可以重复使用字典中的单词。
  2. 你可以假设字典中没有重复的单词。
  • 示例 1：
1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
  • 示例 2：
1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

23.2、解题思路

  • 查询要分解的 s 在字典表中能否找到一个前缀，以示例二为例，查询以 a 字符串作为前缀，发现字典表中没有 a 这个字符串，所以不可以以 a 作为前缀，同理 ap … appl 也不都可以作为前缀
  • 查询 s 字符串是否能以 apple 作为前缀，此时发现 apple 存在于字典中，所以可以以 apple 作为前缀，此时问题转换为以求 s 中除去前缀之外的部分 penapple 能否被拆分的问题
  • 将字符串所有的前缀枚举出来，然后在 s 中一次剔除这些前缀，问题就转换为了剩下字符串的拆分问题，最后将这些前缀的可能性都加起来，就得到了 s 字符串的所有拆分情况，问题就得到了解决。

23.3、解题代码

  • 优化前的代码
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
28
29
30
31
32
public boolean wordBreak(String s, List<String> wordDict) {
    return process(s, 0, wordDict) > 0;
}

/**
 * 字符串中下标范围为 [index, s.length() - 1] 的部分，能够被 wordDict 分解的方法数
 * @param s
 * @param index
 * @param wordDict
 * @return
 */
public int process(String s, int index, List<String> wordDict) {
    // 当 index 到达字符串最后时，证明已经找到了一种合理的分解方法，此时返回 1
    if (index == s.length()) {
        return 1;
    }
    int ways = 0;
    // index 还没到最后
    // 找前缀，先找 index 这个单字符字符串能否作为前缀
    // 如果不行，那么就 index++ ，判断 [index,index + 1] 这个字符串能否作为前缀
    // 以此类推...，这个循环就是判断范围为 [index,end] 的字符串能否作为前缀
    for (int end = index; end < s.length();end++) {
        // 根据范围获取子串
        String pre = s.substring(index, end + 1);
        // 如果字典中含有这个子串，那么证明可以作为前缀
        if (wordDict.contains(pre)) {
            // 如果这个子串可以作为前缀，那么需要判断剔除这个子串，字符串后面的串能否被 wordDict 成功分解
            ways += process(s, end + 1, wordDict);
        }
    }
    return ways;
}
  • 优化后的代码
  1. 将 List 换为 Set ，加快查重速度
  2. 将递归改为动态规划

在原来的递归参数中，只有一个参数是变化的，我们构造一个一维数组 dp[i] ，dp[i] 表示从下标 i 开始，字符串可以被 wordDict 中的字符串分解的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> set = new HashSet<>(wordDict);
    // 记录字符串的长度
    int size = s.length();
    // 创建一个 dp 数组，dp[i] 表示字符串 s 从下标 index 后的子串能被分解的次数
    int[] dp = new int[size + 1];
    // base case：如果走到字符串末尾，那么就得到了一种分解方法
    // 所以初始化 dp[size] = 1
    dp[size] = 1;
    // dp数组中，前一个下标的值可以从后一个下标的值中推出
    for (int index = size - 1;index >= 0;index--) {
        int ways = 0;
        for (int end = index;end < s.length();end++) {
            // 获取子串
            String pre = s.substring(index, end + 1);
            if (set.contains(pre)) {
                ways += dp[end + 1];
            }
        }
        dp[index] = ways;
    }
    // dp[0] 表示字符串 s 从下标 0 开始，能被 wordDict 分解的次数，如果这个值大于0 ，那么证明可以被分解
    return dp[0] > 0;
}

24、寻找峰值

24.1、题目描述

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

  • 示例 1：

    1
    2
    3
    输入：nums = [1,2,3,1]
    输出：2
    解释：3 是峰值元素，你的函数应该返回其索引 2。

  • 示例 2：

    1
    2
    3
    输入：nums = [1,2,1,3,5,6,4]
    输出：1 或 5 
    解释：你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5， 其峰值元素为 6。

24.2、解题思路

  • 如果 nums[0] > nums[1] ，那么返回 0 ，因为 nums[-1] 为负无穷
  • 如果 nums[nums.length - 1] > nums[nums.length - 2] ，那么返回 0 ，因为 nums[nums.length] 为负无穷
  • 如果上面的条件均不满足，那么证明此时 nums[0] < nums[1] 且 nums[nums.length - 2] > nums[nums.length - 1]

从 0 –> 1 ，呈现向上的趋势，而从倒数第二个到最后一个元素，呈下降的趋势，那么证明在数组中间必定存在一个拐点 M ，使得在 M 左边的元素小于 M 元素，而 M 右边的元素也小于 M 元素，这个 M 元素所在下标就是我们要找的值

  • 使用二分查找，找到中间下标 mid 时，判断是否满足以下条件，即 nums[mid] > nums[mid - 1] && nums[mid] < nums[mid + 1]，如果满足，直接返回 mid 即可
  • 如果不满足以上条件，此时 nums[mid - 1] > nums[mid] ，那么由于在 mid - 1 –> mid 之间呈现向下趋势，而 0 -> 1 呈现向上趋势，那么 1 –> mid - 1 之间一定存在一个拐点
  • 如果 nums[mid] < nums[mid + 1]，那么可以往右侧二分；
  • 如果两个条件均满足，那么往左右二分都可以

24.3、解题代码

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
28
29
public int findPeakElement(int[] nums) {
    int size = nums.length;
    if (size < 2) {
        // 只有一个元素时，直接返回 0 即可
        // 因为 nums[-1] 和 nums[2] 默认为负无穷
        return 0;
    }
    if (nums[0] > nums[1]) {
        return 0;
    }
    if (nums[size - 2] < nums[size - 1]) {
        return size - 1;
    }
    // 进行二分，对 [1, size - 2] 返回进行二分
    int left = 1;
    int right = size - 2;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
            return mid;
        } else if (nums[mid] < nums[mid - 1]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // 将唯一剩下的元素下标返回
    return left;
}

25、多数元素

25.1、题目描述

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

25.2、解题思路

  • 在这道题中，数组一定有一个数出现的次数大于 N / 2；
  • 一次在数组中删掉两个不同的数，当数组删无可删时，剩下的数就是要求的数
  • 使用一个 target 变量来表示靶子，用一个 hp 变量来表示靶子的血量，遍历数组
  1. 遍历到一个元素时，查看当前是否存在靶子，如果不存在，那么将当前的元素立为靶子，然后为这个靶子添加一点 hp
  2. 继续遍历，判断当前的元素是否和靶子相同，如果相同，那么让靶子血量 + 1
  3. 继续遍历，如果当前元素与靶子不同，那么将当前元素删除，同时将当前靶子的 hp - 1
  4. 最后剩下的数就是那个多数元素

25.3、解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int majorityElement(int[] nums) {
    // 靶子变量
    int target = 0;
    // 靶子血量
    int hp = 0;
    for (int num : nums) {
        if (hp == 0) {
            // 如果当前靶子的 hp 为 0 ，那么证明不存在靶子
            target = num;
            hp = 1;
        } else if (num == target) {
            hp++;
        } else {
            hp--;
        }
    }
    // 返回靶子
    return target;
}

26、逆波兰表达式求值

26.1、题目描述

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

  • 整数除法只保留整数部分。
  • 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
  1. 示例一
1
2
3
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

26.2、解题思路

  • 创建一个栈，然后遍历字符数组，如果遇到的是一个数字，那么直接压入栈中，如果是符号，那么从栈中弹出两个数，进行运算，然后将结果压入栈中，遍历完成后，最后还留在栈中的元素就是结果

对于减法和除法，需要用后弹出的数减去/除以 先弹出的数

26.3、解题代码

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
28
29
30
31
32
33
public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    for (String token : tokens) {
        if ("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token)) {
            // 从栈中弹出两个数进行运算
            compute(stack, token);
        } else {
            stack.push(Integer.valueOf(token));
        }
    }
    return stack.peek();
}

private void compute(Stack<Integer> stack, String token) {
    int pre = stack.pop();
    int next = stack.pop();
    int res = 0;
    switch (token) {
        case "+":
            res = pre + next;
            break;
        case "-":
            res = next - pre;
            break;
        case "*":
            res = next * pre;
            break;
        case "/":
            res = next / pre;
            break;
    }
    stack.push(res);
}