1BnnW8rtw7M9
34.在排序数组中查找元素的第一个和最后一个位置 二分 classSolution{ publicint[]searchRange(int[]nums,inttarget){ intl=0,r=nums.length1; while(l<r){ intmid=l+r>>1; if(nums[mid]>=target)r=mid; elsel=mid+1; } if(nums.length0||nums[l]!=target)returnnewint[]{-1,-1}; intstart=l; l=0; r=nums.length1; while(l<r)...
39.组合总和 回溯 classSolution{ List<List<Integer>>res=newArrayList<>(); List<Integer>path=newArrayList<>(); publicList<List<Integer>>combinationSum(int[]candidates,inttarget){ backtrack(candidates,target,0); returnres; } voidbacktrack(int[]candidates,inttarge...
32.最长有效括号 栈 classSolution{ publicintlongestValidParentheses(Strings){ Deque<Integer>stack=newArrayDeque<>(); stack.push(-1); intres=0; for(inti=0;i<s.length();i){ if(s.charAt(i)'('){ stack.push(i); }else{ stack.pop(); if(stack.isEmpty()){ stack.push(i); }else{ res=Math.max(res,ista...
33.搜索旋转排序数组 转化为两次二分。 classSolution{ publicintsearch(int[]nums,inttarget){ intl=0,r=nums.length1; //找到分隔点，大于nums[0]的最后一个数（最大的数） while(l<r){ intmid=l+r+1>>1; if(nums[0]>nums[mid])r=mid1; elsel=mid; } if(nums[0]>target)r=nums.length1; elsel=0; //在有序数组中找目标值 while(l<r){ intmid=l+r+...
23.合并K个升序链表 优先级队列 classSolution{ publicListNodemergeKLists(ListNode[]lists){ ListNodedummy=newListNode(-1),d=dummy; PriorityQueue<ListNode>pq=newPriorityQueue<>((a,b)->Integer.compare(a.val,b.val)); for(ListNodehead:lists){ if(head!=null)pq.offer(head); } while(!pq.isEmpty()){ List...
22.括号生成 回溯 classSolution{ List<String>res=newArrayList<>(); StringBuilderpath=newStringBuilder();//path推荐这种写法 publicList<String>generateParenthesis(intn){ backtrack(n,0,0); returnres; } voidbacktrack(intn,intl,intr){ if(r>l||l>n||r>n)return; if(ln&&rn){ res.add...
31.下一个排列 classSolution{ publicvoidnextPermutation(int[]nums){ intn=nums.length,i=n2; while(i>=0){ if(nums[i]<nums[i+1])break; i--; } if(i>=0){ intj=n1; while(nums[j]<=nums[i])j--; swap(nums,i,j); } reverse(nums,i+1,n1); } voidreverse(int[]nums,intl,intr){ while(l<r){ swap(nums,l...
剑指Offer25.合并两个排序的链表 迭代 classSolution{ publicListNodemergeTwoLists(ListNodel1,ListNodel2){ ListNodedummy=newListNode(),h=dummy; while(l1!=null&&l2!=null){ if(l1.val<l2.val){ h.next=l1; l1=l1.next; }else{ h.next=l2; l2=l2.next; } h=h.next; } h.next=l1!=null?l1:l2; returndummy.next; } } 递...
剑指Offer21.调整数组顺序使奇数位于偶数前面 相向双指针 classSolution{ publicint[]exchange(int[]nums){ intl=0,r=nums.length1; while(l<r){ while(l<r&&(nums[l]&1)1)l; while(l<r&&(nums[r]&1)0)r--; inttmp=nums[l]; nums[l]=nums[r]; nums[r]=tmp; } returnnums; } } 同向双指针（快慢双指针） classSolution{ p...
剑指Offer15.二进制中1的个数 每次消去末位的1 publicclassSolution{ //youneedtotreatnasanunsignedvalue publicinthammingWeight(intn){ intres=0; while(n!=0){ n&=n1; res; } returnres; } }
剑指Offer17.打印从1到最大的n位数 dfs函数只输出n位数的情况，相比于让一个函数输出1到最大的n位数可以大大简化。 小技巧：控制循环开始的起点。 classSolution{ List<Integer>res=newArrayList<>(); publicint[]printNumbers(intn){ for(inti=1;i<=n;i){ dfs(i,""); } returnres.stream().mapToInt(x->x).toArray(); } voiddfs(intn,Stringnum){ if(num.length(...
剑指Offer56I.数组中数字出现的次数 位运算 classSolution{ publicint[]singleNumbers(int[]nums){ intn=0,x=0,y=0,d=1; for(intnum:nums)n^=num; d=n&-n;//返回n的最后一位1 for(intnum:nums){ if((d&num)0)x^=num; elsey^=num; } returnnewint[]{x,y}; } }
剑指Offer48.最长不含重复字符的子字符串 滑动窗口 classSolution{ publicintlengthOfLongestSubstring(Strings){ HashSet<Character>set=newHashSet<>(); intres=0; for(intl=0,r=0;r<s.length();r){ charc=s.charAt(r); while(set.contains(c)){ chard=s.charAt(l); set.remove(d); l; } set.add(c); res=Math.max(res,rl...
剑指Offer40.最小的k个数 优先级队列 classSolution{ publicint[]getLeastNumbers(int[]arr,intk){ PriorityQueue<Integer>pq=newPriorityQueue<>((a,b)->Integer.compare(b,a)); for(intnum:arr){ pq.offer(num); if(pq.size()>k)pq.poll(); } returnpq.stream().mapToInt(x->x).toArray(); } } 快速排序 classSo...
剑指Offer28.对称的二叉树 递归 classSolution{ publicbooleanisSymmetric(TreeNoderoot){ if(rootnull)returntrue; returnhelp(root.left,root.right); } booleanhelp(TreeNodeleft,TreeNoderight){ if(leftnull&&rightnull)returntrue; if(leftnull||rightnull)returnfalse; if(left.val!=right.val)returnfalse; retu...
剑指Offer26.树的子结构 两重遍历 classSolution{ publicbooleanisSubStructure(TreeNodeA,TreeNodeB){ if(Bnull||Anull)returnfalse; if(isContain(A,B))returntrue; returnisSubStructure(A.left,B)||isSubStructure(A.right,B); } booleanisContain(TreeNodeA,TreeNodeB){ if(Bnull)returntrue; if(Anull)returnfalse; if(A.val!...
剑指Offer24.反转链表 迭代 classSolution{ publicListNodereverseList(ListNodehead){ ListNodepre=null,cur=head; while(cur!=null){ ListNodenext=cur.next; cur.next=pre; pre=cur; cur=next; } returnpre; } } 递归（使用额外参数） 和上面迭代的思想一样。 classSolution{ publicListNodereverseList(ListNodehead){ returnreverse(head,null);...
剑指Offer19.正则表达式匹配 初始化要考虑主串为空字符串，模式串为abc的形式。 一般情况时，根据模式串是普通字符、'.'、''分情况考虑。为''时，考虑匹配0次和匹配多次的情况，匹配多次时要注意判断前提是能匹配。 classSolution{ publicbooleanisMatch(Strings,Stringp){ intm=s.length(),n=p.length(); boolean[][]dp=newboolean[m+1][n+1]; dp[0][0]=true; for(inti=2;i<=n;i+=2){ if(p.charAt(i1)''){ dp[0][...
剑指Offer18.删除链表的节点 classSolution{ publicListNodedeleteNode(ListNodehead,intval){ ListNodedummy=newListNode(-1,head); ListNodepre=dummy; while(pre.next!=null&&pre.next.val!=val){ pre=pre.next; } pre.next=pre.next.next; returndummy.next; } }
剑指Offer16.数值的整数次方 快速幂算法 classSolution{ publicdoublemyPow(doublex,intn){ longb=n;//n=−2147483648时执行n=−n会因越界而赋值出错 if(n<0){ x=1/x; b=-b; } doubleres=1; while(b!=0){ if((b&1)1)res=x; x=x; b>>=1; } returnres; } }