剑指Offer42.连续子数组的最大和 动态规划 classSolution{ publicintmaxSubArray(int[]nums){ intn=nums.length; int[]dp=newint[n]; 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; } } 因为dp[i]只和前一项有关系，所以可以压缩空间。 classSolution{ publicintm...

剑指Offer41.数据流中的中位数 classMedianFinder{ PriorityQueue<Integer>pq1,pq2; /initializeyourdatastructurehere./ publicMedianFinder(){ pq1=newPriorityQueue<>((a,b)->Integer.compare(a,b));//返回最小的元素，存放较大的一半 pq2=newPriorityQueue<>((a,b)->Integer.compare(b,a));//返回最大的元素，存放较小的一半 } publ...

剑指Offer39.数组中出现次数超过一半的数字 摩尔投票法 classSolution{ publicintmajorityElement(int[]nums){ intres=nums[0]; intcnt=1; for(inti=1;i<nums.length;i){ if(nums[i]res)cnt; elsecnt--; if(cnt<0){ res=nums[i]; cnt=1; } } returnres; } }

剑指Offer38.字符串的排列 方法一 classSolution{ List<String>res=newArrayList<>(); boolean[]vis; publicString[]permutation(Strings){ vis=newboolean[s.length()]; char[]ch=s.toCharArray(); Arrays.sort(ch); backtrack(ch,newStringBuilder()); returnres.toArray(String[]::new); } voidbacktrack(char[]ch,...

10.正则表达式匹配 剑指Offer19.正则表达式匹配

15.三数之和 classSolution{ //先排序，用一个外层循环遍历每个数，内层循环用双指针，时间复杂度是O(n2) publicList<List<Integer>>threeSum(int[]nums){ List<List<Integer>>res=newArrayList<>(); intn=nums.length; Arrays.sort(nums); for(inti=0;i<n;i){ if(i>0&&nums[i]nums[i1])continue; intl=i+1,r=n...