算法入门详解

---

算法入门

当我们谈论算法时，我们谈论的是解决问题的方法和步骤。在计算机科学中，算法是一系列明确定义的指令，用于执行特定任务或解决特定问题。算法在各个领域都起着至关重要的作用，从数据处理到人工智能，无处不在。

---

一、算法简介

1.1 什么是算法

算法可以被视为一种计算过程，通过一系列有序的步骤来执行特定的任务。它是一种数学概念，通常由一组输入、输出和执行步骤组成。一个好的算法应该是正确的、高效的，并且适用于特定问题。

1.2 算法的特性

• 明确定义： 算法应该具有明确的步骤，对于任何给定的输入，都应该产生确定的输出。
• 有限性： 算法必须在有限步骤内结束，不会无限循环或无法终止。
• 输入： 算法可以有零个或多个输入，这些输入是用来执行特定任务的数据。
• 输出： 算法应该产生一个或多个输出，以表示完成任务的结果。

1.3 算法的度量指标

• 时间复杂性： 衡量算法执行所需时间的指标，通常用大O表示法来表示。较低的时间复杂性通常意味着更高的性能。O(f(n))：n为问题的规模，f(n)为执行次数的系数为1的最小阶，O(f(n))表示时间复杂度。
• 空间复杂性： 衡量算法在执行过程中所需内存空间的指标。与时间复杂性类似，我们希望尽量减少算法的空间占用。表示与世界复杂度一样。

二、常用算法

2.1 递归算法

2.1.1 什么是递归算法

递归是一种通过在算法的执行过程中自我调用的方式来解决问题的方法。在递归算法中，问题被分解为更小的子问题，并通过递归调用相同的算法来解决这些子问题。递归算法通常通过定义一个或多个基本情况（边界条件）来终止递归过程。

这样描述可能有点抽象，下面通过几道例题进行加深你的理解。

2.1.2 递归的适用场景

递归算法适用于：

• 问题可以被分解为更小的子问题进行求解的场景

一些常见的应用场景包括：

• 树的遍历： 二叉树的前序、中序和后序遍历就是递归算法的经典示例。
• 图的搜索： 图的深度优先搜索（DFS）和广度优先搜索（BFS）都可以使用递归算法实现。
• 动态规划： 在动态规划问题中，递归算法通常被用来定义子问题的状态转移方程。
• 分治算法： 分治算法将问题拆分为更小的子问题，通常通过递归算法来解决。
• 回溯算法： 在回溯算法中，递归算法用于在解空间中搜索所有可能的解。

2.1.3 递归模板

void func() {
	if (true) { // 递归结束条件
		return // 递归出口
	}
	func(); // 调用自身
}

1
2
3
4
5
6
7

2.1.3 递归详解

• 递归其实是一个相同方法栈，只不过方法的参数不一样
• 最开始进来的方法压在栈底，接着不断调用自身，即往栈中不断加入方法。
• 直到遇到递归出口时，最上面的方法从栈中弹出，然后进行上一个方法的计算，重复执行，直到栈为空。

请看以下例题加深理解。

2.1.3.1 剑指offer.6 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]
1
2

分析：

• 从尾到头进行遍历，必须要找到尾结点，但是尾节点并没有指向上一个节点的指针，所以需要保存所有节点的指针，或者将链表反转再进行遍历。

则我们有以下解决方案：

