【刷题册】hot21-25

目录一、BM21 旋转数组的最小数字二、BM22 比较版本号三、BM23 二叉树的前序遍历四、BM24 二叉树的中序遍历五、BM25 二叉树的后序遍历一、BM21 旋转数组的最小数字题目链接BM21 旋转数组的最小数字题目描述题目解析旋转数组本质是升序数组有相同元素值从头截取一段子数组放到末尾该数组就变成了两段升序数组并且第二段的最大值一定小于等于第一段最小值求最小值解题思路使用二分法利用特性第二段升序数组元素一定小于等于第一段。mid与right 元素值比大小mid元素大证明最小值在[ mid1, right]中mid元素小证明最小值在[ left, mid]中元素值相同right减一缩小范围因为nums[right]这个值还在二分范围中即nums[mid]。解题代码//时间复杂度OlogN//空间复杂度O1importjava.util.*;publicclassSolution{publicintminNumberInRotateArray(int[]nums){intleft0;intrightnums.length-1;if(right0)return0;while(leftright){intmid(leftright)/2;if(nums[mid]nums[right]){rightmid;}elseif(nums[mid]nums[right]){leftmid1;}else{right--;}}returnnums[right];}}二、BM22 比较版本号题目链接BM22 比较版本号题目描述题目解析给我们两个字符串将由.逗号隔开的子字符串进行从从前到后一一比较大小子字符串会有前导0会出现子字符串数量不一致情况相同的子字符串全部相同还有剩余的大。解题思路循环遍历两个字符串直到都走到末尾去拿每一个子字符串的值进行比较即可。拿每一个子字符串的值单独方法处理前导零拿到子字符串值并返回这个值跳过.逗号更新当前遍历的下标循环遍历那每一个子字符串的值时确保当前数组没越界比较子字符串值即可当前遍历到的下标值我们使用一个hash表或者数组来存即可。解题代码//时间复杂度ON//空间复杂度O1importjava.util.*;publicclassSolution{privateHashMapString,IntegerhashnewHashMap();publicintcompare(Stringversion1,Stringversion2){hash.put(v1,0);hash.put(v2,0);intlen1version1.length();intlen2version2.length();while(hash.get(v1)len1||hash.get(v2)len2){intindex1hash.get(v1);intindex2hash.get(v2);intnum10;if(index1len1){num1judge(version1,index1,len1,v1);}intnum20;if(index2len2){num2judge(version2,index2,len2,v2);}if(num1num2)return1;elseif(num1num2)return-1;}return0;}privateintjudge(Stringversion,intleft,intright,Stringv){intindexleft;// 跳过前导零while(indexrightversion.charAt(index)0){index;}intnum0;// 解析数字直到遇到 . 或结束while(indexrightversion.charAt(index)!.){numnum*10(version.charAt(index)-0);index;}// 跳过当前的 .为下一段做准备if(indexrightversion.charAt(index).){index;}hash.put(v,index);returnnum;}}三、BM23 二叉树的前序遍历题目链接BM23 二叉树的前序遍历题目描述题目解析二叉树前序遍历解题思路递归思路根节点-左子树-右子树循环思路使用栈先进后出根节点-右子树-左子树解题代码//空间复杂度ON//时间复杂度ONimportjava.util.*;publicclassSolution{publicint[]preorderTraversal(TreeNoderoot){ArrayListIntegerlistnewArrayList();dfs(root,list);int[]retnewint[list.size()];for(inti0;ilist.size();i)ret[i]list.get(i);returnret;}privatevoiddfs(TreeNoderoot,ArrayListIntegerlist){if(rootnull)return;list.add(root.val);dfs(root.left,list);dfs(root.right,list);}}importjava.util.*;publicclassSolution{publicint[]preorderTraversal(TreeNoderoot){if(rootnull)returnnewint[]{};ArrayListIntegerlistnewArrayList();StackTreeNodestacknewStack();stack.push(root);while(!stack.isEmpty()){TreeNodecurstack.pop();list.add(cur.val);if(cur.right!null)stack.push(cur.right);if(cur.left!null)stack.push(cur.left);}int[]retnewint[list.size()];for(inti0;ilist.size();i)ret[i]list.get(i);returnret;}}四、BM24 二叉树的中序遍历题目链接BM24 二叉树的中序遍历题目描述题目解析二叉树中序遍历解题思路递归前-中-后递归遍历将顺序表赋值给数组。循环 使用栈如果节点是null证明将该节点作为左孩子的节点可以入结果数组了并且将右孩子入栈不是null就将左孩子继续入栈。解题代码//时间复杂度ON//空间复杂度ONimportjava.util.*;publicclassSolution{ArrayListIntegerlistnewArrayList();publicint[]inorderTraversal(TreeNoderoot){fun(root);intlenlist.size();if(len0)returnnewint[]{};//赋值int[]arrnewint[len];for(inti0;ilen;i){arr[i]list.get(i);}returnarr;}//中序遍历privatevoidfun(TreeNoderoot){if(rootnull)return;fun(root.left);list.add(root.val);fun(root.right);}}importjava.util.*;publicclassSolution{publicint[]inorderTraversal(TreeNoderoot){StackTreeNodestacknewStack();ArrayListIntegerlistnewArrayList();if(rootnull)returnnewint[]{};stack.add(root);while(!stack.isEmpty()){TreeNodepopstack.pop();if(pop!null){stack.add(pop);stack.add(pop.left);}elseif(!stack.isEmpty()){TreeNodepop1stack.pop();list.add(pop1.val);stack.add(pop1.right);}}int[]resultnewint[list.size()];for(inti0;ilist.size();i){result[i]list.get(i);}returnresult;}}五、BM25 二叉树的后序遍历题目链接BM25 二叉树的后序遍历题目描述题目解析后序遍历解题思路递归前-中-后递归遍历将顺序表赋值给数组。循环 使用栈拿取栈顶元素如果栈顶左子树不为空上一个栈顶元素不是现在栈顶节点孩子那么左子树入栈如果右子树不为空上一个栈顶元素不是现在栈顶节点右孩子那么右子树入栈都不是就出栈顶元素赋值。解题代码//时间复杂度ON//空间复杂度ONimportjava.util.*;publicclassSolution{ArrayListIntegerlistnewArrayList();publicint[]postorderTraversal(TreeNoderoot){fun(root);intsizelist.size();if(size0)returnnewint[]{};int[]arrnewint[size];for(inti0;isize;i){arr[i]list.get(i);}returnarr;}privatevoidfun(TreeNoderoot){if(rootnull)return;fun(root.left);fun(root.right);list.add(root.val);}}importjava.util.*;publicclassSolution{ArrayListIntegerlistnewArrayList();publicint[]postorderTraversal(TreeNoderoot){StackTreeNodestacknewStack();if(rootnull)returnnewint[]{};stack.push(root);TreeNodecurroot;TreeNodepreroot;while(!stack.isEmpty()){curstack.peek();//左子树不为空上一个栈顶元素不是现在栈顶节点孩子if(cur.left!nullpre!cur.leftpre!cur.right){stack.push(cur.left);}elseif(cur.right!nullpre!cur.right){//右子树不为空上一个栈顶元素不是现在栈顶节点右孩子stack.push(cur.right);}else{//左右孩子节点已经遍历完成list.add(cur.val);prestack.pop();}}intsizelist.size();int[]arrnewint[size];for(inti0;isize;i){arr[i]list.get(i);}returnarr;}}