1BnnW8rtw7M9
剑指Offer13.机器人的运动范围 和剑指Offer12.矩阵中的路径是同一模板 classSolution{ intres=0; boolean[][]vis; publicintmovingCount(intm,intn,intk){ vis=newboolean[m][n]; dfs(0,0,m,n,k); returnres; } voiddfs(intx,inty,intm,intn,intk){ if(x<0||x>=m||y<0||y>=n||vis[x][y]||!check(x,y,k))return; res; vis[x][y]=tru...
剑指Offer27.二叉树的镜像 递归 classSolution{ publicTreeNodemirrorTree(TreeNoderoot){ if(rootnull)returnnull; TreeNodeleft=mirrorTree(root.left); TreeNoderight=mirrorTree(root.right); root.left=right; root.right=left; returnroot; } } 迭代 classSolution{ publicTreeNodemirrorTree(TreeNoderoot){ if(rootnull)r...
剑指Offer14I.剪绳子 和整数拆分是同一道题。 动态规划 classSolution{ publicintcuttingRope(intn){ int[]dp=newint[n+1];//dp[i]表示长度为i的绳子能得到的最大乘积 dp[2]=1; for(inti=3;i<=n;i){ for(intj=2;j<i;j){ dp[i]=Math.max(dp[i],Math.max(j(ij),jdp[ij])); } } returndp[n]; } } 贪心 每次拆出3是最优的。不过注意4不用拆，拆了反而会变小。 classSolution{ public...
剑指Offer35.复杂链表的复制 方法一 哈希表+两次遍历 classSolution{ publicNodecopyRandomList(Nodehead){ Nodedummy=newNode(-1),h=head,d=dummy; HashMap<Node,Node>map=newHashMap<>(); while(h!=null){ d.next=newNode(h.val); map.put(h,d.next); h=h.next; d=d.next; } h=head; d=dummy.next; while(h!=null){ d.random...
剑指Offer34.二叉树中和为某一值的路径 回溯 这里有个注意事项，path是List类型，需要显示回溯，如path.remove(path.size()1);。而target作为int类型不需要显示回溯，因为是不可变类型，类似的还有String。 这里不可变类型指的是：当变量作为形参传递给一个函数，在该函数内部修改了这个变量，回到主函数，如果该变量的值没有发生改变，则认为是不可变类型。 classSolution{ List<List<Integer>>res=newArrayList<>(); List<Integer>path=new...
剑指Offer32III.从上到下打印二叉树III classSolution{ publicList<List<Integer>>levelOrder(TreeNoderoot){ List<List<Integer>>res=newArrayList<>(); if(rootnull)returnres; Deque<TreeNode>queue=newArrayDeque<>(); queue.offer(root); while(!queue.isEmpty()){ intsize=queue.s...
剑指Offer32I.从上到下打印二叉树 classSolution{ publicint[]levelOrder(TreeNoderoot){ if(rootnull)returnnewint[0]; Deque<TreeNode>queue=newArrayDeque<>(); queue.offer(root); //Deque<TreeNode>queue=newArrayDeque<>(){{offer(root);}};//匿名内部类初始化 List<Integer>res=newArrayList<>()...
剑指Offer30.包含min函数的栈 方法一 使用两个栈。 classMinStack{ Deque<Integer>stack=newArrayDeque<>(); Deque<Integer>stack_min=newArrayDeque<>(); publicMinStack(){ } publicvoidpush(intx){ stack.push(x); if(stack_min.isEmpty()||stack_min.peek()>=x){ stack_min.push(x); } } publicvoidpo...
3.无重复字符的最长子串 滑动窗口 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); } set.add(c); res=Math.max(res,rl+1); } return...
2.两数相加 迭代 classSolution{ publicListNodeaddTwoNumbers(ListNodel1,ListNodel2){ ListNodeh1=l1,h2=l2,dummy=newListNode(-1,h1),d=dummy; intcarry=0,sum=0; while(h1!=null&&h2!=null){ sum=h1.val+h2.val+carry; carry=sum/10; h1.val=sum%10; d.next=h1; d=d.next; h1=h1.next; h2=h2.next; } while(h1!=n...
146.LRU缓存 核心数据结构双链表+哈希表 双链表节点由于删除链表最后一个节点时，需要删除对应map中的数据，所以数据域需要保存key，当然value也是必须的。 双链表实现3个方法 addNode(node)：在链表头部插入一个节点。 removeNode(node)：删除链表中任意一个节点。 removeLast()：删除链表最后一个节点并返回该节点，目的是得到key，方便map也删除对应元素。可以复用removeNode(node)。 构造方法 由于需要删除链表最后一个节点，所以需要一个尾指针tail，便于找到最后一个节点。 记得初始化head和tail的指针。 get和p...
剑指Offer14II.剪绳子II 由于取模，只能用贪心，不能用动态规划了。 classSolution{ intmod=(int)(1e9)+7; publicintcuttingRope(intn){ if(n2)return1; if(n3)return2; longres=1; while(n>4){ n-=3; res=(res3)%mod; } res=(resn)%mod; return(int)res; } }
剑指Offer56II.数组中数字出现的次数II 位运算用一个数组累加所有数字的每一位，对3取余，就可以把出现3次的数字都消掉，最后把表示二进制的数组还原成数字，就得到了最终答案。 classSolution{ publicintsingleNumber(int[]nums){ int[]cnt=newint[31]; for(intnum:nums){ intd=1; for(inti=0;i<31;i){ if((d&num)!=0)cnt[i]; d<<=1; } } intres=0,d=1; for(inti=0;i<31;i){ if(cnt[...
剑指Offer54.二叉搜索树的第k大节点 中序遍历 classSolution{ intk,res; publicintkthLargest(TreeNoderoot,intk){ this.k=k; dfs(root); returnres; } voiddfs(TreeNoderoot){ if(rootnull)return; dfs(root.right); k--; if(k0)res=root.val; dfs(root.left); } }
剑指Offer52.两个链表的第一个公共节点 classSolution{ ListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){ ListNodehA=headA,hB=headB; while(hA!=hB){ hA=hAnull?headB:hA.next; hB=hBnull?headA:hB.next; } returnhA; } }
剑指Offer50.第一个只出现一次的字符 哈希表 classSolution{ publiccharfirstUniqChar(Strings){ HashMap<Character,Integer>map=newHashMap<>(); for(inti=0;i<s.length();i){ map.merge(s.charAt(i),1,Integer::sum); } for(inti=0;i<s.length();i){ if(map.get(s.charAt(i))1)returns.charAt(i); } return''; } }
剑指Offer49.丑数 动态规划 classSolution{ publicintnthUglyNumber(intn){ inta=0,b=0,c=0; int[]res=newint[n]; res[0]=1; for(inti=1;i<n;i){ intn2=res[a]2,n3=res[b]3,n5=res[c]5; res[i]=Math.min(n2,Math.min(n3,n5)); if(res[i]n2)a; if(res[i]n3)b; if(res[i]n5)c; } returnres[n1]; } } 优先级队列+哈希表去重 classSoluti...
剑指Offer47.礼物的最大价值 动态规划 classSolution{ publicintmaxValue(int[][]grid){ intm=grid.length,n=grid[0].length; int[][]dp=newint[m][n]; dp[0][0]=grid[0][0]; for(inti=1;i<m;i)dp[i][0]=grid[i][0]+dp[i1][0]; for(inti=1;i<n;i)dp[0][i]=grid[0][i]+dp[0][i1]; for(inti=1;i<m;i){ for(intj=1;j<n;j){ d...
剑指Offer46.把数字翻译成字符串 动态规划 classSolution{ publicinttranslateNum(intnum){ char[]ch=String.valueOf(num).toCharArray(); intn=ch.length; int[]dp=newint[n+1]; dp[0]=1; dp[1]=1; for(inti=2;i<=n;i){ if(ch[i2]'1'||ch[i2]'2'&&ch[i1]<='5'){ dp[i]=dp[i1]+dp[i2]; }elsedp[i]=dp[i1]; } returndp[n]...
剑指Offer43.1～n整数中1出现的次数 数学容易忘 classSolution{ publicintcountDigitOne(intn){ intdigit=1,res=0; inthigh=n/10,cur=n%10,low=0; while(high!=0||cur!=0){ if(cur0)res+=highdigit; elseif(cur1)res+=highdigit+low+1; elseres+=(high+1)digit; low+=curdigit; cur=high%10; high/=10; digit=10; } returnres; } }