1. 将指针/数据存到一个数组/栈中，然后遍历数组/栈。时间复杂度O(n）, 空间复杂度O(n）。且需要遍历两次。
2. 将链表反转再进行遍历，时间复杂度O(n）, 空间复杂度O(1)，但需要遍历两次。
3. 利用递归性质，时间复杂度O(n）, 方法空间复杂度O(1)，栈空间复杂度O(n)。

如何用递归性质：

• 每次打印过程是一样的（最小子问题）。
• 需要保存所有节点的指针，递归方法栈自动帮我们存储。
• 从尾到头打印，尾部即是栈顶。

递归解法：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private int[] res; // 结果数组
    public int[] reversePrint(ListNode head) {
        int len = 0;  // 链表长度
        func(head, len); // 递归
        return res;
    }
    private void func(ListNode head, int len) {
        if (head == null) {
            res = new int[len]; // 在递归出口初始化结果数组，因为在这才直到链表的长度。
            return;
        }
        // 最小子问题
        len ++; // 每递归一次长度加1
        func(head.next, len);
        res[res.length-len] = head.val;
    }
}
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

2.1.3.2 DFS深度优先算法-树的遍历

DFS深度优先算法是树的常用遍历算法，由于树是高度递归的，所以DFS深度优先算法常用递归来实现，也可以使用栈来实现深度优先算法。

这里可以让你更加明白为啥递归是一个隐式方法栈。

DFS深度优先算法模板-递归实现：

// 先序遍历
public static void dfSPre(Node treeNode) {
    if (treeNode == null) {
        return;
    }
    // 遍历节点
    process(treeNode)
    // 遍历左节点
    dfSPre(treeNode.left);
    // 遍历右节点
    dfSPre(treeNode.right);
}
// 后序遍历
public static void dfSPost(Node treeNode) {
    if (treeNode == null) {
        return;
    }
    // 遍历左节点
    dfSPost(treeNode.left);
    // 遍历右节点
    dfSPost(treeNode.right);
    // 遍历节点
    process(treeNode)
}
// 中序遍历
public static void dfSInner(Node treeNode) {
    if (treeNode == null) {
        return;
    }
    // 遍历左节点
    dfSInner(treeNode.left);
    // 遍历节点
    dfSInner(treeNode)
    // 遍历右节点
    dfSInner(treeNode.right);
}
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

DFS深度优先算法模板-非递归实现：

/**
 * 使用栈来实现 dfs
 * @param root
 */
public static void dfsWithStack(Node root) {
    if (root == null) {
        return;
    }

    Stack<Node> stack = new Stack<>();
    // 先把根节点压栈
    stack.push(root);
    while (!stack.isEmpty()) {
        Node treeNode = stack.pop();
        // 遍历节点
        process(treeNode)

        // 先压右节点
        if (treeNode.right != null) {
            stack.push(treeNode.right);
        }

        // 再压左节点
        if (treeNode.left != null) {
            stack.push(treeNode.left);
        }
    }
}
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

补充：BFS

/**
 * 使用队列实现 bfs
 * @param root
 */
private static void bfs(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> stack = new LinkedList<>();
    stack.add(root); //根结点入队

    while (!stack.isEmpty()) {
        Node node = stack.poll(); // 头结点出队
        System.out.println("value = " + node.value); // 对结点的操作
        Node left = node.left;
        if (left != null) { // 头结点的左子树入队
            stack.add(left);
        }
        Node right = node.right;
        if (right != null) { // 头结点的右子树入队
            stack.add(right);
        }
    }
}

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

树的高度递归体现在：

• 对于一棵树，可分为若干个子问题，**该子问题为：**对于根结点的处理，递归到左子树进行处理，递归到右子树进行处理。
• 因此在处理树的问题且带有递归性质时，都是基于以上的思想去解决的。

2.1.3.3 leetcod 437. 路径总和 III - 路径问题通解

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
1
2
3

分析，利用树的高度递归性：

• 对于一棵树，可分为若干个子问题，**该子问题为：对于根结点的处理，递归到左子树进行处理，递归到右子树进行处理
• 对于路径问题，我们需要记录之前路径的值。

其子问题简化为：

1. 以当前结点为父结点
2. 对左子树进行处理，计算左子树某条路径的值和加上父节点的值是否等于taget。
3. 对右子树进行处理，计算右子树某天路径的值和加上父节点的值是否等于taget

代码实现：

// 双递归解法，pathSum用于当前节点的遍历，func获取该结点路径。
class Solution {

    private int res;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        func(root, (double) targetSum);
        pathSum(root.left, targetSum); 
        pathSum(root.right, targetSum);
        return res;
    }
	// 先序遍历获取从根到叶节点的路径。
    private void func(TreeNode root, double targetSum) {
        if (root == null) { // 递归出口
            return;
        }
        if (targetSum-(double) root.val == 0) res++; // 根节点处理
        func(root.left, targetSum-root.val); // 递归到左子树处理
        func(root.right, targetSum-root.val); // 递归到右子树处理
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

值得注意的是，递归算法性能大多数时候是极差的。leetcod 437. 路径总和 III 解析，当我们以10为根结点向下遍历时，5->3,5->2的信息我们已经计算过了，然而在递归到以10为根结点时，我们又计算了一遍，因此递归带来的时很多的重复计算的问题，且由于隐式栈的原因，很难进行优化，所以性能极差，因此在实际开发中不要应避免使用递归算法（递归算法可用栈来替代）。

2.1.3.4 leetcode 70. 爬楼梯-动态规划入门

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
 - 1 阶 + 1 阶 + 1 阶
 - 1 阶 + 2 阶
 - 2 阶 + 1 阶
1
2
3
4
5
6

分析：

• 每次只能爬 1 或 2 个台阶，则 在 第 n 层 只能由 n-2 层 或者 n-1 层跳过来 ，同理 n-1 层也是一样。那么就可以得到最小子问题。
• 最小子问题：对于 第 n 阶 的 爬到 楼梯的方法 等于 n-2 阶 与 n-1阶 的方法之和。即f(n)=f(n-1)+f(n-2)。

代码解：

// 递归方式
class Solution {
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (hashMap.get(n) != null) {
            return hashMap.get(n);
        }else{
            int data = climbStairs(n-1) + climbStairs(n-2);
            hashMap.put(n, data); // 将之前算过的值存储起来，避免重复计算
            return data;
        }
    }
}

// 动态规划方式：数据可拆解为最小子问题，且当前数据可以从之前已经计算过的数据中得到。
class Solution {
public:
    int climbStairs(int n) {
        int dp[n+1];
        if (n<=1) return 1;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<n+1;i++){
            dp[i]=dp[i-1]+dp[i-2]; // dp[i]为当前数据
        }
        return dp[n];
    }
};

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

2.2 分治算法

2.121 什么是分治算法

分治法的设计思想：

• 将难以直接解决的大问题分解成一些规模较小的相同问题，请注意这个相同，以便与动态规划进行区别使用。

分治算法的基本步骤：

1. 分解（Divide）：将原始问题分解为多个相同或相似的子问题。这一步通常涉及将问题划分成更小的规模，以便于处理。
2. 解决（Conquer）：逐个解决每个子问题。对于小规模的子问题，可以直接求解。
3. 合并（Combine）：将各个子问题的解合并，得出原始问题的解。这一步确保子问题的解能够有效地组合成原始问题的解。

2.2.2 分治算法的适用场景

分治算法适用于：

• 问题可以被分解为更小的相同或相似的子问题进行求解的场景

一些常见的应用场景包括：

• 归并排序（Merge Sort）：归并排序是一种经典的排序算法，它利用了分治思想。该算法将一个大的排序问题分解为多个小的排序子问题，分别解决后再将它们合并起来，得到整体有序的结果。
• 快速排序（Quick Sort）：快速排序也是一种常见的排序算法，同样基于分治思想。它通过选取一个基准元素，将数组划分为两个子数组，然后分别对这两个子数组进行排序，最终得到有序结果。
• 最大子数组和问题：这个问题要求在一个整数数组中找到一个连续的子数组，使得子数组的元素和最大。分治算法可以将问题分解为三种情况：最大子数组在左边、最大子数组在右边，或者跨越了数组中点。然后，将这三种情况的解合并，得到全局最优解。

2.2.3 分治算法模板

1

2.2.4 分治算法详解

2.2.4.1 归并排序

public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    merge_sort_recursive(arr, result, 0, len - 1);
}

static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start; // 中间结点
    int start1 = start, end1 = mid; // 划分左边
    int start2 = mid + 1, end2 = end; // 划分
    merge_sort_recursive(arr, result, start1, end1); // 递归的对左边划分
    merge_sort_recursive(arr, result, start2, end2); // 递归的对右边划分
    // 最小规模数据处理
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        result[k++] = arr[start1++];
    while (start2 <= end2)
        result[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = result[k];
}
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

2.2.4.2 快速排序

快排思想：

• 以第一个元素为中枢，中枢左边元素要小于中枢，中枢右边元素要大于中枢。
• 使用双指针，low指针遇到第一个大于中枢值则停止，hign指针遇到第一个小于中枢值则停止，交换两者位置，之后继续遍历，直到low >= hign。
• 递归左右两边。

class quick_sort {
    int[] arr;
    // 交换函数
    private void swap(int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
    private void quick_sort_recursive(int start, int end) {
    	// 最小规模数据处理
        if (start >= end)
            return;
        int mid = arr[end];
        int left = start, right = end - 1;
        while (left < right) {
            while (arr[left] <= mid && left < right)
                left++;
            while (arr[right] >= mid && left < right)
                right--;
            swap(left, right);
        }
        if (arr[left] >= arr[end])
            swap(left, end);
        else
            left++;
        quick_sort_recursive(start, left - 1); // 递归的对左边划分
        quick_sort_recursive(left + 1, end); // 递归的对右边划分
    }
    public void sort(int[] arrin) {
        arr = arrin;
        quick_sort_recursive(0, arr.length - 1);
    }
}
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

2.2.4.3 leetcode 53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
1
2
3
4
5

分治策略：

1. 分解，将序列A[1…N]分成长度相等的两段，A[1…N/2]和A[N/2+1…n]，分别求这两段最大字段和。
2. 解决
3. 合并

分治解法代码：

public class Solution {

    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        return maxSubArraySum(nums, 0, len - 1);
    }

    private int maxCrossingSum(int[] nums, int left, int mid, int right) {
        // 一定会包含 nums[mid] 这个元素
        int sum = 0;
        int leftSum = Integer.MIN_VALUE;
        // 左半边包含 nums[mid] 元素，最多可以到什么地方
        // 走到最边界，看看最值是什么
        // 计算以 mid 结尾的最大的子数组的和
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }
        sum = 0;
        int rightSum = Integer.MIN_VALUE;
        // 右半边不包含 nums[mid] 元素，最多可以到什么地方
        // 计算以 mid+1 开始的最大的子数组的和
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
    }

    private int maxSubArraySum(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        return max3(maxSubArraySum(nums, left, mid),
                maxSubArraySum(nums, mid + 1, right),
                maxCrossingSum(nums, left, mid, right));
    }

    private int max3(int num1, int num2, int num3) {
        return Math.max(num1, Math.max(num2, num3));
    }
}
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

