[数据结构与算法]【恋上数据结构，Java-SSM框架相关面试题整理

static int coins(int n) {

	if (n < 1) return -1; // 处理非法数据

	int[] dp = new int[n + 1];

	// 递推(自底向上)过程

	for (int i = 1; i <= n; i++) {

		int min = dp[i - 1]; // 由于下面两行是必然执行的, 直接这么写就行了

		// int min = Integer.MAX_VALUE;

		// if (i >= 1) min = Math.min(min, dp[i - 1]);

		if (i >= 5) min = Math.min(min, dp[i - 5]);

		if (i >= 20) min = Math.min(min, dp[i - 20]);

		if (i >= 25) min = Math.min(min, dp[i - 25]);

		dp[i] = min + 1;

	}

	return dp[n];

} 

思考题：输出找零钱的具体方案（具体是用了哪些面值的硬币）

static int coins4(int n) {

	if (n < 1) return -1; // 处理非法数据

	int[] dp = new int[n + 1];

	// faces[i]是凑够i分时最后选择的那枚硬币的面值

	int[] faces = new int[dp.length]; // 存放硬币面值(为了输出)

	for (int i = 1; i <= n; i++) {

		int min = Integer.MAX_VALUE;

		if (i >= 1 && dp[i - 1] < min) {

			min = dp[i - 1];

			faces[i] = 1;

		}

		// 上面一步其实必然执行, 可以直接写成下面这样

		// int min = dp[i - 1];

		// faces[i] = 1;

		if (i >= 5 && dp[i - 5] < min) {

			min = dp[i - 5];

			faces[i] = 5;

		}

		if (i >= 20 && dp[i - 20] < min) {

			min = dp[i - 20];

			faces[i] = 20;

		}

		if (i >= 25 && dp[i - 25] < min) {

			min = dp[i - 25];

			faces[i] = 25;

		}

		dp[i] = min + 1;

		print(faces, i); // 打印凑够面值 1 ~ n 的方案

	}

	// print(faces, n); // 打印凑够面值 n 的方案

	return dp[n];

}

// 打印凑够面值 n 的方案

static void print(int[] faces, int n) {

	System.out.print("[" + n + "] = ");

	while (n > 0) {

		System.out.print(faces[n] + " ");

		n -= faces[n];

	}

	System.out.println();

} 

尝试打印了 n = 41 的情况，打印出了凑够 1~41 所有面值的情况：

[1] = 1 

[2] = 1 1 

[3] = 1 1 1 

[4] = 1 1 1 1 

[5] = 5 

[6] = 1 5 

[7] = 1 1 5 

[8] = 1 1 1 5 

[9] = 1 1 1 1 5 

[10] = 5 5 

[11] = 1 5 5 

[12] = 1 1 5 5 

[13] = 1 1 1 5 5 

[14] = 1 1 1 1 5 5 

[15] = 5 5 5 

[16] = 1 5 5 5 

[17] = 1 1 5 5 5 

[18] = 1 1 1 5 5 5 

[19] = 1 1 1 1 5 5 5 

[20] = 20 

[21] = 1 20 

[22] = 1 1 20 

[23] = 1 1 1 20 

[24] = 1 1 1 1 20 

[25] = 25 

[26] = 1 25 

[27] = 1 1 25 

[28] = 1 1 1 25 

[29] = 1 1 1 1 25 

[30] = 5 25 

[31] = 1 5 25 

[32] = 1 1 5 25 

[33] = 1 1 1 5 25 

[34] = 1 1 1 1 5 25 

[35] = 5 5 25 

[36] = 1 5 5 25 

[37] = 1 1 5 5 25 

[38] = 1 1 1 5 5 25 

[39] = 1 1 1 1 5 5 25 

[40] = 20 20 

[41] = 1 20 20 

3 

找零钱 - 通用实现

public static void main(String[] args) {

	System.out.println(coins5(41, new int[]{1, 5, 20, 25})); // 3

}



static int coins(int n, int[] faces) {

	if (n < 1 || faces == null || faces.length == 0 ) return -1;

	int[] dp = new int [n + 1];

	for (int i = 1; i <= n; i++) {

		int min = Integer.MAX_VALUE;

		for (int face : faces) {

			// 假如给我的面值是20, 要凑的是15, 则跳过此轮循环

			if (face > i) continue; // 如果给我的面值比我要凑的面值还大, 跳过此轮循环

			min = Math.min(dp[i - face], min);

		}

		dp[i] = min + 1;

	}

	return dp[n];

} 

改进，如果不能凑成则返回 -1：

