怎样在赶集微网站做微招聘信息,天津网站制作福州,企业信息化建设网站,温州微信网站定制力扣爆刷第158天之TOP100五连刷56-60#xff08;子集、最小栈、最长有效括号#xff09; 文章目录 力扣爆刷第158天之TOP100五连刷56-60#xff08;子集、最小栈、最长有效括号#xff09;一、78. 子集二、105. 从前序与中序遍历序列构造二叉树三、43. 字符串相乘四、155. …力扣爆刷第158天之TOP100五连刷56-60子集、最小栈、最长有效括号 文章目录 力扣爆刷第158天之TOP100五连刷56-60子集、最小栈、最长有效括号一、78. 子集二、105. 从前序与中序遍历序列构造二叉树三、43. 字符串相乘四、155. 最小栈五、32. 最长有效括号 一、78. 子集
题目链接https://leetcode.cn/problems/subsets/description/ 思路对于子集问题典型的回溯解法搜集所有子集即每一个节点都参与收集而且子集不要求顺序是组合类型需要指定回溯的起始位置。而且元素无重不需要去重。
class Solution {ListListInteger result new ArrayList();ListInteger list new ArrayList();public ListListInteger subsets(int[] nums) {backTracking(nums, 0);return result;}void backTracking(int[] nums, int index) {result.add(new ArrayList(list));for(int i index; i nums.length; i) {list.add(nums[i]);backTracking(nums, i1);list.remove(list.size()-1);}}
}二、105. 从前序与中序遍历序列构造二叉树
题目链接https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/ 思路这也是很经典的一个题目了构造二叉树只需要知道根节点的位置就可以进行划分区间而前序遍历第一个位置就是根节点所以思路是利用前序遍历找到根节点然后去中序遍历中划分左右区间然后递归进行只不过为了快速定位根节点在中序中的位置可以使用map记录对应关系。
class Solution {MapInteger, Integer map new HashMap();public TreeNode buildTree(int[] preorder, int[] inorder) {for(int i 0; i inorder.length; i) {map.put(inorder[i], i);}return createTree(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);}TreeNode createTree(int[] preorder, int[] inorder, int lp, int rp, int li, int ri) {if(lp rp) return null;int mid map.get(preorder[lp]);TreeNode node new TreeNode(preorder[lp]);node.left createTree(preorder, inorder, lp1, lpmid-li, li, mid-1);node.right createTree(preorder, inorder, lpmid-li1, rp, mid1, ri);return node;}
}三、43. 字符串相乘
题目链接https://leetcode.cn/problems/multiply-strings/description/ 思路字符串相乘首先确定拼接方法采用数组拼接方便计算长度的话两个字符串长度相加的长度正好覆盖最大乘积至于进位如何计算因为每次相乘都是个位数进行相乘结果不会超过两位所以维护两位的窗口后一位用来累加进位前一位作为进位。以此往复即可。
class Solution {public String multiply(String num1, String num2) {int n num1.length(), m num2.length();int[] nums new int[n m];for(int i n-1; i 0; i--) {for(int j m-1; j 0; j--) {int x (num1.charAt(i) - 0) * (num2.charAt(j) - 0);int p1 ij, p2 ij1;int sum x nums[p2];nums[p2] sum % 10;nums[p1] sum / 10;}}int k 0;while(k nums.length) {if(nums[k] ! 0) break;k;}StringBuilder sb new StringBuilder();for(int i k; i nums.length; i) {sb.append(nums[i]);}return sb.length() 0 ? 0 : sb.toString();}
}四、155. 最小栈
题目链接https://leetcode.cn/problems/min-stack/description/ 思路求最小栈要求为就是一个正常的栈先进后出然后可以常数时间获取最小值其实只需要维护两个栈一个栈正常入栈出栈另一个栈是最小值当前元素小于栈顶时才入栈否则把栈顶元素重复入栈。
class MinStack {LinkedListInteger stack1 new LinkedList();LinkedListInteger stack2 new LinkedList();public MinStack() {}public void push(int val) {stack1.push(val);stack2.push(Math.min(val, stack2.isEmpty() ? val : stack2.peek()));}public void pop() {stack1.pop();stack2.pop();}public int top(){return stack1.peek();}public int getMin() {return stack2.peek();}
}
五、32. 最长有效括号
题目链接https://leetcode.cn/problems/longest-valid-parentheses/description/ 思路用栈来做栈内记录括号的索引遇到左括号索引入栈遇到右括号栈顶出栈然后判断栈是否为空为空右括号索引入栈不为空记录最大值。
class Solution {public int longestValidParentheses(String s) {LinkedListInteger stack new LinkedList();stack.push(-1);int max 0;for(int i 0; i s.length(); i) {if(s.charAt(i) () {stack.push(i);}else{stack.pop();if(stack.isEmpty()) {stack.push(i);}else{max Math.max(max, i - stack.peek());}}}return max;}
}