分治解法思路比较简单，但是会经常存在重复计算与合并操作复杂的问题，因此在一些特定问题上，可以采用动态规划的方式进行处理，往往可以用分治法解决的，都可以使用动态规划进行解决，而分治的核心在于最小子问题的思想，往往配合其他算法使用。

2.3 动态规划算法

2.3.1 什么是动态规划算法

动态规划算法是一种常用的问题解决方法。它通过将问题分解为更小的子问题，并保存子问题的解，以避免重复计算。与分治法不同的是，动态规划算法的子问题往往是不相同的且有关联的。

动态规划的核心在于：

• 现在的问题由过去求解，分析当前解是如何从过去的解中得到的，即从问题中得到递推式。
• 使用一个表来记录所有已解决的子问题的答案，不管他以后是否被用到，只要他被计算过，就将其结果记录表中。
• 明确dp[i][j]所指的含义

这样描述可能有点抽象，下面通过几道例题进行加深你的理解。

2.3.2 动态规划的适用场景

动态规划适用于：

• 问题可以被分解为更小的子问题进行求解的场景

一些常见的应用场景包括：

• 背包问题： 给定一组物品和一个背包，每个物品有自己的重量和价值，要求选择一些物品放入背包，使得背包中物品的总价值最大。动态规划算法可以帮助我们解决这个问题，通过构建一个价值表格，在每个状态下选择最优的决策。
• 最长公共子序列问题： 给定两个字符串，找到它们之间最长的共同子序列的长度。通过构建一个二维表格，依次计算每个子问题的最长公共子序列长度，并保存在表格中。
• 最优路径规划： 在一个网格中，从起点到终点，要求找到路径的总和最小或者最大的路径。动态规划算法可以通过构建一个二维表格，依次计算每个子问题的解，并保存在表格中，最终得到最优路径。