static int coins5(int n, int[] faces) {

	if (n < 1 || faces == null || faces.length == 0 ) return -1;

	int[] dp = new int [n + 1];

	for (int i = 1; i <= n; i++) {

		int min = Integer.MAX_VALUE;

		for (int face : faces) {

			// 假如给我的面值是20, 要凑的是15, 则跳过此轮循环

			if (face > i) continue; // 如果给我的面值比我要凑的面值还大, 跳过此轮循环

			// 比如给的面值是{4}, 要凑的是6, 先给出一张4, 再看6-4=2, 是否能凑成

			// 2无法凑成, 则跳过此轮循环 

			int v = dp[i - face];

			if (v < 0 || v >= min) continue;

			min = v;

		}

		// 说明上面的循环中每次都是continue, 要凑的面值比给定的所有面值小

		if (min == Integer.MAX_VALUE) {

			dp[i] = -1;

		} else {

			dp[i] = min + 1;

		}

	}

	return dp[n];

} 

动态规划（Dynamic Programming）

============================================================================================

动态规划的常规步骤

动态规划，简称 DP

• 是求解最优化问题的一种常用策略

通常的使用套路（一步一步优化）:

① 暴力递归（自顶向下，出现了重叠子问题）

② 记忆化搜索（自顶向下）

③ 递推（自底向上）

动态规划中的 “动态” 可以理解为是 “会变化的状态”；

• ① 定义状态（状态是原问题、子问题的解）

  比如定义 d p ( i ) dp(i) dp(i) 的含义

• ② 设置初始状态（边界）

  比如设置 d p ( 0 ) dp(0) dp(0) 的值

• ③ 确定状态转移方程

  比如确定 d p ( i ) dp(i) dp(i) 和 d p ( i ? 1 ) dp(i - 1) dp(i?1) 的关系

动态规划的一些概念

维基百科的解释：

Dynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.

① 将复杂的原问题拆解成若干个简单的子问题

② 每个子问题仅仅解决1次，并保存它们的解

③ 最后推导出原问题的解

可以用动态规划来解决的问题，通常具备2个特点：

• 最优子结构（最优化原理）：通过求解子问题的最优解，可以获得原问题的最优解

• 无后效性：

  某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响（未来与过去无关）

  在推导后面阶段的状态时，只关心前面阶段的具体状态值，不关心这个状态是怎么一步步推导出来的

有后效性与无后效性

首先了解一下什么是有后效性：

然后再去理解什么是无后效性：

练习2：最大连续子序列和

===============================================================================

题目：给定一个长度为 n 的整数序列，求它的最大连续子序列和

• 比如 -2、1、-3、4、-1、2、1、-5、4 的最大连续子序列和是 4 + (-1) + 2 + 1 = 6；

  以 nums[0] -2 结尾的最大连续子序列是 -2，所以 d p ( 0 ) = ? 2 dp(0) = -2 dp(0)=?2

  以 nums[1] 1 结尾的最大连续子序列是 1，所以 d p ( 1 ) = 1 dp(1) = 1 dp(1)=1

  以 nums[2] -3 结尾的最大连续子序列是 1、-3，所以 d p ( 2 ) = d p ( 1 ) + ( ? 3 ) = ? 2 dp(2) = dp(1) + (-3) = -2 dp(2)=dp(1)+(?3)=?2

  以 nums[3] 4 结尾的最大连续子序列是 4，所以 d p ( 3 ) = 4 dp(3) = 4 dp(3)=4

  以 nums[4] -1 结尾的最大连续子序列是 4、-1，所以 d p ( 4 ) = d p ( 3 ) + ( ? 1 ) = 3 dp(4) = dp(3) + (-1) = 3 dp(4)=dp(3)+(?1)=3

  以 nums[5] 2 结尾的最大连续子序列是 4、-1、2，所以 d p ( 5 ) = d p ( 4 ) + 2 = 5 dp(5) = dp(4) + 2 = 5 dp(5)=dp(4)+2=5

  以 nums[6] 1 结尾的最大连续子序列是 4、-1、2、1，所以 d p ( 6 ) = d p ( 5 ) + 1 = 6 dp(6) = dp(5) + 1 = 6 dp(6)=dp(5)+1=6

  以 nums[7] -5 结尾的最大连续子序列是 4、-1、2、1、-5，所以 d p ( 7 ) = d p ( 6 ) + ( ? 5 ) = 1 dp(7) = dp(6) + (-5) = 1 dp(7)=dp(6)+(?5)=1

  以 nums[8] 4 结尾的最大连续子序列是 4、-1、2、1、-5、4，所以 d p ( 8 ) = d p ( 7 ) + 4 = 5 dp(8) = dp(7) + 4 = 5 dp(8)=dp(7)+4=5

