1BnnW8rtw7M9
85.最大矩形 classSolution{ publicintmaximalRectangle(char[][]matrix){ intm=matrix.length,n=matrix[0].length; int[]heights=newint[n]; intres=0; for(inti=0;i<m;i){ for(intj=0;j<n;j){ if(matrix[i][j]'1')heights[j]; elseheights[j]=0; } res=Math.max(res,largestRectangleArea(heights)); } returnres; ...
84.柱状图中最大的矩形 双指针 classSolution{ publicintlargestRectangleArea(int[]heights){ intn=heights.length; int[]minLeftIndex=newint[n]; int[]minRightIndex=newint[n]; minLeftIndex[0]=-1; for(inti=1;i<n;i){ intt=i1; while(t>=0&&heights[t]>=heights[i])t=minLeftIndex[t]; minLeftIndex[i]=t; } ...
79.单词搜索 不要用int[][]dir={{0,1},{1,0},{0,-1},{-1,0}};的写法了，下面这种比较好记。 classSolution{ boolean[][]vis; publicbooleanexist(char[][]board,Stringword){ intm=board.length,n=board[0].length; vis=newboolean[m][n]; for(inti=0;i<m;i){ for(intj=0;j<n;j){ if(dfs(board,i,j,word,0))returntrue; } } returnfal...
76.最小覆盖子串 滑动窗口 经典写法 classSolution{ publicStringminWindow(Strings,Stringt){ HashMap<Character,Integer>window=newHashMap<>(),need=newHashMap<>(); for(charc:t.toCharArray())need.merge(c,1,Integer::sum); intcnt=0,start=0,len=Integer.MAX_VALUE; for(intl=0,r=0;r<s.length();r){ //窗口...
75.颜色分类 双指针——快慢指针 classSolution{ publicvoidsortColors(int[]nums){ intn=nums.length; intp0=0; for(inti=0;i<n;i){ if(nums[i]0){ swap(nums,p0,i); p0; } } intp1=p0; for(inti=p0;i<n;i){ if(nums[i]1){ swap(nums,p1,i); p1; } } } voidswap(int[]nums,intx,inty){ inttmp=nums[x]; nums[x]=nums[y]; num...
53.最大子数组和 动态规划 classSolution{ publicintmaxSubArray(int[]nums){ intn=nums.length; int[]dp=newint[n];//dp[i]表示以nums[i]为结尾的子数组的最大和 dp[0]=nums[0]; intres=dp[0]; for(inti=1;i<n;i){ dp[i]=Math.max(dp[i1]+nums[i],nums[i]); res=Math.max(res,dp[i]); } returnres; } } 动态规划——压缩空间 classSolution{ publici...
70.爬楼梯 动态规划 classSolution{ publicintclimbStairs(intn){ if(n<=2)returnn; int[]dp=newint[n+1]; dp[1]=1; dp[2]=2; for(inti=3;i<=n;i){ dp[i]=dp[i1]+dp[i2]; } returndp[n]; } } 压缩空间 classSolution{ publicintclimbStairs(intn){ if(n<=2)returnn; inta=1; intb=2; for(inti=3;i<=n;i){ intc=a+b;...
72.编辑距离 动态规划 classSolution{ publicintminDistance(Stringword1,Stringword2){ intm=word1.length(),n=word2.length(); int[][]dp=newint[m+1][n+1]; for(inti=1;i<=m;i)dp[i][0]=i; for(inti=1;i<=n;i)dp[0][i]=i; for(inti=1;i<=m;i){ for(intj=1;j<=n;j){ if(word1.charAt(i1)word2.charAt(j1)){ dp[i]...
64.最小路径和 动态规划 classSolution{ publicintminPathSum(int[][]grid){ intm=grid.length,n=grid[0].length; for(inti=1;i<m;i)grid[i][0]+=grid[i1][0]; for(inti=1;i<n;i)grid[0][i]+=grid[0][i1]; for(inti=1;i<m;i){ for(intj=1;j<n;j){ grid[i][j]+=Math.min(grid[i1][j],grid[i][j1]); } } returngrid[m...
55.跳跃游戏 贪心 classSolution{ publicbooleancanJump(int[]nums){ intn=nums.length; intfar=nums[0];//最远距离 for(inti=0;i<n;i){ if(far<i)returnfalse;//最远也跳不到i,返回false far=Math.max(far,i+nums[i]);//更新最远距离 } returntrue; } }
56.合并区间 贪心，按左端点从小到大排序。 classSolution{ publicint[][]merge(int[][]intervals){ Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));//按左端点从小到大排序 List<int[]>res=newArrayList<>(); intstart=intervals[0][0],end=intervals[0][1]; for(inti=1;i<intervals.length;i){ int[]cur=intervals[i...
48.旋转图像 classSolution{ publicvoidrotate(int[][]matrix){ intn=matrix.length; //沿对角线对称交换 for(inti=0;i<n;i){ for(intj=0;j<i;j){ inttmp=matrix[i][j]; matrix[i][j]=matrix[j][i]; matrix[j][i]=tmp; } } //沿中间一列左右翻转 for(inti=0;i<n;i){ for(intj=0;j<n/2;j){ inttmp=matrix[i][j]; matrix[i][j]=matri...
49.字母异位词分组 利用每个字符的出现次数进行编码 classSolution{ publicList<List<String>>groupAnagrams(String[]strs){ HashMap<String,List<String>>map=newHashMap<>(); for(Stringstr:strs){ Stringcode=encode(str); map.putIfAbsent(code,newArrayList<>()); map.get(code).add(str); } returnne...
42.接雨水 双指针 classSolution{ publicinttrap(int[]height){ intn=height.length,res=0; intl=0,r=n1; intl_max=height[0],r_max=height[n1]; while(l<r){ if(height[l]<height[r]){ l_max=Math.max(l_max,height[l]); res+=l_maxheight[l]; l; }else{ r_max=Math.max(r_max,height[r]); res+=r_maxheight[r]; r--; }...
62.不同路径 动态规划 classSolution{ publicintuniquePaths(intm,intn){ int[][]dp=newint[m][n];//dp[i][j]表示从起点到达(i,j)的路径数 for(inti=0;i<m;i)dp[i][0]=1; for(inti=0;i<n;i)dp[0][i]=1; for(inti=1;i<m;i){ for(intj=1;j<n;j){ dp[i][j]=dp[i1][j]+dp[i][j1]; } } returndp[m1][n1]; } }
46.全排列 回溯 classSolution{ List<List<Integer>>res=newArrayList<>(); List<Integer>path=newArrayList<>(); boolean[]vis; publicList<List<Integer>>permute(int[]nums){ vis=newboolean[nums.length]; backtrack(nums); returnres; } voidbacktrack(int[]nums){ if(path....
21.合并两个有序链表 迭代 classSolution{ publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){ ListNodel1=list1,l2=list2; ListNodedummy=newListNode(-1),d=dummy; while(l1!=null&&l2!=null){ if(l1.val<l2.val){ d.next=l1; l1=l1.next; }else{ d.next=l2; l2=l2.next; } d=d.next; } d.next=l1null?l2:l1...
19.删除链表的倒数第N个结点 classSolution{ publicListNoderemoveNthFromEnd(ListNodehead,intn){ ListNodedummy=newListNode(-1,head),slow=dummy,fast=head; for(inti=0;i<n;i)fast=fast.next; while(fast!=null){ slow=slow.next; fast=fast.next; } slow.next=slow.next.next; returndummy.next; } }
17.电话号码的字母组合 回溯 classSolution{ List<String>res=newArrayList<>(); StringBuilderpath=newStringBuilder(); String[]map={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; publicList<String>letterCombinations(Stringdigits){ if(digits.length()0)returnres; backtrack(digits,0); r...
前言 在刷题过程中遇到下面这条语句，看起来十分简洁，但是没看明白其中用到的语法，故学习了一下。 HashMap<Character,String>map=newHashMap<>(){{put('2',"abc");put('3',"def");put('4',>"ghi");put('5',"jkl");put('6',"mno");put('7',"pqrs");put('8',"tuv");put('9',"wxyz");}}; 这里涉及到两个语法，匿名内部类和实例初始化块。 匿名内部类 匿名内部类是一种没有名字的局部内部类。它通常用于创建一个只...