2.3.3 动态规划模板

// 对于递推式f(n) = f(n-1) + f(n-2)
void func(int[] nums) {
	int[] dp = new int[nums.length];
	dp[0] = 0; // 边界条件
	dp[1] = 1; // 边界条件
	for (int i=3; i< dp.length; i++) {
		dp[i] = dp[i-1] + dp[i-2];
	}
	return dp[nums.length-1];
}

1
2
3
4
5
6
7
8
9
10
11

2.3.4 动态规划详解

2.3.4.1 leetcode 198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：
输入：[100,2,3,100]
输出：200
解释：偷窃 1 号房屋 (金额 = 100) ，然后偷窃 4 号房屋 (金额 = 100)。
     偷窃到的最高金额 = 100 + 100 = 200 。
1
2
3
4
5

分析：

• 递推式 ： dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1])，即相邻的金币比较大，则不偷取当前的房屋，若相隔一间加上当前房屋的数额比相邻的大，则偷取当前房屋，并计算能偷取的最大值。
• dp[i]为当前能偷盗金币的最大值。

代码实现：

class Solution {
    public int rob(int[] nums) {
        if (nums.length <= 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(dp[0], nums[1]);
        for (int i = 2; i < nums.length; i++){
            dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
            System.out.println(dp[i]);
        }
        return dp[nums.length-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.3.4.1 背包问题

2.3.4.2 leetcode 300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
1
2
3
4
5

分析：

• 以nums[i]为最长递增子序列的结尾，dp[i]为以nums[i]为最长递增子序列的结尾的序列最大长度。
• 当遍历到nums[i]时，其最长递增子序列可以由上一个小于他的数的最长递增子序列的最大值得到，则得到递推式dp[i] = preMax + 1;
• 如何得到上一个小于他的数的最长递增子序列的最大值呢，则需要再遍历一遍dp[]因此还需要一个for循环来遍历dp[]。

代码如下：

// 动态规划解法
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n  = nums.length;
        if (n == 1) return 1;
        int[] dp  = new int[n];
        dp[0] = 1;
        int res = 1;
        for (int i = 1;  i<n ; i++) {
            int tempMax = 0;
            for (int j = 0; j < i; j++) {
                if (nums[j]< nums[i] && dp[j] > tempMax) {
                    tempMax = dp[j];
                }
            }
            dp[i] = tempMax + 1;
            if (dp[i] > res) res = dp[i];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

递增问题还可以由单调栈进行求解，参考第三章。

2.3.4.3 leetcode 279. 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4
1
2
3
4
5

分析：

1. dp[i]为当前平方和的最小值
2. i = k + j，即 dp[i] = min(dp[i] + dp[j]),dp[i]);

代码实现：

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+2];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i<=n ; i++) {
            int temp = (int)Math.sqrt(i);
            int index = (int)Math.pow(temp,2);
            if (index == i) {
                dp[i] = 1;
            } else{
                int tempMin = n;
                for (int j = i/2; j<=index ; j++){
                    tempMin = Math.min(dp[j] + dp[i-j], tempMin);
                }
                dp[i] = tempMin;
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.4.4.3 leetcod 322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0
1
2
3
4
5
6
7
8
9
10
11
12
13

分析：

• 首先明确： dp[n] 表示 以 n 块钱 所需的最小硬币数目。
• 对于状态 dp[n] 可以由 dp[n-coins[i]] + 1 得到，同时还要取最小值，即dp[i] = Math.min(dp[i-coins[j]]+1, dp[i])，举个例子： 11 块钱的硬币数，可以由 6 块钱的硬币数目加一得到。

代码实现：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;
            for (int j = 0; j < coins.length; j++){
                if (coins[j] <= i){
                    dp[i] = Math.min(dp[i-coins[j]]+1, dp[i]);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.4.4.1 leetcode 152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
1
2
3
4
5
6
7
8
9
10

分析：

• 首先分析：最大的乘积可以从过去的数据中与当前的值相乘得到，所以可以使用动态规划
• 由于有负数的存在，由于负负得正，所以：明确dp[i][0]表示为正数的最大乘积，dp[i][1]表示为负数的最小乘积。
• 则 dp[i][0] = Math.max(nums[i] * dp[i-1][0], Math.max(nums[i], dp[i-1][1]* nums[i])); 即，如果nums[i] * dp[i-1][0]是正数，则赋值，否则取Math.max(nums[i], dp[i-1][1]* nums[i]) （取该值与负数最大值乘以该值的最大值）。
• 则 dp[i][1] = Math.min(nums[i] * dp[i-1][1], Math.min(nums[i], dp[i-1][0]* nums[i])); 即，如果nums[i] * dp[i-1][0]是负数，则赋值，否则取Math.min(nums[i], dp[i-1][0]* nums[i]) （取该值与负数最大值乘以该值的最小值）。

2.3.4.1 最优路径规划

2.4 贪心算法

2.4.1 什么是贪心算法

贪心算法的核心思想是在每一步中**都选择当前状态下的最优解，而不考虑全局后果。**它通常适用于那些问题，其最优解可以通过一系列局部最优解的组合得到。

贪心算法的一般步骤如下：

• 选择阶段： 从问题的所有可能选择中，选择一个局部最优解。
• 限制阶段： 将问题规模缩小，转化为一个子问题。
• 最优解合并阶段： 将局部最优解与子问题的解合并，得到全局最优解。
• 核心思想：贪心算法：从当前的数据可以推断以后的数据；动态规划，以前的数据可以推断现在的数据。注意区分两者的思想，虽然思想不同，但是贪心算法可以解的题也可以用动态规划来解，只是动态规划的时间复杂度与空间复杂度都相对于贪心算法更高一些。

贪心算法的关键是选择合适的贪心策略，以确保每一步都是局部最优的。然而，需要注意的是，贪心算法并不总能得到全局最优解，因此在应用时需谨慎考虑问题的性质。

这样描述可能有点抽象，下面通过几道例题进行加深你的理解。

2.4.2 贪心算法的适用场景

递归算法适用于：

• 问题可以被分解为更小的子问题进行求解的场景
• 局部最优即全局最优的场景，如何证明局部最优可得到全局最优这是贪心算法的难点。

一些常见的应用场景包括：

• 活动选择问题： 给定一系列活动，每个活动有开始时间和结束时间。目标是选择最大数量的不重叠活动，使得参与活动的人数最多。
• 霍夫曼编码： 在数据压缩中，霍夫曼编码是一种用于压缩数据的贪心算法。它通过为出现频率较高的字符分配较短的编码来减少数据的存储空间。
• 最小耗费生成树（Prim算法）：在图中寻找最小生成树的问题中，Prim算法通过从一个初始节点开始，逐步选择与当前树相连的边中权值最小的边，从而构建最小生成树。
• 零钱兑换问题： 给定一些面额不同的硬币和一个目标金额，找出使用最少的硬币来达到目标金额。
• 分数背包问题： 在背包问题中，每个物品有一定的价值和重量，但可以分割成较小的部分。贪心策略是优先选择单位价值最高的物品。

2.4.3 贪心算法模板

1

2.4.4 贪心算法详解

2.4.4.1 leetcode 55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
1
2
3
4
5
6
7
8
9
10

分析：

• 我们可以从当前位置推断能跳到的最大位置， 即 max = Math.max(max, nums[i] + i)。
• 只要当前位置与能跳到的最大位置相等，即i == max，则表示后续的位置便到达不了了。

代码实现：

// 贪心算法解法
class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) return true;
        int max = 0; // max 表示当前可以跳到的最大距离
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] + i > max) max = nums[i] + i;
            if (i == max) return false;
        }
        return true;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.4.4.2 leetcode 45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i] 
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:

输入: nums = [2,3,0,1,4]
输出: 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14

分析：

• 我们可以从当前位置推断能跳到的最大位置， 即 max = Math.max(max, nums[i] + i)。
• 当遍历到上一个最大值位置时，才需要再跳一次，且更新下个能跳的最大值。

代码实现：

class Solution {
    public int jump(int[] nums) {
        int res = 0;
        int max = 0; // 从当前可跳跃的最大值
        int end = 0; // 上一个最大值结束的位置
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] + i > max) {
                max = nums[i] + i;
            }
            if (i == end) { // 当遍历到上一个最大值位置时，需要再跳一次，且更新下个能跳的最大值
                end = max;
                res ++;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.5 回溯算法

2.1.1 什么是回溯算法

回溯算法是一种深度优先的搜索技术，它遵循一种“试错”的思路。在解决问题的过程中，我们通过选择某个路径并探索下去，然后发现当前选择并不是最优或者不符合约束条件时，就返回上一步重新选择路径，直到找到问题的解或者遍历完所有可能的路径。

回溯算法的步骤：

• 定义问题的解空间：确定问题的解可表示为一个N维向量，其中N是问题的规模，一般是一个数组。
• 确定约束条件：定义问题的解必须满足的条件，以便在搜索过程中剪枝，即找到解，进行减枝。
• 选择合适的搜索顺序：根据问题的特点，选择合适的搜索顺序，以提高搜索效率。
• 编码回溯函数：实现回溯函数，其中包括终止条件、约束条件的判断和路径的选择，这个是核心。
• 执行回溯搜索：根据回溯函数进行递归搜索，记录符合条件的解并完成状态回退。

这样描述可能有点抽象，下面通过几道例题进行加深你的理解。

2.1.2 回溯算法的适用场景

回溯算法的应用领域 回溯算法可以用于解决各种问题，尤其是那些具有以下特征的问题：

• 组合问题：在给定一组候选解的情况下，找到所有可能的组合。
• 排列问题：在给定一组元素的情况下，找到所有可能的排列。
• 子集问题：在给定一组元素的情况下，找到所有可能的子集。
• 图问题：对于给定的图结构，找到满足某些约束条件的路径。

2.1.3 回溯算法模板

回溯算法可以看作森林的遍历过程。

简化成一个二维坐标：

• x为同一层级可选择的路径
• y为递归深度

模板代码：

List<?> result = new ArrayList<>();
void backtrack(路径, 选择列表):
    if (满足结束条件){
        result.add(路径)
        return
    }
    for (选择 in 选择列表){ // x
        做选择
        backtrack(路径, 选择列表) // y
        撤销选择
    }
1
2
3
4
5
6
7
8
9
10
11

2.4.4 回溯算法详解

2.4.5.1 leetcode 46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：

输入：nums = [1]
输出：[[1]]
1
2
3
4
5
6
7
8
9
10
11
12

2.4.5.1 leetcode 78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]
1
2
3
4
5
6
7
8

2.4.5.1 leetcode 39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。

你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：

输入: candidates = [2], target = 1
输出: []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.4.5.1 leetcode 17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]
1
2
3
4
5
6
7
8
9
10
11
12