状态转移方程和初始状态：

状态转移方程：

• 如果 d p ( i – 1 ) ≤ 0 dp(i – 1) ≤ 0 dp(i–1)≤0，那么 d p ( i ) = n u m s [ i ] dp(i) = nums[i] dp(i)=nums[i]

• 如果 d p ( i – 1 ) > 0 dp(i – 1) > 0 dp(i–1)>0，那么 d p ( i ) = d p ( i – 1 ) + n u m s [ i ] dp(i) = dp(i – 1) + nums[i] dp(i)=dp(i–1)+nums[i]

初始状态：

• d p ( 0 ) dp(0) dp(0) 的值是 n u m s [ 0 ] nums[0] nums[0]

最终的解：

• 最大连续子序列和是所有 d p ( i ) dp(i) dp(i) 中的最大值 m a x { d p ( i ) } ， i ∈ [ 0 , n u m s . l e n g t h ) max \{ dp(i) \}，i ∈ [0, nums.length) max{dp(i)}，i∈[0,nums.length)

最大连续子序列和 – 实现

static int maxSubArray(int[] nums) {

	if (nums == null || nums.length == 0) return 0;

	int[] dp = new int[nums.length];

	int max = dp[0] = nums[0];

	for (int i = 1; i < dp.length; i++) {

		if (dp[i - 1] > 0) {

			dp[i] = dp[i - 1] + nums[i];

		} else {

			dp[i] = nums[i];

		}

		max = Math.max(max, dp[i]);

	}

	return max;

} 

最大连续子序列和 – 优化

static int maxSubArray(int[] nums) {

	if (nums == null || nums.length == 0) return 0;

	int dp = nums[0];

	int max = dp;

	for (int i = 1; i < nums.length; i++) {

		if (dp > 0) {

			dp = dp + nums[i];

		} else {

			dp = nums[i];

		}

		max = Math.max(max, dp);

	}

	return max;

} 

练习3：最长上升子序列（LIS）

===================================================================================

最长上升子序列（最长递增子序列，Longest Increasing Subsequence，LIS）

leetcode_300_最长上升子序列： https://leetcode-cn.com/problems/longest-increasing-subsequence/

题目：给定一个无序的整数序列，求出它最长上升子序列的长度（要求严格上升）

• 比如 [10, 2, 2, 5, 1, 7, 101, 18] 的最长上升子序列是 [2, 5, 7, 101]、[2, 5, 7, 18]，长度是 4

假设数组是 nums， [10, 2, 2, 5, 1, 7, 101, 18]

• d p ( i ) dp(i) dp(i) 是以 n u m s [ i ] nums[i] nums[i] 结尾的最长上升子序列的长度， i ∈ [ 0 , n u m s . l e n g t h ) i ∈ [0, nums.length) i∈[0,nums.length)

  以 nums[0] 10 结尾的最长上升子序列是 10，所以 d p ( 0 ) = 1 dp(0) = 1 dp(0)=1

  以 nums[1] 2 结尾的最长上升子序列是 2，所以 d p ( 1 ) = 1 dp(1) = 1 dp(1)=1

  以 nums[2] 2 结尾的最长上升子序列是 2，所以 d p ( 2 ) = 1 dp(2) = 1 dp(2)=1

  以 nums[3] 5 结尾的最长上升子序列是 2、5，所以 d p ( 3 ) = d p ( 1 ) + 1 = d p ( 2 ) + 1 = 2 dp(3) = dp(1) + 1 = dp(2) + 1 = 2 dp(3)=dp(1)+1=dp(2)+1=2

  以 nums[4] 1 结尾的最长上升子序列是 1，所以 d p ( 4 ) = 1 dp(4) = 1 dp(4)=1

  以 nums[5] 7 结尾的最长上升子序列是 2、5、7，所以 d p ( 5 ) = d p ( 3 ) + 1 = 3 dp(5) = dp(3) + 1 = 3 dp(5)=dp(3)+1=3

  以 nums[6] 101 结尾的最长上升子序列是 2、5、7、101，所以 d p ( 6 ) = d p ( 5 ) + 1 = 4 dp(6) = dp(5) + 1 = 4 dp(6)=dp(5)+1=4

  以 nums[7] 18 结尾的最长上升子序列是 2、5、7、18，所以 d p ( 7 ) = d p ( 5 ) + 1 = 4 dp(7) = dp(5) + 1 = 4 dp(7)=dp(5)+1=4

状态方程：

状态的初始值：

• d p ( 0 ) = 1 dp(0) = 1 dp(0)=1

