面试必刷101 Java题解 -- part 3

part1 – https://blog.csdn.net/qq_41080854/article/details/129204480

part2 – https://blog.csdn.net/qq_41080854/article/details/129224785

动规五部曲

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化( length + 1 一般不用初始化， length是一定要初始化的)
4. 确定遍历顺序
5. 举例推导dp数组

71、斐波那契数列

public class Solution {public int Fibonacci(int n) {if(n <= 1) return n;//终止条件return Fibonacci(n -1) + Fibonacci(n - 2);}
}

public class Solution {public int Fibonacci(int n) {int[] dp = new int[n + 1];if(n <= 2) return 1;dp[0] = 0;dp[1] = 1;for(int i = 2; i < n + 1; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

72、跳台阶

动态规划的核心思想就是拆分子问题，记住过往，减少重复计算。

动态规划：

1.定义状态：青蛙跳上一个 n 级的台阶总共有多少种跳法

2.编写状态转移方程：f(n)=f(n-1)+f(n-2)

3.设置初始值：f(0)=1,f(1)=1 到达0台阶的方法有一种，就是不跳

public class Solution {public int jumpFloor(int target) {if(target==0 ||target==1) return 1;if(target==2) return 2;int []dp=new int[target+1];dp[0]=1;dp[1]=1;for(int i = 2;i < target + 1; i++){dp[i]=dp[i-1]+dp[i-2];}return dp[target];}
}

73、最小花费爬楼梯

import java.util.*;public class Solution {public int minCostClimbingStairs (int[] cost) {// write code hereif (cost.length == 1) return cost[1];//dp[i]表示爬到第i阶楼梯需要的最小花费int[] dp = new int[cost.length + 1];for (int i = 2; i < cost.length + 1; i++) {//每次选取最小的方案 , 过去的记录 + 现在的子问题dp[i]  = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[cost.length];// 0 ~ cost.length = cost.length + 1 。0状态占用一格}
}

74、最长公共子序列(二)

子序列不连续

dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子序列。

import java.util.*;public class Solution {public String LCS (String s1, String s2) {// write code hereint m = s1.length(), n = s2.length();String[][] dp = new String[m + 1][n + 1];for (int i = 0; i < m + 1; i++) {for (int j = 0; j < n + 1; j++) {if (i == 0 || j == 0) dp[i][j] = "";else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1);} else {dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] :dp[i][j - 1];}}}return dp[m][n] == "" ? "-1" : dp[m][n];}
}

class Solution {public int longestCommonSubsequence(String text1, String text2) {int m = text1.length(), n = text2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 1; i < m + 1; i++) {char c1 = text1.charAt(i - 1);for (int j = 1; j < n + 1; j++) {char c2 = text2.charAt(j - 1);if (c1 == c2) {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[m][n];}
}

75、最长公共子串

子串是连续的

import java.util.*;public class Solution {public String LCS (String str1, String str2) {// write code hereint[][] dp = new int[str1.length() + 1][str2.length() + 1];//因为是连续的，所以记住最后的位置和长度即可int maxlength = 0;int maxindex = 0;for (int i = 1; i < str1.length() + 1; i++) {for (int j = 1; j < str2.length() + 1; j++){if(str1.charAt(i - 1) == str2.charAt(j - 1)){ //如果该两位相同dp[i][j] = dp[i - 1][j - 1] + 1;if(dp[i][j] > maxlength){//更新最大长度maxlength = dp[i][j];maxindex = i - 1; //长度 - 1 ，最前面是空}}else{dp[i][j] = 0;//该位置为0}}}return str1.substring(maxindex - maxlength + 1,maxindex + 1);}
}

76、最长上升子序列(一)

import java.util.*;public class Solution {public int LIS (int[] arr) {// write code hereif (arr.length == 0) return 0;int[] dp = new int[arr.length];//设置数组长度大小的动态规划辅助数组 dp[i]表示以下标i结尾的最长上升子序列的长度Arrays.fill(dp, 1);int res = 1;//只有一个数字时为1for (int i = 1; i < arr.length; i++) { //i = 0也可以for (int j = 0; j < i; j++) { //子数组if (arr[i] > arr[j]) {//i点比j点大，理论上dp要加1dp[i] =  Math.max(dp[i], dp[j] + 1);//找到最大长度res = Math.max(res, dp[i]);}}}return res;}
}

77、最长连续序列

class Solution {public int longestConsecutive(int[] nums) {HashSet<Integer> set = new HashSet<>();//连续序列不允许重复for(int i = 0; i < nums.length; i++){set.add(nums[i]);}int res = 0;for(int i = 0; i < nums.length; i++){if(!set.contains(nums[i] - 1)){//找到了头int num = nums[i] + 1;while(set.contains(num)){num++;}res = Math.max(res, num - nums[i]);}}return res;}
}

78、不同路径的数目(一)

import java.util.*;public class Solution {public int uniquePaths (int m, int n) {// write code hereint dp[][] = new int[m][n];for (int i = 0; i < n; i++) {dp[0][i] = 1;}for (int i = 0; i < m; i++) {dp[i][0] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
}

79、把数字翻译成字符串

import java.util.*;public class Solution {public int solve (String nums) {// write code hereint n = nums.length();String s = " " + nums;char[] cs = s.toCharArray();int[] f = new int[n + 1];f[0] = 1;for (int i = 1; i < n + 1; i++) { // a : 代表「当前位置」单独形成 item// b : 代表「当前位置」与「前一位置」共同形成 itemint a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');// 如果 a 属于有效值，那么 f[i] 可以由 f[i - 1] 转移过来if (1 <= a && a <= 9) f[i] = f[i - 1];// 如果 b 属于有效值，那么 f[i] 可以由 f[i - 2] 或者 f[i - 1] & f[i - 2] 转移过来if (10 <= b && b <= 26) f[i] += f[i - 2];}return f[n];}
}

80、把数字翻译成字符串2

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

class Solution {public int translateNum(int num) {String nums = String.valueOf(num);int n = nums.length();nums = " " + nums;char[] cs = nums.toCharArray();int[] dp = new int[n + 1];dp[0] = 1;for(int i = 1; i < n + 1 ; i++){int a = cs[i] - '0' , b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');if (a >= 0 && a <= 9) dp[i] += dp[i - 1];if (b >= 10 && b <=25 ) dp[i] += dp[i - 2];}return dp[n];}
}

背包问题

01背包是只能被使用一次，完全背包是可以被使用无数次

/* 0-1背包问题* @param V	背包容量* @param N	物品种类* @param weight 物品重量* @param value	物品价值* @return*/
public static int ZeroOnePack2(int V,int N,int[] weight,int[] value){//动态规划int[] dp = new int[V+1];for(int i=1;i<N+1;i++){//逆序实现for(int j=V;j>=weight[i-1];j--){dp[j] = Math.max(dp[j-weight[i-1]]+value[i-1],dp[j]);}}return dp[V];		
}
/* 完全背包的第二种解法* 思路：* 只用一个一维数组记录状态，dp[i]表示容量为i的背包所能装入物品的最大价值* 用顺序来实现*/
public static int completePack2(int V,int N,int[] weight,int[] value){
//和01背包相比在于01背包从后向前遍历，由于使用到之前的状态，从后向前时前面的状态为0，确保了一个物品只使用了一次。
//完全背包使用从前向后遍历，前面的状态先遍历。此时后面的状态再计算时，使第i个物品重复使用。//动态规划int[] dp = new int[V+1];for(int i=1;i<N+1;i++){//顺序实现for(int j=weight[i-1];j<V+1;j++){dp[j] = Math.max(dp[j-weight[i-1]]+value[i-1],dp[j]);}}return dp[V];
}

背包问题

01背包

public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){int wLen = weight.length;//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值int[] dp = new int[bagWeight + 1];//遍历顺序：先遍历物品，再遍历背包容量for (int i = 0; i < wLen; i++){for (int j = bagWeight; j >= weight[i]; j--){dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}//打印dp数组for (int j = 0; j <= bagWeight; j++){System.out.print(dp[j] + " ");}
}

完全背包

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){int wLen = weight.length;//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值int[] dp = new int[bagWeight + 1];//遍历顺序：先遍历物品，再遍历背包容量for (int i = 0; i < wLen; i++){for (int j = weight[i]; j <= bagWeight; j++){dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}//打印dp数组for (int j = 0; j <= bagWeight; j++){System.out.print(dp[j] + " ");}
}

装满背包

递推公式一般为：

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

81、兑换零钱(一)

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

import java.util.*;public class Solution {public int minMoney (int[] arr, int aim) {// write code hereint maxNum = aim + 1; //边界条件int[] dp = new int[aim + 1];//凑齐零钱的最小硬币数Arrays.fill(dp, maxNum); //初始化dp[0] = 0;//零元零种for (int i = 0; i < arr.length; i++) { //每种硬币for (int j = arr[i]; j <= aim; j++) { //总零钱数dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);//1个硬币 + 凑齐（总零钱 - 单个硬币的面值）的最小硬币数}}return dp[aim] == maxNum ? -1 : dp[aim];}
}

零钱兑换 II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

• 输入: amount = 5, coins = [1, 2, 5]
• 输出: 4

解释: 有四种方式可以凑成总金额:

• 5=5
• 5=2+2+1
• 5=2+1+1+1
• 5=1+1+1+1+1

//组合数是先物品后背包，装满背包

//排列数是先背包后物品，装满背包

class Solution {public int change(int amount, int[] coins) {//递推表达式int[] dp = new int[amount + 1];//初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装dp[0] = 1;for (int i = 0; i < coins.length; i++) {for (int j = coins[i]; j <= amount; j++) {dp[j] += dp[j - coins[i]];}}return dp[amount];}
}

82、连续子数组的最大和

• step 1：可以用dp数组表示以下标i为终点的最大连续子数组和。
• step 2：遍历数组，每次遇到一个新的数组元素，连续的子数组要么加上变得更大，要么这个元素本身就更大，要么会更小，更小我们就舍弃，因此状态转移为dp[i]=max(dp[i−1]+array[i],array[i])
• step 3：因为连续数组可能会断掉，每一段只能得到该段最大值，因此我们需要维护一个最大值。

public class Solution {public int FindGreatestSumOfSubArray(int[] array) {int pre = array[0], ans = array[0];for (int i = 1; i < array.length; i++) {pre = pre > 0 ? pre + array[i] : array[i];ans = Math.max(ans, pre);}return ans;}
}

83、编辑距离(一)

import java.util.*;public class Solution {public int editDistance (String str1, String str2) {// write code hereint r = str1.length();int c = str2.length();int[][] dp = new int[r + 1][c + 1];//初始化,空对任何字符串都要编辑（添加）for (int i = 1; i < r + 1; i++) {dp[i][0] = dp[i - 1][0] + 1;}for (int i = 1; i < c + 1; i++) {dp[0][i] = dp[0][i - 1] + 1;}for (int i = 1; i < r + 1; i++) {for (int j = 1; j < c + 1; j++) {if (str1.charAt(i - 1) == str2.charAt(j - 1)) { //相等不需要编辑dp[i][j] = dp[i - 1][j - 1];} else {//不相等需要编辑dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;}}}return dp[r][c];}
}

84、正则表达式匹配

import java.util.*;public class Solution {public boolean match(String s, String p) {//dp[i][j] 表示 s的前i个字符与 p中的前j个字符是否能够匹配int n = s.length();int m = p.length();boolean[][] dp = new boolean[n + 1][m + 1];dp[0][0] = true;for(int i = 0; i < n + 1; i++){for(int j = 1; j < m + 1; j++){if(p.charAt(j - 1) != '*'){dp[i][j] = i >= 1 && j >= 1 && dp[i - 1][j - 1] && isMath(s, p, i, j) ;}else{//* 匹配零个boolean mathZero = j >= 2 && dp[i][j - 2];//* 匹配多个boolean matchMany = i >= 1 && j >= 1 && dp[i - 1][j] && isMath(s, p, i, j - 1);dp[i][j] = mathZero || matchMany;}}}return dp[n][m];}private boolean isMath(String s, String p, int i, int j){return s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.';}
}

85、最长的括号子串

• 一个合法的括号序列需要满足以下两个条件：

  1. 任意前缀中左括号的数量 ≥≥ 右括号的数量；
  2. 左右括号数量相等。

  因此可以根据首次不合法的右括号（右括号数量首次大于左括号数量的位置）将原字符串划分成多段，可以看出，最长有效括号一定在段内产生；之后在每一段内找到所有合法括号序列，求出最大值即可。具体算法如下：

  1. 遇到左括号，将下标入栈；
  2. 遇到右括号：
     1. 如果栈不空，将栈顶元素出栈，与当前右括号匹配：
        1. 出栈后栈不空，则栈顶元素的下一个位置开始即为合法序列；
        2. 出栈后栈为空，则当前段起始点开始都为合法序列；
     2. 如果栈为空，说明此时右括号为首次不合法的右括号，更新段起始位置。

import java.util.*;
public class Solution {public int longestValidParentheses (String s) {int res = 0;//记录上一次连续括号结束的位置int start = -1;Stack<Integer> st = new Stack<Integer>();for (int i = 0; i < s.length(); i++) {//左括号入栈if (s.charAt(i) == '(')st.push(i);//右括号else {//如果右括号时栈为空，不合法，设置为结束位置if (st.isEmpty())start = i;else {//弹出左括号st.pop();//栈中还有左括号，说明右括号不够，减去栈顶位置就是长度if (!st.empty())res = Math.max(res, i - st.peek());//栈中没有括号，说明左右括号行号，减去上一次结束的位置就是长度elseres = Math.max(res, i - start);}}}return res;}
}

86、打家劫舍(一)

import java.util.*;public class Solution {public int rob (int[] nums) {// write code hereint[] dp = new int[nums.length + 1];//最多能偷多少钱dp[0] = 0;//无人可偷 为 0dp[1] = nums[0];//初始化for (int i = 2; i < nums.length + 1; i++) {dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]); //dp[i-1]是上家的价值，nums[i-1]+dp[i-2]是这家和上上家价值}return dp[nums.length];}
}

87、打家劫舍(二)

在原先的方案中第一家和最后一家不能同时取到。

import java.util.*;public class Solution {public int rob (int[] nums) {// write code hereint[] dp = new int[nums.length + 1];dp[1] = nums[0];//偷第一家int res = 0;for (int i = 2; i < nums.length; i++) { //不偷最后一家dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);}res = dp[nums.length - 1];dp[1] = 0; //不偷第一家for (int i = 2; i < nums.length  + 1; i++) { //偷最后一家dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);}res  = Math.max(res, dp[nums.length]);return res;}
}

88、买卖股票的最好时机(一)

import java.util.*;public class Solution {public int maxProfit (int[] prices) {// write code hereint ans = 0, minPrice = prices[0];for(int i = 1; i < prices.length; i++){ans = Math.max(ans, prices[i] - minPrice);minPrice = Math.min(minPrice, prices[i]);}return ans;}
}

89、买卖股票的最好时机(二)

import java.util.*;public class Solution {public int maxProfit (int[] prices) {// write code hereint ans = 0;for(int i = 1; i < prices.length; i++){ans += Math.max(prices[i] - prices[i - 1], 0);}return ans;}
}

90、买卖股票的最好时机(三)

import java.util.*;public class Solution {public int maxProfit (int[] prices) {int n = prices.length;int buy1 = -prices[0], sell1 = 0;int buy2 = -prices[0], sell2 = 0;for (int i = 1; i < n; ++i) {buy1 = Math.max(buy1, -prices[i]);sell1 = Math.max(sell1, buy1 + prices[i]);buy2 = Math.max(buy2, sell1 - prices[i]);sell2 = Math.max(sell2, buy2 + prices[i]);}return sell2;}
}

91、主持人调度

import java.util.*;
public class Solution {public int minmumNumberOfHost (int n, int[][] startEnd) {int[] start = new int[n];int[] end = new int[n];//分别得到活动起始时间for (int i = 0; i < n; i++) {start[i] = startEnd[i][0];end[i] = startEnd[i][1];}//单独排序Arrays.sort(start);Arrays.sort(end);int res = 0;int j = 0;for (int i = 0; i < n; i++) {//新开始的节目大于上一轮结束的时间，主持人不变if (start[i] >= end[j])j++;else//主持人增加res++;}return res;}
}

92、旋转数组

import java.util.*;public class Solution {/* 旋转数组* @param n int整型 数组长度* @param m int整型 右移距离* @param a int整型一维数组 给定数组* @return int整型一维数组*/public int[] solve (int n, int m, int[] a) {// write code herem = m % n; //取余，因为每次长度为n的旋转数组相当于没有变化reverse(a,0,a.length - 1);//1次翻转reverse(a,0,m-1);//2次翻转reverse(a,m,a.length - 1);//3次翻转return a;}private void reverse(int[] a, int l, int r) {while(l < r){int temp = a[l];a[l] = a[r];a[r] = temp;	l++;r--;}}
}

93、字符串变形

import java.util.*;public class Solution {public String trans(String s, int n) {// write code hereString[] ss = s.split(" ",-1);//空格分隔StringBuilder sb = new StringBuilder();for (int i = ss.length - 1; i >= 0 ; i--) {//逆序遍历for (int j = 0; j < ss[i].length(); j++) {char ch = ss[i].charAt(j);//取字符并编写sb.append(Character.isLowerCase(ch)?Character.toUpperCase(ch):Character.toLowerCase(ch));}sb.append(" ");}return sb.toString().substring(0,sb.length() - 1);}
}

94、最长公共前缀

• step 1：处理数组为空的特殊情况。
• step 2：因为最长公共前缀的长度不会超过任何一个字符串的长度，因此我们逐位就以第一个字符串为标杆，遍历第一个字符串的所有位置，取出字符。
• step 3：遍历数组中后续字符串，依次比较其他字符串中相应位置是否为刚刚取出的字符，如果是，循环继续，继续查找，如果不是或者长度不足，说明从第i位开始不同，前面的都是公共前缀。
• step 4：如果遍历结束都相同，最长公共前缀最多为第一个字符串。

import java.util.*;public class Solution {/** @param strs string字符串一维数组* @return string字符串*/public String longestCommonPrefix (String[] strs) {// write code hereif (strs.length == 0) return "";for (int i = 0; i < strs[0].length(); i++) {//第一个字符串的每位for (int j = 1; j < strs.length; j++) { //其他字符串//如果不是或者长度不足，说明从第i位开始不同，前面的都是公共前缀。if (i == strs[j].length() || strs[0].charAt(i) != strs[j].charAt(i))return strs[0].substring(0, i);}}return strs[0];//都相同，最长公共前缀最多为第一个字符串。}
}

95、大数加法

import java.util.*;public class Solution {/* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可* 计算两个数之和* @param s string字符串 表示第一个整数* @param t string字符串 表示第二个整数* @return string字符串*/public String solve (String s, String t) {// write code hereif (s == null || s.length() == 0) return t;if (t == null || t.length() == 0) return s;int carry = 0;//进位int i = s.length() - 1;//s的末位对应数字的第0位int j = t.length() - 1;StringBuilder sb = new StringBuilder();while (i >= 0 || j >= 0 || carry != 0) {int num1 = i >= 0 ? s.charAt(i) - '0' : 0;int num2 = j >= 0 ? t.charAt(j) - '0' : 0;int sum = num1 + num2 + carry;//本次计算结果carry = sum / 10;sb.append(sum % 10);i--;j--;//更新}return sb.reverse().toString();}
}

96、合并两个有序的数组

import java.util.*;
public class Solution {public void merge(int A[], int m, int B[], int n) {//归并的过程if (A == null || B == null || A.length == 0 || B.length == 0) return;int l = 0;int r = 0;int index = 0;//helper的下标int[] helper = new int[m + n];while (l < m && r < n) {if (A[l] <= B[r]) {helper[index++] = A[l++];} else {helper[index++] = B[r++];}}while (l < m) {helper[index++] = A[l++];}while (r < n) {helper[index++] = B[r++];}for (int i = 0; i < m + n; i++) {A[i] = helper[i];}}
}

97、合并区间

import java.util.*;
/* Definition for an interval.* public class Interval {*     int start;*     int end;*     Interval() { start = 0; end = 0; }*     Interval(int s, int e) { start = s; end = e; }* }*/
public class Solution {public ArrayList<Interval> merge(ArrayList<Interval> intervals) {ArrayList<Interval> res = new ArrayList<>();if (intervals == null || intervals.size() == 0) return res;//将乱序的intervals变为升序intervals.sort((o1, o2)->(o1.start - o2.start));res.add(intervals.get(0));//将第一个放入作为初始值int index = 0;//res的最后一个序号for (int i = 1; i < intervals.size(); i++) {Interval cur = intervals.get(i);Interval cmp = res.get(index);if (cur.start <= cmp.end) {cmp.end = Math.max(cur.end, cmp.end);} else {res.add(cur);index++;}}return res;}
}

98、反转字符串

import java.util.*;
public class Solution {public String solve (String str) {char[] ans = str.toCharArray();int len = str.length();for(int i = 0 ; i < len ;i++){ans[i] = str.charAt(len-1-i);}return new String(ans);}
}

滑动窗口

99、最小覆盖子串

使用双指针 i、j，其中 i 遍历字符串 s，j 用来寻找满足条件的位置，使得 j 到 i 的字符串刚好包含字符串 t 的所有字符。

双指针一个left 一个 right，中间夹着的就是子串，right不停往右走，一旦之间的子串符合要求，left收缩直到长度最小，当子串不符合要求的时候，right 继续往右走。

import java.util.*;public class Solution {public String minWindow (String S, String T) {// write code hereint[] hs = new int[128];//mapint[] ht = new int[128];for (int i = 0; i < T.length(); i++) {ht[T.charAt(i)]++;}String res = null;// i 是快 j是慢指针for (int i = 0, j = 0, cnt = 0; i < S.length(); i++) {//添加当前字符串hs[S.charAt(i)]++;if (hs[S.charAt(i)] <= ht[S.charAt(i)]) cnt++; //更新有效字符串数量//去除冗余字符,j 向前移动while (j <= i  &&  hs[S.charAt(j)] > ht[S.charAt(j)]) hs[S.charAt(j++)]--;//完全覆盖if (cnt == T.length()) {// 为空或者大于窗口数量if (res == null || res.length() > i - j + 1) {res = S.substring(j, i + 1);}}}return res == null ? "" : res;}
}

100、最长无重复子数组

使用一个数组记录每个字符上次出现的位置，在遍历的同时移动窗口左边界，最后返回窗口长度的最大值即可。

import java.util.*;public class Solution {public int maxLength (int[] arr) {// write code here// 滑动窗口HashMap<Integer, Integer> map = new HashMap<>();int res = 0;//设置窗口左右边界for (int i = 0, j = 0; i < arr.length; i++) {map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);while (map.get(arr[i]) > 1) { //重复//窗口左侧右移，减去重复该数字的次数map.put(arr[j], map.get(arr[j++]) - 1);}res = Math.max(res, i - j + 1);}return res;}
}

49、滑动窗口的最大值

import java.util.*;
public class Solution {public ArrayList<Integer> maxInWindows(int [] num, int size) {Deque<Integer> deque = new LinkedList<>();//双端队列，单调队列，维护窗口的最大值下标ArrayList<Integer> res = new ArrayList<>();if (num == null || size == 0 || size > num.length) return res;for (int i = 0; i < num.length; i++) {while (!deque.isEmpty() && num[deque.peekLast()] < num[i]) {//维护单调队列deque.pollLast();}deque.offerLast(i);//放入下标while (!deque.isEmpty() && deque.peekFirst() < (i - size + 1)){deque.pollFirst();}if (i - size + 1 >= 0) {res.add(num[deque.peekFirst()]);//最开始的初始化用}}return res;}
}

101、盛水最多的容器

• 使用首尾双指针，具体过程如下：
  • 求出当前双指针对应的容器的容量；
  • 由于对应数字较小的那个指针以后不可能作为容器的边界了，将其丢弃，并移动对应的指针。（移动短板）

import java.util.*;public class Solution {public int maxArea (int[] height) {// write code hereint ans = 0;int l = 0, r = height.length - 1;while (l < r) {ans = Math.max(ans, Math.min(height[l],height[r]) * (r - l));//计算盛水选择短板if (height[l] < height[r])  ++l;else --r; //移动短板}return ans;}
}

102、接雨水问题

知识点：双指针

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。

木桶原理，从当前节点往左找最高的高度，往右找最高的高度，这两个高度我们可以看做是木桶的两个木板，能接的雨水由最短的那块决定，累加每个位置能存的雨水量即可。

import java.util.*;public class Solution {public long maxWater (int[] arr) {// write code hereint l = 0, r = arr.length - 1;int ans = 0, lmax = 0, rmax = 0;while (l < r) {//找左右两边最高的高度lmax = Math.max(lmax, arr[l]);rmax = Math.max(rmax, arr[r]);//接雨水由最短的板子决定，计算雨量和移动短板if (lmax < rmax) {ans += lmax - arr[l];l++;} else {ans += rmax - arr[r];r--;}}return ans;}
}

103、分糖果问题

• 根据每个孩子左（右）侧比当前孩子得分低的相邻单调递增（减）区间内的孩子数量，确定能分配的最少糖果数量，最后累加即可。

import java.util.*;public class Solution {public int candy (int[] arr) {// write code hereint n = arr.length;int[] left = new int[n];int[] right = new int[n];for (int i = 1; i < n; i++) {//左侧单调递增区间if (arr[i] > arr[i - 1]) left[i] = left[i - 1] + 1;}for (int i = n - 2; i >= 0; i--) {//右侧单调递减区间if (arr[i] > arr[i + 1]) right[i] = right[i + 1] + 1;}int ans = 0;for (int i = 0; i < n; i++) {ans += Math.max(left[i], right[i]) + 1;}return ans;}
}

104、螺旋矩阵

维护未遍历数据的上下左右的边界，每次循环获取最外侧一圈边界上的数据，遍历结束后将边界向中心移动，直至边界相交结束循环。

import java.util.ArrayList;
public class Solution {public ArrayList<Integer> spiralOrder(int[][] matrix) {ArrayList<Integer> res = new ArrayList<Integer>();if (matrix.length == 0) return res;int top = 0, down = matrix.length - 1, left = 0, right = matrix[0].length - 1;while(top <= down && left <= right){for(int i = left; i <= right;i++){//从左往右。在top维度res.add(matrix[top][i]);}top++;if(top > down) break;//边界判断for(int i = top; i <= down;i++){//从上往下。在right维度res.add(matrix[i][right]);}right--;if(left > right) break;//边界判断for(int i = right; i >= left;i--){//从右往左。在down维度res.add(matrix[down][i]);}down--;if(top > down) break;//边界判断for(int i = down; i >= top;i--){//从下往上。在left维度res.add(matrix[i][left]);}left++;if(left > right) break;//边界判断}return res;}
}

105、顺时针旋转矩阵

具体做法:**

• step 1：遍历矩阵的下三角矩阵，将其与上三角矩阵对应的位置互换，其实就是数组下标交换后的互换。
• step 2：遍历矩阵每一行，将每一行看成一个数组使用reverse函数翻转。

import java.util.*;public class Solution {public int[][] rotateMatrix(int[][] mat, int n) {// write code here//转置矩阵，下三角和上三角互换for(int i = 0; i < mat.length; i++){for(int j = 0; j< i ;j++){int temp = mat[i][j];mat[i][j] = mat[j][i];mat[j][i] = temp;}}//水平翻转for(int i = 0; i < mat.length; i++){for(int j = 0; j< mat[0].length / 2 ;j++){int temp = mat[i][j];mat[i][j] = mat[i][mat[0].length - 1 - j];mat[i][mat[0].length - 1 - j] = temp;}}return mat;}}

106、LRU

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

解析

哈希表 + 双向链表，哈希表记录 key 和链表节点的映射关系，当需要淘汰时，从链表尾部删除节点；当需要更新时间戳时，通过哈希表获取节点，将其删除并插入到链表头。

import java.util.*;public class Solution {//采用hashmap + 双向链表private class DNode {int key;int vlaue;DNode pre;DNode next;public DNode() {key = 0;vlaue = 0;this.pre = null;this.next = null;}public DNode(int key, int value) {this.key = key;this.vlaue = value;this.pre = null;this.next = null;}}private Map<Integer, DNode> map = new HashMap<>();private int size = 0;//当前容量private int maxCapacity = 0; // 最大容量private DNode head = null; // 头节点放的最近使用的private DNode tail = null;  //尾结点放不使用的public Solution(int capacity) {// write code herethis.maxCapacity = capacity;this.size = 0;head = new DNode();tail = new DNode();head.next = tail;tail.pre  = head;}public int get(int key) {// write code hereif (!map.containsKey(key)) {return -1;//不含这个key} else {DNode node = map.get(key);moveToHead(node);//将该节点移到前面return node.vlaue;}}public void set(int key, int value) {// write code hereif (!map.containsKey(key)) {//不存在直接放入DNode node = new DNode(key, value);map.put(key, node); //map放入对应键size++;insertToHead(node);//双向链表插入node//超过容量if (size > maxCapacity) {deleteTailNode();//删除最后一个不用的size--;}} else {DNode node = map.get(key);//已存在更新值node.vlaue = value;moveToHead(node);//将该节点移到前面}}private void moveToHead(DNode node) {//1、删除该节点deleteNode(node);//2、插入到头节点insertToHead(node);}private void deleteNode(DNode node) {node.pre.next = node.next;node.next.pre = node.pre;node.next = null;node.pre = null;}private void insertToHead(DNode node) {node.next = head.next;node.pre = head;head.next = node;node.next.pre = node;}private void deleteTailNode() {DNode node = tail.pre;//双向链表删除对应节点map.remove(node.key);//map删除对应的键deleteNode(node);}
}/* Your Solution object will be instantiated and called as such:* Solution solution = new Solution(capacity);* int output = solution.get(key);* solution.set(key,value);*/

107、设计LFU缓存结构

双哈希表 + 双向链表-一个哈希表存key-key 和 value-node；一个哈希表存key-频率 和 value-同一个频率的双向链表

import java.util.*;
public class Solution {//设置节点结构static class Node{ int freq;int key;int val;//初始化public Node(int freq, int key, int val) {this.freq = freq;this.key = key;this.val = val;}}//频率到双向链表的哈希表private Map<Integer, LinkedList<Node> > freq_mp = new HashMap<>();//key到节点的哈希表private Map<Integer, Node> mp = new HashMap<>();//记录缓存剩余容量private int size = 0; //记录当前最小频次private int min_freq = 0;public int[] LFU (int[][] operators, int k) {//构建初始化连接//链表剩余大小this.size = k;ArrayList<Integer> res = new ArrayList<>();for (int i = 0; i < operators.length; i++){if (operators[i][0] == 1){set(operators[i][1], operators[i][2]);}else{res.add(get(operators[i][1]));}}int[] ans = new int[res.size()];for (int i = 0; i < ans.length; i++){ans[i] = res.get(i);}return ans;}//调用函数时更新频率或者val值private void update(Node node, int key, int value) { //找到频率int freq = node.freq;//原频率中删除该节点freq_mp.get(freq).remove(node); //哈希表中该频率已无节点，直接删除if(freq_mp.get(freq).isEmpty()){ freq_mp.remove(freq);//若当前频率为最小，最小频率加1if(min_freq == freq) min_freq++;}if(!freq_mp.containsKey(freq + 1))freq_mp.put(freq + 1, new LinkedList<Node>());//插入频率加一的双向链表表头，链表中对应：freq key valuefreq_mp.get(freq + 1).addFirst(new Node(freq + 1, key, value)); mp.put(key, freq_mp.get(freq + 1).getFirst());}//set操作函数private void set(int key, int value) {//在哈希表中找到key值if(mp.containsKey(key)) //若是哈希表中有，则更新值与频率update(mp.get(key), key, value);else{ //哈希表中没有，即链表中没有if(size == 0){//满容量取频率最低且最早的删掉int oldkey = freq_mp.get(min_freq).getLast().key; //频率哈希表的链表中删除freq_mp.get(min_freq).removeLast(); if(freq_mp.get(min_freq).isEmpty()) freq_mp.remove(min_freq); //链表哈希表中删除mp.remove(oldkey); }//若有空闲则直接加入，容量减1else size--; //最小频率置为1min_freq = 1; //在频率为1的双向链表表头插入该键if(!freq_mp.containsKey(1))freq_mp.put(1, new LinkedList<Node>());freq_mp.get(1).addFirst(new Node(1, key, value)); //哈希表key值指向链表中该位置mp.put(key, freq_mp.get(1).getFirst()); }}//get操作函数private int get(int key) {int res = -1;//查找哈希表if(mp.containsKey(key)){ Node node = mp.get(key);//根据哈希表直接获取值res = node.val;//更新频率 update(node, key, res); }return res;}
}