2.4.5.1 17. leetcode 22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]
1
2
3
4
5
6
7
8

2.4.5.1 leetcode 79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
1
2

2.4.5.1 leetcode 131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：

输入：s = "a"
输出：[["a"]]
1
2
3
4
5
6
7
8

2.4.5.1 leetcod 51. N 皇后

按照国际象棋的规则:

• 皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
1
2
3

示例 2：

输入：n = 1
输出：[["Q"]]
1
2

三、 面试常见其他算法

Java 对象一切都是引用，其只能对其引用进行操作，使用等号会更改引用的对象。参考对链表的操作。

3.1 哈希算法

先 get() 再 put()

3.1.1 leetcod 1 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
1
2
3
4
5
6
7
8
9

思路：

• 以差额作为key，下标作为value，当数组中刚好num[i]刚好与key相等，即value存在时，return

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            int t = map.getOrDefault(nums[i],-1);
            map.put(target - nums[i], i);
            if (t >= 0 && i != t) {
                int[] res = new int[2];
                res[0] = i;
                res[1] = t;
                return res;
            }
        }
        return new int[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.1.2 leetcode128 最长连续序列

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

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

示例 1：

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

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9 
1
2
3
4
5
6
7

思路：

• 方法1：先排序再遍历，时间复杂度不符合要求。
• 方法2：以num[i]、nums[i] - left、nums[i] + right 为key，len 为 value。其中left、right为已经遍历过数据的最大连续长度，len = left + right + 1。

代码

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int res = 0;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
            if (!hashMap.containsKey(nums[i])){
                Integer left = hashMap.getOrDefault(nums[i]-1, 0);
                Integer right = hashMap.getOrDefault(nums[i]+1, 0);
                Integer len = left + right + 1;
                res = Math.max(res, len);
                hashMap.put(nums[i], len);
                hashMap.put(nums[i] - left, len);
                hashMap.put(nums[i] + right, len);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.2 双指针算法

核心：

• if (a > b) low++;
• else high++;

3.2.1 leetcode15 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思路：

1. 先排序以便后续进行操作
2. 双指针进行遍历，初始化 low = i +1，high = nums.length -1。
3. 对于每个 num[i]，再使用一个while循环进行遍历。
4. if (nums[i] + nums[low] + nums[high] < 0){ low++;}
5. else if (nums[i] + nums[low] + nums[high] > 0){ high--; }
6. else{ 添加到结果数组}
7. 使用一个while循环调整low/high指针进行结果去重。

代码：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new LinkedList<>();
        for (int i = 0; i < nums.length-2; i++) {
            int low = i+1;
            int high = nums.length - 1;
            if (i != 0 && nums[i] == nums[i-1]){
                continue;
            }
            if (nums[i]+ nums[i+1] + nums[i+2] > 0){
                continue;
            }
            if (nums[i] + nums[nums.length-1] + nums[nums.length-2] < 0){
                continue;
            }
            while (low < high) {
                if (nums[i] + nums[low] + nums[high] < 0){
                    low++;
                }else if (nums[i] + nums[low] + nums[high] > 0){
                    high--;
                }else{
                    List<Integer> temp = new LinkedList<>();
                    temp.add(nums[i]);
                    temp.add(nums[low]);
                    temp.add(nums[high]);
                    res.add(temp);
                    low ++;
                    while (low < high && nums[low] == nums[low-1]){ // 若添加到结果数组时上一个数和现在一样，忽略（去重）。
                        low++;
                    }
                    high --;
                    while (low < high && nums[high] == nums[high+1]){
                        high--;
                    }
                }
            }
        }
        return res;
    }
}
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