• 所有的 d p ( i ) dp(i) dp(i) 默认都初始化为 1

最终的解：

• 最长上升子序列的长度是所有 d p ( i ) dp(i) dp(i) 中的最大值 m a x { d p ( i ) } ， i ∈ [ 0 , n u m s . l e n g t h ) max \{ dp(i) \}，i ∈ [0, nums.length) max{dp(i)}，i∈[0,nums.length)

最长上升子序列 – 实现

时间复杂度：O(n2)，空间复杂度：O(n)

static int lengthOfLIS(int[] nums) {

  	if (nums == null || nums.length == 0) return 0;

  	int[] dp = new int[nums.length];

  	int max = dp[0] = 1; // 只有一个元素则长度为1

  	for (int i = 1; i < dp.length; i++) {

  		dp[i] = 1; // 默认只有一个元素时长度为1

  		for (int j = 0; j < i; j++) {

  			// 无法成为一个上升子序列

  			if (nums[j] >= nums[i]) continue;

  			dp[i] = Math.max(dp[j] + 1, dp[i]);

  		}

  		max = Math.max(dp[i], max);

  	}

  	return max;

  } 

最长上升子序列 – 二分搜索实现

普通实现（非二分搜索）：

static int lengthOfLIS(int[] nums) {

	if (nums == null || nums.length == 0) return 0;

	// 牌堆的数量

	int len = 0;

	// 牌顶数组

	int[] top = new int[nums.length];

	// 遍历所有的牌

	for (int num : nums) {

		int j = 0;

		while (j < len) {

			// 找到一个>=nums的牌顶

			if (top[j] >= num) {

				top[j] = num;

				break;

			}

			// 牌顶 < nums

			j++;

		}

		if (j == len) { // 新建一个牌堆

			len++;

			top[j] = num;

		}

	}

	return len;

} 

二分搜索实现：

static int lengthOfLIS(int[] nums) {

	if (nums == null || nums.length == 0) return 0;

	// 牌堆的数量

	int len = 0;

	// 牌顶数组

	int[] top = new int[nums.length];

	// 遍历所有的牌（二分搜索）

	for (int num : nums) {

		int begin = 0;

		int end = len;

		while (begin < end) {

			int mid = (begin + end) >> 1;

			if (num <= top[mid]) {

				end = mid;

			} else {

				begin = mid + 1;

			}

		}

		// 覆盖牌顶

		top[begin] = num;

		// 检查是否要新建一个牌堆

		if (begin == len) len++;

	}

	return len;

} 

练习4 – 最长公共子序列（LCS）

=====================================================================================

最长公共子序列（Longest Common Subsequence，LCS）

leetcode_1143_最长公共子序列：https://leetcode-cn.com/problems/longest-common-subsequence/

题目：求两个序列的最长公共子序列长度

• [1, 3, 5, 9, 10] 和 [1, 4, 9, 10] 的最长公共子序列是 [1, 9, 10]，长度为 3

• ABCBDAB 和 BDCABA 的最长公共子序列长度是 4，可能是

  ABCBDAB 和 BDCABA > BDAB

  ABCBDAB 和 BDCABA > BDAB

  ABCBDAB 和 BDCABA > BCAB

  ABCBDAB 和 BDCABA > BCBA

思路：

最长公共子序列 – 递归实现

• 空间复杂度：O(k) , k = min{n, m}，n、m 是 2 个序列的长度

• 时间复杂度：O(2n) ，当 n = m 时

/**

 * 递归实现

 */

static int lcs(int[] nums1, int[] nums2) {

	if (nums1 == null || nums1.length == 0) return 0; // 检测非法数据

	if (nums2 == null || nums2.length == 0) return 0; // 检测非法数据

	return lcs(nums1, nums1.length, nums2, nums2.length);

}

/**

 * 求nums1前i个元素和nums2前j个元素的最长g公共子序列长度

 * @param nums1

 * @param i

 * @param nums2

 * @param j

 */

static int lcs(int[] nums1, int i, int[] nums2, int j) {

	if (i == 0 || j == 0) return 0;

	// 最后一个元素相等, 返回前面的公共子序列长度 + 1

	if (nums1[i - 1] == nums2[j - 1]) {

		return lcs(nums1, i - 1, nums2, j - 1) + 1;

	}

	return Math.max(

		lcs(nums1, i - 1, nums2, j), 

		lcs(nums1, i, nums2, j - 1)

	);

} 

最长公共子序列 – 非递归实现

• 空间复杂度：O(n ? m)

• 时间复杂度：O(n ? m)

