资讯类网站建设资质要求,在什么网站上做外贸,国外最火的网站,我想开一家网店怎么开part1 – https://blog.csdn.net/qq_41080854/article/details/129204480
part2 – https://blog.csdn.net/qq_41080854/article/details/129224785 面试必刷101 Java题解 -- part 3动规五部曲71、斐波那契数列72、跳台阶73、最小花费爬楼梯74、最长公共子序列(二)75、最长公共…part1 – https://blog.csdn.net/qq_41080854/article/details/129204480
part2 – https://blog.csdn.net/qq_41080854/article/details/129224785
面试必刷101 Java题解 -- part 3动规五部曲71、斐波那契数列72、跳台阶73、最小花费爬楼梯74、最长公共子序列(二)75、最长公共子串76、最长上升子序列(一)77、最长连续序列78、不同路径的数目(一)79、把数字翻译成字符串80、把数字翻译成字符串2背包问题01背包完全背包装满背包81、兑换零钱(一)零钱兑换 II82、连续子数组的最大和83、编辑距离(一)84、正则表达式匹配85、最长的括号子串86、打家劫舍(一)87、打家劫舍(二)88、买卖股票的最好时机(一)89、买卖股票的最好时机(二)90、买卖股票的最好时机(三)91、主持人调度92、旋转数组93、字符串变形94、最长公共前缀95、大数加法96、合并两个有序的数组97、合并区间98、反转字符串滑动窗口99、最小覆盖子串100、最长无重复子数组49、滑动窗口的最大值101、盛水最多的容器102、接雨水问题103、分糖果问题104、螺旋矩阵105、顺时针旋转矩阵106、LRU107、设计LFU缓存结构动规五部曲
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化( length 1 一般不用初始化 length是一定要初始化的)确定遍历顺序举例推导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(target0 ||target1) return 1;if(target2) return 2;int []dpnew int[target1];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) {HashSetInteger 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[V1];for(int i1;iN1;i){//逆序实现for(int jV;jweight[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[V1];for(int i1;iN1;i){//顺序实现for(int jweight[i-1];jV1;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
解释: 有四种方式可以凑成总金额:
55522152111511111
//组合数是先物品后背包装满背包
//排列数是先背包后物品装满背包
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、最长的括号子串 一个合法的括号序列需要满足以下两个条件 任意前缀中左括号的数量 ≥≥ 右括号的数量左右括号数量相等。 因此可以根据首次不合法的右括号右括号数量首次大于左括号数量的位置将原字符串划分成多段可以看出最长有效括号一定在段内产生之后在每一段内找到所有合法括号序列求出最大值即可。具体算法如下 遇到左括号将下标入栈遇到右括号 如果栈不空将栈顶元素出栈与当前右括号匹配 出栈后栈不空则栈顶元素的下一个位置开始即为合法序列出栈后栈为空则当前段起始点开始都为合法序列 如果栈为空说明此时右括号为首次不合法的右括号更新段起始位置。
import java.util.*;
public class Solution {public int longestValidParentheses (String s) {int res 0;//记录上一次连续括号结束的位置int start -1;StackInteger st new StackInteger();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 ArrayListInterval merge(ArrayListInterval intervals) {ArrayListInterval 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 遍历字符串 sj 用来寻找满足条件的位置使得 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// 滑动窗口HashMapInteger, 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 ArrayListInteger maxInWindows(int [] num, int size) {DequeInteger deque new LinkedList();//双端队列单调队列维护窗口的最大值下标ArrayListInteger 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 ArrayListInteger spiralOrder(int[][] matrix) {ArrayListInteger res new ArrayListInteger();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 MapInteger, 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 MapInteger, LinkedListNode freq_mp new HashMap();//key到节点的哈希表private MapInteger, Node mp new HashMap();//记录缓存剩余容量private int size 0; //记录当前最小频次private int min_freq 0;public int[] LFU (int[][] operators, int k) {//构建初始化连接//链表剩余大小this.size k;ArrayListInteger 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 LinkedListNode());//插入频率加一的双向链表表头链表中对应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 LinkedListNode());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;}
}