3.2.2 leetcode11 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

输入：[1,8,6,2,5,4,8,3,7] 
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
1
2
3

思路：

1. 如果 low 指针高度低于 high 指针，则 low指针++，即if (height[low] < height[high]){low++;}
2. 否则 high –

代码

lass Solution {
    public int maxArea(int[] height) {
        int low = 0, high = height.length -1;
        int res = 0;
        while (low != high) {
            int content = Math.min(height[low], height[high]) * (high - low);
            if (content > res) res = content;
            if (height[low] < height[high]){
                low++;
            }else{
                high--;
            } 
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.2.3 leetcode42 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

输入：height = [4,2,0,3,2,5]
输出：9
1
2
3
4
5
6

思路：

• 需要 双指针 low、high, 与两个临时变量。
• preMax 表示左边边界最大值，初始为零，aftMax 表示右边边界最大值，初始为零
• 取最小的边界减去当前高度 即为容积。

代码：

class Solution {
public:
    int trap(vector<int>& height) {
        int preMax = 0; // 左边边界最大值，初始为零
        int aftMax = 0; // 右边边界最大值，初始为零
        int left = 0;
        int right = height.size() -1;
        int ans = 0;
        while (left <= right){
            if (height[left] > preMax) preMax = height[left];
            if (height[right] > aftMax) aftMax = height[right];
            if (preMax < aftMax) {
                ans += preMax - height[left]; // 取最小的边界减去当前高度 即为容积。
                left++;
            }else{
                ans += aftMax - height[right];
                right--;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.3 滑动窗口算法

3.3.1 leetcode42 无重复最长字串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
1
2
3
4
5
6
7
8

思路：

• map 存储已经出现过的字符
• 双指针构成滑动窗口（双指针同方向移动）

代码：

3.5 栈 与 单调栈

3.6 图

3.7 位运算

四、Java 算法题常用容器与函数

4.1 数组[]与List<>

4.1.1 数组 与 ArrayList/LinkedList 相互转化

String[] strArray = [];

ArrayList<String> list = new ArrayList<String>(Arrays.asList(strArray)); // 数组转 ArrayList

LinkedList<String> list = new LinkedList<String>(Arrays.asList(strArray));

int[] intArray = arrayList.stream().mapToInt(Integer::intValue).toArray(); // ArrayList<Integer> 转 int数组

Integer[] integerArray = arrayList.toArray(new Integer[0]); // ArrayList<Integer> 转 Integer数组
1
2
3
4
5
6
7
8
9

4.1.2 stream流

4.1.2.1 过滤 —— Filter

stream.filter(x -> x > 5) //保留大于 5 的元素。
1

4.1.2.2 映射 —— map

stream.map(x -> x * 2) // 将每个元素都乘以 2。
1

4.1.2.3 去重 —— distinct

stream.distinct() // 将保留唯一的元素。
1

4.1.2.4 排序 —— sorted

stream.sorted() // 将按照默认的自然顺序进行排序。
1

4.1.3 Arrays 工具类 —— 只能操作基本数据类型

4.1.3.1 填充数组 —— Arrays.fill()

int[] arr = new int[5];//新建一个大小为5的数组
Arrays.fill(arr,4);//给所有值赋值4
String str = Arrays.toString(arr); // Arrays类的toString()方法能将数组中的内容全部打印出来
System.out.print(str);
//输出：[4, 4, 4, 4, 4]
1
2
3
4
5

4.1.3.2 数组排序—— Arrays.sort()

int[] arr = {3,2,1,5,4};
Arrays.sort(arr,0,3);//给第0位（0开始）到第3位（不包括）排序
String str = Arrays.toString(arr); // Arrays类的toString()方法能将数组中的内容全部打印出来
System.out.print(str);
//输出：[1, 2, 3, 5, 4]
1
2
3
4
5

4.1.3.3 数组二分查找，返回下标 —— Arrays.binarySearch()

int[] arr = {10,20,30,40,50};
System.out.println(Arrays.binarySearch(arr, 30));
//输出：2 （下标索引值从0开始）
1
2
3

4.1.3.4 数组打印 —— Arrays.toString(arr)

int[] arr = {10,20,30,40,50};
System.out.println(Arrays.toString(arr));
1
2

4.1.3.5 生成List<> —— Arrays.asList(param)

List<String> strings = Arrays.asList("abc", "", "bc", "efg", "abcd","", "jkl");
1

4.2 String、Character

4.2.1 返回指定索引处的 char 值 —— charAt(int index)

char charAt(int index)
1

4.2.2 按字典顺序比较两个字符串 —— compareTo(String anotherString)

int compareTo(String anotherString)
1

注：字符串类不能直接比较，但是char 类型可以直接比较（按照ASCILL编码比较）。

4.2.3 返回此字符串的长度 —— length()

int length()
1

4.2.4 返回一个新字符串，它是此字符串的一个子字符串 —— substring(int beginIndex, int endIndex)

String substring(int beginIndex, int endIndex)
1

4.2.5 将此字符串转换为一个新的字符数组 —— toCharArray()

char[] toCharArray()
1

4.2.6 字符串转int、float、double… —— parseInt(String string)

// number = "-7"
int result = Integer.parseInt(number);

Integer result2 = Integer.valueOf(number);
1
2
3
4

4.2.7 判断char字符是否是数字/字母 —— Character.isDigit()、Character.isLetter()

boolean isLetter(char ch)

public static boolean isDigit(char ch)
1
2
3

4.2.8 转化为大小写 —— toLowerCase()、toUpperCase()

public String toUpperCase()

public String toLowerCase()
1
2
3

4.2.9 按指定字符串分割，返回字符串数组 —— split(String regex)

String[] split(String regex)
1

4.3 Stack

4.3.1 Stack 只有一个无参构造函数 —— new Stack<>()

Stack<Integer> stack = new Stack<>();
1

4.3.2 添加元素到栈顶 —— stack.push(item)

stack.push(item);
1

4.3.3 获取栈顶元素 —— stack.peek()

int topElement = stack.peek();
1

4.3.4 弹出栈顶元素 —— stack.pop();

int poppedElement = stack.pop();
1

4.3.5 获取栈的大小 —— stack.size();

int size = stack.size();
1

4.4 Queue

4.4.1 Queue 由LinkedList实现 —— new LinkedList<>();

Queue<String> queue = new LinkedList<>();
1

4.4.2 添加元素到队尾 —— stack.push(item)

queue.add(item);
1

4.4.3 获取队头元素 —— queue.peek();

String headElement = queue.peek();
1

4.4.4 弹出队头元素 —— queue.poll();

String removedElement = queue.poll(); //remove()
1

4.4.5 获取队列的大小 —— queue.size();

int size = stack.size();
1

4.5 Map —— HashMap、HashTable(线程安全)

4.5.1 HashMap 只有一个无参构造函数 —— new HashMap<key,value>()

HashMap<Integer, String> map = new HashMap<Integer, String>();
1

4.5.2 添加元素到map —— put(key,value);

map.put(1, "Google");
1

4.5.3 获取 key 对应的 value —— get(key)、getOrDefault()

String value = map.get(1);
String value = map.getOrDefault(1, ""); //找不到设置默认值
1
2

4.5.4 删除 key 对应的键值对(key-value) —— remove(key)

map.remove(1);
1

4.5.5 对 hashMap 中的每个映射执行指定的操作 —— forEach((key, value) -> {})

map.forEach((key, value) -> {System.out.print(key + ":" + value);});
1