static int lcs(int[] nums1, int[] nums2) {

	if (nums1 == null || nums1.length == 0) return 0;

	if (nums2 == null || nums2.length == 0) return 0;

	int[][] dp = new int[nums1.length + 1][nums2.length + 1];

	

	for (int i = 1; i <= nums1.length; i++) {

		for (int j = 1; j <= nums2.length; j++) {

			if (nums1[i - 1] == nums2[j - 1]) {

				dp[i][j] = dp[i - 1][j - 1] + 1;

			} else {

				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

			}

		}

	}

	return dp[nums1.length][nums2.length];

} 

最长公共子序列 – 滚动数组优化

可以使用滚动数组优化空间复杂度。

/**

 * 非递归实现(滚动数组优化)

 */

static int lcs(int[] nums1, int[] nums2) {

	if (nums1 == null || nums1.length == 0) return 0;

	if (nums2 == null || nums2.length == 0) return 0;

	int[][] dp = new int[2][nums2.length + 1];

	

	for (int i = 1; i <= nums1.length; i++) {

		int row = i & 1;

		int prevRow = (i - 1) & 1;

		for (int j = 1; j <= nums2.length; j++) {

			if (nums1[i - 1] == nums2[j - 1]) {

				dp[row][j] = dp[prevRow][j - 1] + 1;

			} else {

				dp[row][j] = Math.max(dp[prevRow][j], dp[row][j - 1]);

			}

		}

	}

	return dp[nums1.length & 1][nums2.length];

} 

最长公共子序列 – 一维数组优化

练习5 – 最长公共子串

===============================================================================

最长公共子串（Longest Common Substring）

• 子串是连续的子序列

题目：求两个字符串的最长公共子串长度

• ABCBA 和 BABCA 的最长公共子串是 ABC，长度为 3

假设 2 个字符串分别是 str1、str2：

• i ∈ [1, str1.length]

• j ∈ [1, str2.length]

假设 d p ( i , j ) dp(i, j) dp(i,j) 是以 str1[i – 1]、str2[j – 1] 结尾的最长公共子串长度：

• d p ( i , 0 ) dp(i, 0) dp(i,0)、 d p ( 0 , j ) dp(0, j) dp(0,j) 初始值均为 0

• 如果 str1[i – 1] = str2[j – 1]，那么 d p ( i , j ) = d p ( i – 1 , j – 1 ) + 1 dp(i, j) = dp(i – 1, j – 1) + 1 dp(i,j)=dp(i–1,j–1)+1

• 如果 str1[i – 1] ≠ str2[j – 1]，那么 d p ( i , j ) = 0 dp(i, j) = 0 dp(i,j)=0

惊喜

最后还准备了一套上面资料对应的面试题（有答案哦）和面试时的高频面试算法题（如果面试准备时间不够，那么集中把这些算法题做完即可，命中率高达85%+）

[](https://gitee.com/vip204888/java-p7)最长公共子序列 – 一维数组优化

-----------------------------------------------------------------------------------



[](https://gitee.com/vip204888/java-p7)练习5 – 最长公共子串

===============================================================================



**最长公共子串**（Longest Common Substring）



*   子串是连续的子序列



题目：求两个字符串的最长公共子串长度



*   ABCBA 和 BABCA 的最长公共子串是 ABC，长度为 3



假设 2 个字符串分别是 str1、str2：



*   i ∈ \[1, str1.length\]

*   j ∈ \[1, str2.length\]



假设 d p ( i , j ) dp(i, j) dp(i,j) 是以 `str1[i – 1]`、`str2[j – 1]` 结尾的最长公共子串长度：



*   d p ( i , 0 ) dp(i, 0) dp(i,0)、 d p ( 0 , j ) dp(0, j) dp(0,j) 初始值均为 0

*   如果 `str1[i – 1]` = `str2[j – 1]`，那么 d p ( i , j ) = d p ( i – 1 , j – 1 ) + 1 dp(i, j) = dp(i – 1, j – 1) + 1 dp(i,j)\=dp(i–1,j–1)+1

*   如果 `str1[i – 1]` ≠ `str2[j – 1]`，那么 d p ( i , j ) = 0 dp(i, j) = 0 dp(i,j)\=0


# 惊喜

最后还准备了一套上面资料对应的面试题（有答案哦）和面试时的高频面试算法题（如果面试准备时间不够，那么集中把这些算法题做完即可，命中率高达85%+）

[外链图片转存中...(img-2NTzTvM0-1628428408729)]


[外链图片转存中...(img-ftqCP572-1628428408730)]

**[资料获取方式：戳这里免费领取](https://gitee.com/vip204888/java-p7)**